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

📄 arXiv: 2511.06471v2 📥 PDF

作者: Jingtao Tang, Hang Ma

分类: cs.AI, cs.RO

发布日期: 2025-11-09 (更新: 2025-11-13)

备注: Accepted to AAAI-2026

💡 一句话要点

GHOST：求解凸集图上的旅行商问题，用于轨迹规划

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 旅行商问题 轨迹规划 凸集图 组合优化 凸优化 机器人 路径规划

📋 核心要点

  1. 传统TSP方法无法直接应用于边成本动态变化的凸集图上的轨迹规划问题。
  2. GHOST通过分层框架，结合组合路径搜索和凸轨迹优化，实现最优解。
  3. 实验表明，GHOST比现有方法快几个数量级，并能处理复杂约束。

📝 摘要（中文）

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

🔬 方法详解

问题定义：论文旨在解决凸集图上的旅行商问题（GCS-TSP）。传统TSP算法无法处理GCS-TSP中边成本随轨迹变化的情况，因为边成本不再是固定的，而是依赖于在凸区域内选择的具体轨迹。这使得传统的组合优化方法难以直接应用，需要同时考虑路径规划和轨迹优化。

核心思路：GHOST的核心思路是将问题分解为高层组合搜索和低层凸优化。高层搜索负责寻找最优的访问凸区域的顺序（即TSP路径），低层优化则负责在给定的访问顺序下，优化每个凸区域内的轨迹，从而最小化总成本。通过这种分层结构，可以将复杂的GCS-TSP问题分解为更容易处理的子问题。

技术框架：GHOST的整体框架包含以下几个主要模块：1) 图构建：基于凸集图构建完全图，每个凸集对应图中的一个节点。2) 抽象路径展开：用于计算给定TSP路径的可行下界，指导搜索。3) 最佳优先搜索：在高层搜索TSP路径，并使用抽象路径展开计算的下界进行剪枝。4) 凸轨迹优化：在低层优化每个凸区域内的轨迹，得到实际的路径成本。

关键创新：GHOST的关键创新在于其抽象路径展开算法，该算法能够有效地计算TSP路径的可行下界。这个下界考虑了凸区域内的轨迹优化，因此比简单的欧几里得距离更准确。通过使用这个下界，GHOST能够更有效地剪枝搜索空间，避免不必要的凸优化调用，从而提高搜索效率。此外，GHOST还提供了一种有界次优变体，可以在时间紧迫的情况下快速找到近似最优解。

关键设计：GHOST的关键设计包括：1) 使用最佳优先搜索算法，保证找到最优解。2) 抽象路径展开算法的设计，需要平衡计算复杂度和下界精度。3) 凸轨迹优化问题的建模，需要考虑轨迹的平滑性和动力学约束。4) 有界次优变体的设计，需要在求解质量和计算时间之间进行权衡。

📊 实验亮点

实验结果表明，GHOST在解决GCS-TSP问题上具有显著优势。对于简单情况，GHOST比统一的混合整数凸规划基线快几个数量级。此外，GHOST能够处理涉及高阶连续性约束和不完整GCS的复杂轨迹规划问题，而这些问题是现有方法难以解决的。这表明GHOST在实际应用中具有很高的价值。

🎯 应用场景

GHOST可应用于机器人轨迹规划、自动驾驶、无人机路径规划等领域。在这些场景中，环境可以被分解为一系列凸区域，GHOST可以帮助找到最优或近似最优的访问顺序和轨迹，从而实现高效、安全的路径规划。该方法尤其适用于需要考虑高阶连续性约束和复杂环境的场景。

📄 摘要（原文）

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.