Zero-Shot Trajectory Planning for Signal Temporal Logic Tasks
Authors: Ruijia Liu
Ancheng Hou
Xiao Yu
Xiang Yin
Venue: NeurIPS 2025 poster ()
Keywords: signal temporal logic
diffusion model
trajectory planning
Primary area: reinforcement_learning

Abstract: Signal Temporal Logic (STL) is a powerful specification language for describing complex temporal behaviors of continuous signals, making it well-suited for high-level robotic task descriptions. However, generating executable plans for STL tasks is challenging, as it requires consideration of the coupling between the task specification and the system dynamics. Existing approaches either follow a model-based setting that explicitly requires knowledge of the system dynamics or adopt a task-oriented data-driven approach to learn plans for specific tasks. In this work, we address the problem of generating executable STL plans for systems with unknown dynamics. We propose a  hierarchical planning framework that enables zero-shot generalization to new STL tasks by leveraging only task-agnostic trajectory data during offline training. The framework consists of three key components: (i) decomposing the STL specification into several progresses and time constraints, (ii) searching for timed waypoints that satisfy all progresses under time constraints, and (iii) generating trajectory segments using a pre-trained diffusion model and stitching them into complete trajectories. We formally prove that our method guarantees STL satisfaction, and simulation results demonstrate its effectiveness in generating dynamically feasible trajectories across diverse long-horizon STL tasks. Project Page: https://cps-sjtu.github.io/Zero-Shot-STL/

Zero-Shot
Trajectory Planning for Signal Temporal Logic Tasks
Ruijia Liu Department of Automation Shanghai Jiao Tong University liurui jiaβsjtu....... edu.
Ancheng Hou Department of Automation Shanghai Jiao Tong University hou. anchengês jtu edu.
Xiao Yu Institute of Artificial Intelligence Xiamen University x xiaoyuêxmu xmu, edu.cn
Xiang Yin Department of Automation Shanghai Jiao Tong University yinxianges jtu.
edu. edu.
Abstract
Signal Temporal Logic (STL) a powerful specification language for describing complex temporal behaviors of continuous signals, making it well-suited for high- level robotic task descriptions. However, generating executable plans for STL it requires consideration of the coupling between the task
tasks is challenging, specification and the system dynamics. Existing approaches either follow a model- based setting that explicitly requires knowledge of the system dynamics adopt task-oriented data-driven approach to learn plans for specific tasks. In this work, we address the problem of generating executable STL plans for systems with unknown dynamics. We propose hierarchical planning framework that enables zero-shot generalization new STL tasks by leveraging only task-agnostic trajectory data during offline training. The framework consists of three key components: (i) decomposing the STL specification into several progresses and time constraints. (ii) searching for timed waypoints that satisfy all progresses under time constraints, and (iii) generating trajectory segments using pre-trained diffusion model and stitching them into complete trajectories. We formally prove that our method guarantees STL satisfaction, and simulation results demonstrate its effectiveness generating dynamically feasible trajectories across diverse long-horizon STL tasks. Project Page: https: ccps- sjtu. github. io/ Zero- Shot-Sotttt STL/
Introduction
Signal Temporal Logic (STL) is formal specification language used to deseribe the temporal behavior of continuous signals. It has become widely adopted for specifying high-level robotic behaviors due its expressiveness and the availability of both Boolean and quantitative evaluation measures. Controlling robots under STL task constraints, however, is a challenging problem, as requires balancing both the satisfaction of the task and the feasibility of the system dynamies. In cases where the environment and system dynamics are fully known, several representative methods have been developed. including optimization- based approaches [1, 2, 3], gradient- based techniques [4, 5], and sampling-batt basedd methods [6]. However, these methods are often difficult to apply in practical scenarios, where the system dynamics and environment are either unknown difficult to model.
To address the challenge of unknown dynamics, several learning based approaches have been pro- posed. One typical method is reinforcement learning (RL) [7, 8, 9, 10. 11, 12). where appropriate reward function is designed to approximate the satisfaction of the STL task. However, these methods
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

often struggle with long-horizar STL tasks and lack generalization capabilities across different tasks. Another approach involves first learning a system model and then integrating it with model-based planning methods. For example, in [13], the authors trained a neural network to approximate the system dynamies and combined it with an optimization-base
approach. However, this method is limited to simple short-horizon STL tasks due to its high computational cost. In [14], the authors used goal-conditioned RL to train multiple goal-conditioned policies, referred to as "skills," to accomplish specific objectives. They then applied search algorithm to determine the optimal sequence of "skills" needed to satisfy the given STL tasks. While this approach enables a certain degree of task generalizations, these tasks must be based on pre-defined objectives associated with the skills.
More recently, generative models, such as diffusion models [15], have emerged as a new approach for generating trajectories for systems with unknown dynamics [16, 17, 18, 19, 20], gaining popularity across various applications. Compared to traditional model-based reinforcement learning methods, these generative approaches are better suited for long-horizon decision-makinn
and offer greater test-time flexibility [16], making them particularly effective for complex tasks. For example, for finite Linear Temporal Logic (LTL,) tasks, [21] introduced classifier-based guidance approach to steer the sampling of diffusion models, ensuring that generated trajectories satisfy LTL, requirements. Similarly, [22] proposed a hierarchical framework that decomposes co-safe LTL tasks into sub- tasks using hierarchical reinforcement learning. This framework employs a diffusion model with determinant- baasdd sampling strategy to generate diverse low-level trajectories, improving both planning success rates and task generalization.
In the context of STL trajectory planning, the use of generative models has also been explored recently. For example, [23] proposed classifier- guidance approach that leverages robustness gradients to guide diffusion model sampling, enabling the generation of vehicle trajectories that adhere to traffic rules specified by STL. Building on this, [24] introduced a data augmentation method to enhance trajectory diversity and improve rule satisfaction rates. However, these approaches are still limited to simpler STL tasks, primarily due to the complexity of optimizing robustness values and the inherent trade-off between maximizing reward objectives and maintaining the feasibility of the generated trajectories [25].
In this paper, considering that trajectories satisfying complex STL specificaatin are typically difficult to collect in real-world scenarios, we focus on composing such trajectories by stitching together short trajectory chunks. The main challenge lies in determining appropriate ways combine these chunks such that the resulting trajectory satisfies the global STL specification while maintaining dynamic consistency and feasibility. Inspired by recent advances in decomposition- we propose a novel hierarchical framework that integrates task decomposition, search algorithms, and generative models. First, complex STL tasks are decomposed into a set of time-aware reach-avoid progresses. Next, a search algorithm, heuristically guided by the trajectory data, is employed to allocate these progresses and generate sequence of waypoints with corresponding timestamps. Finally, a pre-trained diffusion model, trained on task-agnostic data, is used to sequentially generate trajectory chunks that connect adjacent timed waypoints. All trajectory chunks then stitched together to form the complete trajectory.
STL planning[26],
To the best of our knowledge, our algorithm is the first data-driven approach with zero-shot gen- eralization capability for complex STL tasks. We have formally proven the soundness of our STL decomposition and planning algorithm, which guarantees that the generated trajectories satisfy any given STL specification. Furthermore, we empirically evaluate the dynamic consistency and feasibil- ity of the planned trajectories through simulation experiments. Simulation results demonstrate that our method achieves a high execution success rate across diverse long-horizon STL tasks, where the diffusion- based baseline fails. Moreover, it outperforms both the diffusion basedd bascline and standard non-data driven method in planning efficiency.
2 Preliminaries
2.1
System Model
We consider a discrete time system with unknown dynamics
Xx+1 f(x,, az);
(I)
2

---

