TeLoGraF: Temporal Logic Planning via Graph-encoded Flow Matching

We thank Reviewer 8aYy for the thoughtful feedback and appreciation of our ablation studies and graph-based encoding, which aim to enhance symbolic understanding in decision-making. Below, we address the comments on novelty and trajectory realizability.

Significance of STL planning: (same to Reviewer 8mCx) We argue that it is non-trivial to extend the existing LTL2Action [1] to STL, particularly for the key technique “progression” [2] used to update task spec based on assignments. Consider an example (Sec 3.3 in LTL2Action) “First reach R, then reach G”. In LTL, this can be written as $F(R \land F(G))$. Once reach R, following LTL2Action, the LTL is updated to $F(G)$, and the updated reward will encourage reaching G.

STL expresses this in $F_{[ta,tb]} (R \land F_{[tc,td]} G)$ where [ta, tb] is the time range to reach R, and [tc, td] is the relative range that G should be reached after reaching R. Now, the progression is non-trivial - when reaching R, we need to: (1) ensure the event “reach R” happens in [ta, tb] (2) store this event time because the success of “reach G” will depend on the time R was reached. So we need to bookkeep all the “reach R” events as well as their times, and whenever we reach G, we need to iterate all the past “reach R” events to check if the “reach G” event happens after any of it within the [tc,td] range. The complexity is $O(T^2)$, where T is the trace length. The complexity is $O(T^L)$ for L nested temporal layers in STL. Thus, it is not trivial nor efficient to extend LTL2Action to STL.

Because STL doesn’t have automata-like forms as LTL does, it is hard to efficiently augment the state to be Markovian, as mentioned in our paper (page 2, lines 81-83, right column). Thus we use imitation learning to learn diverse STL, and we believe this distinction highlights the novelty and our contribution. That said, we value the reviewer’s observation, and we will cite LTL2Action [1] and the progression paper [2] with explanations in the final version.

Realizability: (same to Reviewer GKRz) We appreciate the reviewer’s question regarding dynamics consistency. In all cases, our method generates waypoint trajectories, regardless of whether actions are also predicted during training. These waypoints serve as high-level plans, which can directly get actions from inverse dynamics or be tracked by PD controllers. While we do not enforce dynamics during inference, our focus is on generating STL-compliant high-level paths. Ensuring executability can be done through future extensions such as trajectory refinement or policy warm-starting, as explored in prior works [3], and we will clarify this in the final version.

Q1: $\phi_{and}$ and $\phi_{or}$: This is a good observation, and the distinction was intentionally designed: $\phi_{and}$ and $\phi_{or}$ are used to enforce “structured”, canonical forms: $\phi_{and}$ requires all its children nodes to be “disjunctions” (OR-type) while $\phi_{or}$ requires its children to be conjunctions (AND-type). The reviewer's proposed formula will allow both cases. For instance, we allow STL formulas like $A \lor (B \land C)$ but do not allow redundant nesting such as $A \land (B \land C)$, which can be flattened into $A \land B \land C$. This structural design eases the NN training by reducing the variability of data in syntactic forms.

Q2: $\phi_{partial}$: Sorry for the confusion. In fact, in our implementation, we additionally add “Eventually Reach $O_p$” to ensure the agent will first reach $O_q$ and then move to $O_p$ (as shown in our appendix, Figures 19, 20). In some other cases (Figure 37 in our appendix for the PointMaze env), we don’t explicitly specify to reach K0 and K1, but from the layout the agent has to reach the keys first. We will make these clear in our final paper.

Q3: measure in executable policy: It is possible to define the executable policy for simple cases like Linear and Dubins from the predicted waypoint trajectories, but hard for PointMaze (higher-order ODE for dynamics), AntMaze (higher-order ODE, contact force) or Franka Panda (inverse kinematics to convert workspace trajectories to the configuration space to derive the policy). We can measure satisfaction by executing this calculated policy in some cases, but as mentioned in the Realizability section, we focus on planning STL-compliant high-level paths. Ensuring executability can be done through future extensions as explored in [3], and we will clarify it in the final version.

References:

1. Vaezipoor, Pashootan, et al. "Ltl2action: Generalizing ltl instructions for multi-task rl." ICML 2021.
2. Bacchus, Fahiem, and Froduald Kabanza. "Using temporal logics to express search control knowledge for planning." Artificial intelligence 116.1-2 (2000): 123-191.
3. Ajay, Anurag, et al. "Is conditional generative modeling all you need for decision-making?." ICLR 2023

