CS Paper Radar

Fast and Robust Temporal Logic Planning via ADMM-based Trajectory Optimization

Lukas Pries, Joris Verhagen, Jon Arrizabalaga, Jana Tumova, Markus Ryll, Zachary Manchester

cs.RO cs.FL ·submitted 2026-09-19 14:13 UTC · v1

Abstract

We present a fast numerical method for safe continuous-time motion planning under Temporal Logic (TL) specifications. The method generates smooth continuous trajectories that remain collision-free while robustly satisfying temporal and logical task requirements. A central component of our method is the formulation of nonconvex safety and logic constraints as unions of convex sets where associated discrete decisions are encoded in a joint feasibility graph. This graph representation allows Euclidean projection onto the feasible set and proximal robustness maximization to be reformulated as shortest- and widest-path problems, respectively. Building on this structure, we develop a nonconvex splitting method based on the Alternating Direction Method of Multipliers (ADMM), which decouples smooth spatio-temporal trajectory optimization from nonsmooth discrete constraint handling within the optimization. The resulting algorithm exhibits reliable convergence across benchmarks and scales to large-scale motion-planning problems, providing a 4.7x average speedup over the state of the art on discrete and continuous-time logic problems.

Closest papers

Nearest neighbours by meaning across the whole index.

Motion Planning with Temporal Logic Precedence Specifications in Dynamic Environments via Spacetime Augmented Graphs of Convex Sets

eess.SY ·2026-10-19 ·Shilin You, Lars Lindemann, Tyler H. Summers
similarity 0.68
Abstract

We extend the augmented graph of convex sets GCS framework for motion planning with temporal logic precedence specifications to dynamic environments in which obstacles, keys, and doors undergo piecewise-linear translation and/or dilation over time. The main insight is that piecewise-linear motion of polytopic sets in R^d lifts exactly to a static polytopic partition of spacetime R^d X R_>=0. We show that the main result from the static case carries over to spacetime essentially without modification: a shortest path in the spacetime augmented GCS provides an exact optimal solution to the motion planning problem with precedence specifications. Moreover, the layered subgraph lattice that encodes signal temporal logic (STL) precedence specifications retains precise correspondence with the Bellman--Held--Karp (BHK) algorithm, and the full library of restricted but expressive STL specifications generalizes to the dynamic setting. Further, the framework allows time-gated keys and doors, collectible or passable only within a temporal window. The geometric side of the framework requires two modifications: a causality constraint (the time coordinate of a trajectory must be non-decreasing) and a spacetime speed constraint (bounded physical velocity), both of which are convex in the Bézier control points.

0.23

Graphs of Trajectory Bundles for Nonlinear Motion Planning

cs.RO ·2026-10-23 ·Joris Verhagen, Jon Arrizabalaga, Jana Tumova, Zachary Manchester
similarity 0.65
Abstract · 9 pages, 4 figures

We present the Graphs of Trajectory Bundles (GTB) method for motion planning of systems with nonlinear and black-box dynamics, combining sampling-based motion planning with trajectory optimization and graph search. Based on a graph-of-convex-sets decomposition of the workspace, GTB iteratively constructs a graph of trajectory bundles that captures the local dynamics of the system at any vertex. By solving a shortest-path problem on this graph, we find maximally dynamically feasible iterates that satisfy the system's dynamics in the limit and any constraints such as collision avoidance or additional safety or specification constraints by construction of the underlying graph. As a result, GTB can handle highly nonlinear, unstable, and even black-box dynamics with complex collision and specification constraints, making it a powerful tool for motion planning of complex systems.

0.17

Asymptotically Optimal Multi-Robot Task and Motion Planning

cs.RO ·2026-09-16 ·Thi Thuy Ngan Duong, Cheuk Tung Shadow Yiu, Rahul Shome, Yoonchang Sung
similarity 0.65
Abstract

