A Framework for Motion Planning with Temporal Logic Precedence Specifications via Augmented Graphs of Convex Sets
Shilin You, Gael Luna, Tyler H. Summers · 2026
Read A Framework for Motion Planning with Temporal Logic Precedence Specifications via Augmented Graphs of Convex Sets by Shilin You, Gael Luna, Tyler H. Summers (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00842.txt.
Introduction
You, Luna, and Summers plan robot paths under rules about order in this 2026 paper. Their worlds hold obstacles, keys, and doors. Picking up a key opens its door, and open doors can yield shorter routes. The plan must dodge obstacles and honor the order rules, stated in a fragment of signal temporal logic.
Their method starts with an exact convex split of the free space. The split marks how convex regions, keys, and doors connect. On it they build an augmented graph of convex sets. Its layered form encodes the key-door logic in full. A shortest path through that graph does two jobs at once. It picks the best key order and draws the best smooth path, as a Bézier curve. The solution is exact up to that curve form. The frame suits games, warehouses, and any task where access must be earned in sequence.
Catalog record
| CREATOR | Shilin You, Gael Luna, Tyler H. Summers |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.00842
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Framework for Motion Planning with Temporal Logic Precedence Specifications via Augmented Graphs of Convex Sets Shilin You, Gael Luna, Tyler H. Summers Abstract We present a framework for planning trajectories that avoid obstacles and satisfy logical precedence constraints expressed with a fragment of signal temporal logic (STL). Our approach models environments containing obstacles, keys , and doors , where collecting a key unlocks its associated door and potentially opens shorter paths to a goal. Based on an exact convex partitioning of the free space that encodes connectivity among convex free space, key, and door regions, we construct an augmented graph of convex sets (GCS) whose layered structure exactly encodes the key-door precedence logic. A shortest path in the augmented GCS simultaneously selects an optimal key collection sequence and computes an optimal continuous trajectory, providing an exact solution up to a finite Bézier curve parameterization. The present work substantially extends [ 54 ] with three main contributions. First, we formally prove soundness, completeness, and cost equivalence of the augmented GCS construction. Second, we establish a precise correspondence between the augmented GCS layer structure and the Bellman-Held-Karp (BHK) dynamic programming algorithm for the Traveling Salesman Problem (TSP), showing that our augmented GCS framework can be interpreted as a continuous-geometry generalization of both the TSP and the shortest Hamiltonian path problem within the same combinatorial complexity class as BHK. Third, we develop an initial library of eight STL mission specification variations with proven correctness, including mandatory key collection, pure wayset collection (without precedence constraints), ordered key collection, disjunctive keys, conjunctive doors, items/tools (multi-door keys), timed keys and doors, and conditional (if-then) constraints. Numerical experiments on an expanded benchmark suite demonstrate that our approach achieves an exponential speedup over methods that use general-purpose temporal logic tools, scales to large environments, and yields solutions within 2% of the global optimum on almost all tested instances. I Introduction Motion planning is a fundamental problem in robotics and autonomous systems involving the computation of feasible, optimized trajectories for agents navigating through complex environments [ 31 , 29 ] . Beyond obstacle avoidance, many real-world tasks impose rich logical and sequential constraints on how an agent must interact with its environment. A warehouse robot must pick and verify an item at one station before proceeding to delivery locations. An autonomous underwater robot must make a surface communications handshake before descending into a deep zone. A surgical robot must exchange the correct tool at a swap station before entering the next anatomical tissue layer. An inspection robot must confirm sensor access before traversing a restricted zone. In general, these are precedence constraints : conditions under which parts of an environment become accessible only after prior actions have been completed, such as task execution, confirmation, clearance, or manipulation. Encoding and solving motion planning problems with such constraints efficiently and optimally is a major challenge, due to the inherent coupling between combinatorial sequencing (determining the order of actions) and continuous geometric optimization (computing a smooth trajectory through the environment). These problems are coupled tightly: the optimal action sequence depends on the geometry, and the feasibility of a continuous path depends on the action sequence. Existing approaches, discussed in detail in the related work section below, tend to handle one problem well, but rarely both. The graphs of convex sets (GCS) framework, introduced by Marcucci et al. [ 37 , 36 , 38 ] , provides a powerful framework to address this discrete-continuous coupling. By associating convex programs with the nodes and edges of a graph, GCS elegantly unifies combinatorial graph search with continuous convex optimization into a single optimization problem. For shortest path problems, solving the relaxation of a tight mixed-integer convex reformulation yields certifiably near-optimal or globally optimal solutions for many practical motion planning problems, essentially using only convex optimization. The goal of the present paper is to extend the GCS framework to a much richer class of mission planning problems with precedence constraints, expressed as a fragment of signal temporal logic (STL). An overview of the proposed approach is shown in Fig. 1 . Prior work of You et al. [ 54 ] introduced augmented graphs of convex sets that encode key-door precedence constraints within the GCS framework. The main insight was that by constructing carefully layered and modified copies of the base GCS – one subgraph per reachable subset of collected keys – and linking layers via zero-cost directed edges at key nodes, the combinatorial precedence structure is exactly encoded in the graph topology. A shortest path in the augmented GCS simultaneously selects an optimal key-collection sequence and computes an optimal continuous trajectory, solving the discrete-continuous problems jointly. On benchmark instances, our approach runs several orders of magnitude faster and scales to far larger environments than general-purpose temporal logic motion planning tools [ 26 ] . Fig. 1 : Overview of the proposed approach. The environment is first partitioned and represented as a Graph of Convex Sets (GCS). An augmented GCS is then constructed to encode precedence specifications, and a shortest path problem is solved for the augmented GCS. The present paper substantially extends You et al. [ 54 ] . We provide formal proofs of optimality, establish a precise connection to a landmark classical combinatorial algorithm, develop a library of specification variations, and present an expanded computational study. I-A Contributions Prior work [ 54 ] made the following contributions: (1) an exact convex partitioning algorithm (Algorithm 1) that constructs a labeled GCS encoding connectivity among free space, key, and door regions; (2) an algorithm (Algorithm 2) for constructing an augmented GCS with an informal argument that a shortest path in the augmented GCS exactly solves the original motion planning problem; and (3) a key-door benchmark generator and numerical experiments demonstrating orders-of-magnitude speedup over general-purpose temporal logic tools. The present paper contributes the following beyond [ 54 ] : Formal proofs of correctness and optimality (Theorem 1). We present proofs of soundness and completeness, establishing a bijection between augmented GCS paths and feasible trajectories, and of cost equivalence. Bellman-Held-Karp (BHK) correspondence (Theorem 2). We demonstrate that the layer structure and inter-layer edges of the augmented GCS correspond exactly to the BHK dynamic programming recurrence [ 4 , 20 ] for the Traveling Salesman Problem (TSP), generalized from discrete city-to-city costs to shortest paths through continuous geometry. The augmented GCS matches the combinatorial complexity class of BHK while additionally solving the continuous geometry problem that BHK takes as preprocessed input. The BHK correspondence is not just an elegant aesthetic observation, it also opens the door to connect with more than 70 years of research on the TSP, one of the most widely studied combinatorial optimization problems. It strongly motivates translating a wide variety of heuristics into the augmented GCS framework; these heuristics can enable scaling to extremely large instances despite worst-case (exponential) computational complexity. Extended Specification Library (Section VII ). We develop eight specification variations extending the key-door precedence logic: mandatory key collection, pure wayset collection (without precedence constraints), ordered key collection, disjunctive keys, conjunctive doors (multi-key doors), items/tools (multi-door keys), timed keys and doors, and conditional (if-then) constraints. For each variation, we provide the modified STL formula, the corresponding modification for augmented GCS construction in Algorithm 2,