← 返回 PaperDaily 视觉与图像

巡检顺序、传感、轨迹一次选完，新框架30秒搞定

当离散路径选择和连续轨迹优化纠缠在一起，传统方法常在无限解空间里迷路。这篇最新论文把Steiner旅行商问题搬进凸集图，用统一分支定界把访问顺序、传感模式和连续轨迹一次打包，180个基准实例30秒内全部找到可行解，还自带ε-最优性证书。搞机器人自主规划的同学值得读一读！

龙哥读论文发布于 2026-08-25 00:20:18 阅读 4 查看原文

#机器人 #人工智能 #AI应用

原论文信息如下：

论文标题:
Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets

发表日期:
2026年08月

发表单位:
论文中未标注作者单位

原文链接:
https://arxiv.org/pdf/2608.21319v1.pdf

项目链接:
https://sites.google.com/view/steiner-tsp-gcs

先来做个小思想实验：假设龙哥是一个轮式巡检机器人，被丢进一个堆满货架、匣子、障碍物的仓库里，老板下达的任务是——去检查货架上的 8 个重点区域，然后回到充电桩。看似简单，但问题来了：先查哪个后查哪个？从 A 区域到 B 区域，是穿过左边空隙还是右边通道？到了某个区域后，是直接走去下一个，还是先绕个圈调整姿态再走？这些选择叠在一起，组合出无数条可能的巡线。更可怕的是，如果允许“绕圈”，那理论上机器人可以在任意两个区域之间无限绕圈，路线数量直接爆炸成无限多。传统办法要么老老实实把所有组合拆开暴力搜，要么用启发式碰运气。而这篇论文给出的答案是：把“无限条路”的问题装进一个统一的搜索框架里，30 秒内全部解完，还附带一个“最优性保证书”。

这篇论文由 Jingtao Tang 和 Hang Ma 共同完成，核心是把经典图论中的 Steiner 旅行商问题（Steiner Traveling Salesman Problem，即只要求访问指定的目标子集、其他节点仅作中转）搬到“凸集图”上，然后设计了一套统一的分支定界搜索算法，同时解决访问顺序、是否绕路、以及连续轨迹的最优化问题。

问题背景与挑战：从GCS到Steiner-TSP

很多读者可能不熟悉“凸集图”（Graphs of Convex Sets，简称 GCS）这个概念。简而言之，它是一张特殊的地图：每一个节点都挂着一个凸的几何区域（比如机器人关节空间里的一个无碰撞区域），每条边则代表两个区域之间允许的连续过渡。机器人在每个区域里可以取无数个具体位姿，而“从一个区域动到另一个区域”不再是简单的线段连接，而是要找一条满足物理约束的连续轨迹。这种图把离散的路线选择（走哪个节点）和连续的轨迹优化（在区域内怎么走）强行绑在了一起。

经典的旅行商问题（Traveling Salesman Problem，TSP）要求访问图上所有节点并回到起点。而本篇论文研究的是它的“指定子集版”变体——Steiner-TSP：只有一部分节点是必须访问的“目标”，其余节点只是可用可不用的“中转站”。这与现实中机器人巡检场景高度契合：你关心的是货架上的几个检查点，而不是整个空间里的每个角落。

凸集图上的Steiner旅行商问题，寻找从根节点r（红色）出发、访问所有目标凸集（黄色）并返回的最小代价闭合轨迹。黑色虚线为有向GCS边（实际走过的边为实线）。橙色解(a)可以不重复访问任何顶点；蓝色解(b)则是利用了顶点重复访问、达到了全局最优，圆圈数字标识了底层的GCS边。

这个模型允许在访问过程中重复经过某个节点。可别小看这个“允许”，图1给出了一个很微妙的例子：橙色解不绕路也能走通，但蓝色解专门绕了个圈、代价反而更小。这说明“不重复访问”这种在古典组合优化里常用的约束，在连续轨迹规划里不仅是不必要的，甚至可能直接丢掉最优解。而一旦允许重复访问，有限图也能产生无限多条走走停停的回路——这就是本论文要啃的第一块硬骨头：如何在无限解空间里做搜索。