where R" and E Rm are the state and the action at time instant t, respectively. Given an initial state Xn and a sequence of actions agā₁ ........ ay- the resulting trajectory of the system is Xpagxxaai -x-, where 7' is the horizon. The signal of the trajectory is referred to as the state sequence s Xox1 ... .y and we denote by 8; X,X Xy the sub-signal starting from time step I.
2.2 Signal Temporal Logic
We use signal temporal logic (STL) to describe the formal task imposed on the generated state sequence [27]. Specifically, we consider STL formula in the Positive Normal Form (PNF) [28] whose
syntax is as follows:
p: p P1 App | P1 Vi2 F(a.M/PP Gla.y (01 [n.6)/P2
(2)
where is the true predicate and μ is an atomic predicate associated with an evaluation function hn : IR + R. i.e., predicate μ is true at state x, iff f2 (xt) 2 0. Furthermore, A and V are logic operators "conjunction" and "disjunction", respectively; Uja.6] F[a.6) and Gja,j| are temporal operators "until", "eventually" and "always", respectively; [a, b] is a time interval such that a, e 2,0 0 S < b < xx. Note that, negation is not used in the PNF. However, as shown in [28], this does not result any loss of generality as one can always redefine atomic predicates to account for the presence of negations, allowing any general STL formula to be expressed in PNF In our work, we impose an additional restriction on the Prenex Normal Form formulas. Specifically, for any formula of the form 9o P2, (Pi can only involve temporal operator "always". This restriction is introduced for technical reasons, as it facilitates the decomposition of the overall formula into a set denote by s, F oo if satisfies STL formula yo
of progresses. For any signal time t, and we denote by s F o if su FF s. This is formally defined by the Boolean semantics of STL formulae as shown in Appendix C.1.
XgX1 ... .T.
2.3 Planning with Unknown Dynamies
In the context of STL planning, the objective is to determine an action sequence such that the resulting signal satisfies the specified STL formula. When the system dynamics are perfectly known, this problem can be solved using model-based optimization approaches (e.g., see [1, 2, 3). In contrast, our work addresses a setting with unknown dynamics. Specifically, we assume the mapping f: RR" x R + R" is unknown, but a dataset of historical operational trajectories, consistent with the underlying unknown system dynamics, is available. Note that each trajectory in the dataset is collected from the previous task-agnostic operations and may vary in length. Our goal is to leverage these task agnnosici trajectories to generate new trajectories that satisfy any given STL formula, thereby achieving zero-shot task generalization at test time.
Problem 1. Given a set of trajectories from the unknown system (1) and STL formula & in the desired form, find sequence of actions agai ... ar such that the resulting signal s satisfies the STL formula, i.e., F sp
3
Our Method
3.1 Overall Framework
First, we provide an overview of our proposed planning framework, whose overall structure is illustrated in Figure 1. Our method consists of three key components. The first is semantics- based task decomposition. in which the given STL formula is decomposed into a set of spatial- temporal progresses P = UF. where PR denotes the set of reachability progresses and pz the set of invariance progresses. These progresses must be satisfied under a set of time con- straints T defined over time variables A. The second component is dynamics-aware progress allocation. While the above decomposition satisfied in the correct temporal order requires considering the system's underlying dynamics. To this end, we use a pre-trained Time Predictor, learned from task-agnostic trajectory data, to esti- mate the time required to transition between waypoints, A search-based algorithm then determines a sequence of timed waypoints (Xo, lo); ) (X,, 41),..,, (X,, 4,)) such that each waypoint satisfies corresponding reachability progress in P and complies with all invariance progresses in PT.
task-centric, ensuring that the progresses can be

---

Progresses and Constraints
The third component is trajectory generation. Given the sequence of timed waypoints, we gen- erate an executable trajectory that ensures each waypoint is visited the correct time while satisfy- ing all invariance progresses by stitching together shorter trajectory segments. We instantiate this using existing constrained sampling frameworks (e.g., SafeDiffuser [29]), which leverage diffusion models pre-traine pre-trained trajectory data to produce trajec-
Decomposition
Task
Time? Predictor
Progress Allocation
Trajectory Data
Diffusion Model
Waypoints Sequence
dynamically feasible, constraint-comple tories through constrained sampling. Next, we provide the technical details of each component.
Trajectory
Task- Conk-Compliont Trajectory
Generation
Figure 1: The Overall Framework of Our Pro- posed Method.
3.2 Decompositions of STL Formulae
Eliminating Disjunctions. For the given STL task ş. our first step is covert it into the dis- junctive normal form (DNF) & (p V P2 V.. Pn. where each subformula y; involves no "disjunction". Formally, for any STL formula, one can obtain its disjunctive normal form (DNF) by recursively applying the following replacements: (i) replace F(a,o) (1P) V y22) with F(a,o)PP V [a.,))|P2 (ii) replace G(a,4) (P1 Vop2) with G(a,6)P1 V G[a. and (iii) replace (ø1 V (a, (PP (p V (22) with (1.2 o;U [a..j... Note that the last two replacements are not equivalent, making the resulting DNF & stronger than the original formula yp; i.e., ; = but not conversely, adding conservativeness while preserving soundness. Furthermore, achieve the task defined by G. suffices satisfy one of the subformulas si. Without loss of generality, we will assume henceforth that the DNF contains only single subformula, as the STL planning problem can be addressed for each subformula individually, In other words, moving forward, we will focus on STL formulae, denoted directly by ip, without negations (due the PNF) and without disjunctions (due to the DNF). Similar simplifications and assumptions are common in STL planning or control synthesis literature [30].
Progresses. We encode the STL task +p by finite set of progresses together with set of time- variable constraints. For a signal fragment 8, = x,X++1 XT, we use two canonical progress types:
Reachability progress R(as + b, + L, k)): there exists l' E [ax + 1, + (] such that X μ. Invariance progress I(aa + t, bA + tt, p): for all t' E [ax +,,, ba t] it holds that xy F ns.
Unless stated otherwise we take f and write simply R(as, bs, (1) and I(a,, b))
Time Variables and Constraints. The subscript "A" indicates that the interval endpoints may depend finite set of time variables A, (AI...., )|x/ A concrete assignment is vector
A = A jlYry - Throughout our decomposition (see Appendix D), each endpoint is an affine 0-1 combination of these variables (plus constants), hence we view as. 6Λ 2 + Σ All time constraints unary interval bounds of the form X; [a 5.]; we collect them in a set Tę.
Feasible Assignment Set. The feasible set induced by Tip is
Fx = A E 2|A= Vt T AFt].
where X = (A: E [a,, b:]) iff the i-th component of X lies in the specified interval. Because constraints are unary, Fip factorizes coordinatewise.
Satisfaction of Progresses under an Assignment. Given Fips we abbreviate so = P(A) for the satisfaction of Paax (A), ba (A), H), where P E (R,I):
So F R(ax (A), (A), p) + e (A) ba (A)]: : x F
(3)
So = (A),
e VI (A), (A)] x, p.
The full recursive decomposition procedure is detailed in Appendix D. To establish the soundness of the decomposition process with respect to the original STL specification, we propose the following lemma and the proof is provided in Appendix G.

---

Lemma 1 (Soundness of Semantics- based STL Decomposition). Let be an STL formula in positive normal form (PNF) without disjunctions, and let (F p, T,p) along with the time-variable set Au be the result of the recursive decomposition. Let Fip denote the set of feasible assignments that satisfy all time constraints. Then, for any signal 50,
So p = F S.I. P. So P(A).
In particular, Ap Ø. i.e. no time variables appear in the decomposition procedure, the condition reduces to So F 9 VP Fw: So F P.
3.3 Progress Allocation
Basic Idea. By Lemma when system dynamics are ignored, STL planning reduces a constraint- satisfaction problem over the decomposed progresses and time constraints (P' T.p) Concretely, So y holds iff there exists a feasible variabariable assignment À Fup such that every progress in 1P is satisfied. This reformulation is advantageous for signal construction: instead of reasoning directly with temporal quantifiers in the original formula, it suffices (i) ensure the existence of feasible A, and (ii) construct signal that satisfies all progresses under that assignment. We refer to this process as progress allocation.
However, unknown system dynamics pose additional challenges, as arbitrary allocation may result in dynamically infeasible plans. To address this, we adopt search-basee allocation algorithm, where the feasibility of each assignment is evaluated using model (Time Predictor) learned from trajectory data, which implicitly captures the system dynamics.
Preprocessing. To perform the saarch-based allocation process, we further split the progresses PP as follows. For each invariance progress I(as, ba, P.p. we decompose it into reachability progress R(as. AA (1) and an invariance progress I(ax + +1, bA (u). For simplicity, we will denote the further decomposed progresses (I, T) without subscripts, where P p UP Due this further decomposition, each invariance progress follows a unique reachability progress.
The main algorithm for progress allocation is presented in Algorithm 1. Note that the podudo-code presents the search with an explicit stack for readability, whereas reference implementation executes the same logic recursively. The algorithm employs depth-fing first search (DFS) to sequentially assign satisfaction times and waypoints for each reachabil- ity progress in PR. When the algorithm terminates, it returns a sequence of way- points with associated timestamps of form (Ko, (81, ()........ (&n; (x) such that each waypoint corresponds to the satisfaction of a reachability progress in IRR During the search process, we maintain the cur- rent state x, the current time step t, the set of remaining reachability progresses P the set of all time constraints T, and the searched sequence of waypoints with asso- ciated timestamps 8.
Main Allocation Algorithm.
Algorithm 1 Main-
Input: Initial state Xo. reachability progresses PR invariance progresses pT, time variable constraints T Output: valid waypoints sequence é None solu- tion is found
1: Initialize:
2: current state x <- Xn: current time <- 0
3: sequence š <- [(x, ()]
4: stack +- [[x, t, P
TT,)] ,T))
5: while stack is not empty do
6:
(x. L. , T,
pop(stack)
7:
if Pf
then
8:
return š, T // All reachability progresses satisfied for each progress R(as, R)) F do
9:
At each step, we select remained reachability progress R(ax, b1) from pR as the next target progress from
10:
t', x' + SaapleeStaeeR(ao, b), x,t, )
11:
if None then
12:
s' <- (xx''(1') R + RR (R(as, H)} nt , bx, T, x')
the current state tx. Specifically, to achieve progress R(ax, H), function
13:
14:
T' <- Updatecoonste
SampleState ate is used to determine sat-
15:
// Push new state onto the stack
isfaction time t' and corresponding new
16:
push (x',,, ' T', P') onto stack
state x' such that x' } μ.. Then the searched waypoint (x',1) (') is appended s and we remove progress R(as, bx. from P Furthermore, the time con- straints T are updated based on the assigned state x' and time t' according to function
17:
end for
18: end while
19: return None
// No valid sequence found
5

---

UpdateConstraint. Finally, the algorithm proceeds to the next iteration. If PR becomes empty, indicates that all reachability progresses have been successfully assigned a satisfaction time. If no feasible assignment can be made, the algorithm backtracks to explore alternative assignments.
Dynamic Maintenance of Time Variable Constraints. During allocation, we dynamically maintain the set of time variable constraints T. Once the satisfaction time of a reachability progress determined, additional constraints are added accordingly. This enables the planner to query T at any point to determine potential ranges of aa and by (we denote by [aX, "X,T Jo [ (x,T)) in a progress P(as. bA. (4) by solving integer linear programs (ILP), while ensuring consistency with previously assigned progresses. For example, to obtain min constraints in T.
AAT we minimize (A()) subject to all
Note that only the constraints are updated during planning; the time variable set A remains fixed. As new constraints are introduced, the feasible assignment set F becomes increasingly restricted. If F becomes empty-i..., no assignment À satisfies all constraints- the current allocation is deemed infeasible, and backtracking is triggered to revise earlier decisions.
Heuristic Order. In the DFS of Algorithm 1, reachability progresses from pR are selected based on heuristic order: progresses with earlier potential deadlines PNTT are prioritized; if multiple candidates share the same deadline, the one with the earlier potential start time minn is preferred.
Constraint Update. Let R(as. da μu) be the selected progress and (x', t') the assigned waypoint with time. We then add the following time constraints to T:
0A S and Da 2
These constraints ensure that the progress can be satisfied at time t'. Recall that in our decomposition, each original invariance progress Z(a bA 14) is split into reachability progress Raas, aA u1) and residual invariance progress I(a, + bA, Rt). Thus, if constraints (5) are added for a reachability progress of the form R(as, aA, f)., the value of aa is fixed to t'. Let PP denote the set of invariance progresses whose starting times have been determined. For any I(c, dA,H) E P if x E μr, we add an additional constraint dA < l' to ensure that the invariance progress terminates before t', thereby avoiding conflicts with the assigned waypoint.
When reachability progress R(as, dA, p)) is se- lected, we use function SampleState to determine a valid satisfaction time and waypoint state for this progress while ensuring compliance with invariance progresses. The pseudocode of this function is shown in Algorithm 2. The process starts by com- puting the largest possible time interval Umin; bmax] for the reachability progress. Then the algorithm attempts to sample a candidate state x' with the satisfication re- gion of μ up to Nmax times. For each at- tempt, we first calculate the minimum pos- sible conflict time interval, denoted by O, during which x' conflicts with the invari- ance progresses.
Sample Timed Waypoints.
Algorithm 2 SampleState
p.). Input: reachability progress R(a, b, jJ), current state x, time step f, time variable constraints T, invariance progresses pz
Output: Assigned satisfaction time know of constraint R(a, b.) and new state x' or None if no solution found
1: fmin + -,,T, fmax + b
min
2: for up to Nmax attempts do
3: Sample state x' such that x' = Initialize: conflict time interval O < 5: for all I(c, p') E F with determined starting time do
Once the conflict time interval O is computed, we further use function Ti PePrrdict predict the arrival time from the current state x to the sample state x'. Particularly, (i) t' > fmaxi or (ii) the feasible interval [max((', ('', fmin), maax] fully occupied by conflicting intervals
6:
if x' # p. then O O+ [c, gmin end end for
9:
10:
t' - t TimePredirrccc ct
in O, then it means that the sample state x' not feasible and we proceed to the next attempt. Otherwise, the earliest available time Inew in the feasible interval is assigned as the satisfaction time, and the algorithm returns fnew along with the sampled state x'.
11:
if fmax [max(!' (f', fmin), } {max] O 1 then
12:
Continue to next sampling attempt
13:
end if
14: Inew eearliest time in [max(( Jmmua), lmax] NO
15: return fuew,
16:
end for
17: return None // No valid time found

---

When calculating the conflict time interval O. we only consider invariance progresses whose starting times are determined. This because, in the preprocessing process, we make each invariance progress follows a "preceding" reachability progress. If the starting time of an invariance progress is not determined, then it implies that its "preceding" reachability progress has not yet been satisfied and will only be satisfied strictly later than the current reachability progress. Consequently, this invariance progress will also start strictly later.
Remark 1.
Prediction of Reachability Time. In Algorithm 2, model TimePredict is used to estimates the time step (trajectory length) needed to transition from the current state x to the new state x'. This model is trained on the same trajectory data, that will be used to train the Diffusion model. It assumes that the trajectory length between two states follows a Gaussian distribution. A simple multilayer perceptron (MLP) is used the backbone of mean and variance of the trajectory length using a negative log-likelihood loss function. To account for tasks with avoidance requirements, which may require longer trajectories, scaling factor ? is applied to the predicted mean trajectory length. This factor allows control over the algorithm's conservativeness by adjusting the predicted trajectory length as needed.
model, and it is trained to predict the
Soundness of the Progress Allocation Algorithm. We establish the soundness of the progress allocation algorithm in Lemma 2, with proof provided in Appendix G.
Lemma 2 (Soundness of Progress Allocation Algorithm). Let (xo, TR,,R,,,P,, be the input to Algorithm Assume the depth-first allocation terminates with a waypoint sequence (Ka. to) (R,, f1) ... ...((,,,t.)) tn): 0 = to S t S .... S tn, and let T be the final set of time-variable constraints with feasible assignment space Fy.
Then Fy + Ø, and for any signal so XoXI XT with T 2 La and Xx, 82; for 0 S i S n, there exists Fy such that
VR(as.bs.H) EEPPPR F R(ax bA))
M) At [aa(A), da (A)] n (t X FM
In other words, by interpreting the returned waypoints as key states within the signal So, the algorithm guarantees that, under some feasible assignment time variables, all reachability progresses are satisfied and no invariance progress is violated at any selected waypoint.
3.4 Trajectory Generation
Lemma 2 ensures that the signal constructed from the waypoints returned by the Progress Allocation algorithm satisfies all reachability progresses and does not violate any invariance progress at the selected time steps. We now address the problem of completing the full system trajectory so that the entire signal satisfies all progress conditions. Suppose the Progress Allocation algorithm returns a waypoint sequence = (Xo, 4o) (x1,4) ... (Xn, bn); 0 to S l S ... S In- Our goal is to generate a system trajectory T = X 1xT under system dynamics (1), whose corresponding signal Sq = X,x1 ... XT satisfies:
T tn: X x for all i E (0, nO,
(6)
VI E PZ,
So Z.
Note that the time intervals of all invariance progresses are now fixed by selecting specific feasible assignment A E Fy. A special case arises when certain invariance progresses have not yet terminated at time tn. In this situation, we simply wait at Xn until all invariance progresses end, since according to Lemma 2, Xn satisfies all predicates corresponding to the active invariance progresses at that time.
To solve this conditional trajectory generation problem, we employ a diffusion model trained on task- agnostic trajectory data, which enables the generation of dynamically feasible trajectories. Moreover, by incorporating constraints into the sampling process, the generated trajectories can be aligned with additional task requirements. However, directly generating long trajectories is challenging, as they often deviate from the training distribution. To mitigate this, we adopt a trajectory stitching strategy, generating individual segments т, between each pair of adjacent waypoints (x,, 1,) and (X4+1, 4411), and concatenating them to form the final trajectory т. Specially, each segment must
7

---

satisfy the following conditions: (i) the length is 44+1 - t + 1. (ii) it starts at state x; and ends at state 1,+ and (iii it satisfies all invariance progresses active within the time interval [t,, 14+1).
The diffusion model implementation is detailed in Appendix E. Briefly, the trajectory length is con- trolled via the length of initial noise, leveraging architectural properties of the backbone network [16]. Endpoint conditions are handled as an inpainting problem [16], by fixing the start and end states at every denoising step. To enforce invariance progresses, each I(a, b, (4) is translated into set of pointwise state constraints hy, (xx) 2 0 for t = a,.... b, commonly referred to as safety constraints. These constraints can be handled using various existing constrained sampling methods for diffusion models [31, 29, 32, 33, 34, 35]. We employ SafeDi i f fuser [29], which integrates control barrier functions (CBFs) [36] to enforce these constraints within the sampling process, providing formal guarantees under mild conditions.
Soundness Analysis. We establish the soundness of the overall framework in the following theorem. The proof is provided in Appendix G.
Theorem (Soundness of the Overall Planner). Let yp be an STL formala satisfying all assumptions in Sections 2.2 and 3.2. Assume that the Semantics-based Decomposition terminates with a finite set of progresses and constraints, the Progress Allocation algorithm returns a sequence of timed waypoints and non-emply feasible assignment set, and the Trajectory Generation module produces a trajectory T whose signal So visits all timed waypoints and satisfies all active invariance progresses. Then the resulting signal satisfies the STL specification: So F 4.
3.5 Action Sequence and Control Protocol
Following mainstream diffusion- diffusion-planner practice, we use the diffusion model solely to generate the state sequence; since action sequences are high-frequency and less smooth [17], we recover them via an learned inverse dynamics model [37] or with controllers that track the generated state sequence during execution. To guarantee strict adherence to the temporal windows imposed by STL tasks, we adopt a time-synchoooou control protocol: each planning step is aligned with fixed number i of control steps, where k is specified at task definition time to relate the planning horizon to the control frequency. At each planning step, the controller or inverse dynamics model therefore outputs exactly k actions and executes k control updates, ensuring that the temporal structure of the trajectory is preserved at runtime; unless otherwise stated, we set = 1, so each planning step corresponds to precisely one control step.
4 Case Study
To illustrate the workflow of our algorithm, we con- sider a sequential visit and region avoidance task in the Maze2D (Large) environment [38]. In this scenario, the agent starts at the yellow point shown in Figure and aims to complete the following STL task: F(0,35) (H4 A (F (35545) 45) (P2 A F P(1),30)ss)) 1oo (-/44 A -p5ss where the predicate (4 repre- sents "reach region 14," and -Mu, denotes "avoid re- gion y:=". Intuitively, this STL task requires the agent to sequentially visit circular regions μt, μ2, and μ4 within specific time intervals while avoiding regions/ μ4 and μí throughout the entire episode.
Table 1: STL Task Decomposition Results.
Type
Details
R(A1, AI, AI, R(Ar >z, + d2, R(Ai + X2 + >y. A1 + d2 us), R00,0, -aa). R(0,0, 0, -Ms)
Z(1, 110, v44). I(1, 110, yes)
T
A: E [0.35] A2 E [35, 45), As E [10,30]
The environment layout and target regions are depicted in Figure 2. Our method leverages only an STL lask-agnostic trajectory dataset to train the diffusion model, without prior knowledge of the map or system dynamics. The decomposed progresses and time constraints The planning algorithm then assigns completion times to each reachability progress, as indicated by the numbers next start point and regions (41, //2, and j&z in Figure 2, resulting in sequence of waypoints with corresponding times. The diffusion model is then used to sequentially generate trajectories between adjacent waypoints while ensuring all invariance progresses are satisfied. The final generated trajectory is shown in the left subfigure of Figure 2. To evaluate the feasibility of the planned trajectory, we employ a simple PD controller to track as described in Section 3.5.
summarized in Table 1.
8

---

The resulting execution trajectory is shown in the right subfigure of Figure Using the open-source library st st.pyy [2], we calculate the robustness values for both the planned and actual execution trajectories as 0.180 and 0.115, respectively. Since both values are positive, the trajectories satisfy the STL task requirements.
L
Figure 2: Planned Trajectory (left) and Actual Execu- tion Trajectory (right) in Case Study.
Experiments
Although Theorem guarantees the STL satisfaction of the trajectory, the use diffusion model to generate trajectories for systems with unknown dynamics means cannot guarantee dynamic feasibility. Furthermore, our algorithm is not complete and exhibits some conservatism. Therefore, in experiments, primarily focus evaluating the dynamic feasibility of the trajectories and the conservatism of the planning algorithm. To this end, we design several experiments to test these two aspects, All experiments were
PC with an Intel 17-13700K CPU and Nvidia 4090 GPU.
5.1 Experiment in Maze2D Environment
Experimental Settings. We evaluate our algorithm in three Maze2D environments (U-Maze, Medium, and Large) to assess its zero-shot generalization capability on randomly generated STL. tasks. The agent, starting from random position, must complete the STL task by reaching the target regions within specified time intervals. generate random STL tasks, we design nine templates (Table F.1) and randomly generate time intervals and atomic predicate regions for each template, resulting in 150 randomized tasks per environment. We compare our method with the Robustness Guided Diffuser (RGD) [23], which uses diffusion model with robustness value gradient guidance to optimize the robustness value trajectory. Both algorithms use diffusion models trained on the D4RL dataset [38] to generate trajectories and PD controller for trajectory execution.
Table Partial Result Experiment Maze2D, U:U-Maze; M:Medium; L:Large.
Success Rate( %)
Robustness Valuet
Total Planning Time(s).
Env
Type
T1(s)
RGD
ours
RGD
ours
RGD
ours
1
80.00
97.33
0.108420.1132
0.193810.0715
13.43
0.86
0.86
U
2
36.67
92.00
0.220811.28226
0.150410.0814
16.65-2.00
0.6410.11
0.64
32.00
91.33
0.1695110.5221
0.135410.0745
19.68111.76
1.3110.15
1.21
70.00
94.67
0.0885+0.2768
0.3205=0.0957
53.90++5.78
3.74
3.74
M
34.67
89.33
-0.2277+0.
0.2013+0. 1950
70.69+48.77
2.72+0067
2.72
35.33 3
83,33
0.2393310.3130
0..76110.2000
129.87:127.25
5.53.10.3
5.43
1 34.67
92.00
-0. 0.13999
0.3180=#.122
55.48+5.31
3.62+-0.3
3.62
L
2
16.67
81.33
0.33926+002288.
0.1672=002411
78.70
2.88+0.63
2.87
3
26.67
79.33
-0.2886+002934
0.1639=6.2286
136.35+38.11 12
5.59+0.34
5.49
Evaluation Metrics. We evaluate both methods using Execution Success Rate (SR), Average Robustness Value (RV), and Total Planning Time (TO) to assess the task satisfaction of the actually exccuted trajectories and the overall planning efficiency. Additionally, we record the Trajectory Generation Time (T1) to analyze the computational efficiency of the trajectory generation module of our algorithm. More details about these evaluation metrics and experiment settings are provided in Appendix F.3.
Results and Analysis. Due to page limitations, we present subset the experimental results in Table 2, with the full results available in Table F.2. The results indicate that RGD works only on simple tasks (Types 1-3) and struggles with more complex tasks, as cannot guarantee STL satisfaction and faces challenges balancing robustness optimization with dynamic feasibility for the entire long trajectories. In contrast, our method guarantees STL. satisfaction and focuses the challenge ensuring dynamic fcasibility of short trajectory segments. In simpler environments, such as

---

U-Maze, our method achieves over 80% execution success rate across all task types, and maintains at least 69% success in the more complex Large environment. Moreover, the average robustness values of the actually executed trajectories using our method are consistently higher, further demonstrating its advantage in task satisfaction performance. Our approach is also more efficient, outperforming RGD by over 10x in planning time. By comparing Trajectory Generation Time (TT) and Total Planning Time (TO), we identify trajectory generation as the primary bottleneck in our algorithm. This is primarily due to the additional runtime introduced by SafeDi ffuser, which uses complex quadratic programming for safety constraints enforcement. We plan to accelerate the trajectory generation module in future work by incorporating advanced sampling acceleration techniques for diffusion models [39, 40, 41].
5.2 Experiments under More Complex Dynamics
We further evaluate the generality of our framework on two dynamics-rich domains from OG- Bench [42]: Cube (6-DoF UR5e manipulator) and AntMaze (8-DoF Ant). Training uses only task-agnostic trajectory datasets provided by OGBench; at evaluation time replace the original goal-conditioned objectives with STL specifications. In Cube we plan and track end-effector tra- jectories in Cartesian space, and in AntMaze inverse-dynamics controller. Across nine STL templates per environment, the framework attains high execution success rate in Cube (over 84%) ) and robust performance in AntMaze (over 60% 60%). with planning times that remain practical despite the increased dynamical complexity (Table F.3). These results indicate that the proposed aecomposition-allcatiiie wwl.lllationnggeerattiiioo pipeline transfers beyond simple scenarios to higher-dimension settings. Full experimental settings, metrics, and analyses are provided in Appendix F.4
plan in the workspace and execute with learned
5.3 Comparative Experiment with Optimization-basee Method
In the previous experiments, due to the lack of access to precise system dynamics in the simulation environment, could not use cound-and-complee methods to verify the feasibility of randomly generated STL tasks. Instead, task feasibility was determined by our progress allocation module, which may lead to slightly optimistic estimation of the overall success rate, it overlooks the conservativeness of our approach. To more accurately assess this conservativeness, we conduct additional experiments in a custom-built environment with full access to both the environment and system dynamics. In this setting, we adopt sound and complete optimization- which utilizes full model information to rigorously verify the feasibility of STL formulas. Our algorithm is then evaluated on those verified feasible cases. Results show that the progress allocation module achieves success rate exceeding 80% across various task scenarios. highlighting its strong capability to identify feasible solutions. Full experimental details are provided in Appendix F.5.
method [4],
6 Conclusion
We presented a data-driven hierarchical framework for planning trajectories that satisfy complex Signal Temporal Logic (STL) tasks under unknown dynamics using only task-agnostic offline trajectories. The approach semantically decomposes an STL formula into time-aware progresses, allocates timed waypoints via a dynamics-aware search guided by learned reachability heuristic, and synthesizes short constrained trajectory segments with diffusion- based generator; these segments are then stitched into complete trajectories. We established formal soundness of the planning pipeline for STL satisfaction, and validated the method extensively. On Maze2D, the framework attains high execution success rate on long-horizon tasks while delivering over 10x speedups relative to a robustness-guii -uided diffusion baseline and higher robustness values with smaller variance. On dynamics-rich domains (Cube and AntMaze), maintains strong success rates with practical planning times, and in a custom environment with known dynamics the progress-allocation module achieves 80% feasibility rigorously certified instances, underscoring completeness in practice. Overall, the results indicate that unifying logic-level task decomposition with data-driven trajectory synthesis yields scalable and general solution for zero-shot STL planning; future work will pursue stronger time-pree cime-prediction and control modules, verification enhancements, and accelerated diffusion sampling for even longer horizons.
10

---

References
[1] V. Raman, M. Maasoumy, and A. Donzé, "Model predictive control from signal temporal logic specifications: A case study." in Proceedings of the 4th ACM SIGBED International Workshop on Design, Modeling, and Evaluation of Cyber-Physical Systems, 2014, pp. 52-55.
[2] V. Kurtz and H. Lin, MMixed-integee programming for signal temporal logic with fewer binary variables," JEEE Control Systems Letters, vol. 6, pp.
2022.
[3] D. Sun, J. Chen, S. Mitra, and C. Fan, "Multi-ageni motion planning from signal temporal logic
specifications." " IEEE Robotics and Automation Letters, vol. 7, no. 2. pp. 3451-3458, 2022.
[4] Y. Gilpin, V. Kurtz, and H. Lin, "A smooth robustness measure signal temporal logic for symbolic control," IEEE Control Systems Letters, vol. 5, no. pp. 241-246, 2020.
[5] C. Dawson and C. Fan, "Robust counterexample-guider optimization for planning from differ- entiable temporal logic," " in 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2022, pp. 7205-7212.
[6] R. B. Hyes, Q. H. Ho, and M. Lahijanian, "Stochastic robustness interval for motion planning with signal temporal logic." " in 2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023, pp. 5716-5722.
[7] D. Aksaray, A. Jones, Z. Kong, M. Schwager, and C. Belta, "Q-learning for robust satisfaction of signal temporal logic specifications," in 2016 IEEE 55th Conference on Decision and Control (CDC). IEEE, 2016, pp. 6565-6570.
[8] A. Balakrishnan and J. V. Deshmukh, "Structured reward functions using stl," in Proceedings of the 22nd ACM International Conference on Hybrid Systems: Compulation and Control, 2019,
pp. 270-271.
[9] K. C. Kalagarla, R. Jain, and P. Nuzzo, "Model-free reinforcement learning for optimal control of markov decision processes under signal temporal logic specifications." in 202/ 60th IEEE Conference on Decision and Control (CDC). IEEE, 2021, pp. 2252-2257.
[10] H. Venkataraman, D. Aksaray, and P. Seiler, "Tractable reinforcement learning of signal temporal logic objectives," in Learning for Dynamics and Control. PMLR, 2020, pp. 308-317.
[11] Ikemoto and T. Ushio, "Deep reinforcement learning under signal temporal logic constraints using lagrangian relaxation," JEEE Access, vol. 10, pp. 144814-114825 2022.
[12] S. Wang, S. Li, L.. Yin, and X. Yin, "Synthesis of temporally-robust policies for signal temporal logic tasks using reinforcement learning," " in 2024 IEEE International Conference on Roboties and Automation (ICRA). IEEE, 2024, pp. 10 10503110500.
[13] P. Kapoor, A. Balakrishnan, and J. V. Deshmukh, "Model-based reinforcement learning from signal temporal logic specifications," arXiv preprint arXiv::011 /.0450, 2020.
[14] Y. He, P. Liu, and Y. Ji, "Scalable signal temporal logic guided reinforcement learning via value function space optimization," arXiv preprins arXiv:2408.0 0/923, 2024.
[15] J. Ho, A. Jain, and P. Abbeel, "Denoising diffusion probabilistic models," Advances in neural information processing systems, vol. 33, pp. 6840-6851 2020.
[16] M. Janner, Y. Du, J. Tenenbaum, and S. Levine, "Planning with diffusion for flexible behavior synthesis," " in International Conference on Machine Learning. PMLR, 2022, pp. 9902-9915.
[17] A. Ajay, Y. Du, A. Gupta, Tenenbaum, T. Jaakkola, and P. Agrawal, "Is conditional generative modeling all you need for decision-making?? arXiv preprint arXiv:2211. 1.1657,,,,67 2022.
[18] C. Chi, Z. Xu, S. Feng, E. Cousineau, Y. Du, B. Burchfiel, R. Tedrake, and S. Song, "Diffusion policy: Visuomotor policy learning via action diffusion," The International Journal of Robotics 2023.
Research, p. 0278364924127388
[19] J. Carvalho, A. T. Le, M. Baierl, D. Koert, and J. Peters, "Motion planning diffusion: Learn- ing and planning of robot motions with diffusion models," in 2023 IEEE/RSJ International Conference Intelligent Robots and Systems (IROS). IEEE, 2023, pp. 1916-1923.
[20] R. Huang, Y. Pei, G. Wang, Y. Zhang, Y. Yang. P. Wang, and H. Shen, "Diffusion models as optimizers for efficient planning in offline r1," in European Conference on Computer Vision. Springer, 2025, pp. 1-17.
11

---

[21] Z. Feng, H. Luan, P. Goyal, and H. Soh, "Ltldog: Satistying temporally -exeennde symbolic constraints for safe diffusion-basee planning," IEEE Robotics and Automation Letters, 2024,
[22] Z. Feng, H. Luan, K. Ma, and H. Soh, "Diffusion meets options: Hierarchical generative skill composition for temporally-cxtender tasks," in 2025 IEEE International Conference Robotics and Automation (ICRA). IEEE, 2025, pp. 10 854-10860.
[23] Z. Zhong, D. Rempe, D. Xu, Y. Chen, S. Veer, T. Che, B. Ray, and M. Pavone, "Guided conditional diffusion for controllable traffic simulation," in 2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023, pp. 3560-3566.
[24] Y. Meng and C. Fan, "Diverse controllable diffusion policy with signal temporal logic," IEEE Robotics and Automation Letters, 2024.
[25] X. Li, Y. Zhao, C. Wang, G. Scalia, G. Eraslan, S. Nair, T. Biancalani, A. Regev, S. Levine, and M. Uehara, "Derivative-free guidance in continuous and discrete diffusion models with soft value-based decoding," " CoRR, 2024.
[26] Kapoor, E. Kang, and R. Meira-GGoer "Safe planning through incremental decomposition of signal temporal logic specifications," in NASA Formal Methods Symposium. Springer, 2024, pp. 377-396.
[27] O. Maler and D. Nickovic, "Monitoring temporal properties of continuous signals," in Interna- tional Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems. Springer, 2004, pp. 152-166.
[28] S. Sadraddini and C. Belta, "Robust temporal logic model predictive control," in 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2015, pp. 772-779.
[29] W. Xiao, T.-H. Wang, C. Gan, R. Hasani, M. Lechner, and D. Rus, "Safediffuser: Safe planning with diffusion probabilistic models," in International Conference on Learning Representations, 2025.
[30] P. Yu, X. Tan, and D. V. Dimarogonas, "Continuous-time control synthesis under nested signal temporal logic specifications," IEEE Transactions on Robotics, vol. 40, pp. 2272-2286, 2024.
[31] J. Zhang, L. Zhao, A. Papachristoddoulo. and J. Umenberger, "Constrained diffusers for safe planning and control," arXiv preprint arXiv:2506. 12544, 2025.
[32] N. Botteghi, Califano, M. Poel, and C. Brune, "Trajectory generation, control, and safety with denoising diffusion probabilistic models," arXiv preprint arXiv:2306. 155/2, 2023.
[33] K. Mizuta and K. Leung. "Cobl-diffusion: Diffusion-based conditional robot planning in dynamic environments using control barrier and Yуаршпоv functions," " in 2024 IEEE/RS/ Inter- national Conference on Intelligent Robots and Systems (IROS). IEEE, 2024, pp. 801-11 808.
[34] Y. Zheng, J. Li, D. Yu, Y. Yang, S. E. Li, X. Zhan, and J. Liu, "Safe offline reinforcement learning with reasibility-guuide diffusion model," arXiv preprint arXiv:2401. 10700, 2024.
[35] J. K. Christopher. S. Back, and F. Fioretto. "Constrained synthesis with projected diffusion models," in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[36] Q. Nguyen and K. Sreenath, "Exponential control barrier functions for enforcing high relative- degree safety-critical constraints," " in 2016 American Control Conference (ACC). IEEE, 2016, pp. 322-328.
[37] P. Agrawal, A. V. Nair, P. Abbeel, J. Malik, and S. Levine, "Learning to poke by poking: Experiential learning of intuitive physics," Advances in neural information processing systems, vol. 29, 2016.
[38] Fu, A. Kumar, O. Nachum, G. Tucker, and S. Levine, "D4rl: Datasets for deep data-driven reinforcement learning." arXiv preprini arXiv:2004.07219 2020.
[39] J. Song, C. Meng, and S. Ermon, "Denoising diffusion implicit models," arXiv preprint arXiv:2010.02502. 2020.
[40] 7. Xiao, K. Kreis, and A. Vahdat, "Tackling the generative learning trilemma with denoising diffusion gans," arXiv preprint a:Xiv:2112.07804, 2021.
12

---

[41] W. Zhou, Z. Dou, Z. Cao, Z. Liao, J. Wang, W. Wang, Y. Liu, T. Komura, W. Wang, and L. Liu, "Emdm: Efficient motion diffusion model for fast and high-quality motion generation." " in European Conference on Computer Vision. Springer, 2025, pp. 18-38.
[42] S. Park, K. Frans, B. Eysenbach, and S. Levine, "OGBench: Benchmarking offline goal- conditioned RI."" in The Thirteenth International Conference Learning Representations (ICLR), 2025.
[43] K. Leahy, M. Mann, and C.-L. Vasile, "Rewrite- decomposition of signal temporal logic specifications," in NASA Formal Methods Symposium. Springer, 2023, pp. 224-240.
[44] x. Yu, C. Wang. D. Yuan, S. Li, and X. Yin, "Model predictive control for signal temporal logic specifications with time interval decompasition." in 2023 62nd IEEE Conference on Decision and Control (CDC). IEFE, 2023, pp. 7849-7855.
[45] G. Li, Y. Shan. Z. Zhu, T. Long, and W. Zhang, "Diffstitch: Boosting offline reinforcement learning with diffusion-based trajectory stitching." in International Conference on Machine Learning. PMLR, 2024, pp. 28 597-28 609.
[46] S. Kim, Y. Choi, D. E. Matsunaga, and K.-F. Kim, "Stitching sub-trajectories with conditional diffusion model for goal-conditioned offine rl," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 12, 2024, pp. 13 160-13 167.
[47] Y. Luo, U. A. Mishra, Y. Du, and D. Xu, "Generative trajectory stitching through diffusion composition," arXiv preprint arXiv:2503.0515: 2025.
[48] L. Yuan, Y. Bian, L. Li, Z. Zhang, C. Guan, and Y. Yu, "Efficient multi-agent offline coordination via diffusion- trajectory stitching," " The Thirteenth International Conference on Learning Representations, 2025.
[49] P. Yu, Y. Gao, F. J. Jiang, K. H. Johansson, and D. V. Dimarogonas, "Online control synthesis for uncertain systems under signal temporal logic specifications," The international journal of robotics research, vol. 43, no. 6, pp. 765-790, 2024.
[50] Z. Gu, Y. Zhao, Y. Chen, R. Guo, J. K. Leestma, G. S. Sawicki, and Y. Zhao, "Robust- locomotion-be by-loogi: Perturbation-resilee bipedal locomotion via signal temporal logic guided model predictive control," IEEE Transactions on Robotics, 2025.
[51] T. Wang, Torralba, Isola, and Zhang, "Optimal goal-reaching reinforcement learning via quasimetric learning," in International Conference on Machine Learning. PMLR, 2023, pp. 36411-36 430.
[52] V. Myers, B. C. Zheng, Eysenbach, and S. Levine, "Offline goal-conditioned reinforcement learning with quasimetric representations," arXiv preprint arXi::2509.20478, 2025.
[53] R. Liu, A. Hou, S. Li, and X. Yin, "Vh-diffuser: Variable horizon diffusion planner for time- aware goal-conditioned trajectory planning," arXiv preprint arXiv:2509.11930 2025.
[54] E. Bartocci, J. Deshmukh, A. Donzé, G. Fainekos, O. Maler, D. Ničković, and S. Sankara- narayanan, "Specification--asee" monitoring of cyber-physical systems: survey on theory, tools and applications," Lectures on Runtime Verification: Introductory and Advanced Topics, pp. 135-175, 2018.
[55] K. Leung. N. Aréchiga, and M. Pavone, "Backpropagation through signal temporal logic specifications: Infusing logical structure into gradient- based methods," The International Journal of Robotics Research, vol. 42, no. 6, pp- 356-370, 2023.
[56] G. Zhou, S. Swaminathan, R. V. Raju, J. S. Guntupalli, W. Lehrach, J. Ortiz, A. Dedieu, M. Lázaro-Grediill,, and K. Murphy, "Diffusion model predictive control," arXiv preprint arXiv:2410.05364. 2024.
[57] S. Zhou, Y. Du, S. Zhang, M. Xu, Y. Shen, W. Xiao, D.-Y. Yeung, and C. Gan, "Adaptive online replanning with diffusion models," Advances in Neural Information Processing Systems, vol. 36, 2024.
[58] F. Opryshko, J. Quan, C. Voelcker, Y. Du, and I. Gilitschenski, "Test-time graph search for goal-conditioned reinforcement learning," arXiv preprint arXiv:2510.07255 2025.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction sections clearly state the main contributions and scope the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss main limitations of our work in Appendix B.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

The full proofs of all theoretical results presented in the paper are included in Appendix G.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide detailed implementation descriptions and key experimental settings in both the main text and the appendix. addition, we have included the experimental code in the supplementary materials. We also commit to open nour-iou the code and will add the corresponding link in the paper upon publication.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
15

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
We will include the link to the code repository on the project page.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (bttps://nipp cc/
publ i / gu des CooeeSuom i ss onnPo cyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //niss.. cc cc/pput htppppullcc/c/c//ppppppppooocccl /elicuu/uuaa guidess CooeeSoeSuuue sumii as wwwssssnoooooo oooolllyy)) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Full details will be provided with the code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
The results are accompanied by error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
16

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We describe our computer resources in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /neurips.....///
Answer:
[Yes]
Justification:
The research in the paper conform with the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work focuses primarily on the theoretical aspects of task planning and does not pose any foreseeable societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: we cite the original paper that produced the code package or dataset.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use package should be provided. For popular datasets, hapersw's thoode. com / datases sets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
We will provide document alongside our code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //euuruii ps cc/ Conferences/ / 2025/ LLM) for what should should not be described.
20

---

A Related Works
A.1 STL Decomposition
To address the high complexity of STL control synthesis problems, several decomposition- methods have been proposed [43, 44, 26]. In [43], the authors proposed a formula transformation- based method for multi-agent STL planning. This approach jointly decomposes an STL specification and team of agents. In [44], the authors decompose STL tasks into several subtasks with non- overlapping time intervals using time interval decomposition and sequentially apply the shrinking horizon Model Predictive Control (MPC) algorithm to each short-time-ineerall subtask. However, this method is limited to handling STL fragments that do not include nested temporal logic operators.
The work most similar to our STL decomposition framework is [26]. This work first decomposes STL tasks into several spatio-temporal subtasks with time variable constraints. Then, through time variable simplification, partial ordering, and slicing, the subtasks are segmented into several time intervals. Finally, planning algorithm is subsequently used to sequentially solve the atomic tasks within each time interval. Our algorithm similarly begins by decomposing the STL task into several spatio-temporal progresses and time variable constraints. However, adopt search-based approach to determine the completion times and corresponding states to achieve each progress. During the search process, our method dynamically maintains the time variable constraints on-the-fly according to the completion of progresses. By incorporating the search mechanism, our algorithm achieves greater completeness compared to the incremental planning approach used in [26]. Additionally, the dynamic maintenance of time variable constraints enables a more natural handling of relationships
between subtasks and extends the applicability of our approach to more complex STL task fragments that allows "until" operator.
A.2 Planning with Diffusion Model
Recent advancements in diffusion-basee planning methods highlight their remarkable flexibility, as they rely exclusively on offline trajectory datasets and do require direct interaction with or access to the environment. By leveraging guided sampling, these methods can address a wide range of objectives without the need for retraining. This approach has been widely applied long-horizon task planning and decision decision-making, facilitating the generation of states or actions for control purposes [16, 17, 18].
In the domain of diffusion-based planning for temporal logic tasks, several significant studies have been conducted [23, 24, 21, 22]. For instance, [21] proposed classifier-based guidance approach to direct the sampling process of the diffusion model, enabling the generation of trajectories that fulfill finite Linear Temporal Logic (LTL,) tasks. Similarly, [22] introduced data-driven hierarchical framework that decomposes co-safe LTL tasks into sub-tasks using hierarchical reinforcement learning. This framework integrates diffusion model with determinant- bbaed sampling technique to efficiently produce diverse low-level trajectories, enhancing both planning success rates and task generalization capabilities.
For diffussoon based Signal Temporal Logic (STL) planning, [23] employed a classifier-basee guidance method that leverages the gradient of robustness values guide the sampling process of diffusion model. This method enabled the generation of vehicle trajectories compliant with STL-specified traffic rules. Expanding this work, [24] introduced data augmentation process further improve trajectory diversity and increase the satisfaction rate of specified rules. However, these approaches remain constrained to relatively simple STL tasks due the inherent complexity of optimizing robustness values, as well as the trade-off between maximizing reward objectives and preserving the feasibility of generated trajectories [25].
We compare our algorithm with the method proposed in [23] in the experiments. The results demonstrate that our algorithm can handle complex and long-horizon STL tasks that the method in [23] cannot address, while also exhibiting significant advantages in runtime efficiency.
A.3 Trajectory Stitching
In practical applications of diffusion- based trajectory planning, the training data for diffusion models typically consist of short and simple trajectories. As result, the learned models struggle to capture the
21

---

distribution of more complex behaviors, making it difficult to generate trajectories that satisfy intricate task specifications through guided sampling. To address this limitation, recent studies [45, 46, 47, 48] leverage trajectory stitching methods. The core idea is to construct long-horizon trajectories by stitching together shorter trajectory segments, thereby enabling the satisfaction of more challenging tasks. Current research on trajectory stitching mainly focuses on data augmentation [45, 48] or enabling diffusion models, trained on simple sub-optimal trajectories, to perform relatively complex long-horizon goal-reaching tasks [46, 47].
In contrast to these works, we focus on using trajectory stitching generate trajectories that satisfy complex, long- morizorizon STL tasks by leveraging a diffusion model trained on task-agnostic, sim- ple trajectory data. We address the challenge generating trajectories that satisfy complex STL specifications by decomposing the global task into simpler local sub-tasks using an hierarchical STl_ddccomooiiton and planning framework. For each sub-task, a diffusion model employed to generate a locally feasible trajectory segment, and the final trajectory is obtained by stitching these segments together. The key difficulty lies in ensuring that the decomposition and stitching process preserves satisfaction of the original global STL specification.
B Limitations
B.1 Algorithmic Incompleteness
The main limitation of the proposed framework lies in its incompleteness-the planner may fail find a solution even when one exists-due to three inherent sources of conservativeness:
(i) Specification strengthening. Eliminating disjunctions transforms the original formula oo into logically stronger formula S. While this may exclude some feasible solutions, such transformation is typical in STL planning [30].
(ii) Heuristic allocation.
The depth-first, heuristic- progress allocation (Algorithm 1) relies on approximate time-to-reach estimations and greedy ordering, which may prematurely prune feasible branches. This can be partially mitigated by treating the first feasible solution as a candidate rather than terminating immediately. Exploring more candidates improves solution quality but increases planning time.
(iii) Data-driven synthesis. The diffusion model can only generate trajectories that resemble its training distribution. When the task requires behaviors beyond this distribution, the model may fail to synthesize valid segments.
In fact, the incompleteness is inevitable in any sound, data-driven planner under this scenario. Achieving completeness would require full knowledge of the true system dynamics f. contradicting the core assumption of the problem. Therefore, pursuing absolute completeness is neither meaningful nor practical. Instead, a sound yet statistically conservative framework offers greater value in real-world applications.
We outline some directions that can reduce (though never eliminate) the conservativeness:
Adaptive progress allocation. Replacing the greedy allocation with a beam search or widening strategy, and integrating uncertainly-awar arrival-time predictors (e.g., conformal prediction bounds), can diminish the risk of pruning viable branches.
Hybrid model refinement. When limited model knowledge is available (e.g., coarse dynamics model or learned residual), incorporating it as a constraint inside trajectory generator may shrink the realism gap and enhance synthesis coverage.
Data Augmentation for Synthesis Coverage. Enhance the diffusion prior and Time Predictor using stitching-based data augmentation [45], which increases the coverage of rare transitions and long detours. This augmentation mitigates the sensitivity of data-driven synthesis to dataset sparsity and distribution shift.
We leave these possible improvements for future work.
22

---

B.2 Optimality
Our current objective prioritizes task correctness and dynamic feasibility under unknown dynamics. The optimization of secondary criteria such as makespan, temporal slack, energy, or risk remains outside our present scope and is particularly challenging in our setting.
Nevertheless, incorporating optimality represents promising research direction. practical approach is to replace the current ftrst-feasible" strategy with an anytime allocator that continues to explore the search space after finding an initial solution, thereby trading additional computation for improved objectives such as reduced makespan or increased slack within invariance windows. This approach can be combined with (i) multi oujti--beecctve scoring that integrates feasibility and soft cost terms, (ii) admissible pruning based on uncertainty-awarr time-to-reach bounds, and (iii) post-allocation local refinements such as waypoint re-timing under STI. windows while maintaining soundness.
It is important to emphasize that any extension toward optimality must still preserve dynamic feasi- bility. Overemphasizing cost minimization may increase dynamic infeasibility during downstream synthesis or execution. Systematically balancing these trade-off's through anytime search, Pareto-front maintenance, or constrained optimization over progress schedules an important direction for future work.
B.3 Scenario Limitations
As planning framework, our method currently performs planning in a relatively low-dimensional task space rather than directly in the high-dimensional configuration space. During execution, control still handled by a low-level controller or an learned inverse dynamics model, as described in Section 3.5. This design choice may limit the planner's ability to fully account for low-level dynamic feasibility when generating trajectories, resulting executed trajectories. Nevertheless, executed trajectorics, and the results show that even in challenging environments with complex low-level dynamics, such as AntMaze, our method still achieves satisfactory performance.
potential gap between the planned and the experiments evaluate the success rate based on the actually
STL tasks, in which the atomic predicates typically specify reaching certain regions, and the overall task requires sequentially visiting designated goals within specified time windows. This follows the mainstream setting adopted in most studies on temporal logic task planning and control synthesis [12, 21, 22, 30, 49, 26]. However, temporal logie can also describe other types of behaviors, such as safety constraints and maintenance conditions [24, 50]. These scenarios usually involve relatively simple temporal logic specifications, whereas our focus is on planning under long-horizon and complex temporal logic tasks. Therefore, we restrict our experiments to navigation-style tasks and leave other types of STL scenarios for future exploration.
In addition, our current experiments primarily focus on navigation-ste
B.4 Time Predictor Limitations
The Time Predictor (TP) uses offline trajectories to estimate time-to-reach between states, thereby injecting a notion of dynamical feasibility into allocation. This data-driven design has inherent limitations. When datasets sparse misaligned with the evaluation distribution, the TP can overfit local transition patterns or extrapolate poorly to pairs of states that do not appear in the data. This issue becomes more pronounced when avoidance constraints require long detours. Coverage requirements also increase with the dimensionality of the planning space, and without sufficient cross-episode transitions the predictions can become biased or insufficiently dispersed, which may lead to unreachable schedules.
Effectiveness within our regime. In the data regimes considered here, where abundant task- agnostic trajectories are available, the TP works in concert with the generator and the controller. The TP proposes a horizon, the diffusion- iiffusion-based generator synthesizes a segment of the corresponding length, and the time-synchronous controller executes it. The achieves high execution reliability in practice (as shown in Section F.6.. These results indicate that moderate TP accuracy is often sufficient when combined with segment-level generation and closed-loop tracking in our framework.
generator-controolle pipeline
23

---

Mitigations and modular improvements. Within our modular framework, several upgrades can reduce TP-induced failures while preserving soundness:
Stronger Line-prediction models. Replace the lightweight TP with more expressive predictors that can better capture long detours and heterogeneous dynamics. Options include models with calibrated uncertainty as well as recent approaches that learn temporal-distanee or hitting-tim style quantities [51, 52, 53]. These predictors can be paired with slack-aware scheduling to translate predictions into more robust waypoint times.
Data augmentation for coverage. Increase support for rare transitions through stitching- augmentation [45], which composes cross- cross-episode segments to create longer feasible paths and improves coverage in sparsely sampled regions.
We leave these possible improvements for future work.
C Semantics of Signal Temporal Logic
C.1 Boolean Semantics
The Boolean semantics of STL formula & with respect to signal 8, starting at time are defined inductively as follows [54]:
8; F F (x.) 2 0, 91 As 92: s; 91 V
(C.1)
S; F 9
(C.2)
V F 92;
(C.3)
s; F 11 3/ a s.t. Sy F 4:
(C.4)
s; Gla V E +t b] s.t. Sy p.
(C.5)
3L E at b] s.t. Sp 422
^ A tt,t Sp" P1.
(C.6)
For simplicity, we slightly abuse the notation x F μ to denote h (x++ 2 0, and thus, we have
St F μ (x.) 2 + x4 F.
(C.7)
C.2 Quantitative Semantics
Besides the Boolean semantics, STL also incorporates a concept of robustness value [54], which refers its quantitative semantics used to measure the degree to which a signal satisfies or violates a formula. Positive robustness values signify satisfaction, while negative values indicate violation. The quantitative semanties of STL formula yp with respect to a signal 8 starting time are defined as follows:
(( T) Pmax: where Pmax >> 0,
p (St, p) (x1))
p (st, 7p) (xx(
p (St, P1 (22) min (p (st, (P)) (St, (22)) (St, Pi V v22) max (Se, 10) , (Sr, sp2)), (st, ((a))P)
(S), max v'tta,,
(C.8)
(st. G(aojjp)
min Meittattt
(Sv, v),
St, 901 (1.))122))
min (p (S,,
min p (Sr 11)) re(t,t"
D
Semantic-Based STL Decomposition
The decomposition procedure is defined recursively as follows:

---

If p F (o,b) n. then we have F - (R(),, A4 |D} and T. {A E (a, (a.b]). Ap = (rit, where A
is a new time variable.
If q (/,b//4 14, then we have P== b, 14) and =0, Ao 0.
& i nı Valia.0/u2 then we have P. (I(O, MI), R(,,, Ae, [2]} and Thp = {dr
[a, b]], Ag = (Ai), where X is a new time variable.
If o pi 92, then merge the progresses and time constraints, i.e., P. pp w Pgg and Te = Tw, t T2 Ap = Ap, t App. We use "d" to emphasize that the two merged sets contain no duplicate elements.
If sp F [o.0).. then (i) introduce new time variable X;, i.e., Ag A, w {1+} ; (ii) add new time constraint T = =T, w {}: E (a, b]j; (iii) increase each time indices in each progress by A ie.. / = {P(cA + Xe, dA + As. Plca, da. pPP))
Specifically. if vp' F/,, then we do not introduce a new time variable. In this case, we set Agr = Ap, T = TT P. = (P(cA + a, dA + (4. Pl(cs ()
o' G|, we treat as x = Are(ao)) FIR.AjP. Each subformula FIR.A/PP corresponds to separate copy of progresses (p()) time variables A,e and the associated constraints T. Therefore, k dA 1)) P(cc,,d,,Al
Agr = -ee A T UhE(a.0) Tb P.p UUE[a.D) p(
Specifically, for an invariance progress in P.p of the form I(c, d, μi) that does not contain any time variables, applying the operation F FIR.IIP on its copy in IP(4) yields I(c + ki d + p)). We then merge all such copies I(c + k. d + k. μ)) for & [a, into single progress I(c a, d + b, p). If s' (U, sp, then (i) introduce a new time variable A;i.e., Agr = Ap w }A:}: and (ii) add new time constraint, i.c., T., = Tr 4 (Λ, E [a, b]}; and (iii) increase each time indices in each progress in P by X; and modify each invariance progress I(c. d, μ) Po to I(c, d + X; n)) i.e. P.r = (P(cA + Xi dA + Xs n)) P(ca,da, E Pppt (I(c, d + ).,H) I(c, d. n) E P
Remark 2. Since we require that, for any subformula of the form so (1,6) the subformula 41
does not contain the operators F or U. it follows that in the case of o' (a no time variables or reachability progresses introduced by the operations within c. Therefore, we have Ag 2.
T = 2, and Ps = {I(e, d, n)).
R(A:
A
+ Ag.
R
18
+ 18,
R(A
19,
A1 + 19,
R
20,
20,
I(2
Ao.
10
As.
>; E [7,
16) A2
[2
T
da, E [4, 10)
R((i + Az, Ar Ass mi) I(2 Ag, 10 Pz)
R(Aa 18, 18,
P
R(AA 19, A + 19, R((As
20, pa)
T
A 7, [5, 12]
T
As. Ae, As E [4, 10)
R(A,, As, m1) I(2, 10, Ms)
P
IP
R(Aa, As. As)
A [7,16]
T
Ag
P R(.A.A1.
I22, 10, E 16
0
Figure D.I: Decomposition Process of STL Formula (D.1).
Example 1. To illustrate the above progress decomposition process. we consider the following STL formula
A ((2)10/22) A 2 F 13.100
(D.1)
25

---

The decomposition process is shown in Figure D.I, where the progress and time constraints are constructed incrementally from the bottom the top. The top node represents the overall decomposed (Ip TT) for the STI formuua sp
E
Trajectory Generation
E.1 Diffusion Models for Trajectory Planning
The core concept of diffusioon-modllbassse trajectory planning[16, 17] is employ the diffusion model to learn the distribution of pre-collected trajectories (r") ) in the current environment under the system dynamics, thereby transforming planning or control synthesis problems into conditional trajectory generation.
Diffusion models consist of two processes: the diffusion process and the denoising process.
The diffusion process gradually adds Gaussian noise to a trajectory 7", transforming into noise. At each timestep i, the noisy trajectory is given by:
q(T' r N(T VI -,, (,I),
(E.1)
where B, controls the noise scale, and N the total number of diffusion steps. The noisy trajectory I' at any step can be directly computed as:
VarT -1- -,e e e~ I0,,),
(E.2)
with a; = (1 3,).
The denoising process reverses the diffusion by iteratively recovering the trajectory from Gaussian noise. The reverse distribution is approximated as:
pa(T"-1| r²) -NTT
E").
(E.3)
where (4p(T',)) i) is parameterized by the model, and E' is typically fixed. Instead of learning Hg directly, the model typically predicts the noise Eo(T", i) and gets Mo(T', according to the relationship[15]:
1 Mo(T',0) .)) Vas v - Css
(+'
az Eo ( .1)
(E.4)
The model is trained by minimizing simplified loss function:
(( E,,,, |||= Eø(T', (
(E.5)
In this paper, superscripts denote the diffusion time step, while subscripts indicate the trajectory time step. For example, Ti represents the state trajectory time step & during diffusion time step i. For noise-free trajectories, 7", we omit the superseript when there is ambiguity.
E.2 Trajectory Stitching
Directly generating an entire long-horizon trajectory that meets all STL constraints is challenging. since the resulting trajectories may fall far outside the training distribution, which typically consists of shorter demonstrations. Inspired by recent work on trajectory stitching [45, 47], we decompose the problem into segment- wise generation. Specifically, between two adjacent way-points (x,, and (x;+1. f4+1), we generate a segment т; that:
1. has length 4++1 4 + 2. starts at and ends at x satisfies all invariance progresses active in [t,,
The complete trajectory is then formed by concatenating all segments 7;. This design balances tractability with expressiveness, ensuring that long-horizon STL. tasks can be addressed while maintaining consistency with the learned trajectory distribution.
26

---

E.3 Constrained Generation Mechanisms
To enforee the above conditions, we incorporate several mechanisms into the generation process:
Length control. As noted in [16], the planning horizon of a diffusion model is not fixed by its architecture but dynamically adapts based on the input noise size. This allows for variable-length plans during the denoising process at test time. In this work, we leverage this adaptability by directly adjusting the input noise size to generate trajectories of the desired length. During experiments, observe that models trained with longer planning horizons generalize better to different trajectory lengths during testing. In contrast, models trained with shorter planning horizons exhibit weaker generalization. To address this, one can employ multiple models trained with different horizons, each responsible for generating trajectories whose lengths are close to their respective training horizons. Alternatively, one can train one diffusion model using trajectory segments of varying lengths, which has been shown to improve the generalization ability of diffusion models for generating trajectories of different lengths [53].
Waypoint inpainting. To respect waypoint constraints, we treat generation as an inpainting problem as [16], where the start and end states of each segment are replaced with (x,, X(+1) after every denoising step.
Safety constraints. Each invariance progress I(a, b, ju) is decomposed into constraints of the form hn, (xx) 2 0 for t = o, a + 1..... b, which can be handled by many existing methods [29, 32, 33, 34, 35]. We adopt SafeDi ffuser [29], which integrates control barrier functions (CBFs) [36] into the denoising dynamics. At each diffusion step, a quadratic program (QP) is solved to minimally adjust the update direction while ensuring all CBF constraints are satisfied, thereby providing finite-time invariance guarantees during trajectory generation.
F
Details of Experiments
F.
Environments
We evaluate our proposed framework across a diverse set of environments that encompass both navigation and robotic manipulation domains, as well as a custom-built environment designed for controlled comparisons. These environments differ significantly in their underlying dynamics and control dimensionality, thereby providing a comprehensive test of the generality and robustness of our approach. Importantly, in all experiments we only utilize the environments and their associated STI aask-tgnostic trajectory datasets provided by the original benchmarks. We explicitly discard the original task definitions and evaluation protocols, and instead redefine all tasks as Signal Temporal Logic (STL.) specifications, allowing to unify the evaluation across domains. Visualizations of all environments are shown in Figure F.I.
DARL Maze2D [38] (U-Maze, Medium, Large). This environment features point-mass agent navigating within wo-diimesiooall maze layouts of increasing complexity. The original benchmark tasks are goal-reaching problems defined by start and goal locations. In our experiments, these tasks are reformulated as STL specifications that require the agent to sequentially reach multiple target regions in the maze, enforcing both temporal ordering and spatial reachability constraints.
OGBench AntMaze [42]. In this environment, an 8-DoF quadruped "ant" robot must traverse a large two-dimensional maze. Compared to Maze2D, the AntMaze environment introduces substan- tially more complex locomotion dynamics. While the original benchmark evaluates performance by whether the ant reaches a single goal region, we instead define STL tasks that require visiting multiple spatial regions in prescribed temporal order.
OGBench Cube [42]. This environment involves a 6-DoF UR5e robotic arm performing cube manipulation on a tabletop. The original benchmark tasks assess coal-conditioned manipulation success using predefined demonstrations, For our evaluation, we abstract away from the physical cubes and focus the Cartesian-space motion of the robot's end-effector. We define STL tasks that constrain the end-effector to visit a sequence of spatial waypoints within specified temporal windows, thereby converting the manipulation process into structured STL-constrained trajectory planning problem. This abstraction allows large-scale and systematic testing of our framework.
Custom-built Environment. To further evaluate the reliability of the Progress Allocation module in our framework, we construct custom simulation environment consisting of a bounded two-
27

---

μ42
P2
μd
U4
Figure F.1: Visualization of the environments used in our experiments. From left to right and top to bottom: the three Maze2D environments (U-Maze, Medium, Large), the AntMaze environment, the Cube environment and the custom-built environment.
dimensional square arena with circular obstacle. The agent follows double-integrator dynamics and required to accomplish randomly generated STL tasks by reaching designated regions within specified time intervals. Unlike the benchmark environments, this setting provides full access the system model and environment information, which are relatively simple, thereby enabling direct comparison with sound and complete optimization-base baselines that require full knowledge of system dynamics and environment layout.
F.2
STL Task Generation
To generate random STL tasks, we design nine STL task templates, as illustrated in Table F.1. For each template, we randomly sample time intervals as well as the positions and sizes of the regions corresponding the atomic predicates, thereby producing diverse randomized STL. tasks. The feasibility of each generated STL task is verified using the Progress Allocation module of our method in all experiments, except for the custom-built environment experiment, where feasibility instead verified using the sound-and -annd--nd-copplee baseline algorithm.
Table F.1: STL Task Templates for Experiments
Type
STL Templates
1
Fi A G(
2
F1,M4 A F1,/22
3
Fi,41 A (-HAUU
4
Fí, (1 A (Fi, (p2 A Fig (ug A (i)())))))
5
Fí, (Mi A (Fis A Fr, (1()))))) A G(-r4)
6
Fí, (F)) F1, (#2) A (1,( A G(-m))
7
Fí, (Gi, (un)) A F1, (H2) G(-P3)
8
FI, (Mi Fr, (G, (p2)))
9
F1, Fi, (P2) A Fr, (Pg) GL,(44)
28

---

F.3 Details of Experiment in Maze2d Environment
Baseline Algorithm. We compare our algorithm with the method proposed in [23]. which adopts classifier-bass based guidance and directly leverages the gradient of the trajectory's 's robustness value to guide the sampling process of the diffusion model, thereby optimizing the robustness of the generated trajectory. The gradient of robustness is calculated by the STLCG method proposed in [55]. In the following text, we refer to this algorithm as the Robustness Guided Diffuser (RGD).
Experimental Settings, The diffusion models used in both RGD and our algorithm are trained following the procedure in [16] using the D4RL dataset [38]. A simple multilayer perceptron (MLP) with four fully connected layers is used as the TimeP redi ct model in our algorithm and it is also trained using the same dataset. In our experiments, we employ diffusion model to generate only the state sequence of the trajectory and use a simple PD controller to follow the state sequence during running get the actual execution trajectory as described in Section 3.5.
Evaluation Metrics. For each pair of Maze2D environment (U-Maze, Medium, Large) and task template listed in Table F.1, generate 150 feasible random STL formulae testing cases and test RGD and our algorithm on them and record the following metrics:
Execution Success Rate (SR): The proportion of cases where the actual exccution trajectory achieve non-negative robustness values.
Average Robustness Value (RV): The average robustness value of the executed trajectories, after
discarding the top and bottom 5% to mitigate the effect of outliers.
Total Planning Time (TO): The average total running time (in seconds) to plan trajectory per case.
In addition, we also record the average Trajectory Generation Time (TI), which is the average time spent by the Trajectory Generation module of our algorithm per case. By recording this metric, we analyze the proportion of runtime contributed by each module in our algorithm.
For total planning time, we report both the mean and standard deviation in our results. For success rate, we compute the proportion of successful cases over the total number of test cases.
Full Results. The full experimental results are presented Table F.2.
More Cases. We visualized some of the experimental results. The actual execution trajectories for some successful cases (where the STL tasks were satisfied by the execution trajectories) are shown in Figure F.2 to Figure F.4. For some failed cases (where the STL tasks were not satisfied), the trajectories planned by our algorithm are shown in Figure F.5.
Failure-case Analysis. Notably, by analyzing the calure we identified that the primary reason for execution failure is that the trajectories generated by the diffusion model significantly violated system dynamics, such as colliding with obstacles in the environment or having excessively large distances between consecutive states. To further enhance the actual execution success rate, our method can be integrated with some receding horizon control methods [56] or online replanning strategies [57]. This extension will be explored in our future work.
F.4 Details of Experiments under More Complex Dynamies
To further evaluate the generality and robustness of our framework, we conduct experiments on two dynamics-rich domains from the offline goal-conditioned RL benchmark OGBench [42]: cube-single- ("AntMaze").
play ("Cube") and ontmaze--edium--navviei
Experimental Settings. The Cube environment involves 6-DoF UR5e robotic arm manipulating a cube, while AntMaze features an 8-DoF quadruped ant navigating through a complex maze. In both environments, training relies solely on STL task-agnostic trajectory datasets provided by the benchmark; during evaluation, we replace the original goal-conditioned objectives with randomly generated STL tasks that encode multi-stage temporal and spatial constraints.
For AntMaze, we adopt the STL formulation described in Section 5.1: the agent must visit designated regions in a specific temporal order to satisfy the task specification. Planning is performed in the two-dimensional x-y workspace, while execution uses an inverse dynamics controller that maps a 19-dimensional observation and the next z-y target to an 8-dimensional action each control step as
29

---

Table F.2: Full Result of Experiment in Maze2D Environment, U:U-Maze; M:Medium; L:Large:
RGD: Robustness Guided Diffuser, Ti:Traecctory Generation Time. "_" means that RGD fails to generate feasible trajectory.
Success Rate %6T
Robustness Valuet
Total Planning Time(s).
Env
Type
(i(s)
RGD
RGD
RGD
80.00
97.33
0.011210.1132
0.0035
13.43.11.51
0.16=0.13
0.86
36.67
92.00
0.220
0.1504=0.0814
16.65=2..06
0.64=0.17
0.64
3
32.00
91.33
0.1695:+0.2221
0.1354=0.0745
19.68
1.31=0.15
1.21
4
90.00
0.1120=0.144 1424
1.64=0.20
1.38
U
5
84.67
0.0921=000984
2.59-0.45
2.46
6
86.67
0.00000000800
2.35-0.42
2.35
89.33
0.1293-000066
1.86-0.33
8
97.33
0. 0.1965=1.0433
0.98=0.15
0.81
9
88.67
0.104710.100 1081
1.53
1.52
1
70.00
94.67
0.0885+00.768
0.0955=000957
53.90
3.74=0.34
3.74
2
34.67
89.33
-0.2277
0.2013=0. 1950
70.69+8.27
2.72=0.67
2.72
35.33
83.33
0.2393310.31300
0..26110.2060
129.87-17..25
5.53
5.43
83.33
0.153410.2215
7.09
6.80
M
5
82.00
0.1457:10.2182
11.36:11.32
11.22
6
84.67
0.1477=0.1977
11.76=11.36
11.76
7
90.00
0.2148=00, 1599
8.01=1.21
8.00
91.33
0.2712==0.172
3.87=0.38
3.71
82.67
0.1320==0.2454
6.53-0.74
6.52
34.67
92.00
1.1927
0.3180-+0.122
55.48+15.31
3.62-0.33
3.62
2
16.67
81.33
0.3926:1022844
0.1672:10.2411
68.70117.65
2.88=0.63
2.87
3
26.67
79.33
0.2886-10.2934
0. 0.1639
136.35
5.59=0.34
5,49
4
69.33
0.0389
7.46=0.52
7.13
L
5
79.33
O. 0.1324=0.266
12.62++0.75
12.45
6
73.33
0. 0.170
12.37
12.37
7
84.00
0.1770=0.2360
8.18=0.68
8.18
8
85.33
0.2424
3.93
3.75
9
76.67
0..2700
6.63
6.92
SUE
SUP
RUC
50C
Figure F.2: Successful Execution Trajectories in Maze2D-large Environment under STL Template F1,41 A (2) The task requires the agent eventually reach region li within given time interval, but before reaching #n, must first visit region μ22.
30

---

Figure F3: Successful Execution Trajectories in Maze2D- medium Environment under STL Template 4: F1, (Mg (F1, (N2 F1, (us F1, (H4))))). The task requires the agent to sequentially visit regions H1 U2: Aa P4 within the given time intervals.
Figure F4: Successful Execution Trajectories in Maze2D-umaze Environment under STL Template 5: Fr, (N) (F1, (Hz A Fi, (Ha)))) G(-u4). The task requires the agent to scquentially visit regions H1, M2: Aa within the given time intervals and always avoid the region /44-
SAA
Figure F.5: Planned Trajectories in Some Failure Cases.
31

---

in [47]. Given the higher dynamic complexity of this domain, we set & = 2, such that each planning timestep corresponds to two control steps, as described in Section 3.5.
For the Cube environment, we focus on the end-effector's Cartesian motion rather than the physical manipulation of objects. Trajectories are generated in æ-Y/² space and tracked via PD controller, as in Section 3.5. This abstraction ensures methodological consistency with other experiments while still capturing the essential planning characteristics of high-dimensional robotic control.
Evaluation Metrics. For each environment and STL task template (as defined Table F.I,, we randomly generate 100 feasible STL formulae test cases. We report two quantitative metrics: Execution Success Rate (SR) and Total Planning Time (TO).
The complete results summarized in Table F.3. Our framework achieves high success rates across both environments, with moderate computational cost despite the distinct dynamic structures of the two systems.
Results.
Table F.:: Results in Cube and AntMaze. SR: Execution Success Rate; TO: Total Planning Time;
Env
Type
SR(% ()
TO(s)
1
100.0
0.6910.12
2
95.0
0.69:0:26
3
95.0
1.20++0200
4
84.0
1.43+0.17
Cube
5
89.0
2.12+0.32
6
88.0
1.83+0.18
7
91.0
1.22:10.16
8
91.0
0.76:10.13
9
85.0
1.27:10.14
1
92.0
7.95++2.87
2
94.0
4.53+-0.00
3
81.0
9.95+2.81
4
83.0
9.72#1.01
AntMaze
5
62.0
32.42:1.889
6
64.0
24.63+1..57
7
82.0
15.80=4.778
8
91.0
4.58
9
60.0
8.98
Analysis. In the Cube environment, our method achieves consistently strong performance, with exe- cution success rates exceeding 90% most task templates. The low planning time (typically below 2 seconds) indicates that the framework efficiently handles the dynamics the 6-DoF manipulator. Performance degradation is observed only in more complex templates (Types 4 and 9), which involve long-horizon temporal dependencies and nested STL tasks. These cases require more extensive search and multiple calls to the trajectory generator, slightly increasing the planning time while reducing the success rate due to accumulated modeling uncertainty. Nevertheless, the overall high success rate demonstrates that our framework generalizes well to this manipulation-likk domains.
In contrast, the AntMaze environment presents a substantially greater challenge due to its high- dimensional locomotion dynamics and strong coupling between joint configurations and global motion. Here, the average success rate remains around 80-90% for moderate templates but drops to around %0% for the most complex ones (Types 5, 6, and 9). A closer examination reveals that these harder tasks often involve stringent temporal nesting and "avoid" constraints, which are more sensitive to execution noise and controller-inducee deviation. The higher planning times-especially for long- horizon templates (e.g.. Type 5 and 6)-reflect the reduced efficiency the trajectory generation module in scenarios requiring longer trajectories due more complex dynamics. Nevertheless, method is still able to produce feasible trajectories in most cases within an acceptable time frame.
Overall, these results confirm that the proposed framework scales effectively from smooth, fully actuated manipulation systems to complex locomotion environments. The modular combination of decomposition, allocation, and diffusion- trajectory generation allows efficient reasoning over
32

---

STL objectives, maintaining both computational efficiency and high task success rates across diverse dynamical regimes.
E,5
Details of Comparative Experiment with Optimization-basee based Method
To further evaluate the success rate of the progress allocation module in our algorithm, we compare against widely-used optimization- based algorithm [4] in custom-bure simulation environment. The baseline algorithm is employed as a sound and complete solution to accurately assess the feasibility of randomly generated test cases.
Experimental Settings. The experiment conducted within bounded 10 10 square 2D plane containing circular obstacle. The underlying system dynamies are modeled using double integrator. The agent starts from a randomly generated position and must complete the randomly generated STL tasks by reaching the target region within the specified time interval.
In this experiment, the baseline algorithm is implemented using the open-source library st.lpy [2] and has full knowledge of the environmental information and system dynamics, while our algorithm only has access the trajectory dataset.
To generate the trajectory dataset, we randomly sample start and end points in the environment and the baseline algorithm solve reach-avoid tasks. This process produces 200,000 collision-free trajectories that satisfy the system dynamics, which are then used to train the diffusion model and the Time Predictor.
To further enhance the trajectory generator's ability to produce trajectories varying lengths, we train two diffusion models with different horizons: dedicated to generating shorter trajectories and the other specialized for longer trajectories. The first model is trained on trajectory segments of length 16 for shorter trajectories, while the second model uses segments of length 32 to improve generalization to longer trajectories.
We generate 200 feasible STL tasks for each template, described in Section F.2. The deterministic baseline algorithm is used to ensure the feasibility of these tasks. However, for templates 4 and which involve multi-layer nesting of temporal operators, the baseline algorithm fails to find solutions within an acceptable time. In these cases, we still employ our algorithm's 's progress allocation module to verify feasibility.
Evaluation Metrics. addition the Execution Success Rate (SR) and Total Planning Time (TO) metrics described in Section 5, we introduce additional evaluation metrie:
Progress Allocation Success Rate (SRO): The proportion of cases where the progress allocation module successfully identifies a sequence of waypoints. This metric specifically measures the reliability of the progress allocation module our algorithm.
Table F.4: Result of Experiment in Custom-buil Environment. SRO: Progress Allocation Success
Rate; SR: Execution Success Rate;
Total Planning Time(s).
Type
SRO %)
SR(%)
ours
baseline
1
96.0
93.5
0.99.10.08
3.82.11.44
2
98.0
96.5
0.81
6.30+11.3
3
96.0
89.0
1.26::0.05
31.60+
4
78.5
2.10--0
Timeout
5
83.0
2.57+00.10
Timeout
6
97.5
69.5
2.8740.12
24.23:16.39
80.0
73.5
1.8010.08
7.51
89.5
89.0
0.82+00.03
106.58+82.11
9
81.0
72.0
1.616
151.19
The experimental results are summarized in Table F.4. Since the pptimization-basee baseline used as an expert solver to certify the feasibility of randomly generated STL. tasks, its execution success rate (SR) is naturally 100% and thus omitted from Table E4. Our algorithm achieves
Analysis.
33

---

consistently high success rates across test cases generated from diverse task templates. Notably, the Execution Success Rate (SR) exceeds 69% in all scenarios, demonstrating the algorithm's strong generalization capability for STL tasks.
For all templates except 4 and 5, the Progress Allocation Success Rate (SRO) exceeds 80%, indicating that the progress allocation module is generally reliable, albeit slightly conservative.
Finally, by comparing the Total Planning Time, our algorithm significantly outperforms the optimization-based baseline algorithm, highlighting the efficiency of the task decomposition and planning framework employed in our approach. Notably, for templates 4 and 5, which involve multi- layered nested STL tasks, the baseline algorithm fails to find feasible solutions within a reasonable time. In contrast, our algorithm demonstrates both high success rates and high efficiency, even in these complex scenarios.
F.6 Analysis of the Tredicto--Generatoo-Contttu Framework
In our framework, the Time Predictor serves as a crucial component that provides heuristic guidance on system reachability during progress allocation. By estimating the time required for transitions between states, it allows the allocation process to consider not only the logical satisfaction of STI. constraints but also the underlying dynamical feasibility between consecutive waypoints, thereby creating favorable conditions for subsequent trajectory generation. The Time Predictor operates in close collaboration with the diffusion--assee trajectory generator. Specifically, the predictor estimates the expected travel time between two states, and the generator then produces a trajectory of the corresponding length. Although the true time-to-reach can vary considerably due to stochasticity and unmodeled dynamics, a generator trained on trajectory segments of diverse lengths demonstrates strong generalization. In practice, typically suffices to produce a dynamically feasible trajectory. Moreover, the feedback control layer further compensates for residual prediction errors, ensuring consistent execution despite model approximation. To empirically validate the effectiveness of this collaboration, we conducted an additional experiment in both Maze2D and AntMaze environments.
moderately accurate statistical estimate from the predictor
Experimental Settings. For each environment, we randomly sampled 1000 start-goal pairs (with goal region radii ranging from 3% to 6% of the arena size). For each case, the Time Predictor estimated the required trajectory length from the start position to the center of the goal region; the trajectory generator then produced trajectory of that length, which was subsequently executed using a PD controller (in Maze2D) or an inverse dynamics model (in AntMaze) under the strict time-synchronous control protocol described in Section 3.5 (with h: = 1 in Maze2D and k = 2 in AntMaze). All modules were employed exactly as implemented in our main framework, without additional tuning-
Results and Analysis. The resulting execution success rates, summarized Table F.5, demonstrate that even in the more challenging AntMaze setting, the current achieves high overall reliability. These results underscore the effectiveness of modular integration among prediction, generation, and control within our framework. Given this modular design, each component can be further improved independently-for example, by incorporating more accurate time prediction models [51, 52, 58] more expressive trajectory generators-to handle increasingly complex dynamical systems. We leave such extensions as promising directions for future work.
pipeline
Table F55: Execution Success Rate (%) of the Seaiictor-Geerratoor Controller Pipeline in Different Environments. Each result is computed over 1000 randomly sampled start-goal pairs.
Environment
Umaze
Medium
Large
AntMaze
Execution Success Rate (%)
93.9
89.0
83.7
84.8
E.7
Implementation Details of Experiments
F.7.1
Calculation of the Robustness Value
In our experiments, we compute the robustness values of execution trajectories using the open- source library stlpy [2], which implements quantitative semanties for Signal Temporal Logic
34

---

(STL). However, in environments such as Maze2D, AntMaze, and Cube, transitions between states often require relatively long trajectories. As a result, the corresponding STL task intervals become lengthy, leading substantial computational burden when evaluating robustness directly on the full-resolution trajectories often exceeding the available computational resources.
To mitigate this issue, we introduce a temporal sampling factor which defines the mapping between the time scale of the STL task and the resolution of the system trajectory used for evaluation. Specifically, one discrete time step in the STL task corresponds to time steps in the system trajectory. When computing robustness, we sample one state every 1) steps to obtain down-sanpp nown-sampled trajectory. and then evaluate robustness on this sampled sequence. Importantly, the STL formula used for evaluation is also temporally rescaled, with all time intervals divided by 17. so that the robustness value is computed with respect to temporally consistent but shorter- STL specification. This procedure effectively reduces computational overhead while preserving the temporal and logical structure of the original task.
is worth emphasizing that the parameter is conceptually distinct from the parameter k introduced in the control protocol (Section 3.5). While & determines the number of low-level control updates executed per planning step during runtime-thus linking planning and control frequencies-1) only affects the post-hoc evaluation of robustness by defining how densely the executed trajectory is sampled for STL computation.
F.7.2 Experimental Parameter Settings
Some of the parameters involved in the experiments are listed below, and their specific values are shown in Table F.6:
Table F.6: Parameters Used in the Experiments
Env
Nmax
H
N
?
Maze2D-Umare
128
64
0.8
Maze2D-Medine
256
256
0.9
8
Maze2D-Lare
384
256
1.1
8
1
AntMaze
512
512
1.0
12
Cube
128
64
1.2
Custom-Batt
16832
64
1
Maximum Number of Attempts (Nmax): The maximum number of attempts for new state sampling in Algorithm 2.
Horizon (H): The planning horizon used during the training of the diffusion model.
Total Denoise Steps (N): The total number of steps the denoising process.
Scaling Factor (7)): Applied to the predicted mean trajectory length, used to control the conserva- tiveness of the Progress Allocation Module, described in Section 3.3.
Sampling Factor (7)): Used when computing the robustness value of trajectories, described in Section F.7.I.
Control Frequency (k): The number of low-level control updates executed per planning step during runtime, as described in Section 3.5.
G Proofs
G.1 Proof of Lemma
Proof. We prove the statement by structural induction on yp. Throughout, we assume discrete time t e Zzo and use the shorthand so + R(a,b, + 3t [a, b] x; FF and F I(a, b, + Vt [a, b] : X; μ (cf. (3)-(4)).
Base cases.
35

---

(i) o = F(oNj. The decomposition yields P. the Boolean semanties of F (Eq. (C.4)),
Tp = Ap {a). By
Su = Fla + YE E (a, bj s.t. XA F u YE E [a, s.t. So R(2, 1,),
which is exactly the desired form with = [N E Fv.
(ii) yp (o,b)) The decomposition yields P, {I(a, b. n)) and A2 = TTp By Eq. (C.5),
So F G/,.b]1 e E (a, F μs e so F b(),b.)))
which matches the target equivalence (no time variables).
(iii) y = 44g M42. The decomposition yields P. {I X, m1), R(A, X, (2)) To {> [].
Ap {A}. By Eq. (C.6),
So a U (a U2
+ EX E [a, bl: xx μ2 EE 00 X1 X #1
YE E (a, b]: so F 12) So F (0,
again yielding the target form with X F
Inductive steps. For each constructor below we assume the lemma holds for the immediate subfor- mula(e).
(I) Conjunction y = Φ A D2. By semantics, So F o (su F 91 A So F (22). The decomposition uses disjoint unions P. P,,, u P T. = TT W Tep: Ap Ap, W Apy implicitly a-renaming to avoid clashes. Since each constraint in T,, involves a single variable, the feasible set factors: F& F. Fz By the IH on y1, 922 and the fact that every progress in P. depends only on its own component of = 121,)2). we obtain
So FOFEE P + EAEF S.t.V..YPP E P.p
So F P(A).
(2) Outer finally vp' F FlaMpp. By Eq. (C.4), so F p + YE E [a, : Sx p. Time-shift identity. For any progress P(c, d. μ) and any le E Zza.
Sk F p) + so F P(c+ k. d d p).
(G.1)
This is immediate from the definitions of R and I. The decomposition introduces fresh A Ja, b) and shifts every progress of yp by +A; hence Ag' = Ap 전 (Λ} and Fgr { ^] X E Fpp X [a, b]}. Applying the IH to oo the shifted signal S and then using (G.1) yields
so F o'
XXE E F s.t. VP' Po
so F P'('')
(The special case F (a.n) is the same with a constant shift ta and no new variable.)
(3) Outer always s' = 1jp. In discrete time,
Gaa,/0p A FI..E/P
(G.2)
since Su Gla iff St for every integer E b). The decomposition makes an independent
copy (IP(A) ((k Al (1)) for each & and shifts every progress by +h; then merges all copies:
b P wr (P(ca + dA + k,) P(Ca,,s,M E Ep(()) Apr
(k)
F
F
A=O
A=
k=a
Applying item (2) to each F( factor and using (G.1) yields the target form. Merging constant invariances. If,, d, vt) E P. has constant endpoints, then its shifted copies [I(c+ k. d+ d+k, p))a are equivalent to the single I(c + a, d b, (u) because Ic k, d k) = [c+ a, d + b] in discrete time; hence merging preserves truth.
(4) Outer until y' = 1a By assumption, contains no or U, thus its decomposition consists solely of invariance progresses with constant endpoints and Ag To Ø. The decomposition
36

---

of q': introduce À E la, bl, shift each progress of by +X, and prolong every I(c, d)) E P
I(c, μ.). Formally.
P (P(ea + da + pA (I(e,d x. I(e, Po).
F&' = [[ A E F 6/,
By Eq. (C.6),
VT [0, s, =d).
so F @Ua +
s.t. Fs (a
(G.3)
The first conjunct is handled by item (2) with the shift identity (G.1). For the second conjunct, note the following Miding-invariane identity: for any constant d,
(VT A]: s, F I(c,d,
So I(c,d+
(G.4)
because S, = I[c, μd means At [,+ discrete time. Since P& a conjunction of such invariances, applying (G.4) to each member yields the prolonged invariances in P.p. Combining these observations with (G.3) gives
μ., and U+ +, -]= [c.d d + X] in
Su o EXE E FΦ s.t. YP' E P. So P'(''
Conclusion, All constructors preserve the claimed equivalence. By structural induction, for any PNF STL formula without disjunctions,
So F yp
s.L. aEE F. YP P So F P(A).
If A Ø3, then F& {0) and the statement reduces So F vP Pp F.P
G.2 Proof of Lemma 2
Proof. We argue by maintaining inductive invariants along the DFS. At each node of the search tree we keep a tuple (x, f, IPR T) where š is the waypoint list accumulated so far and PR are the remaining reachability progresses.
Inductive invariants. After initialization and after every successful extension by Algorithm 2 and UpdateConstraingg the following hold:
(II) Feasibility is preserved: the current constraint set T admits at least one assignment of time variables (i.e., the feasible set is nonempty).
(12) Committed reachabilities are honored: for every reachability progress R(as, ba (a) that has been assigned a waypoint (x', and removed from PR T contains the inequalities a I I' and ba 2 t'. Hence any X feasible for satisfies E bax
rem:
(13) Waypoint-level invariance consistency: let I(c, dA n²) be any invariance progress whose start time has been determined (by preprocessing every I has a preceding R(c, c, n²); once that R is assigned at time point (x', t') is appended with x' / μ², Algorithm computes conflict interval O and Updates seponteConstrall iaitt adds d, < t'; consequently, no feasible À can make the interval (c, d, (A)] cover t', so I cannot be active at t..
t², the start is fixed). Whenever a new way-
Initialization. At the start, š [[xo, 0)] and T is the given constraint set; by assumption it feasible, so (11) holds. No progress has been assigned, so (12) and (I3) are vacuous.
Preservation under one extension. Suppose the algorithm chooses remaining reachability R(ax, bx. μ) at (x, and calls Algorithm 2. By construction, the routine computes the largest currently feasible time window [fmin mmax] consistent with T, and samples candidate x' + μ together with predicted arrival time t'. If t' > fmax or the residual feasible window is covered by conflicts, the attempt discarded: otherwise the routine returns the earliest nonconflicting time fnew E [max(t', fmin) fmax]] \. O. Therefore, with t* := fnew, the augmented constraints a < 1r, ba 2 1" are consistent with the current T, establishing (II) and (12) at the child node. Moreover, for every invariance with determined start time that is violated by x', UpdateConst ra i inserts dA < L": since Algorithm 2 avoided O and 1x lies strictly to the right of the current lower bound for da, the new inequality is compatible with T. Hence (I3) holds well.
37

---

Termination case and witness construction. When the algorithm returns, PR
rem Ø and the final constraints are T with feasible f + Ø by (II). Pick any X Fy. By (12). for every assigned reachability with waypoint time 4. we have 4 E (A(A),b((A)
hence So = (X), ba (A),))) nr). For any invariance I(a by. μ²) and any waypoint time that lies in its active window (A), by (A)], there are two possibilities: waypoint trivially satisfies the invariance; or (ii X, μ,, in which case the start of this invariance has already been determined by its preceding reachability, and (I3) guarantees that t, cannot lie in the interval (because dA < 4 was added). Either way, the stated waypoint-level invariance condition holds. This proves the lemma.
(i) X }F jé,, in which case the
Remark (Scope of the guarantee). The lemma certifies that, under some feasible time-variable assignment, all reachability progresses are satisfied and no invariance progress violated at the returned waypoint times. It does not claim invariance satisfaction at every intermediate time step between waypoints.
G.3 Proof Theorem
Proof. Let (IP Tpp) be the progress/constraint pair returned by the Semantics- Decomposition, and let $ (Xo. to) (x,,t))
(K,, (n) with 0 to S ... S tn and final constraint set T f be the output of the Progress Allocation algorithm. By assumption, Fy * Ø. Fix any feasible assignment X E Fy and let S. = X ...1...X ... (T 2 tx) be the signal induced by the trajectory returned by the Trajectory Generation module, which (by assumption) satisfies: (i) Xt, X; for all i, and (ii) for every invariance I(as, ba u)) Vt E [xx(X"), (X()] we have X2 } J.
Reachability progresses. By construction of the allocation phase and by Lemma 2. for every R(as, 14) E Pr there exists an index such that (a) x; } and (b) 4, (X*),, ba (A")), because Ty contains the constraints aA S f; and ba 2 t. which are satisfied by X Since the generated signal visits all waypoints, Xx, = š;, hence So = ba
Invariance progresses. By property (ii) of the generated trajectory. for every bA, E Py we have VI (ax (A*), by bx x } n, i.e. so = I(a, (A"), (x*)).
Conclusion via decomposition soundness. X;
We have shown that for the same feasible assignment
VP Pp: so P(X").
Therefore, by Lemma 1, so F This proves the theorem.
38


Reviews:
[{"review_id": "jpJUFcJJTx", "reviewer": "Reviewer_vwWP", "summary": "This paper presents a planning algorithm for STL specifications. The proposed method first decomposes the STL formula into several basic formulations with reachability, invariance, and temporal constraints. Then a search-based algorithm is developed to generate waypoints that can satisfy this STL. The full trajectory is generated with a conditional diffusion model pre-trained on trajectory data.", "questions": "Please see the weaknesses part.", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n* The problem of planning for STL from offline trajectory data is interesting and meaningful.\n\n* The proposed decomposition and search algorithm can solve certain STL formulations.\n\n## Weaknesses\n\n* Major\n\n  * The major weakness is that the proposed search algorithm for waypoints generation did not take system dynamics into consideration. It seems that from STL decomposition to allocation, the proposed solution depends mainly on the STL formulation itself. Although there is a neural network based time predictor that can predict the time required to visit a future state from a current state, this predictor can overfit or generate unrealistic predictions. My understanding is that if two states are not in the same trajectory in the dataset, then according to the description of this training pipeline, the time predictor cannot learn state pairs outside individual episodes.\n  * Therefore:\n    * In state search/sample, it might not find new state that is actually possible by stitching together dataset trajectories;\n    * The generated waypoints, although can satisfy the STL, may not be achievable due to overfitting, as there does not exist a valid trajectory to satisfy the goal based on demonstration;\n    * Although scaling factors are added for time prediction, this does not align well with the actual trajectories, as the avoidance requirements may lead to much longer distance and time through detour path.\n  * The experimental environments used in this work are very toy example as they are all two dimensional navigation tasks for a point mass agent.\n\n* Minor\n\n  * The proposed framework depends on additional assumptions on the form of STL, for example, assuming operator “until” only has “always” temporal operator for its first operand, assuming DNF only has single subformula, and using replacement in DNF. The method only solves the resulting STL. Therefore, the solution is no longer optimal with respect to the original STL specification. And in the worst case, there might be no feasible solutions after these assumptions and transformation.\n\n  * The paper also implicitly assumes that the evaluation function is know to the planner if I am understanding correctly. I think this should be pointed out since it will make the method unrealistic in the environments where the atomic propositions of a state can only be observed once the agent really interacts that state.", "was_revised": true, "final_justification": "After the rebuttal and discussion, I acknowledge the clarifications provided regarding the additional experiments. The main contribution of the machine learning module is a time predictor, which, however, faces limitations on sparse datasets and is prone to overfitting. Including evaluations in a high-dimensional task space would further strengthen the contribution.", "rebuttal": "We sincerely thank you for the constructive feedback, especially for pointing out the limitations of our experimental scenarios. This insight motivated us to expand our experiments and strengthen our empirical evaluation.\n\n**R1.1 Major: The search algorithm for waypoints does not consider system dynamics.**\n\nOur waypoint search **does** incorporates dynamic feasibility **implicitly** through the **TimePredictor**, which is trained on a large set of offline trajectories generated under the actual system dynamics. By estimating realistic travel times between states, the TimePredictor determines the timing of each waypoint, ensuring feasible transitions and filtering out dynamically infeasible ones.\n\nThe TimePredictor’s dynamic information is leveraged during the search process as follows: without dynamics constraints, the search algorithm would produce a vast number of allocations due to unconstrained variable choices. However, by integrating the TimePredictor into the search, we steer solutions toward dynamically feasible ones, and effectively use the implicit system dynamics to guide the search.\n\nFor the unknown dynamic problem setting, in principle,  one can never guarantee **absolute** dynamic compliance as only latent information can be inferred from trajectory data. Nevertheless, our experiments show that the algorithm still successfully finds dynamically feasible solutions in most cases. Even in the more complex antmaze scenarios (detailed in R1.3), where our method maintains strong feasibility performance.\n\n**R1.2 Major: The time predictor may over-fit or fail for unconnected states; the method may miss possible samples or produce unreachable plans, especially when avoidance enlarges path length.**\n\nThe role of the TimePredictor is to leverage historical trajectory data to estimate the realistic travel time between two states. In scenarios with abundant historical trajectories, most state pairs are covered by these data, so the TimePredictor can make accurate predictions in most cases, providing a degree of feasibility assurance for the final solutions, as reflected in our experimental results.\n\nWe acknowledge that when data are sparse, some state transitions may not be represented in the trajectories, causing the TimePredictor to produce unrealistic predictions, particularly in cases that require avoidance behaviors. We will include a discussion of this limitation in the revised version. \n\nCurrently, we mainly focus on the scenario with abundant historical trajectories and begin with a lightweight TimePredictor module and compensate by exposing a redundancy scaling factor and already yields a relative high success rates. In situations with limited trajectory data, since our framework is modular, we allow the TimePredictor module to be improved, e.g., by swapping in a more powerful model or by employing trajectory-stitching data-augmentation techniques (e.g., [1]) to generate longer cross-episode samples. We plan to explore these improvements in future work.\n\n\n**R1.3 Major: The experimental environments used in this work are simple.**\n\nWe have **extended our evaluation to two dynamics‑rich tasks** from the offline goal‑conditioned RL benchmark **OGBench** [2]: *cube-single-play* (“cube”) and *antmaze-medium-navigate* (“antmaze”). The cube environment involves controlling a 6-DoF UR5e robot arm to manipulate cubes, whereas the antmaze environment involves controlling an 8-DoF Ant agent to navigate in a maze. \n\nIn our experiments, we train exclusively on the STL task-agnostic trajectory datasets provided by OGBench, but replace the original goal-conditioned tasks with STL tasks. Specifically, in the antmaze environment, we adopt the same task formulation as in Sec. 5, requiring the agent to reach specified regions to satisfy the STL formula. In the cube environment, we focus solely on the end-effector position, requiring it to visit designated regions to satisfy the STL task (ignoring cube manipulation). In the cube environment, following the settings in our experiment, we first generate trajectories in the $x$–$y$–$z$ space and then track them with a PD controller. In the antmaze environment, following [3], we plan trajectories in the $x$–$y$ space and track with an inverse dynamics model that takes a 29-dimensional observation and the next $x$–$y$ goal as input and outputs an 8-dimensional action at each step.\n\nAs in Sec. 5, we generate 100 test cases for each of the nine task templates (Table F.1) in both environments and report the execution success rates in the following Table. These results (over 60 % in antmaze and over 85 % in cube) confirm that our framework remains effective under substantially more complex dynamics.\n\nA more detailed description of the experimental setup, along with comprehensive results and analysis, will be provided in the revised manuscript.\n\n|Environment|Template|Execution Success Rate (%)|\n|-|-|-|\n| antmaze | 1 | **91.0**    |\n| antmaze | 2 | **97.0**    |\n| antmaze | 3 | **84.0**    |\n| antmaze | 4 | **63.0**    |\n| antmaze | 5 | **71.0**    |\n| antmaze | 6 | **63.0**    |\n| antmaze | 7 | **81.0**    |\n| antmaze | 8 | **87.0**    |\n| antmaze | 9 | **67.0**    |\n| cube| 1 | **98.0**    |\n| cube| 2 | **100.0**   |\n| cube| 3 | **98.0**    |\n| cube| 4 | **98.5**    |\n| cube| 5 | **85.0**    |\n| cube| 6 | **90.0**    |\n| cube| 7 | **97.0**    |\n| cube| 8 | **100.0**   |\n| cube| 9 | **99.0**    |\n\nOur current implementation adopts **simple baseline modules** for time prediction, trajectory generation, and low-level control. In highly challenging scenarios such as **antmaze**, these basic choices become potential performance bottlenecks. Since our framework is designed to be modular, each component can be replaced by a stronger alternative. Recent advances in diffusion-based trajectory planning (e.g., [1, 3]) provide promising drop-in candidates. We will integrate these enhanced modules and extend the evaluation to even more demanding environments to quantify their benefit in future work.\n\n**R1.4 Minor: Assumptions on STL (e.g., restricted until, DNF transformation)**\n\nThe extra syntactic restrictions and transformations are **intentional**: they enable tractable progress decomposition and simplify allocation. While they narrow the theoretical task class, they still cover *the vast majority of practical robotic tasks specifications*. In our work, the formula in Disjunctive Normal Form (DNF) is slightly stronger than the original expression. However, converting the original expression into this form improves scalability while preserving soundness: it may reject some borderline-feasible tasks, but it never produces a false-positive plan. This trade-off is discussed in Sec. B (*Limitations*).\n\nSimilar simplifications and assumptions are common in STL planning or control synthesis literature (e.g., [4, Sec. III-A] and [5, Remark 2.2–2.3]) and have proven effective in real-world deployments.\n\n**R1.5 Minor: Implicitly assumes the evaluation function (for APs) is known during planning.**\n\nWe focus on scenarios in which the evaluation functions for atomic propositions (APs) are provided alongside the STL task. In some settings an agent must explore a specific state before it can determine whether a particular AP is satisfied. However, those cases primarily involves **planning and exploration** in unknown environments, which differ from our scenario assumptions. In the revised manuscript, we will further discuss the distinctions between our scenario and those settings.\n\n> [1] Chen C, Hamed H, Baek D, et al. Extendable long-horizon planning via hierarchical multiscale diffusion[J]. arXiv:2503.20102, 2025.\n> \n> [2] Park S, Frans K, Eysenbach B and Levine S (2025) Ogbench: Benchmarking offline goal-conditioned rl. In: International Conference on Learning Representations.\n> \n> [3] Luo Y, Mishra U A, Du Y, et al. Generative trajectory stitching through diffusion composition[J]. arXiv:2503.05153, 2025.\n> \n> [4] Yu P, Tan X, Dimarogonas D V. Continuous-time control synthesis under nested signal temporal logic specifications[J]. IEEE Transactions on Robotics, 2024, 40: 2272-2286.\n> \n> [5] Yu P, Gao Y, Jiang F J, et al. Online control synthesis for uncertain systems under signal temporal logic specifications[J]. The international journal of robotics research, 2024, 43(6): 765-790."}, {"review_id": "dxRFXWTeki", "reviewer": "Reviewer_E3cN", "summary": "The paper seeks to generate plans that satisfy signal temporal logic (STL) specifications without access to a transition model but assumes the state variables and their domain (values that can be assigned to them) are known. The algorithm decomposes an STL specification into a set of reachability and invariance progresses as well as time constraints. Based on this and a start state, a depth-first search is performed for a sequence of waypoints that satisfies the STL. At each node in the depth-first search, all possible unsatisfied progresses are examined and states that satisfy those progresses are sampled. After the waypoints are found a diffusion model trained on offline data is used to find the intermediate states and a sequence of actions that connects the state sequence is found via an inverse dynamics model. The algorithm was evaluated on 2D maze tasks.", "questions": "How is sampling of x’ in Algorithm 2 performed such that x’ entails \\mu?", "limitations": "Search for waypoints is based on a depth-first search, which will not scale to larger state spaces.\nSampling waypoints does not directly depend on the current waypoint, which can lead to inefficient plans.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\nThe approach can find a sequence of states that satisfies an STL specification without needing a model since the diffusion model is trained via an offline dataset. Decomposes and STL specification into progresses to better integrate with search for waypoints.\n\n**Weaknesses**\n\nIt appears the main innovation of this paper is satisfying STL constrains in a model-free manner. However, the algorithm to accomplish this finds waypoints via a depth-first search that does not use a domain-specific heuristic function (which could be learned). Therefore, I do not believe this algorithm will scale to larger search spaces.\n\nWhile there is preference given to next waypoints with a lower predicted time to be reached from the current waypoint, the manner in which these states are generated does not directly depend on the current waypoint. Therefore, very inefficient plans may be found.\n\nGiven the sequence of states, generating action sequences still depends on an inverse model. Therefore, I do not think that this method truly addresses the problem of satisfying STL plans with unknown dynamics.\n\nFor the evaluation, there are failure cases. However, it is not clear where the algorithm failed (i.e. at waypoint search, state trajectory generation with the diffusion model, or action generation).", "was_revised": true, "final_justification": "The authors addressed my concerns about search scaling. The details on the inverse model, which I am now told is trained, are not clear. So, I am adjusting my score from a 3 to a 4.", "rebuttal": "We sincerely thank you for the very constructive comments, particularly for highlighting the gaps in our analysis of failure modes. This insight has guided us to provide a more detailed breakdown of where and why our method may fail, making our analysis more comprehensive.\n\n**R2.1 The method lacks scalability due to naive DFS and no learned domain-specific heuristic.**\n\nOur DFS-style search is not a blind traversal. In fact, we employ two kinds of domain-specific heuristics: task-aware and environment-aware. \n- For the task-aware heuristic, at each iteration we order the remaining progresses using the **Heuristic Order** (lines 283–285), prioritizing those with tighter admissible time windows. \n- The environment-aware heuristic is implicitly embedded via the TimePredictor, which is trained on abundant trajectory data consistent to the actual behavior in the environment, thereby assisting in determining the timing of each waypoint and guiding the search.\n\nIn addition to these heuristics,\n**(i)** We apply an **early-pruning rule** (lines 230–239) that backtracks immediately when the feasible set of shared time variables becomes empty.\n**(ii)** The search is conducted **in the space of reachability progresses**, not in the full product space of task and workspace. Workspace states are derived directly and efficiently from the corresponding states in the progress space.\n\nEmpirically, the Progress Allocation module accounts for only a small fraction of the total runtime (Sec. 5). Even for complex, long-horizon STL tasks with multi-layer nested structures that the optimization-based counterpart struggles to solve efficiently (Sec. G), this module does not become a performance bottleneck. Furthermore, in our additional tests on two scenarios with more complex dynamics with a 6-DoF robotic arm and an 8-DoF ant agent (see Sec. R1.3 in response to reviewer vwWP), the module still find a solution with an average time of less than 1s and does not pose a performance bottleneck. These experiments demonstrate that, with the aforementioned optimizations, our Progress Allocation module exhibits strong scalability.\n\nWe agree that other learned heuristics may further improve scalability, and we will explore this direction in future work.\n\n\n**R2.2 Candidate samples of next waypoint are drawn without conditioning on the current waypoint, inefficient plans may be found.**\n\nThe main objective of this work is to ensure dynamic feasibility rather than optimality. Therefore, our current method for obtaining the next waypoint involves sampling a candidate state within the target region and checking whether it is dynamically feasible to reach that state within the admissible time window from the current waypoint. As a result, compared to selecting the “nearest” state, the resulting trajectory may indeed be longer. Of course, we could incorporate additional heuristics to preferentially sample states that are as “close” as possible. However, we believe that pursuing a globally optimal (shortest) trajectory within our current framework is a highly challenging problem: relying solely on this myopic strategy is insufficient and would likely require further global structural adjustments. In the revised manuscript, we will clarify that our focus is on dynamic feasibility rather than optimality, and we plan to explore approaches for optimality in future work.\n\n\n**R2.3 Action generation still depends on an inverse dynamics model, doesn’t fully solve unknown‑dynamics planning.**\n\nThe inverse-dynamics model is not given but  trained **offline** on the trajectory data that implicitly encode system dynamics. Therefore, it requires **no analytic model**. This aligns with the unknown-dynamics setting we consider here. In fact, using an inverse-dynamics model as the low-level controller to generate action sequences is a common practice in diffusion-based trajectory planning frameworks, and our approach follows this standard methodology [1,2].\n\n\n**R2.4 Failure‑case analysis is missing, it’s unclear which stage fails.**\n\nOur experiments reveal three distinct failure modes:\n1. **Allocation failure.** The Progress Allocation algorithm can occasionally miss an existing solution because it is not complete. This is quantified by the **Progress Allocation Success Rate** in Sec. G and discussed with remedies in Sec. B (*Limitations*).\n2. **Execution failure.** The planned trajectory satisfies the STL but is difficult to track under real dynamics by the controller, leading to task violation during execution. This is the **dominant** error source and is captured by the **Execution Success Rate** in Secs. 5 & G; mitigation ideas (e.g., online replanning) appear in Sec. F.1.\n3. **Rare synthesis failure.** Our method provides a formal guarantee for generating STL‑compliant trajectories (Theorem 1), with part of the guarantee inherited from SafeDiffuser [3]. In very rare cases, SafeDiffuser fails to generate a segment that fully respects the constraints, yielding an STL‑violating plan; across **4050** Maze2d trials, this occurred only **5** times (≈ **0.12 %**).\n\nWe will add a dedicated subsection summarizing these statistics, clarifying where failures occur, and outlining mitigations for each mode.\n\n**R2.5 Algorithm 2: how is `x'` sampled such that it satisfies μ?**\n\nAs detailed in Sec. 2.2, each atomic predicate $\\mu$ comes with an *explicit* evaluation function $h_{\\mu}$. A state $x$ satisfies $\\mu$ iff $h_{\\mu}(x) \\geq 0$. Consequently, one can perform rejection sampling (or uniform sampling over a pre-computed feasible set) and accept a candidate $x'$ only when $h_{\\mu}(x') \\geq 0$. Because $h_{\\mu}$ is part of the task specification, this check is analytic and incurs negligible overhead.\n\n> [1] Ajay A, Du Y, Gupta A, et al. Is Conditional Generative Modeling all you need for Decision Making?[C]//The Eleventh International Conference on Learning Representations.\n> \n> [2] Luo Y, Mishra U A, Du Y, et al. Generative trajectory stitching through diffusion composition[J]. arXiv:2503.05153, 2025.\n> \n> [3] Xiao W, Wang T H, Gan C, et al. Safediffuser: Safe planning with diffusion probabilistic models[C]//The Thirteenth International Conference on Learning Representations."}, {"review_id": "YxJLjjMvSE", "reviewer": "Reviewer_TNZu", "summary": "The authors propose a method for satisfying STL specifications using a combination of spatio-temporal decomposition and trajectory generation using diffusion. Using previously collected trajectory data, the authors generate estimates for travel times between regions in space, in addition to training a diffusion model for generating short trajectories that can be stitched together. The decomposed STL specification is used to generate “progresses” that capture reachability and invariance properties implied by the STL specification. The time estimates assign times to these progresses to generate a sequence of timed waypoints, and the diffusion model is used to generate trajectories to reach those timed waypoints. Results are compared against a recent diffusion approach for STL satisfaction.", "questions": "Was there a reason that alternatives to diffusion were not used as comparators? For example, one could imagine using RRT* or related methods to generate candidate trajectory segments. Since there needs to be some controller to track the diffusion trajectory anyway, it seems like you could apply the same controller to an RRT* generated trajectory.\n\nRelatedly, what were the dynamics used in the simulation results? This seems to have strong implications for how successful the method would be. I would expect it to be easier to learn a model for a single integrator than for more complex nonlinear dynamics. However, the latter is where a method such as this would probably be more useful.\n\nWhere do $a_{\\Lambda,\\mathbb{T}}^{min}$ and $b_{\\Lambda,\\mathbb{T}}^{max}$ come from? I was confused about the heuristic order, and it seems to hinge on how these are calculated.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This paper covers an interesting and timely problem area. The method outperforms recent methods on the provided metrics.\n- The discussion of limitations is thorough and fair, and the authors even include examples of failure cases.\n- The paper is reasonably clear—for someone well-versed in this area, it is easy to gather the main ideas and most of the important details.\n\nWeaknesses:\n- The descriptions in sec. 3.3 should refer to line numbers in the algorithms. It seems like the backtracking element is not presented in the algorithm. Does this happen outside of Algorithm 1, or within it? In general, some more details about the algorithm would be appreciated – is it guaranteed to terminate? Obviously, the results suggest it is fast, but what is the complexity? If I’m not mistaken, there is an ILP in the algorithm that could cause bottlenecks depending on what variables impact its performance.\n- Unless I missed it, there is no comparison of robustness of RGD and the proposed method. Quantitative semantics are one of the key motivators for using STL, and it would be informative to see whether the methods perform comparably.\n\nMinor:\n- Line 110, missing space in “unknown,but”\n- Line 202, should “way-point” be “waypoints”?\n- Line 215 “remained” should be “remaining”\n- Line 252 “fucntion\"\n- Line 286 “estimates” should be “estimate”", "was_revised": true, "final_justification": "I am satisfied by the responses by the authors to my own questions, as well as to the questions posed by the other reviewers. Most importantly, I am glad that the authors have elected to include the robustness value. Therefore, I choose to keep my original rating of Accept.", "rebuttal": "We scincerely thank you for the very constructive comments, especially for suggesting the inclusion of robustness as an additional quantitative metric and for pointing out the simplicity of our initial experimental settings. These suggestions prompted us to expand and strengthen our evaluation. We also appreciate your recognition of the novelty of our approach.\n\n**R3.1 Lack of detail in Algorithm 1: backtracking element not clear, termination guarantees**\n\nBack‑tracking is handled **within** Algorithm 1 via the explicit **stack**: Each loop (lines 5–18) pops the current node, iterates over its remaining reachability progresses, tries to sample a waypoint, updates constraints, then pushes the resulting child node. When a branch fails or is exhausted, the next `pop` naturally returns to a shallower depth and no external mechanism is required.\n\nFor readability, the pseudo-code presents the search with an explicit stack, whereas our reference implementation executes the same logic recursively. We will clarify this in the revised manuscript.\n\n**Termination** is ensured because the search space is finite and monotonically shrinking: each successful expansion removes exactly one unsatisfied progress from $\\mathbb{P}^{\\mathcal{R}}$, and a sampling failure never re-pushes the same node. Hence the maximum depth equals the initial number of reachability progresses, and with finite branching the DFS must finish after exploring all configurations or upon finding a complete solution.\n\n\n**R3.2 Complexity, impact of ILP**\n\nA precise worst‑case analysis of the Progress Allocation search is indeed intractable because the branching factor varies with STL structure and time‑window interactions. In broad terms, runtime grows exponentially with the number of reachability progresses, yet *in practice* two factors keep it modest: (i) heuristic ordering and early pruning limit branching, and (ii) inter‑progress time‑window tightening rapidly collapses the feasible subtree. **Empirically the allocator runs in milliseconds–seconds** and is not the overall bottleneck. We will explore stronger heuristics and branch-parallelisation to further improve scalability in our future.\n\nAbout ILP:\nThe **ILP** that arise inside Progress Allocation are lightweight and well-structured: (i) Each instance involves a *fixed* set of time variables (their count does not grow during search) with tight upper‑ and lower‑bound box constraints inherited from the STL time windows. (ii) All objectives and inequalities are 0‑1 combinations of those variables (iii) In scenarios involving repeated ILP solves, the objectives remains unchanged, and constraints are incrementally added rather than rebuilt from scratch. Consequently, each ILP solve is, on average, extremely fast.\n\nIn our current implementation, we do not yet exploit these structural properties and instead rely on the off‐the‐shelf solver PuLP (a Python‐based LP/MIP modeler). Our experiments confirm that, **even with this straightforward setup, the ILP component does not constitute a performance bottleneck**. We will investigate in future work how these properties can be leveraged to further improve efficiency.\n\n**R3.3 No comparison of robustness**\n\nFollowing your suggestion, we computed the average robustness of the executed trajectories (excluding the top & bottom 5 %) for both methods on Maze2d. Our approach outperforms RGD in every scenario:\n\n|Env|Template|RGD|Ours|\n|-|-|-|-|\n|U | 1 | 0.1084 ± 0.1132  | 0.1938 ± 0.0715 |\n|U | 2 | -0.2208 ± 0.2826 | 0.1504 ± 0.0814 |\n|U | 3 | -0.1695 ± 0.2521 | 0.1354 ± 0.0745 |\n|M | 1 | 0.0885 ± 0.2768  | 0.3205 ± 0.0957 |\n|M | 2 | -0.2277 ± 0.3089 | 0.2013 ± 0.1950 |\n|M | 3 | -0.2393 ± 0.3130 | 0.1761 ± 0.2060 |\n|L | 1 | -0.1927 ± 0.3198 | 0.3180 ± 0.1228 |\n|L | 2 | -0.3926 ± 0.2284 | 0.1672 ± 0.2411 |\n|L | 3 | -0.2886 ± 0.2934 | 0.1639 ± 0.2286 |\n\nThese results (will be added to the revised paper) reflect that the trajectories produced by our algorithm consistently better satisfy the STL tasks.\n\n**R3.4  Why alternatives to diffusion (RRT\\*) were not used as comparators.**\n\nClassical planners such as RRT* require explicit knowledge of both the **environment map** and the **system dynamics**—neither is available in our setting. In Maze2d, the agent’s dynamics and the maze geometry are both *unknown*; this renders RRT* (and some optimization-based methods) inapplicable. By contrast, a diffusion model can be trained solely from offline trajectories, implicitly capturing dynamics and environmental constraints without needing a map. This is also one factor why RRT* is often not selected as a comparison baseline in many diffusion-based trajectory planning studies [1,2,3].\n\n**R3.5 What are the dynamics used in simulation? Why not more complex systems?**\n\nIn the Maze2D experiments (Sec. 5), we control a spherical agent whose intrinsic dynamics are relatively simple, but the maze environment introduces complex constraints that also must be learned from trajectory data, thereby increasing the overall complexity. In the comparative experiments in Sec. G, we use double‐integrator dynamics.\n\nIn response to your suggestion, we have **extended our evaluation to two dynamics‑rich tasks** from the offline goal‑conditioned RL benchmark **OGBench** [4]: *cube-single-play* (“cube”) and *antmaze-medium-navigate* (“antmaze”). The cube environment involves controlling a 6-DoF UR5e robot arm to manipulate cubes, whereas the antmaze environment involves controlling an 8-DoF Ant agent to navigate in a maze. \n\nIn our experiments, we train exclusively on the STL task-agnostic trajectory datasets provided by OGBench, but replace the original goal-conditioned tasks with STL tasks. Specifically, in the antmaze environment, we adopt the same task formulation as in Sec. 5, requiring the agent to reach specified regions to satisfy the STL formula. In the cube environment, we focus solely on the end-effector position, requiring it to visit designated regions to satisfy the STL task (ignoring cube manipulation). In the cube environment, following the settings in our experiment, we first generate trajectories in the $x$–$y$–$z$ space and then track them with a PD controller. In the antmaze environment, following [1], we plan trajectories in the $x$–$y$ space and track with an inverse dynamics model that takes a 29-dimensional observation and the next $x$–$y$ goal as input and outputs an 8-dimensional action at each step.\n\nAs in Sec. 5, we generate 100 test cases for each of the nine task templates (Table F.1) in both environments and report the execution success rates in the following Table. These results (over 60 % in antmaze and over 85 % in cube) confirm that our framework remains effective under substantially more complex dynamics.\n\nA more detailed description of the experimental setup, along with comprehensive results and analysis, will be provided in the revised manuscript.\n\n|Environment|Template|Execution Success Rate (%)|\n|-|-|-|\n|antmaze|1|**91.0**|\n|antmaze|2|**97.0**|\n|antmaze|3|**84.0**|\n|antmaze|4|**63.0**|\n|antmaze|5|**71.0**|\n|antmaze|6|**63.0**|\n|antmaze|7|**81.0**|\n|antmaze|8|**87.0**|\n|antmaze|9|**67.0**|\n|cube|1|**98.0**|\n|cube|2|**100.0**|\n|cube|3|**98.0**|\n|cube|4|**98.5**|\n|cube|5|**85.0**|\n|cube|6|**90.0**|\n|cube|7|**97.0**|\n|cube|8|**100.0**|\n|cube|9|**99.0**|\n\n\nOur current implementation adopts **simple baseline modules** for time prediction, trajectory generation, and low-level control. In highly challenging scenarios such as **antmaze**, these basic choices become potential performance bottlenecks. Since our framework is designed to be modular, each component can be replaced by a stronger alternative. Recent advances in diffusion-based trajectory planning (e.g., [1, 2]) provide promising drop-in candidates. We will integrate these enhanced modules and extend the evaluation to even more demanding environments to quantify their benefit in future work.\n\n**R3.6 Clarify $a_{\\Lambda,\\mathbb{T}}^{min}$ and how heuristic order is computed.**\n\nFor a given progress $\\mathcal{P}(a_\\Lambda, b_\\Lambda, \\mu)$, $a_{\\Lambda,\\mathbb{T}}^{min}$ denotes the minimal possible value of $a_\\Lambda$ under the current time‐variable constraints in $\\mathbb{T}$. It reflects the earliest possible activation time of that progress. It can be obtained by solving the following ILP:\n\\begin{aligned}\n&\\min_{\\lambda} \\quad a_\\Lambda(\\lambda) \\\\\n\\text{s.t.}\\quad & \\lambda \\models \\mathfrak{t}, \\quad \\forall \\mathfrak{t} \\in \\mathbb{T},\\\\\n& \\lambda \\in \\mathbb{Z}_{+}^{|\\Lambda|}.\n\\end{aligned}\n\nThe quantities $a_{\\Lambda,\\mathbb{T}}^{max}$, $b_{\\Lambda,\\mathbb{T}}^{min}$, and $b_{\\Lambda,\\mathbb{T}}^{max}$ are defined analogously. Due to space limitations, we have provided only a brief description of the above at lines 230–235; the revised version will include a more detailed exposition.\n\nRegarding the Heuristic Order (lines 283–285), we prioritize progresses with earlier potential deadlines $b_{\\Lambda,\\mathbb{T}}^{min}$. If multiple candidates share the same deadline, we prefer the one with earlier potential start time $a_{\\Lambda,\\mathbb{T}}^{min}$.\n\n**R3.7 Typos and descriptions in Sec. 3.3**\n\nThank you for spotting these issues. We will fix all reported typos and revise Sec. 3.3 so that the exposition is clearer in the final version.\n\n> [1] Luo Y, Mishra U A, Du Y, et al. Generative trajectory stitching through diffusion composition[J]. arXiv:2503.05153, 2025.\n> \n> [2] Chen C, Hamed H, Baek D, et al. Extendable long-horizon planning via hierarchical multiscale diffusion[J]. arXiv:2503.20102, 2025.\n> \n> [3] Xiao W, Wang T H, Gan C, et al. Safediffuser: Safe planning with diffusion probabilistic models[C]//The Thirteenth International Conference on Learning Representations.\n> \n> [4] Park S, Frans K, Eysenbach B and Levine S (2025) Ogbench: Benchmarking offline goal-conditioned rl. In: International Conference on Learning Representations."}, {"review_id": "hIsmBaQJYL", "reviewer": "Reviewer_fjcC", "summary": "This paper presents a novel, data-driven hierarchical framework for generating robot trajectories that satisfy complex Signal Temporal Logic (STL) tasks when the system dynamics are unknown. The proposed method decomposes the STL specification into simpler timed objectives, searches for waypoints to achieve them, and then uses a pre-trained diffusion model to generate and stitch together the final trajectory segments. This approach allows for zero-shot generalization to new tasks using only task-agnostic data and is formally proven to guarantee the satisfaction of the given STL specification if a solution is generated. Run-time execution performance is shown to be quicker than existing diffusion-based solutions with a higher overall success rate.", "questions": "1. In Algorithm 2, L7, what is $d^{\\text{min}}_{det}$? On a related note, I find it difficult to understand the purpose of L5-9 in Algorithm 2, could I get an explanation please or a reference to where it is explained in detail?\n2. Would it be possible to include experiments with more complicated dynamics such as the Ant robot?\n3. In the Results section (L411-412), why is the performance of the method underplayed? It appears to have a greater than 90% and 79% overall success rate (vs 80 and 69 as mentioned). \n4. In Table G.1, why is the success rate of STLPY not mentioned?\n5. How does the approach manage discrepancies between planning times and execution delays (i.e., failure to reach a goal on time due to the controller)? How does this impact the success rate?\n6. Typos:\n    - L202: way-point → way-points\n    - L207: satisfication → satisfaction\n    - L252: fucntion → function\n    - L681: Sementic → Semantic", "limitations": "- Assumes a valid $\\texttt{TimePredict}$ function exists for the entire system, but this is not easy in many environments. For example, a setting where multiple robots are placed in a maze, predicting the time between global system states could be hard due to conflicts.\n- The algorithm heuristics may lead to sub-optimal solutions in terms of makespan which is not fully examined.\n- Delays during execution can cause the specification to not be satisfied and this does not appear formalized.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "## Strengths:\n\n- **Novelty:** The algorithm, while being manually constructed and heuristic based, focuses on generating a valid solution to a given STL specification using Diffusion-based sampling. The approach is novel and cleverly avoids the problem of getting long range trajectories with diffusion models (by sampling between generated waypoints) as well as handling Invariance or Avoidance Predicates (by using $\\texttt{SafeDiffuser}$ that integrates Control Barrier Functions while sampling).\n- **Speed:** The algorithm is shown to be much faster than existing approaches and elegantly handles the slow inference time of diffusion models.\n\n## Weaknesses:\n\n- **Assumption of TimePredict:** The accuracy of $\\texttt{TimePredict}$ is important and is hard to guarantee in a general setting. For example, depending on the maze structure, the time between states may vary drastically. Some requirements on this function (such as assumed accuracy range) along with related experiments (in a given maze) would be helpful to understand the validity of the approach and how easy it would be to get this function. This is especially the case in environments with complex dynamics (e.g., instead of a point mass as in the experiments, if the agent was a quadruped or a differential drive robot).\n- **Solution Optimality:** The approach has several heuristics and assumptions that guide the solution generation yet may not be optimal in many scenarios. Consider Algorithm 1 L9 For each progress ordered by starting time $a_\\Lambda$ - this may cause poor solutions in terms of makespan, e.g. $\\phi = F_{[0,100]} {A}\\land F_{[1,100]}{B}$ where goal A is far away and goal B is near the starting state. This would yield a solution visiting the far goal A first and the coming back for goal B. I realize there are no mentions of solution optimality by the given algorithm, but this is just pointing out the fact that different solutions have distinct characteristics which are often of concern to the user.\n- **Metrics Beyond Success Rate:** On a related note, rather than success rate alone, a makespan equivalent metric or “time to complete” metric could help to give a better idea of solution quality rather than simply success rate.\n- **Writing:** Although the ideas proposed are interesting, the writing and organization could do with several refinements.\n    - **Organization of Section 3:** At over four pages, Section 3 is overly long, making it difficult to follow. Subsection 3.3, in particular, should be reorganized into distinct subsections for each primary module of the algorithm (e.g., Main-Allocation, $\\texttt{SampleState}$) to clearly delineate their functions.\n    - **Clarity of Notation:** I found the notation in L163-L174 somewhat unclear. While going through the appendix provided the necessary clarification, I suggest incorporating some of those details into the main body to improve readability.  For example, the definition of $\\Lambda$ (L163) being a set of time instance variables (clarified in L236) and the domain of $\\mathfrak{t}\\in\\mathbb{T}_\\varphi$ (L171) could be made more explicit in the main text.\n    - **Correction of References:** L 283 mentions “the above DFS” which erroneously points to Algorithm 2, while I believe this references Algorithm 1 (a reference could be inserted here). Additionally, this line could be in the suggested new Main-Allocation subsection which can be separate from the $\\texttt{SampleState}$ subsection.\n    - **Refinement of Figure 1:** The figure lacks clarity and consistency with the text. Labels in the diagram, such as \"Guided Sampling,\" should be updated to match section titles like \"Trajectory Generation.\" The diagram itself should also employ standard conventions, using different shapes to distinguish processes from outputs (e.g., \"Progress Allocation\" vs. \"Waypoints Sequence\").", "was_revised": true, "final_justification": "The additional post-rebuttal study on the `TimePredict` function as a measure of the system dynamics helped alleviate some concerns of its ability. The approach is still largely heuristic-based and an option to modify the optimality criteria would have been ideal. However, as it is, the paper provides an interesting contribution to field of STL-guided planning. A standardized open-source implementation for future work to compare against would be a useful contribution.", "rebuttal": "We scincerely thank you for your very constructive feedback. In particular, your suggestions to analyse the feasibility of the TimePredictor, include additional metrics, and conduct experiments in more challenging environments guided us to broaden and strengthen our evaluation. We also appreciate your acknowledgement of the novelty of our approach.\n\n**R4.1 TimePredict accuracy is critical and might be unreliable in complex domains.**\n\nIn our framework, the TimePredictor collaborates with the trajectory generator: the TimePredictor estimates the realistic travel time between states, and the trajectory generator produces a trajectory of that length. Admittedly, time‑to‑reach can vary drastically. However, a generator trained on trajectories of diverse lengths exhibits sufficient generalization; in practice, even a moderately accurate statistical estimate from the Time Predictor is usually adequate for producing a feasible trajectory.\n\nTo illustrate this collaboration, we conducted a simple test in **Maze2d** and **antmaze** (will be introduced in R4.6). For each environment we created **1 000** random start‑and‑goal cases (goal region radius = 3 %–6 % of the arena size). For each case, we used TimePredictor to estimate the required trajectory length from the start to the center of the goal region, then generated a trajectory of that length using the trajectory generator, and finally tracked it with a PD controller (in Maze2d) or an inverse dynamics model (in antmaze). All modules were used as implemented in our method. The execution success rates shown in the following Table indicate that even in the challenging antmaze setting, our current modules achieve high success. Given our modular design, each component can be upgraded independently for more complex scenarios. We will further dissect module contributions and explore potential improvements in future work.\n| Maze2d-Umaze|Maze2d-Medium|Maze2d-Large|Antmaze-Medium|\n|-|-|-|-|\n|93.9%|89.0%|83.7%|84.8%|\n\n**R4.2 Lack of optimality**\n\nNote that our heuristic order (lines 283–285) is as follows: we prioritize progresses with earlier potential **deadlines**. If multiple candidates share the same deadline, we prefer the one with the earlier potential start time. Therefore, in this example, the algorithm will attempt to complete goal **B** first, because its deadline is earlier.\n\nOur current objective is **task correctness plus dynamic feasibility**, which is already challenging under unknown dynamics. We agree that incorporating additional metrics (e.g., makespan) is a promising research direction. One feasible approach to achieve this may involve replacing our current “stop at the first solution” mode with an anytime mode, allowing it to obtain better solutions by increasing the search effort. We appreciate this suggestion and will add a related discussion in the revised version, as well as investigate this direction in future work.\n\n**R4.3 Evaluation metrics: success rate alone is insufficient.**\n\nAs explained above, we do not currently focus on additional optimization objectives. However, we agree that introducing quantitative metrics beyond success rate to assess solution quality is a valuable suggestion. Besides success rate, we now report the **average STL robustness value** of executed trajectories (top & bottom 5 % trimmed) in Maze2d. Our method consistently outperforms RGD. We will include these results and the corresponding analysis in the revised manuscript.\n\n|Env|Template|RGD|Ours|\n|-|-|-|-|\n|U | 1 | 0.1084 ± 0.1132 |0.1938 ± 0.0715|\n|U | 2 | -0.2208 ± 0.2826|0.1504 ± 0.0814|\n|U | 3 | -0.1695 ± 0.2521|0.1354 ± 0.0745|\n|M | 1 | 0.0885 ± 0.2768 |0.3205 ± 0.0957|\n|M | 2 | -0.2277 ± 0.3089|0.2013 ± 0.1950|\n|M | 3 | -0.2393 ± 0.3130|0.1761 ± 0.2060|\n|L | 1 | -0.1927 ± 0.3198|0.3180 ± 0.1228|\n|L | 2 | -0.3926 ± 0.2284|0.1672 ± 0.2411|\n|L | 3 | -0.2886 ± 0.2934|0.1639 ± 0.2286|\n\n**R4.4 Writing & presentation.**\n\nThank you for the suggestions. We will streamline Section 3, clarify the notation, fix the reference and figure labels, and correct all typos to improve readability in the revision.\n\n**R4.5 About Algorithm 2.**\n\nIn Algorithm 2, line 7, $d_{\\Lambda,\\mathbb{T}}^{min}$ denotes the earlist possible end time of the invariance progress $\\mathcal{I}(c,d_\\Lambda,\\mu)$ under time‐variable constraints $\\mathbb{T}$. Analogous to $a_{\\Lambda,\\mathbb{T}}^{min}$, it can be obtained by solving an ILP as described in lines 230–235.\n\nFor lines 5–9 of Algorithm 2, we first correct a typo by renaming the $\\mu$ in $\\mathcal{I}(c,d_\\Lambda,\\mu)$ to $\\mu'$ to distinguish the predicates. The purpose of this segment is to accumulate time intervals during which the state $x'$ is forbidden. Concretely, for each active invariance progress $\\mathcal{I}(c,d_\\Lambda,\\mu')$, we check whether $x'$ satisfies $\\mu'$. If not, it conflicts with that invariance progress, implying that $x'$ if forbidden while the invariance progress is active. We then compute the earliest possible end time $d_{\\Lambda,\\mathbb{T}}^{min}$ for that progress and add the interval $[c,\\;d_{\\Lambda,\\mathbb{T}}^{min}]$ to the conflict intervals.\n\n**R4.6 Experiments with more complicated dynamics**\n\nWe have **extended our evaluation to two dynamics‑rich tasks** from the offline goal‑conditioned RL benchmark **OGBench** [1]: *cube-single-play* (“cube”) and *antmaze-medium-navigate* (“antmaze”). The cube environment involves controlling a 6-DoF UR5e robot arm to manipulate cubes, whereas the antmaze environment involves controlling an 8-DoF Ant agent to navigate in a maze. \n\nIn our experiments, we train exclusively on the STL task-agnostic trajectory datasets provided by OGBench, but replace the original goal-conditioned tasks with STL tasks. Specifically, in the antmaze environment, we adopt the same task formulation as in Sec. 5, requiring the agent to reach specified regions to satisfy the STL formula. In the cube environment, we focus solely on the end-effector position, requiring it to visit designated regions to satisfy the STL task (ignoring cube manipulation). In the cube environment, following the settings in our experiment, we first generate trajectories in the $x$–$y$–$z$ space and then track them with a PD controller. In the antmaze environment, following [2], we plan trajectories in the $x$–$y$ space and track with an inverse dynamics model that takes a 29-dimensional observation and the next $x$–$y$ goal as input and outputs an 8-dimensional action at each step.\n\nAs in Sec. 5, we generate 100 test cases for each of the nine task templates (Table F.1) in both environments and report the execution success rates in the following Table. These results (over 60 % in antmaze and over 85 % in cube) confirm that our framework remains effective under substantially more complex dynamics.\n\nA more detailed description of the experimental setup, along with comprehensive results and analysis, will be provided in the revised manuscript.\n\n|Environment|Template|Execution Success Rate (%)|\n|-|-|-|\n|antmaze|1|**91.0**|\n|antmaze|2|**97.0**|\n|antmaze|3|**84.0**|\n|antmaze|4|**63.0**|\n|antmaze|5|**71.0**|\n|antmaze|6|**63.0**|\n|antmaze|7|**81.0**|\n|antmaze|8|**87.0**|\n|antmaze|9|**67.0**|\n|cube|1|**98.0**|\n|cube|2|**100.0**|\n|cube|3|**98.0**|\n|cube|4|**98.5**|\n|cube|5|**85.0**|\n|cube|6|**90.0**|\n|cube|7|**97.0**|\n|cube|8|**100.0**|\n|cube|9|**99.0**|\n\nOur current implementation adopts **simple baseline modules** for time prediction, trajectory generation, and low-level control. In highly challenging scenarios such as **antmaze**, these basic choices become potential performance bottlenecks. Since our framework is designed to be modular, each component can be replaced by a stronger alternative. Recent advances in diffusion-based trajectory planning (e.g., [2, 3]) provide promising drop-in candidates. We will integrate these enhanced modules and extend the evaluation to even more demanding environments to quantify their benefit in future work.\n\n**R4.7 Why is the performance of the method underplayed**\n\nTable 2 shows only a subset of results due to page limits; full statistics are in Table F.2. Values quoted in the text are aggregate summaries of the complete table. We will clarify this in the revised version.\n\n**R4.8 Why is the success rate of STLPY not mentioned?**\n\nSTLPY is a *sound and complete* planner with full dynamics and map access, so every randomly generated test case is conditioned to be solvable by STLPY; its success rate is therefore **100 %**. We omitted it for brevity but will add this explanation.\n\n**R4.9 Discrepancies between planning times and execution delays**\n\nOur system outputs one control action per planned step. If tracking error prevents reaching a waypoint in time, the STL specification may be violated. The execution success rates in our experiments indeed reflects this kind of failure modes.\n\nThese kind of execution failures can arise from:\n- **Controller limits** (e.g., a sub-optimal inverse-dynamics model).\n- **Insufficient dynamic feasibility** of the planned trajectory.\n\nPotential future remedies include:\n\n- Improving the TimePredictor and diffusion-based trajectory generator to produce more dynamically feasible plans.\n- Introducing **online re-planning** when the deviation exceeds a predefined threshold (Sec. F.1).\n- Allowing low-level controllers to execute multiple sub-steps per planned state, as long as the total time remains within the discrete-time budget.\n\nWe will elaborate on these points in the revised version.\n\n> [1] Park S, Frans K, Eysenbach B and Levine S (2025) Ogbench: Benchmarking offline goal-conditioned rl. In: International Conference on Learning Representations.\n> \n> [2] Luo Y, Mishra U A, Du Y, et al. Generative trajectory stitching through diffusion composition[J]. arXiv:2503.05153, 2025.\n> \n> [3] Chen C, Hamed H, Baek D, et al. Extendable long-horizon planning via hierarchical multiscale diffusion[J].arXiv:2503.20102, 2025."}]

Author rebuttal:

Meta-review: The authors propose a method for satisfying Signal Temporal Logic (STL) specifications through a combination of spatio-temporal decomposition and trajectory generation using diffusion. The paper addresses an interesting and timely problem and demonstrates that the proposed method outperforms recent approaches on the reported metrics. The discussion of limitations is thorough and balanced, with illustrative examples of failure cases provided. The manuscript is clear and well-structured. Overall, this work represents a valuable and timely contribution to the field, and with its innovative approach and strong empirical results, it merits publication.
Decision: Accept (poster)