IEEE Transactions on Robotics

C$^{*}$: A New Bounding Approach for the Moving-Target Traveling Salesman Problem

作者：Allen George Philip, Zhongqiang Ren, Sivakumar Rathinam, Howie Choset · 机构：Texas A&M University, College Station, TX, USA; Shanghai Jiao Tong University, Shanghai, China; Carnegie Mellon University, Pittsburgh, PA, USA

会议/期刊：IEEE Transactions on Robotics · 发布日期：2025 · 页码：4663-4678

运动规划状态估计

精读笔记

Problem Setting

论文处理的是 MT-TSP with time windows 的 certifiable planning 问题：给定多个目标的已知连续轨迹，agent 需要在时间窗内逐一拦截并回 depot，目标是最小总完成时间。这里的核心难点不是 TSP 的排列本身，而是排列与拦截时间的双向耦合：访问顺序决定每个目标被访问时的位置，而访问时间又受前序运动可达性约束。

传统离散采样路线只能把连续轨迹上的有限点变成 GTSP，因此通常给的是可行解/上界；它不能证明没有更好的中间时间选择。SOCP 路线在直线轨迹上很强，但依赖目标位置是时间的仿射函数，一旦轨迹是 piecewise-linear、多时间窗或 Dubins curve，就很难保持同样干净的 conic formulation。关键矛盾是：要 general trajectory，就需要摆脱强解析模型；要 optimality guarantee，又不能只做 sampling heuristic。

Motivation

这篇的动机不是“求更快的 heuristic”，而是补 MT-TSP 里 lower bound 这一块的空缺。对于一般轨迹，文献里缺少能给紧下界的方法；没有下界，所有可行解质量都无法判断。作者看到的结构性机会是：MT-TSP 的全局难度很大程度来自访问目标时的连续性约束，即 agent 到达某个移动目标的时刻必须同时作为下一段 travel 的出发时刻。

如果把每个时间窗切成小段，并允许在同一小段内到达和离开不是同一时刻，就得到一个天然松弛。这个松弛足够强，因为它保留了时间窗、目标轨迹、可达性和访问顺序；也足够弱，因为它打破了最难的连续衔接约束。缺口就在这里：已有方法要么完全离散成可行点，要么直接求原连续问题；C* 选择中间路线，构造一个可收敛的下界序列。

Core Idea

C* 的核心思想是把“访问一个移动目标”从 point event 放松成 interval event。每个目标的时间窗被分成若干 trajectory intervals；GTSP 只需要为每个目标选一个 interval，而不是选精确访问时刻。边权表示从一个 interval 到另一个 interval 的最短可行 travel 的下界。于是，原问题中的连续时间优化被局部化到边权计算，全局访问顺序被离散化为 GTSP。

本质区别在于它不是对连续时间做 sampling upper approximation，而是做 continuity relaxation lower approximation。sampling 点越多通常只让可行解更好；C* 的 interval 越细则让松弛逐渐消失，下界向原问题收敛。这是建模方式上的改变：从“选择具体拦截点”改成“选择可访问时段，并允许局部不连续”，引入的 inductive bias 是时间连续性只在 interval 尺度上近似保持。

Method

方法里真正重要的不是四个变体本身，而是边权必须是 SFT 的 lower bound。只要每条边低估从 interval p 到 interval q 的真实最短可行 travel，那么 GTSP 最优值必然低估 MT-TSP 最优值。这一设计把 correctness 从全局优化转移到局部边权的 admissibility。

C*-Lite 解决的是最低成本地构造 admissible bound，只利用时间窗下界，因此很弱但快。C*-Geometric 忽略时间运动细节，只用两个轨迹集合之间最短欧氏距离除以最大速度，增加了几何信息，通常比 Lite 明显强。C*-Sampling 用 EFAT 的单调性在出发 interval 内采样构造更接近 SFT 的下界，本质是在用 test-time compute 换 tightness。C*-Linear 对 piecewise-linear 轨迹精确求 SFT，依赖 EFAT/LFDT 的单调互逆关系，把候选段对从二次组合降到线性数量；这是方法中最实质的算法贡献。

GTSP 求解器承担了全局组合部分。这里的核心变化是，原 MT-TSP 的连续全局约束不再进入一个庞大的 mixed-integer nonlinear model，而被拆成“局部可达下界 + 离散簇选择”。

Key Insight / Why It Works

最关键的 insight 是：放松访问处的连续性会给下界，而不是破坏下界。任意原 MT-TSP 可行解都对应 GTSP 中每个目标选一个包含其真实访问时刻的 interval；由于边权低估真实 travel time，GTSP 的总成本一定不超过原解成本。因此 C* 的 correctness 非常干净，几乎不依赖具体边权算法，只依赖 admissibility。

有效性主要来自 better relaxation / better inductive bias，而不是 scaling 本身。它没有试图学习或猜测访问时间，而是识别出原问题中最难但可控的一类约束——同一目标处的到达/离开连续性——并将其参数化为 partition size。这个松弛的好处是 gap 可解释：每个目标最多引入一次 interval 内 discontinuity，目标越多、interval 越大，gap 越大；interval 越细，gap 越小。