严格地说，论文要优化的目标函数是这样的：一条由k个顶点组成的轨迹，其总代价是每一步的顶点代价与边代价之和。

公式1：轨迹总代价定义。其中x_i 为第i个顶点对应的连续变量（表示机器人位姿），c_v 为该顶点代价（如表征停留耗时），c_(v_i,v_i+1) 为相邻两个顶点之间边的转移代价。

整个问题的约束包括：首尾都在根节点r、轨迹形成闭环、必须覆盖全部目标集合V_t、并且每个连续步都要满足图上的边关系。这样一套“离散顺序+连续轨迹”联合优化的问题，即便固定一条路径，剩余的子问题也是凸优化；但路径本身就组合爆炸，整体是NP难的。更麻烦的是，候选解不再能预先限定为无环walk（一串允许重复经过顶点的顶点序列）。因为无环候选集可能根本不存在可行解，即使在存在的情况下，其最优解也可能比带绕圈的差（图1就展示了这种情形）。

统一分支定界搜索框架：核心机制与理论保证

面对无限解空间，最朴素的想法是“把所有可能性枚举出来”——但这显然不可行。论文采用的办法是分支定界（Branch-and-Bound，B&B）：把问题一步步拆成互相不重叠的子问题（分支），同时每步计算一个“下界”来判断这个子问题还有没有潜力（定界），没有潜力的直接剪枝，有潜力的优先处理。

具体到这个场景里，搜索树上的每一个节点，对应一条从根节点r出发的前缀walk（即顶点序列）。一个节点n既存了走到当前前缀的代价下界ĝ(n)，也存了一个启发式h(n)，表示从当前状态继续访问剩余目标并返回根节点所需代价的下界。两者相加就得到了整个节点的下界值：

公式2：节点下界f(n)由已走部分代价下界ĝ(n)与未走部分代价下界h(n)组成。只要h是“可采纳的”（admissible，即真实剩余代价的一个下界），那么f(n)就能安全地为所有经过该前缀的完整解提供下界。

整个搜索流程非常清爽：先从根节点出发，把所有一步可达到的邻居节点作为初始搜索前缀；然后用一个开放节点队列（Frontier）维护所有“还有希望”的节点。每次循环，从队列里取出一个节点：如果它已经是一个完整解（访问过所有目标、且回到了根节点），就把它扔进凸优化求解器里算出一条真实轨迹，若能刷新当前最优解就更新。无论是不是完整解，都要继续展开它的所有后继节点；只有当下界值小于当前最优解代价的节点才有资格继续留在队列里。

队列的取出顺序决定了搜索策略。论文比较了两种经典策略：一种是最佳优先（Best-First，BF），即用优先队列按f(n)从小到大取节点，相当于“永远先处理最有希望的支路”；另一种是深度优先（Depth-First，DF），即用后进先出栈，一条路走到黑再回头。两种策略共用一套节点生成与剪枝逻辑，所以是“统一”的搜索框架。

光有搜索策略还不够，必须回答一个更深层的问题：这棵搜索树是无限的，凭什么敢说能停下来？论文给出了漂亮的理论证明，其核心是一个“均匀正代价”假设：每个顶点的代价都至少是一个正数η（实验中取0.1秒）。这意味着每向前走一步，已走代价下界ĝ至少增加η。而所有“尚有希望”的节点必须满足f(n)小于当前已知最优解代价，这直接限制住了搜索深度——深度不可能超过最优解代价除以η。有限分支+有限深度，就保证了一定能在有限步内终止。更妙的是，论文证明了在全局停止条件“当前最优解c̄ ≤ ε × 全局下界”满足时，得到的一定是ε-近似最优解，给出了严格的最优性证书。

下界图松弛与连通流启发式：高效搜索的关键

