🤖 AI

Zero-Shot Signal Temporal Logic Planning with Disjunctive Branch Selection in Dynamic Semantic Maps

This paper proposes a zero-shot Signal Temporal Logic planning framework that combines a map-conditioned Transformer with a lightweight heuristic and Transitive Reinforcement Learning to generate feasible, logically coherent trajectories in dynamic semantic maps without requiring retraining.

Original authors: Bowen Ye, Ancheng Hou, Junyue Huang, Ruijia Liu, Xiang Yin

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bowen Ye, Ancheng Hou, Junyue Huang, Ruijia Liu, Xiang Yin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a robot tasked with navigating a maze to complete a complex mission. The mission isn't just "go from A to B." It's a set of rules written in a special language called Signal Temporal Logic (STL).

Here is what that language sounds like: "Go to the red zone within 10 seconds, then avoid the blue zone forever, OR if you can't do that, go to the green zone within 20 seconds."

The problem is that mazes change. Sometimes there are walls where there used to be open space. Sometimes the "red zone" is blocked. Traditional robots either:

Think too slowly: They try to calculate every possible path mathematically, which takes too long for real-time use.
Memorize too much: They learn by practicing in one specific maze. When you put them in a new maze, they get confused and fail.

This paper introduces a new "brain" for robots that solves this problem. Here is how it works, using simple analogies:

1. The "Decompose-Then-Synthesize" Strategy

Instead of trying to solve the whole giant puzzle at once, the robot breaks the mission down into smaller, manageable steps.

The Analogy: Imagine you are planning a road trip with a complex itinerary. Instead of driving blindly, you first break the trip into "Drive to City A," then "Drive to City B." The robot does the same with its logic rules, turning a giant sentence into a list of small checkpoints.

2. The "Smart Chooser" (Heuristic Disjunction Selection)

The tricky part of the mission is the "OR" (disjunction). The robot might have a choice: "Go through the left door OR the right door."

The Problem: If the robot picks randomly, it might choose the door that leads to a dead end or a wall.
The Solution: The authors added a "Smart Chooser." Before the robot starts moving, this module looks at the map and the rules. It asks: "Which door is easier to reach? Which one has more time to spare? Which one is less complicated?"
The Metaphor: Think of it like a GPS that doesn't just pick a route, but picks the best route based on current traffic and road conditions. It filters out the "bad choices" so the robot doesn't waste time trying to go through a wall.

3. The "Map-Reading Architect" (Transformer)

Once the robot knows what to do (the small steps) and which path to take, it needs to figure out how to move.

The Innovation: The robot uses a Transformer (a type of AI famous for understanding language). But instead of reading words, it reads maps.
How it works: The robot looks at the maze layout (the walls, the open spaces) and the mission steps simultaneously. It learns to generate a smooth path that fits the specific shape of the current maze.
The "Zero-Shot" Magic: This is the most impressive part. The robot was trained on a bunch of mazes, but it was never shown the specific maze it is facing right now. Yet, it can still navigate it perfectly. It's like a chef who has learned to cook many different dishes and can instantly cook a new recipe they've never seen before, simply by understanding the ingredients on the counter.

4. The "Time-keeper" (Transitive Reinforcement Learning)

The robot also needs to know when to do things. "Reach the red zone in 10 seconds."

The Problem: Guessing time is hard. If the robot guesses wrong, it might arrive too early or too late.
The Solution: The authors used a technique called Transitive Reinforcement Learning (TRL).
The Analogy: Imagine teaching a child to judge distances. Instead of just saying "This is 5 miles," you say, "This is farther than that, but closer than the other one." TRL teaches the robot to understand the relationship between times (A is longer than B, B is longer than C) rather than just memorizing exact numbers. This makes the robot much better at estimating how long it will take to get from point A to point B in a new, unfamiliar maze.

The Result

The authors tested this system in digital mazes with different sizes and obstacle layouts. They also tested it with two different types of robot movement (one that moves like a car, one that moves like a sliding puck).

The findings were:

Higher Success Rate: The robot successfully completed its missions more often than previous methods, especially in complex, cluttered mazes.
Faster Decisions: By using the "Smart Chooser" to pick the best path early on, it saved time.
True Generalization: It worked perfectly on maps it had never seen before, without needing to be retrained.

In short, this paper presents a robot planner that is fast, adaptable, and smart enough to pick the right path in a changing world without needing a manual for every new room it enters.

Technical Summary: Zero-Shot Signal Temporal Logic Planning with Disjunctive Branch Selection in Dynamic Semantic Maps

1. Problem Formulation

The paper addresses the challenge of Signal Temporal Logic (STL) planning in variable-map environments where system dynamics are unknown. The goal is to synthesize a finite-horizon trajectory $x_{0:T}$ that satisfies a complex STL specification $\phi$ while adhering to collision avoidance constraints defined by a dynamic binary maze map $M$ .

Key constraints and challenges include:

Zero-Shot Generalization: The solver must handle unseen map layouts, obstacle configurations, and STL specifications without instance-specific retraining or fine-tuning.
Unknown Dynamics: The planner operates without an explicit transition function $f(x_t, u_t)$ , relying instead on an offline dataset of historical trajectories.
Disjunctive Complexity: STL specifications often contain disjunctions (OR operators, $\lor$ ). Resolving these requires selecting a specific branch of the logic to satisfy. In dynamic environments, unguided selection can lead to choosing branches that are geometrically infeasible or dynamically difficult, causing planning failure.
Temporal Grounding: Decomposing a high-level STL formula into sub-tasks requires accurate temporal allocation (determining when to visit specific regions), which is difficult to learn consistently across varying map geometries.

2. Methodology

The proposed framework follows a "decompose-then-synthesize" paradigm, integrating three core components:

A. Heuristic Disjunctive Branch Selection
To address the combinatorial explosion and feasibility issues of disjunctions, the STL formula is first converted into Disjunctive Normal Form (DNF). A lightweight heuristic then ranks candidate branches ( $\phi_k$ ) to select the most feasible one ( $\phi^*$ ) based on three criteria:

Temporal-Operator Complexity: Penalizes branches with complex nesting of temporal operators (e.g., $U$ , $G$ ), which are empirically harder to satisfy.
Map Reachability: Computes graph-based distances (e.g., BFS/DFS) on the current map $M$ to penalize branches requiring regions that are difficult to reach or separated by obstacles.
Temporal Slack: Rewards branches with larger time intervals between sub-tasks, offering more flexibility for trajectory generation.
The branch with the minimum heuristic score is selected for downstream planning.

B. Transitive Reinforcement Learning (TRL) for Time Prediction
A learned time predictor estimates the number of discrete time steps required to travel between sub-goal waypoints. To ensure temporal consistency across different map scales and layouts, the predictor is trained using Transitive Reinforcement Learning (TRL) rather than standard pointwise regression.

Mechanism: TRL enforces that predicted step lengths preserve the relative ordering implied by the training data. If trajectory $i$ takes longer than trajectory $j$ in the ground truth, the model must predict $\hat{\Delta t}_i > \hat{\Delta t}_j$ .
Loss Function: The training objective combines an $L_1$ regression loss with a margin-based ranking loss ( $L_{TRL}$ ) that penalizes violations of transitive ordering constraints. This improves the global calibration of time estimates.

C. Map-Conditioned Transformer Trajectory Generator
The final trajectory is synthesized using an autoregressive Transformer that conditions on:

Map Tokens: Encoded binary maze map $M$ and region descriptors.
Time Tokens: Temporal intervals derived from the selected STL branch.
Trajectory Prefix: The current state history.
The model generates the trajectory token-by-token (state-by-state). To mitigate exposure bias during training, scheduled sampling is employed, gradually transitioning from teacher forcing (using ground-truth states) to autoregressive generation (using model predictions). The generator is dynamics-agnostic, meaning it does not receive explicit dynamic model parameters at inference time.

3. Key Contributions

Heuristic Disjunction Handling: Introduction of a lightweight, three-criteria heuristic for selecting disjunctive branches, significantly expanding the range of solvable STL specifications in practice by avoiding infeasible logical paths.
Zero-Shot Planning on Variable Maps: Development of a map-conditioned Transformer trajectory generator that generalizes to unseen obstacle layouts and map sizes without retraining, enhancing the universality of STL solving.
Transitive Reinforcement Learning for Temporal Grounding: Application of TRL to train the time predictor, ensuring consistent temporal allocation across decomposed sub-tasks and improving overall STL satisfaction robustness.
Empirical Validation: Demonstration of consistent performance gains across diverse environments (varying map complexities) and dynamics (double-integrator and unicycle models), validating the framework's robustness to distribution shifts.

4. Experimental Results

Experiments were conducted on a grid-based navigation benchmark (U-Maze family) with map sizes of $5\times5$ , $7\times7$ , and $9\times9$ , under both double-integrator (DI) and unicycle (UNI) dynamics.

Success Rate: The proposed method achieved consistent improvements in success rates compared to a baseline (the same method without heuristic branch selection). Gains were most pronounced in larger, more complex maps (e.g., $9\times9$ ), where the heuristic effectively pruned infeasible branches.
Robustness: The robustness values (quantitative measure of STL satisfaction) remained comparable to or exceeded the baseline, indicating that higher success rates were not achieved by sacrificing specification margins.
Efficiency: While nominal planning time was comparable to the baseline, the inclusion of heuristic selection substantially reduced the effective planning time by pruning the search space early.
Generalization: The trajectory generator successfully synthesized feasible trajectories for both DI and UNI dynamics without explicit dynamic model inputs, demonstrating strong transferability across motion models.

5. Significance and Claims

The paper claims that its primary significance lies in bridging the gap between formal logical reasoning and data-driven trajectory synthesis in dynamic, unknown environments. By decoupling high-level logical branching (via the heuristic) from low-level geometric realization (via the Transformer), the framework addresses the brittleness of existing zero-shot planners when faced with variable map geometries and complex disjunctive logic.

The authors emphasize that their approach offers a scalable, zero-shot solution that does not require environment-specific retraining, making it a promising direction for deploying STL-based planners in real-world scenarios where maps and obstacles change unpredictably. The integration of TRL is highlighted as a novel method to improve the temporal coherence of learned planners, a critical factor for satisfying long-horizon temporal constraints.