Motion Planning with Precedence Specifications Via Augmented Graphs of Convex Sets
Shilin You, Gael Luna, Juned Shaikh, David Gostin, Yu Xiang, Justin Koeln, Tyler Summers
AI summary
Problem
General temporal logic tools struggle with the computational complexity of motion planning when environments contain precedence constraints like keys unlocking doors. This paper addresses how to efficiently compute optimal trajectories that satisfy such logical constraints while navigating complex obstacle-free spaces.
Approach
The method partitions the obstacle-free space into convex sets and constructs a layered augmented graph where each layer represents a different set of collected keys. A shortest path problem solved on this graph simultaneously finds the optimal route and the sequence of key pickups needed to unlock doors.
Key results
- Exact convex partitioning algorithm for free space, keys, and doors with labeled connectivity graph
- Augmented graph of convex sets construction that exactly encodes key-door precedence logic
- Pipeline solves motion planning via shortest path on the augmented graph, achieving near-optimal solutions within 1% of optimal
- Demonstrates several orders of magnitude speedup over state-of-the-art general temporal logic tools on key-door maze benchmarks
Why it matters
It enables efficient, certifiably near-optimal trajectory planning for robots navigating complex, logic-constrained environments, bridging the gap between theoretical temporal logic and practical computational efficiency.
Abstract
We present an algorithm for planning trajectories that avoid obstacles and satisfy key-door precedence specifi- cations expressed with a fragment of signal temporal logic. Our method includes a novel exact convex partitioning of the obstacle free space that encodes connectivity among convex free space sets, key sets, and door sets. We then construct an augmented graph of convex sets that exactly encodes the key-door precedence specifications. By solving a shortest path problem in this augmented graph of convex sets, our pipeline provides an exact solution up to a finite parameterization of the trajectory. To illustrate the effectiveness of our approach, we present a method to generate key-door mazes that provide challenging problem instances, and we perform numerical experiments to evaluate the proposed pipeline. Our pipeline is faster by several orders of magnitude than recent state-of- the art methods that use general purpose temporal logic tools.