分支定界的效率高低，完全取决于下界算得紧不紧、快不快。如果每生成一个搜索节点都要去解一次完整的凸轨迹优化，那计算开销将会大到不可接受。论文的解决方案是把连续轨迹的信息“预压缩”进一个离散结构——下界图（Lower-Bound Graph，简称LBG）。

下界图的构造思想很巧妙：对GCS中任意连续的三元组顶点(u,v,w)，即一条长度为2的walk，单独解一个小型凸优化问题，算出“经过中间顶点v并转移到w”的最小局部代价ℓ_t：

公式4：三元组局部凸优化。该式在约束(x_u,x_v)∈X_(u,v)且(x_v,x_w)∈X_(v,w)的前提下，最小化中间顶点v的顶点代价与出边(v,w)的边代价之和。

这些ℓ_t在搜索开始前一次性预计算完，之后查找一个三元组的代价就是O(1)的查表操作。因为每个三元组的优化是独立的、相邻三元组之间不需要共享连续变量，所以这种松弛天然低估了全局一致轨迹的真实代价——它舍弃了跨区域连续性的耦合约束，因此给出的代价必然是一个下界。论文中称这种性质为“下界图的松弛代价不超过任何可行轨迹的真实代价”。

基于预计算好的ℓ_t，一个搜索前缀的已走代价下界ĝ可以简单地用前缀中连续三元组代价之和来表示。而剩余代价的启发式h就复杂一些了：它需要回答“从当前所在位置出发，把所有没访问过的目标都逛一遍，再回到根节点，至少要花多少代价”。论文把这个问题建模成一个在LBG上的割分离连通流线性规划（cut-separated connected-flow LP），下面给出其形式化描述：

公式8（a）（c）：连通流LP的目标函数与割约束。目标是在LBG上找一条从当前源边到汇节点的最小代价单位流；割约束则要求对每一个“把源边与某个未访问目标的所有入边隔开”的割S，流经该割的流量至少为1，从而确保流真的“逛到了”每个目标。

这个LP的约束数量是指数级的，直接求解不可行。论文采用了经典的行生成（row generation）技巧：先解一个没有割约束的最小费用流，然后用最大流最小割（max-flow/min-cut）算法检查当前解是否违反了某些割约束，把违反的割重新加入约束后重新求解，直到没有新割能加入为止。因为每次迭代解的都是线性规划（LP）而不是混合整数凸规划（MICP），即使反复迭代多轮，计算开销也远小于完整解一次轨迹优化。

这个h(n)和短视的贪心不同，它在真正意义上考虑了“把剩余所有目标全部访问一遍”的全局连通性，因此它是可采纳的——即它永远不超过真实的剩余代价。同时，因为只用了离散的LBG流做松弛，没有做任何轨迹层面的完整性约束，所以它的下界往往比真实代价低不少——这是换取速度的代价，也是分支定界里“松弛的紧度”与“求解的速度”之间经典的此消彼长。

实验结果与案例分析：多领域验证与性能对比

论文的验证并不是只在玩具例子上跑一跑，而是横跨了三个形态差异极大的任务域，每个任务域构造了60个实例，合计180个基准实例。三个任务域分别是：rand（2D空间中的随机多边形凸集网络）、maze（3D空间中的递归分割迷宫）、iiwa（7自由度机械臂关节空间）。最有意思的是maze域：它将迷宫的空闲体素（voxel）经过最小基数分解成一组不相交的轴对齐长方体，凡共享一个面即视为相邻，这样形成的GCS天然就没有“穿墙”的嫌疑。

图2：Steiner-TSP on GCS在三个域中求得的轨迹（蓝色）：rand域是2D GCS，背景是灰色多边形；maze域是3D GCS，将黑色墙壁以外的自由体素做精确分解；iiwa域是7维关节空间GCS，区域由IRIS-NP [25]生成，并用无碰撞的代表性组态作为种子。