We appreciate Reviewer GKRz's thorough review and positive evaluations. We are glad to see that our contributions (first STL generative model; diverse setups; fast inference) have been recognized. We conducted new experiments as requested. Below are our responses to the concerns and questions.

(New experiment) MILP baseline: We use the official codebase from [1] to run MILP baseline on Linear and PointMaze benchmarks. Dubins and AntMaze are omitted due to their nonlinear dynamics and similarity to Linear and PointMaze, respectively. We omit Franka Panda due to its nonlinear constraints from the configuration space. In Linear, we approximate the circular goal/obstacle regions using polygons. We run MILP under various timeouts (“second”):

The result shows that TeLoGraF(Fast) outperforms MILP (90) in STL satisfaction, with 400X speed-up (MILP runtime is reasonable compared to TABLE I in paper [1]). MILP is slow as it generates thousands of binary variables in our long-horizon tasks (horizon T=64). We further ran MILP on “PointMaze” (horizon T=512) and it only achieves 0.02 STL satisfaction with average runtime 329.785 seconds, highlighting the efficiency and scalability of our method for long-horizon STL planning.

(New experiment) Evaluation with varied random seeds: We redo the experiment in Figure 4 with three random seeds to generate error bars - for learning-based methods, we train and evaluate the NN from different seeds; for non-learning methods, we directly evaluate them with different seeds. Due to time constraints, current results are just for the first three benchmarks, and we will complete this figure by the end of the rebuttal phase. The updated Figure 4 is at https://postimg.cc/XX4LtW62 - the statistical trends remain consistent with those reported in our submission.

Q1: implementation details: For each STL spec in the validation set, the robustness score is only used in evaluation to select the best quality trajectory (out of 1024 sampled trajectories). We have 256 STL specs in the validation set. For the gradient-based planner, we use “backprop-through-time” (BPTT) [2] to optimize trajectories thus, it differentiates through the dynamics. The timesteps are 64 for Linear, Dubins and Franka Panda, and 512 for PointMaze and AntMaze.

Q2: Grad outperforms TeLoGraD/F: This is an interesting finding, and we agree with the reviewer’s insight. Another factor is that “Linear” has simple, fully actuated dynamics, making it well-suited for gradient-based optimization. In contrast, “Dubins” involves second-order dynamics (acceleration -> speed -> position) with limited control, making them more “dragged” and underactuated and hindering gradient-based planners from efficiently finding solutions.

Q3: Realistic trajectories: We appreciate the reviewer’s question regarding dynamics consistency. In all cases, our method generates waypoint trajectories, regardless of whether actions are also predicted during training. These waypoints serve as high-level plans, which can directly get actions from inverse dynamics or be tracked by PD controllers. While we do not enforce dynamics during inference, our focus is on generating STL-compliant high-level paths. Ensuring executability can be done through future extensions such as trajectory refinement or policy warm-starting, as explored in prior works [3], and we will clarify this in the final version.

Q4: STL metrics: The STL satisfaction rate is evaluated over 256 STL specs on the validation set (unless otherwise specified, like in Figure 5). For each STL spec, we use our method or other baselines to generate 1024 trajectories and pick the one with the highest STL score as the final trajectory. So these 256 trajectories (one for each STL spec) will be marked as 1 (satisfaction) or 0 (STL violation). And the STL satisfaction rate is computed across these binary outcomes.

Q5: MILP baseline: Thanks for the suggestion; we have conducted the experiment showing “TeLoGraF (Fast)”’s advantage over MILP for long-horizon STL tasks.

Missing STL references: Thanks. We will cite those accordingly.

Other suggestions: Thanks for pointing out the potential improvement in P6, L310, and the typo in P12, L639. We will modify the paper in the final version.

References:

1. Kurtz, Vincent, and Hai Lin. "Mixed-integer programming for signal temporal logic with fewer binary variables." IEEE Control Systems Letters 6 (2022): 2635-2640.
2. Leung, Karen, and Marco Pavone. "Semi-supervised trajectory-feedback controller synthesis for signal temporal logic specifications." ACC 2022.
3. Ajay, Anurag, et al. "Is conditional generative modeling all you need for decision-making?." ICLR 2023.

We thank the reviewer for the thoughtful reviews. Below are our responses to the concerns.