Multi-robot task and motion planning (MR-TAMP) requires jointly reasoning about discrete task decisions and continuous collision-free motions of multiple interacting robots. Although asymptotically optimal algorithms have been developed for task and motion planning, extending these guarantees to the multi-robot setting introduces an important challenge: different task transitions may involve different subsets of robots and therefore impose constraints of different dimensions on the composite configuration space. Consequently, an asymptotically optimal planner must not only optimize motion within each task mode, but also ensure sufficient exploration of the different types of transitions connecting them. We characterize this transition structure and establish sufficient conditions for global asymptotic optimality in MR-TAMP, requiring persistent coverage of relevant transitions and asymptotically improving motion planning within connected feasible regions. Based on these conditions, we develop an efficient asymptotically optimal MR-TAMP algorithm that combines evolving individual-robot roadmaps with implicit tensor-product search, avoiding explicit construction of the composite roadmap. The planner further employs conditional transition sampling, lazy collision checking, and mode- and solution-level guidance to improve finite-time planning efficiency while retaining persistent exploration. The resulting framework provides asymptotic optimality guarantees for multi-robot manipulation while efficiently exploiting the structure of individual-robot motion planning.

0.22

Efficient Hybrid Hard--Soft Signal Temporal Logic MPC for Driving under Multimodal Uncertainty

cs.RO eess.SY ·2026-10-11 ·Kumar Manas, Adrian Paschke
similarity 0.65
Abstract · 8 pages

Motion planning for automated vehicles in interactive traffic has to simultaneously ensure safety, respect traffic rules, and maintain comfortable progress under multi-modal behavior uncertainty. Imposing all these requirements as hard constraints reduces feasibility, whereas treating them all as costs allows safety-critical requirements to be traded against progress. We propose a hybrid hard--soft Signal Temporal Logic (STL) MPC framework that optimizes a single shared ego trajectory against every retained behavior hypothesis: minimum-distance and speed predicates are imposed as explicit hard constraints, while soft STL robustness terms shape clearance, comfort, and interaction quality within the resulting feasible driving corridor. This retains robustness to discrete interaction modes without branch-specific contingent ego policies. We further identify substantial symbolic graph-construction overhead and introduce reachability-certified relevance screening and vectorized symbolic construction to reduce computational cost while preserving the feasible set and objective. Closed-loop Monte Carlo evaluation over six highway and intersection scenarios shows the highest strict success rate among the compared planners with no observed collisions or rule violations, at roughly a quarter of the planning latency of the unoptimized formulation. An ablation study separates the two layers: the hard constraints define the safety envelope, while the soft terms improve clearance and motion quality within it.

0.26

Safety-aware Model Predictive Path Integral Control with Signal Temporal Logic

cs.RO eess.SY ·2026-08-25 ·Yiqi Zhao, Taekyung Kim, Hideki Okamoto, Bardh Hoxha, Jyotirmoy V. Deshmukh +2 more
similarity 0.65
Abstract

Safety-aware motion planning remains a challenge in robotics, especially when missions are time-critical and are under complex specifications. In this paper, we propose safety-aware-stl-mppi, a computationally efficient sampling-based receding-horizon planning framework designed to promote satisfaction of constraints expressed in Signal Temporal Logic (STL). Our approach encodes discrete-time STL formulas into candidate time-varying control barrier functions (CBF), which are integrated into a model predictive path integral (MPPI) controller. Our method inherits the benefits of low computational cost from an efficiently parallelizable sampling based planner and utilizes CBF for constraints expressed in STL. We compare against several MPPI baselines using four artificial Mars Rover planning case studies with a diverse environment and cost setups, where we show our method consistently achieving high safety and efficiency. We show a quadcopter planning experiment with NVIDIA Isaac Lab.

0.16

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

cs.RO cs.FL ·2026-08-19 ·Sayem Nazmuz Zaman, Cyrus Neary
similarity 0.64
Abstract

