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的复杂轨迹规划问题。