Extend LTL work to STL: We argue that it is non-trivial to extend the existing LTL2Action [1] to STL, particularly for the key technique “progression” [2] used to update task spec based on assignments. Consider an example (Sec 3.3 in LTL2Action) “First reach R, then reach G”. In LTL, this can be written as $F(R \land F(G))$. Once it reaches R, following LTL2Action, the LTL is updated to $F(G)$, and the updated reward will encourage reaching G.

STL expresses this in $F_{[ta,tb]} (R \land F_{[tc,td]} G)$ where [ta, tb] is the time range to reach R, and [tc, td] is the relative range that G should be reached after reaching R. Now, the progression is non-trivial - when reaching R, we need to: (1) ensure the event “reach R” happens in [ta, tb] (2) store this event time because the success of “reach G” will depend on the time R was reached. So we need to bookkeep all the “reach R” events as well as their times, and whenever we reach G, we need to iterate all the past “reach R” events to check if the “reach G” event happens after any of it within the [tc,td] range. The complexity is $O(T^2)$, where T is the trace length. The complexity is $O(T^L)$ for L nested temporal layers in STL. Thus, it is not trivial nor efficient to extend LTL2Action to STL.

Because STL doesn’t have automata-like forms as LTL does, it is hard to efficiently augment the state to be Markovian, as mentioned in our paper (page 2, lines 81-83, right column). Thus we use imitation learning to learn diverse STL, and we believe this distinction highlights the novelty and our contribution. That said, we value the reviewer’s observation, and we will cite LTL2Action [1] and the progression paper [2] with explanations in the final version.

Data collection labor in real-world: We understand reviewer’s concern regarding paired expert data. However, we note that learning from demonstrations for robots is a widely adopted paradigm in both simulation and real-world settings. In cases where no efficient solver exists, it is common to collect demonstrations from scripted policies, human operators, or off-the-shelf planners. STL belongs to this category, as mentioned in our paper (page 1, L25-L36, right column). We view our work as a first step toward enabling STL-conditioned policy learning from demonstrations—an area that is currently underexplored and, to our knowledge, lacks dedicated prior work.

Although we consider the paired data in our work, in the future, demonstrations do not need to be paired with STL. Recent works have shown STL can be inferred from offline demonstrations [3,4,5,6] or translated from natural language [7,8,9]. With these techniques and the increasing availability of open and modular data collection pipelines (e.g., UMI [10]), we argue that the reliance on demonstrations should not be viewed as a major limitation.

Contribution: We respectfully disagree that our contribution is incremental. As acknowledged by the other reviewers, our work introduces a novel conditional flow model for general STL planning with solid experiments. Reviewer GKRz appreciated the diverse STL coverage and fast generation of satisfying plans, and Reviewer 8aYy highlighted that our model effectively captures STL semantics with efficient inference. During rebuttal, we also conduct extra experiments, including evaluations across varied random seeds and compare with an MILP baseline. These perspectives support the relevance of our contributions and their potential impact on the STL planning community.

We hope this addresses the concerns, and we welcome further discussions.

References:

1. Vaezipoor, Pashootan, et al. "Ltl2action: Generalizing ltl instructions for multi-task rl." International Conference on Machine Learning. PMLR, 2021
2. Bacchus, Fahiem, and Froduald Kabanza. "Using temporal logics to express search control knowledge for planning." Artificial intelligence 116.1-2 (2000): 123-191
3. Liu, Wenliang, et al. "Interpretable generative adversarial imitation learning." arXiv 2024
4. Leung, Karen, and Marco Pavone. "Semi-supervised trajectory-feedback controller synthesis for signal temporal logic specifications." ACC 2022
5. Meng, Yue, and Chuchu Fan. "Diverse controllable diffusion policy with signal temporal logic." RA-L 2024
6. Vazquez-Chanlatte, Marcell, et al. "Learning task specifications from demonstrations." NeurIPS 2018
7. Shah, Ankit, et al. "Bayesian inference of temporal task specifications from demonstrations." NeurIPS 2018
8. Cosler, Matthias, et al. "nl2spec: Interactively translating unstructured natural language to temporal logics with large language models." CAV 2023
9. He, Jie, et al. "Deepstl: from english requirements to signal temporal logic." International Conference on Software Engineering. 2022
10. Chi, Cheng, et al. "Universal manipulation interface: In-the-wild robot teaching without in-the-wild robots." RSS 2024