# Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 31 references that are in the map.
- First posted on arXiv 21 Aug 2026.

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

- [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)
- [Towards Tight Convex Relaxations for Contact-Rich Manipulation](https://mlsanity.com/paper/2402.10312/) (2024)
- [Temporal Logic Motion Planning with Convex Optimization via Graphs of Convex Sets](https://mlsanity.com/paper/2301.07773/) (2023)
- [GCS*: Forward Heuristic Search on Implicit Graphs of Convex Sets](https://mlsanity.com/paper/2407.08848/) (2024)
- [Implicit Graph Search for Planning on Graphs of Convex Sets](https://mlsanity.com/paper/2410.08909/) (2024)
- [Growing Convex Collision-Free Regions in Configuration Space using Nonlinear Programming](https://mlsanity.com/paper/2303.14737/) (2023)
- [Superfast Configuration-Space Convex Set Computation on GPUs for Online Motion Planning](https://mlsanity.com/paper/2504.10783/) (2025)
- [Hierarchical Temporal Logic Task and Motion Planning for Multi-Robot Systems](https://mlsanity.com/paper/2504.18899/) (2025)
- [Multi-Query Shortest-Path Problem in Graphs of Convex Sets](https://mlsanity.com/paper/2409.19543/) (2024)
- [Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning](https://mlsanity.com/paper/2503.00583/) (2025)
- [Mixed Discrete and Continuous Planning using Shortest Walks in Graphs of Convex Sets](https://mlsanity.com/paper/2507.10878/) (2025)
- [GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2511.06471/) (2025)
- [Augmented Graphs of Convex Sets and the Traveling Salesman Problem](https://mlsanity.com/paper/2604.06406/) (2026)
- [A Framework for Motion Planning with Temporal Logic Precedence Specifications via Augmented Graphs of Convex Sets](https://mlsanity.com/paper/2606.00842/) (2026)
- [Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets](https://mlsanity.com/paper/2607.00444/) (2026)

## Abstract (arXiv)

We formalize the Steiner Traveling Salesman Problem (Steiner-TSP) on Graphs of Convex Sets (GCS), which seeks a minimum-cost closed trajectory through required convex sets while allowing optional transit vertices and revisits. To explore the resulting infinite solution space, we propose a unified branch-and-bound search over rooted walk prefixes. Additive lower-bound-graph costs bound committed prefixes, while a cut-separated connected-flow relaxation lower-bounds the residual cost of visiting every remaining target and returning to the root. Under a uniform positive-cost assumption, best-first traversal terminates after finitely many expansions on every feasible instance without an initial incumbent, whereas depth-first traversal does so once a finite incumbent is available. For a user-specified factor ε≥1, a global lower bound certifies that either strategy's incumbent cost is at most ε times the global optimum. We further demonstrate joint sensing-mode, visitation-order, and continuous-trajectory selection for a mobile-manipulator inspection task, including action precedences expressed in linear temporal logic over finite traces (LTLf). Both traversal strategies find feasible solutions on all benchmark instances within 30s with mean certified optimality gaps of 28.1% and 29.7%, respectively, whereas two recent baselines succeed on only about half of the instances