Framework encodes key-door precedence logic in a layered augmented graph of convex sets for simultaneous optimal sequence selection and continuous trajectory computation with STL specs.
Augmented Graphs of Convex Sets and the Traveling Salesman Problem
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We present a trajectory optimization algorithm for the traveling salesman problem (TSP) in graphs of convex sets (GCS). Our framework uses an augmented graph of convex sets to encode the TSP specification and solve it exactly as a shortest path problem in GCS. We establish a precise relationship between the landmark Bellman-Held-Karp algorithm and the augmented graph of convex sets with a TSP specification. Additionally, we present a branch and bound heuristic that uses minimum 1-trees to obtain certifiably optimal or near optimal solutions and scales to problems far larger than the exact framework can handle. To assess and certify performance, we explore several alternative lower bounds.
fields
eess.SY 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
A Framework for Motion Planning with Temporal Logic Precedence Specifications via Augmented Graphs of Convex Sets
Framework encodes key-door precedence logic in a layered augmented graph of convex sets for simultaneous optimal sequence selection and continuous trajectory computation with STL specs.