💻 computer science

When Automata Meet Streams: Temporal Logic Compilation for Stream-Based Robotics Task and Motion Planning

This paper introduces SAM-TD, a compilation method that enables stream-based Task and Motion Planning to enforce arbitrary Linear Temporal Logic over finite traces constraints by embedding regressed automaton guards into action schemas, thereby handling dynamically generated objects without modifying the underlying planner.

Original authors: Sayem Nazmuz Zaman, Cyrus Neary

Published 2026-08-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sayem Nazmuz Zaman, Cyrus Neary

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

Robots are increasingly expected to do more than just move from point A to point B; they are being asked to perform complex, multi-step jobs in messy, real-world environments like kitchens, laboratories, and factories. To succeed, a robot must solve two distinct problems at once. First, it needs a high-level plan, a sequence of logical steps like "pick up the cup" or "open the door." Second, it must figure out the continuous, physical details of how to actually do those things, such as the exact angle to grip the cup or the smooth path to avoid a table leg. This dual challenge is known as task and motion planning. While computers are good at the logical steps, the physical details are often generated on the fly as the robot searches for a solution, creating a moving target that changes as the plan develops.

The difficulty deepens when we add rules about time and safety. A robot in a chemistry lab cannot mix dangerous chemicals until the ventilation system is on. A drone must always keep a path open to return to its charging station. These are temporal constraints: rules that dictate the order of events or require certain conditions to remain true throughout a task. For decades, researchers have developed ways to force robots to follow such rules, but those methods assumed the robot was working with a fixed, known set of objects. When a robot uses on-the-fly generators to create new physical possibilities during its planning process, those old methods break down. They cannot handle a situation where the list of things the robot might interact with is constantly growing and changing.

A team of researchers at the University of British Columbia has developed a new method to solve this specific problem. They created a system called Synchronous Action Monitoring with Token Destruction, or SAM-TD, which allows robots to follow complex time-based rules even while they are inventing new physical options as they plan. The core idea is to turn the rules into a set of state machines, or simple tracking systems, that run in the background. As the robot considers a potential action, the system checks if that action would break any of the rules. If an action would cause the robot to violate a safety rule or an ordering constraint, the system does not necessarily block the action immediately. Instead, it removes a special "validity token" that the robot needs to reach its final goal.

This mechanism is clever because it lets the robot's planning software do the heavy lifting. The robot's search algorithm is designed to find the most efficient path to a goal. When the validity token is removed, the algorithm realizes that the current path can no longer lead to a successful outcome, because the goal now requires that token to be present. The algorithm then naturally discards that path and looks for a different one, effectively pruning the bad options before the robot ever wastes time calculating the physical details of a forbidden move. This approach works without needing to list every possible object the robot might encounter in advance, which is crucial for tasks where new objects or positions are discovered during the planning process.

The researchers tested this system in three different robotic environments: a kitchen setting, a tabletop manipulation task, and a sorting zone. In these simulations, they introduced various rules, such as requiring a robot to place a white block before moving a red one, or forbidding a robot from entering a dangerous zone. In every case, the system successfully guided the robot to a plan that satisfied all the rules. The experiments showed that the time it took to set up these rules grew linearly with the number of rules added, meaning the system remained efficient even as the constraints became more complex. Crucially, the method prevented the robot from wasting time exploring paths that would inevitably fail, saving significant computational effort.

The study also compared this new method against existing techniques used for standard, non-streaming planning problems. The results showed that the new system was just as fast and effective as the best current methods for those simpler tasks, proving that its ability to handle complex, dynamic environments did not come at the cost of performance on standard problems. The researchers found that the most expensive part of the process was not the rule-checking itself, but the standard work of translating the robot's instructions into a format the computer could execute. This confirmed that the new method integrates smoothly with existing planning tools without introducing a new bottleneck.

By solving the incompatibility between dynamic object generation and time-based rules, this work opens the door for robots to handle more sophisticated, safety-critical tasks in unstructured environments. It demonstrates that robots can be given strict instructions about the order of operations and safety limits, even when the specific physical details of the job are not fully known until the robot starts working. The findings suggest that future robots could be deployed in homes and labs with confidence that they will not only find a way to do a job, but will do it in the correct, safe, and logical order, regardless of how the environment changes around them.

Technical Summary: SAM-TD for Stream-Based TAMP

Problem Statement

Stream-based Task and Motion Planning (TAMP) integrates discrete symbolic planning with continuous geometric reasoning. Systems like PDDLStream utilize "streams"—black-box generators that dynamically produce geometric objects (poses, grasps, trajectories) on-demand during the search process. This creates an expanding, potentially infinite object set, contrasting with classical planning which assumes a fixed, finite universe of objects.