Stream-based robotics Task and Motion Planning (TAMP) integrates discrete symbolic planning with dynamically generated continuous geometric parameters, such as poses, grasps, and trajectories. However, stream-based planners typically reason only about goal reachability, whereas long-horizon tasks also demand adherence to temporal specifications, such as safety-critical ordering, invariance, and liveness constraints. No methods currently exist to enforce such temporal constraints for stream-based solvers because streams generate an expanding geometric object set via iterative stream refinement loops during planning, rendering existing temporal-logic compilation techniques incompatible. We therefore present Synchronous Action Monitoring with Token Destruction (SAM-TD), a compilation method that enforces arbitrary Linear Temporal Logic over finite traces ($\textrm{LTL}_f$) specifications in stream-based TAMP. SAM-TD translates arbitrary $\textrm{LTL}_f$ constraints into automata and embeds regressed automaton guards into action schemas, which are pre-specified before planning begins. By doing so, SAM-TD can handle objects generated by streams during planning, thus circumventing the need to enumerate a fixed object set or modify the underlying planner. During search, SAM-TD synchronously updates automaton states and uses a validity token shared across all automata to prune constraint-violating branches. We show that SAM-TD supports dynamically generated stream objects from iterative stream refinements during plan search. Experimental results provide the first ever demonstration of stream-based TAMP under $\textrm{LTL}_f$ constraints in three robotics PDDLStream environments. Furthermore, on standard discrete PDDL benchmarks, SAM-TD is competitive with state-of-the-art temporal-constraint compilation methods.

0.24

Hybrid Optimization-Generative Motion Planning for Multiagent Affine Formations

cs.RO eess.SY ·2026-11-16 ·Zhonggang Li, Hongyu Zhou, Raj Thilak Rajan
similarity 0.63
Abstract

Formation maneuver control enables a multiagent system to cooperatively navigate through constrained environments in collective motion. While various formation controllers exist, they rely heavily on high-quality and dynamically feasible reference trajectories provided a priori, making formation motion planning (FMP) essential. To address the computational challenges for high-dimensional joint trajectories faced by conventional constrained optimization-based solutions, this paper introduces a hybrid optimization-generative framework with a focus on affine formations, which provide the necessary spatial flexibility. By formulating the planning task as a constrained Maximum-a-Posteriori estimation, we decouple multiagent objectives to leverage pre-trained single-agent diffusion priors for dynamic feasibility, obstacle avoidance, and smoothness. We then interleave the generative process with projected gradient descent (PGD) to strictly enforce affine geometric constraints with safety guarantees. Simulations demonstrate that our framework generates highly smooth, collision-free plans that are readily trackable by common distributed controllers and outperforms state-of-the-art planners in various metrics.

0.18

SparseMax-dSTL: Sound Robustness with Horizon-Independent Gradient Allocation for Temporal Logic Trajectory Optimization

eess.SY cs.LOcs.RO ·2026-10-16 ·Sai Sandeep Damera, Ryan Matheu, John S. Baras, Calin Belta
theory similarity 0.63
Abstract · 8 pages, 5 figures. This work has been submitted to the IEEE for possible publication

A gradient-based solver that enforces a Signal Temporal Logic (STL) specification uses a smooth approximation of its quantitative semantics, the robustness. In safety-critical trajectory optimization, this approximation must have two properties. First, it must be sound, that is, nonnegative only on trajectories that satisfy the specification. Second, at each temporal operator, the weight of its gradient on the violating samples must stay bounded away from zero, however long the horizon. The approximations in use, including the log-sum-exp, its sound variant, and the generalized-mean robustness, do not have both. We introduce lower approximations of the minimum and the maximum whose gradients are sparsemax projections, and we prove that the robustness built from them has both. It lies below the exact robustness and is therefore sound, and its error has a bound that is independent of the number of samples and known before optimization. The gradient of each approximation is exactly zero on every sample beyond a data-dependent threshold, so the weight on violating samples a gap beyond the others has a positive lower bound at every horizon. On a planar unicycle and on a seven-joint manipulator beside a person in simulation, the log-sum-exp approximation is positive on a violating trajectory. As the horizon of the manipulator's task grows from 10 to 80 s, the gradient weight of the sound variant on the violating samples falls from 0.22 to 0.04, while that of sparsemax stays at 1. In a constrained trajectory optimization of the unicycle, the constraint on the log-sum-exp robustness returns a violating trajectory, whereas the constraint on the sparsemax robustness returns a trajectory that satisfies the specification with the required margin.

0.20