跳转至

文章背景与核心概要

本文针对凸集图（Graphs of Convex Sets, GCS）上的斯坦纳旅行商问题（Steiner-TSP）进行了形式化定义。该问题旨在寻找一条通过一组必需凸区域的最小成本闭合轨迹，同时适应可选的过渡顶点和重复访问需求。为了系统性地遍历无限的解空间，作者在带根的行走前缀上引入了一个统一的分支定界（branch-and-bound）搜索框架。

该方法的核心亮点包括：通过加法下界图成本评估已承诺的前缀，并利用割集分离的连通流松弛来界定访问所有剩余目标并返回根节点所需的残余成本；在统一正成本假设下，最佳优先遍历在任何可行实例上经有限次扩展后即可终止，而深度优先遍历在建立初始可行解后也能保证有限时间内的终止；同时支持\(\epsilon\)-最优性保证。在机器人应用方面，该框架被成功应用于复杂的移动操作机检测任务中，能够同时进行联合传感模式、访问顺序以及连续轨迹的选择，并处理通过有限迹线性时序逻辑（\(\text{LTL}_f\)）表达的动作先后顺序约束。在实验性能方面，两种遍历策略均能在30秒内成功识别出所有基准测试实例的可行解，平均认证最优性间隙分别为28.1%和29.7%，而现有基准方法仅能成功解决约一半的基准实例。

Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets

Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets

Authors: Jingtao Tang, Hang Ma
Primary Subject: Artificial Intelligence (cs.AI)
Secondary Subject: Robotics (cs.RO)
arXiv ID: arXiv:2608.21319 [cs.AI]
Submitted on: August 21, 2026

Authors: Jingtao Tang, Hang Ma
Primary Subject: Artificial Intelligence (cs.AI)
Secondary Subject: Robotics (cs.RO)
arXiv ID: arXiv:2608.21319 [cs.AI]
Submitted on: August 21, 2026

Abstract Summary

Abstract Summary

本文对凸集图（GCS）上的斯坦纳旅行商问题（Steiner-TSP）进行了形式化定义，该问题旨在寻找一条通过一组必需凸区域的最小成本闭合轨迹，同时适应可选的过渡顶点和重复访问需求。

This paper formalizes the Steiner Traveling Salesman Problem (Steiner-TSP) on Graphs of Convex Sets (GCS), which addresses the challenge of finding a minimum-cost closed trajectory passing through a set of required convex regions while accommodating optional transit vertices and revisits.

为了系统性地遍历无限的解空间，作者在带根的行走前缀上引入了一个统一的分支定界搜索框架。该方法的主要亮点包括： * 定界机制： 加法下界图成本用于评估已承诺的前缀，而割集分离的连通流松弛则界定了访问所有剩余目标并返回根节点所需的残余成本。 * 终止保证： 在统一正成本假设下，最佳优先遍历在任何可行实例上经有限次扩展后即可终止（即使没有初始可行解），而深度优先遍历一旦确立初始可行解即可保证有限时间内的终止。 * \(\epsilon\)-最优性： 全局下界确保任意策略的最 incumbent 成本保持在全局最优解的用户指定因子 \(\epsilon \ge 1\) 之内。 * 机器人应用： 该框架在复杂的移动操作机检测任务中得到了验证，能够执行联合传感模式、访问顺序以及连续轨迹的选择，并处理通过有限迹线性时序逻辑（\(\text{LTL}_f\)）表达的动作先后顺序。

To systematically navigate the infinite solution space, the authors introduce a unified branch-and-bound search framework over rooted walk prefixes. Key highlights of the methodology include: * Bounding Mechanisms: Additive lower-bound-graph costs evaluate committed prefixes, while a cut-separated connected-flow relaxation bounds the residual costs required to visit all remaining targets and return to the root. * Termination Guarantees: Under a uniform positive-cost assumption, best-first traversal terminates after a finite number of expansions on any feasible instance (even without an initial incumbent), whereas depth-first traversal guarantees finite-time termination once an initial incumbent is established. * \(\epsilon\)-Optimality: A global lower bound ensures that either strategy's incumbent cost remains within a user-specified factor \(\epsilon \ge 1\) of the global optimum. * Robotics Application: The framework is demonstrated on complex mobile-manipulator inspection tasks, executing joint sensing-mode, visitation-order, and continuous-trajectory selection, alongside action precedences expressed in Linear Temporal Logic over finite traces (\(\text{LTL}_f\)).

Empirical Performance

Empirical Performance

两种遍历策略均在30秒内成功识别出所有基准测试实例的可行解，平均认证最优性间隙分别达到 28.1% 和 29.7%。相比之下，现有的基准方法仅能在约一半的基准实例上成功求解。

Both traversal strategies successfully identified feasible solutions across all benchmark instances within 30 seconds, achieving mean certified optimality gaps of 28.1% and 29.7% respectively. In contrast, existing baseline methods succeeded on only about half of the benchmark instances.

Key Metadata & Resources

Key Metadata & Resources