GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets
This addresses trajectory planning problems in robotics or autonomous systems where classical TSP methods fail due to variable edge costs, offering a novel solution with proven optimality and efficiency gains.
The paper tackles the GCS-TSP, a variant of the Traveling Salesman Problem where edge costs depend on trajectory selection in convex regions, by introducing GHOST, a hierarchical framework that optimally solves it by combining combinatorial tour search with convex trajectory optimization, achieving orders-of-magnitude speed improvements over baselines in experiments.
We study GCS-TSP, a new variant of the Traveling Salesman Problem (TSP) defined over a Graph of Convex Sets (GCS) -- a powerful representation for trajectory planning that decomposes the configuration space into convex regions connected by a sparse graph. In this setting, edge costs are not fixed but depend on the specific trajectory selected through each convex region, making classical TSP methods inapplicable. We introduce GHOST, a hierarchical framework that optimally solves the GCS-TSP by combining combinatorial tour search with convex trajectory optimization. GHOST systematically explores tours on a complete graph induced by the GCS, using a novel abstract-path-unfolding algorithm to compute admissible lower bounds that guide best-first search at both the high level (over tours) and the low level (over feasible GCS paths realizing the tour). These bounds provide strong pruning power, enabling efficient search while avoiding unnecessary convex optimization calls. We prove that GHOST guarantees optimality and present a bounded-suboptimal variant for time-critical scenarios. Experiments show that GHOST is orders-of-magnitude faster than unified mixed-integer convex programming baselines for simple cases and uniquely handles complex trajectory planning problems involving high-order continuity constraints and an incomplete GCS.