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.

翻译：我们研究GCS-TSP，这是旅行商问题（TSP）的一个新变体，定义在凸集图（GCS）上——一种用于轨迹规划的强有力表示方法，它将配置空间分解为通过稀疏图连接的凸区域。在此设置中，边成本并非固定，而是取决于通过每个凸区域所选的具体轨迹，这使得经典TSP方法无法适用。我们引入GHOST，一种分层框架，通过将组合路径搜索与凸轨迹优化相结合，最优地求解GCS-TSP。GHOST系统地在由GCS导出的完全图上探索路径，使用一种新颖的抽象路径展开算法来计算可接受的下界，这些下界指导高层（在路径上）和低层（在实现路径的可行GCS路径上）的最佳优先搜索。这些边界提供了强大的剪枝能力，实现了高效搜索，同时避免了不必要的凸优化调用。我们证明GHOST保证了最优性，并提出了一个用于时间关键场景的有界次优变体。实验表明，对于简单情况，GHOST比统一的混合整数凸规划基线快几个数量级，并且独特地处理了涉及高阶连续性约束和不完整GCS的复杂轨迹规划问题。