表1：Steiner-TSP on GCS实例复杂度。|V|、|E|、平均度（degree）和|V_t|列分别报告最小值/平均值/最大值；d列为构型空间维度；LBG列报告LBG预计算的平均耗时（秒）。可以看到三个域的实例规模从几十个节点到数百个节点不等，维度跨度从2维到7维，覆盖面相当广。

实验环境是Apple M4处理器配16GB内存，算法用Python实现，GCS相关的轨迹优化走Drake库+Gurobi求解器。每个实例只给30秒预算。主结果表格在下图呈现：

表2：与两类近期基线的对比实验结果。两种遍历策略（BF与DF）在所有180个实例上均能在30秒预算内找到可行解，平均认证最优性差距分别为28.1%和29.7%；而两个近期基线（MICP [1]与GHOST [13]）仅在大约一半的实例上找到了可行解。

这个结果至少说明两件事：一是在论文设定的三类任务、180个实例、30秒的预算内，统一搜索框架的成功率做到了100%，远超当前两大主流的MICP统一优化与GHOST两级搜索方案；二是BF与DF两种遍历策略的表现十分接近，说明搜索框架的核心性能受遍历策略影响不大，真正起作用的是LBG松弛和连通流启发式带来的裁剪力。但也要注意，28%-30%的认证最优性差距并不算小——它意味着全局下界与当前解之间仍有相当的距离，30秒的硬时间预算也挡住了不少潜在的进一步优化。

图3：移动机械臂检测任务对比。(a) 基于PRM的广义TSP基线；(b) 本文方法（BF）；(c) 本文方法（BF）加上用线性时序逻辑（LTL_f [27]）表达的动作前置约束。半透明的机械臂位姿颜色编码了活动进度（蓝色=早期，橙色=晚期），见右侧色条。红色圆圈字母A–H是任务点，黑色圆圈数字1–8表示执行顺序与仿真时间戳。

除了三个标准测试域，论文还做了一个更具实际意义的案例研究：移动机械臂检测。任务不是简单“走一圈”，而是要同时决定每个目标点用哪种传感模式去观察（比如不同角度或不同传感器）、以什么样的顺序执行、在哪里绕路、以及每条机械臂轨迹具体怎么走。更有意思的是，论文允许用户用线性时序逻辑（Linear Temporal Logic over Finite Traces，缩写LTL_f）来表达“动作A必须在动作B之前完成”这类前置约束。从图3可以看到，加入LTL_f约束后，执行顺序从自由选择变成了严格排序的1→2→3…→8，而算法仍然能够在一个统一的框架内找到可行解。

总结与展望：方法优势、局限与未来方向

这篇论文的主要贡献可以梳理成四条线：第一，首次形式化定义了凸集图上的Steiner旅行商问题，严格描述了允许重复访问的无限解空间；第二，设计了一个“统一分支定界搜索框架”，把最佳优先和深度优先统一进同一个算法骨架，并证明了有限终止与ε-最优性证书；第三，提出了割分离连通流LP这一可采纳启发式，把指数级约束的连通流下界高效地嵌入搜索过程；第四，在180个基准实例上展示了两类遍历策略的100%成功率，并在移动机械臂检测任务中验证了传感模式、访问顺序、LTL_f动作前置约束与连续轨迹的联合优化能力。

不过也得冷静看待：平均28%的认证最优性差距意味着下界松弛还有不小的提升空间。LBG三元组松弛虽然快，但它完全忽略了更长范围的连续耦合；连通流LP虽然考虑了全局目标覆盖，但流量模型毕竟是离散的，无法模拟轨迹层面的几何约束。未来有几个很自然的方向：一是设计更高阶的松弛（比如4元组甚至更长的子路径），用更多预计算换取更紧的下界；二是把初始可行解构造得更好，一个优秀的初始解可以直接砍掉大量搜索分支；三是研究自适应的ε调度策略，让算法在有限时间内尽可能逼近全局最优而不是等时间耗尽才被迫停止。

