A Framework for Motion Planning with Temporal Logic Precedence Specifications via Augmented Graphs of Convex Sets
It provides an exact solution for motion planning with logical precedence constraints, which is a known bottleneck in robotics and formal methods.
The paper presents a framework for motion planning under temporal logic precedence constraints (e.g., key-door) using an augmented graph of convex sets, achieving exact optimality up to Bézier parameterization.
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.