C*-Linear 的贡献更具体：EFAT 单调性和 LFDT 互逆性说明从一个轨迹 interval 到另一个 interval 的最优 travel 不需要枚举所有 segment pairs，而可以通过对应的 breakpoints 对齐，把 piecewise-linear SFT 变成线性数量的子问题。这部分不是普通 engineering，而是利用了移动拦截几何的结构。

相对地，C*-Lite/Geometric/Sampling 的新意较有限。Lite 是 trivial admissible heuristic；Geometric 是经典几何下界；Sampling 是用更多局部计算逼近 SFT。它们的价值在于形成 tightness/runtime tradeoff，而不是概念创新。整体性能提升有相当部分来自把问题规整成 GTSP 后调用成熟 branch-and-cut/CPLEX；这属于合理的 optimization engineering，但不应被解读为大规模 MT-TSP 已被解决。

Relation To Prior Work

最接近的路线有两类：一类是直线轨迹 MT-TSP 的 mixed-integer SOCP 精确建模，另一类是时间采样后转 GTSP/ATSP 的启发式求解。C* 和 SOCP 的本质差异是放弃直接精确建模原连续问题，转而构造可收敛下界；因此它对 trajectory class 更宽，但不能直接给 optimum。和 sampling GTSP 的差异更关键：sampling 选具体时刻，得到的是可行拦截点和上界；C* 选时间区间并放松连续性，得到的是下界。

从技术谱系看，C* 属于 relaxation hierarchy + admissible heuristic bounds + combinatorial reformulation。看似新的 GTSP 图构造其实和 discretization-based planning 很接近，但“interval node + discontinuity relaxation + SFT lower-bound edge”这个组合是实质创新。它把连续轨迹规划问题转成一个有单调收敛性质的离散下界问题，这是与 prior 的核心差别。

Dataset / Evaluation

评估覆盖了三类随机实例：直线轨迹、piecewise-linear 轨迹、Dubins 曲线；目标数最多 15；每个目标带有限时间窗。直线轨迹上与 SOCP 对比是合理 sanity check，因为那里有强 baseline；一般轨迹上没有可用 exact baseline，因此只能比较可行解与下界 gap。

实验基本支持“C* 能给有效下界，并且在 15 targets 直线场景比 SOCP 更快”这个 claim。但它没有充分支持“大规模可扩展”或“真实机器人部署”层面的 claim：实例规模仍然小，轨迹和时间窗是合成生成，agent 动力学极简，且没有在线不确定性。文中显示真正的 runtime bottleneck 是 GTSP 求解，随着 discretization 和 target number 增加会迅速变重。因此 evaluation 更像验证了建模路线的可行性，而不是验证了产业级 planning scalability。

Limitation

第一，方法把连续优化难度转移到了 GTSP 规模上。partition 越细，下界越好，但节点数和边数膨胀，GTSP 求解成为主瓶颈。这不是小实现问题，而是方法的内在 tradeoff。

第二，下界 gap 会随目标数累积。每访问一个目标就允许一次 interval 内不连续，因此即使单个 interval 很小，多目标情况下总松弛误差仍可能显著。文中实验中目标数增加 gap 变大，正是这个机制的表现。

第三，成立前提偏强：轨迹已知、目标速度恒定、agent 只有最大速度约束、且 v_max 大于所有目标速度。真实机器人中的加速度、转向、避障、感知误差、通信延迟都会破坏 SFT 的简单形式。Dubins 只用于 target trajectory，不是 agent dynamics。

第四，泛化性主要来自几何/优化模型本身，不是 learned generalization；所谓 general trajectory 也依赖能计算或下界化 interval-to-interval travel cost。若轨迹更复杂、可达性非欧氏、环境有障碍，SFT 下界设计会重新成为核心难题。

第五，部分 runtime 结论依赖具体 GTSP solver 和 CPLEX 表现。SOCP 在 15 targets 变慢并不必然说明 C* 在更大规模更强；也可能只是不同 formulation/solver 在该规模段的交叉点。文中未充分说明不同 solver、cut strategy、memory limit 对结论的敏感性。

Takeaway

  • 1. 这篇最值得迁移的思想是：对连续规划问题，不一定只能采样成上界；也可以通过“局部连续性松弛”构造可收敛下界 hierarchy。
  • 2. 对 moving-target planning，访问处的连续性是一个高价值松弛点。
  • 它既足够局部，便于控制误差；又足够关键，能解耦访问顺序和拦截时间。
  • 3. 未来真正值得做的是 adaptive C*：不是均匀细分所有时间窗，而是在 bound gap 贡献大的 interval 上分裂，并把 lower-bound GTSP、upper-bound feasible repair、branch-and-cut 结合起来。

一句话总结

C* 是一类面向一般轨迹 MT-TSP 的 continuity-relaxation lower-bound framework，真正贡献在于把连续拦截时间耦合转化为 interval-level GTSP 下界，而不是提供一个通用大规模精确求解器。