# GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets

arXiv: https://arxiv.org/abs/2511.06471 · HTML: https://mlsanity.com/paper/2511.06471/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 37 references that are in the map.
- First posted on arXiv 9 Nov 2025.

## Builds on (most cited first, 17 of 17)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [Motion Planning around Obstacles with Convex Optimization](https://mlsanity.com/paper/2205.04422/) (2022)
- [Shortest Paths in Graphs of Convex Sets](https://mlsanity.com/paper/2101.11565/) (2021)
- [Certified Polyhedral Decompositions of Collision-Free Configuration Space](https://mlsanity.com/paper/2302.12219/) (2023)
- [Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets](https://mlsanity.com/paper/2305.06341/) (2023)
- [GCS*: Forward Heuristic Search on Implicit Graphs of Convex Sets](https://mlsanity.com/paper/2407.08848/) (2024)
- [Fast Path Planning Through Large Collections of Safe Boxes](https://mlsanity.com/paper/2305.01072/) (2023)
- [Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding](https://mlsanity.com/paper/2208.01222/) (2022)
- [Approximating Robot Configuration Spaces with few Convex Sets using Clique Covers of Visibility Graphs](https://mlsanity.com/paper/2310.02875/) (2023)
- [Implicit Graph Search for Planning on Graphs of Convex Sets](https://mlsanity.com/paper/2410.08909/) (2024)
- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets](https://mlsanity.com/paper/2403.04917/) (2024)
- [A Complete and Bounded-Suboptimal Algorithm for a Moving Target Traveling Salesman Problem with Obstacles in 3D](https://mlsanity.com/paper/2504.14680/) (2025)
- [Multi-Robot Connected Fermat Spiral Coverage](https://mlsanity.com/paper/2403.13311/) (2024)
- [A^* for Graphs of Convex Sets](https://mlsanity.com/paper/2407.17413/) (2024)
- [Toward Asymptotically-Optimal Inspection Planning via Efficient Near-Optimal Graph Search](https://mlsanity.com/paper/1907.00506/) (2019)

## Built on by (most cited first, 2 of 2)

- [Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets](https://mlsanity.com/paper/2607.00444/) (2026)
- [Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2608.21319/) (2026)

## Abstract (arXiv)

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.