带病句式的总结：这套统一分支定界框架的价值，不在于它把某个特定问题的解法刷到极致，而在于它示范了一种“离散搜索+连续松弛”的组合范式——把连续的几何信息压缩成离散的下界，再用离散搜索反哺连续优化。这种思路，对机器人任务规划、多目标巡检、物流调度等无数场景都可能产生借鉴意义。

龙迷三问

下面是龙哥对于大家可能的一些问题的解答：

这篇论文到底在解决什么问题？首次形式化定义凸集图上的Steiner旅行商问题。统一分支定界搜索在30秒内于全部180个基准实例上求得可行解，平均最优性差距约28%，并提供ε-最优性证书；移动机械臂检测案例同步验证。

这篇工作最值得看的点是什么？提出的两种遍历策略（BF和DF）在所有180个基准实例上均能在30秒内找到可行解，平均认证最优性差距分别为28.1%和29.7%，而两个近期基线方法仅在约半数实例上成功。

这篇工作的边界或风险在哪里？优点：1）统一的分支定界框架能够处理无限解空间；2）LBG松弛和连通流松弛提供了有效的上下界；3）理论保证完备性和ϵ-最优性；4）在多个领域验证了有效性。缺点：1）在iiwa领域Gap较大（62.4%）；2）深度优先策略在某些情况下可能不如最佳优先；3）对大规模问题计算开销可能较大。

如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~

龙哥点评

论文创新性分数：★★★★☆

提出一种统一的分支定界搜索框架，通过加性下界图（LBG）松弛和割分离连通流松弛，在根行走前缀树上高效搜索Steiner-TSP on GCS的最优解。

实验合理度：★★★★☆

Cost Regret、Gap、Feasible、NPI（Time-Normalized Primal Integral）、Closed Nodes、Evaluated Walks

学术研究价值：★★★★☆

提出一种统一的分支定界搜索框架，通过加性下界图（LBG）松弛和割分离连通流松弛，在根行走前缀树上高效搜索Steiner-TSP on GCS的最优解；更关键的是问题定义是否可复用到同类任务。

稳定性：★★★☆☆

现有材料未提供充分的极端条件、重复运行或扰动测试，稳定性暂按中性评价。

适应性以及泛化能力：★★★☆☆

现有材料未完整展示跨数据集、跨场景或分布外实验，泛化能力仍需进一步验证。

硬件需求及成本：★★★☆☆

在Apple M4处理器上，LBG预计算时间平均为0.07s（rand）、0.14s（maze）、4.57s（iiwa）；搜索在30s预算内完成所有180个实例。

复现难度：★★★☆☆

现有材料未确认完整代码、配置、数据处理脚本和权重是否齐备，复现难度暂按中性评价。

产品化成熟度：★★★☆☆

论文验证以研究实验为主，真实部署中的时延、成本、维护和异常场景仍需补充验证。

可能的问题：1）在iiwa领域Gap较大（62.4%）；2）深度优先策略在某些情况下可能不如最佳优先；3）对大规模问题计算开销可能较大。

主要参考文献

[1] Jingtao Tang, Hang Ma. Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets. arXiv:2608.21319, 2026.

[2] 项目主页（含可视化与视频）：https://sites.google.com/view/steiner-tsp-gcs

[3] 论文中引用的GCS、GHOST等文献详见原文参考文献列表。

*本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！

路径有穷，算法无穷。跟龙哥一起，在无限解空间里找最优解～ 🚀
欢迎加入龙哥读论文粉丝群，扫描下方二维码或者添加龙哥助手微信号加群：kangjinlonghelper。一定要备注：研究方向+地点+学校/公司+昵称（如机器人规划+北京+某厂+龙哥），根据格式备注，可更快被通过且邀请进群。
『龙哥读论文』微信群目前包含：图像处理、大模型及智能体、自动驾驶及机器人、AI医疗及AI金融5个群
wechat_helper