DAG-STL: A Hierarchical Framework for Zero-Shot Trajectory Planning under Signal Temporal Logic Specifications

Signal Temporal Logic (STL) has emerged as a powerful formal language for specifying tasks in robotics and intelligent systems. Its strength lies in its ability to precisely describe temporal and logical task requirements, making it ideal for complex task planning. However, a major challenge in STL planning is ensuring task satisfaction while being compatible with system dynamics. When the environment and system dynamics are fully known, STL planning can be formulated as a hybrid optimization problem where system dynamics and STL constraints are explicitly encoded. However, such optimization-based approaches often incur substantial computational burdens, especially for large planning horizons. Additionally, these methods rely on accurate knowledge of the system model, which is often unavailable in many practical systems. To address these issues, data-driven alternatives have emerged, particularly in settings where accurate dynamics models are unavailable. These methods utilize trajectory data collected from simulations or prior operations, avoiding the need for explicit mathematical models.

Planning under unknown dynamics using Signal Temporal Logic (STL) is a challenging task. Traditional methods often rely on explicit system models or learn task-specific behaviors through reinforcement learning, limiting their zero-shot generalization to unseen STL tasks. Specifically, existing methods face computational burdens and model dependencies when dealing with complex long-horizon STL tasks. Moreover, direct robustness-guided diffusion methods perform poorly under complex long-horizon constraints, as directly optimizing STL robustness in trajectory space becomes increasingly difficult. Thus, how to leverage task-agnostic trajectory data for STL planning under unknown dynamics remains an unsolved problem.

The DAG-STL framework introduces several innovations: First, it decomposes STL formulas into reachability and invariance progress conditions linked by shared timing constraints, simplifying complex task planning and enhancing flexibility. Second, DAG-STL allocates timed waypoints using learned reachability-time estimates, enabling effective planning under unknown dynamics. Finally, DAG-STL synthesizes trajectories with a diffusion-based generator, improving trajectory generation efficiency and planning execution reliability. Compared to existing methods, DAG-STL excels in handling complex tasks and demonstrates broad applicability across various navigation and manipulation scenarios.

The implementation of the DAG-STL framework involves several key steps:

• �� Semantic Decomposition: Decomposes STL formulas into reachability and invariance progress conditions linked by shared timing constraints.

• �� Progress Allocation: Allocates timed waypoints using learned reachability-time estimates, constructing a waypoint skeleton.

• �� Trajectory Generation: Synthesizes trajectory segments between consecutive waypoints using a diffusion-based generator and concatenates these segments into a full state trajectory.

• �� Dynamic Consistency Metric: Introduces a rollout-free dynamic consistency metric to evaluate the state and transition support of a planned trajectory under the offline dataset.

• �� Anytime Refinement Search: Refines progress allocation by exploring multiple admissible state-time hypotheses and revising upstream decisions responsible for poorly supported local transitions.

• �� Online Replanning: Performs either local segment repair or global history-consistent re-allocation during execution to handle tracking drift and disturbances.

The experimental design includes tests in Maze2D, OGBench AntMaze, and the Cube domain to evaluate the performance of DAG-STL. The experiments used multiple benchmark datasets and set different task scenarios to test the framework's performance on complex long-horizon STL tasks. Key experimental metrics include task completion rate, trajectory generation efficiency, and execution reliability. Ablation studies were also conducted to verify the contribution of each component to the overall performance. Results show that DAG-STL significantly outperforms direct robustness-guided diffusion methods in handling complex tasks, demonstrating strong generalization capabilities and computational efficiency.

Experimental results show that DAG-STL excels in complex long-horizon STL tasks, significantly outperforming direct robustness-guided diffusion methods. In tests across Maze2D, OGBench AntMaze, and the Cube domain, DAG-STL achieved higher task completion rates and trajectory generation efficiency. Additionally, DAG-STL demonstrates strong generalization capabilities across navigation and manipulation settings, enabling zero-shot task planning under unknown dynamics. By introducing a rollout-free dynamic consistency metric and an anytime refinement search procedure, DAG-STL improves multiple allocation hypotheses under finite budgets and introduces a hierarchical online replanning mechanism for execution-time recovery.

The DAG-STL framework has broad application potential across multiple fields. Firstly, it can be directly applied to robotic navigation and manipulation tasks, especially in dynamically changing environments. Secondly, DAG-STL can be used for path planning in autonomous vehicles, enhancing decision-making capabilities in complex traffic scenarios. Additionally, the framework can be applied to task scheduling and resource allocation in industrial automation, improving production efficiency and flexibility. By integrating with other planning and learning methods, DAG-STL is expected to achieve wider application across more fields.

Despite DAG-STL's excellent performance in multiple experiments, there are still some limitations. Firstly, DAG-STL may face computational burdens when handling extremely complex STL formulas, as the decomposition and allocation process requires managing numerous time variables and constraints. Secondly, in some cases, the hierarchical online replanning mechanism may not fully recover trajectory deviations caused by model mismatches or environmental changes. Additionally, DAG-STL relies on the quality and diversity of offline datasets, which may limit its application in data-scarce or incomplete environments. Future research directions include optimizing DAG-STL's computational efficiency, extending the framework to support more diverse tasks and environments, and exploring integration with other planning and learning methods.