While Linear Temporal Logic over finite traces (LTLf) is a standard formalism for encoding safety-critical ordering, invariance, and liveness constraints in robotics, existing compilation techniques for enforcing LTLf are incompatible with stream-based TAMP. Classical methods rely on eager grounding (enumerating all objects before search) or inserting synchronization actions, both of which fail when the object set is unknown and grows iteratively. Consequently, there is no existing method to enforce arbitrary LTLf constraints in stream-based solvers without modifying the underlying planner or pre-sampling a prohibitively large library of geometric objects.

Methodology: SAM-TD

The authors propose Synchronous Action Monitoring with Token Destruction (SAM-TD), a compilation framework that embeds LTLf constraint monitors directly into the lifted action schemas of a PDDLStream problem. SAM-TD operates without modifying the planner's search algorithm or the stream instantiation layer.

Core Components

LTLf to DFA Translation: Each LTLf constraint is translated into a Deterministic Finite Automaton (DFA). The DFA acts as a monitor, transitioning states based on the sequence of true atomic propositions in the plan trace.
Lifted Action Regression: Since DFA guards evaluate the state after an action, but the planner must decide before execution, SAM-TD uses weakest precondition regression. It translates DFA transition guards (which refer to post-action states) into equivalent conditions on the pre-action state and action parameters. This allows the constraints to be checked against the lifted action schema before grounding.
Synchronous Monitor Updates: The compiled action schemas include conditional effects that update the DFA state (represented by fluent predicates $M^k_j$ ) in lockstep with the execution of the original domain action. This ensures the monitor advances exactly one step for every domain action, preserving the semantics of step-sensitive operators like "next" ( $X$ ).
Token Destruction Mechanism: To handle violations, SAM-TD introduces a shared validity token, Valid.
- If a transition leads to a DFA "sink" state (a non-accepting state from which no accepting state is reachable), the conditional effect permanently deletes the Valid token.
- The planning goal is augmented to require Valid to be true.
- Since no action can re-add Valid, any branch that triggers a sink transition becomes a dead end. Standard delete-relaxation heuristics (e.g., $h_{FF}$ ) assign infinite cost to states lacking Valid, allowing the planner to prune violating branches symbolically before expensive geometric sampling occurs.

Design Constraints

SAM-TD is explicitly designed to satisfy three requirements of stream-based TAMP:

Schema-level encoding: It operates on lifted schemas rather than grounded operators, accommodating the dynamic introduction of objects.
Skeleton preservation: It does not insert synchronization actions, maintaining the one-to-one correspondence between domain actions and trace steps required by the plan-sample-refine loop.
Sampling-aware pruning: It prunes constraint-violating branches at the symbolic level, preventing wasted computation on geometric sampling for invalid plans.

Key Contributions

First Compilation for Stream-Based TAMP: SAM-TD is the first technique to embed arbitrary LTLf constraints into stream-based TAMP problems, guaranteeing that any solution returned satisfies the constraints without modifying the solver.
Token Destruction Mechanism: The paper identifies and formalizes the "Token Destruction" mechanism as a two-state monitor over DFA sink transitions, demonstrating that it allows violations to be handled via conditional effects rather than precondition blocking.
Empirical Evaluation: The authors provide the first empirical evaluation of LTLf-constrained stream-based TAMP across three robotics environments (Kitchen, Tabletop Manipulation, and ZoneSort).
Backward Compatibility: The method is shown to be competitive with state-of-the-art temporal compilation techniques on standard discrete PDDL benchmarks, proving that stream compatibility does not degrade performance on classical problems.

Experimental Results

Stream-Based Performance: In PDDLStream environments, SAM-TD successfully enforced arbitrary LTLf constraints. The compilation time grew linearly with the number of constraints (approx. 30–80 ms per constraint), while the dominant cost remained the grounding of action schemas by the underlying translator (Fast Downward).
Ablation Study (Token Destruction vs. Precondition Blocking): An ablation variant, SAM-PB, enforced constraints by adding negated guards to action preconditions. SAM-PB suffered from an exponential explosion of ground operators due to the disjunctive nature of negated guards, often exhausting memory budgets before planning began. In contrast, SAM-TD's use of conditional effects kept grounding tractable.
Classical PDDL Benchmarks: On six standard PDDL3 tasks, SAM-TD solved 100% of 30 instances, matching the success rate of other top methods (BM06, TCORE, Plan4Past) and achieving the second-lowest geometric-mean total time among methods that solved all instances.

Significance and Claims

The paper claims that SAM-TD demonstrates that temporal constraints in stream-based TAMP can be enforced through compilation alone, without requiring changes to the planner or pre-sampling of geometric objects. The end-to-end cost is governed by the planner's own grounding process rather than the compilation logic or search.

The authors emphasize that this work bridges a fundamental gap between temporal logic compilation and the dynamic nature of stream-based planning. By preserving the domain-action skeleton and utilizing token destruction for pruning, SAM-TD enables the application of complex temporal specifications to long-horizon robotics tasks where geometric parameters are unknown until planning time. Future work is noted to extend this approach to mobile/multi-robot systems and bi-level planners combining reinforcement learning with heuristic search.