知识卡片：统一分支定界搜索求解凸集图上的 Steiner 旅行商问题

一句话结论：论文提出一种在“凸集图（Graphs of Convex Sets, GCS）”上求解 Steiner 旅行商问题（Steiner-TSP）的统一分支定界搜索方法。该方法在允许可选中间顶点和重复访问的无限连续解空间中，能够有限次扩展找到具有可认证 ε 最优性的可行解，并在移动机械臂巡检任务中实现了感知模式、访问顺序与连续轨迹的联合选择。

英文关键词（据摘要整理，非官方）：Steiner Traveling Salesman Problem; Graphs of Convex Sets; Branch-and-Bound Search; Mobile Manipulator Inspection; LTL_f

事件概述 / 研究问题：研究将 Steiner-TSP 形式化到 Graphs of Convex Sets 上，问题目标是寻找一条最小代价的闭合轨迹，使其穿过所有“必达凸集”，同时允许经过可选的中转顶点并允许重访。由于连续轨迹和组合访问顺序交织，解空间是无限的，因此需要新的搜索与剪枝机制。

方法/产品要点：

• 提出统一的分支定界搜索框架，在“有根游走前缀”（rooted walk prefixes）上探索解空间。
• 用可加的下界图代价约束已承诺前缀；用割分离的连通流松弛（cut-separated connected-flow relaxation）为剩余访问代价给出下界。
• 在代价一致为正的假设下，最佳优先遍历即使没有初始可行解，也能在可行实例上经过有限次扩展后终止；深度优先遍历则在已有有限可行解后有限次终止。
• 用户可指定因子 ε≥1，借助全局下界认证当前解的代价不超过全局最优解的 ε 倍。
• 展示场景包括移动机械臂巡检任务中的联合感知模式选择、访问顺序选择和连续轨迹规划，并支持用 LTL_f（有限迹线性时态逻辑）表达的先后约束。

主要结果 / 产业意义：

• 两种遍历策略均在所有基准实例上于 30 秒内找到可行解；最佳优先和深度优先的平均认证最优性差距分别为 28.1% 和 29.7%。
• 相比之下，两个近期基线方法仅在约一半实例上成功。
• 潜在产业意义：可服务于需要同时决定“看哪里、按什么顺序看、怎么走过去”的移动机械臂巡检、检测与覆盖类任务。

为什么重要：

• 该方法把离散访问顺序与连续轨迹规划统一到一个搜索框架中，并在无限连续解空间内提供有限终止和全局最优性认证。
• 与已有相关卡片没有直接延续关系；本条属于新的算法/机器人规划方向，增量信息在于“Steiner-TSP 与凸集图结合”以及“分支定界搜索在连续空间中的 ε 最优性保证”。

局限与不确定性：

• 摘要未给出基准实例的具体构成、两个基线方法名称、计算环境等细节，待核实。
• 终止性理论依赖“代价一致为正”的假设；实际 ε 最优性认证也需要有可用的全局下界。
• 该方法在大规模问题上的扩展性、与其他 GCS 求解器的对比等信息未在摘要中体现，待核实。

可用于图书/PPT/简报的角度：

• 以“移动机械臂巡检”为例：它需要从多个候选感知位置中决定访问哪些区域、按什么顺序访问，并规划连续路径。
• 可强调的反直觉点：即使可行路径是无限多的连续空间问题，也可以通过分支定界搜索在有限步内找到有最优性保证的解。
• 可向非专业读者解释为“既要排顺序，又要走路线”的组合-连续联合优化问题。

原始材料：

• English Title: Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets
• Authors: Jingtao Tang, Hang Ma
• arXiv ID: 2608.21319v1
• Categories: cs.AI, cs.RO
• Published/Updated: 2026-08-21T17:28:03Z
• Abstract URL: https://arxiv.org/abs/2608.21319v1
• PDF URL: https://arxiv.org/pdf/2608.21319v1