技术摘要：Anytime 全局张量运动规划 (Anytime Global Tensor Motion Planning)

问题定义

本文研究了在复杂高维配置空间（$C \subseteq \mathbb{R}^d$）中的运动规划问题。核心挑战在于寻找自由空间（$C_{free}$）的连通分量，并将起始配置（$q_0$）与目标配置（$q_g$）连接起来。传统的基于采样的规划器通常将全局探索与局部连接尝试耦合在一起，这导致在狭窄通道处效率低下，并且倾向于仅返回单一的可行路径，而非拓扑多样化的备选路径。

作者将 $\delta$-清晰路径 ($\delta$-clear path) 定义为与障碍物保持最小距离 $\delta$ 的路径。同伦类 (Homotopy class) 是指具有固定端点且可以连续变形而不与障碍物相交的一组路径。目标是保证覆盖所有具有有限长度的 $\delta$-清晰同伦类，并可选地收敛到这些类中的最优代价。

方法论

本文通过将全局采样结构与局部连接机制解耦，推广了 全局张量运动规划 (GTMP) [5]。

1. 广义 GTMP 图

该方法构建了一个分层多部图，其中：

• 层 (Layers)： 路径被离散化为 $M+2$ 层（包括起始和目标）。中间层 $V_m$ 包含 $N$ 个采样配置。
• 边 (Edges)： 边仅存在于相邻层之间（从 $V_m$ 到 $V_{m+1}$）。
• 黑盒局部规划器 (LP)： 与使用直线插值的原始 GTMP 不同，广义版本允许使用任何随机局部规划器（例如：线性插值、样条曲线、RRT-Connect、轨迹优化或生成式采样器）来实现边。如果局部规划器在查询椭球体 $E(u, v; \ell)$ 内找到了无碰撞路径，则认为边 $(u, v)$ 已实现。
• 采样策略： 样本通过混合方式抽取：有 $1/2$ 的概率从自由空间上的均匀测度中抽取（以确保理论覆盖性），另外 $1/2$ 的概率从启发式采样器中抽取（可能受成本界限启发）。

2. 图搜索

实现的图是一个有向无环图 (DAG)。最短可行链通过在 $O(MN^2)$ 时间内进行 价值迭代 (Value Iteration)（动态规划）来寻找。

• 类增强搜索 (Class-Augmented Search)： 为了追踪拓扑多样性，状态通过同伦标签 $\kappa$（例如 h-signature）进行增强。价值迭代同时计算每个已实现同伦类的最小代价。

3. 两种 Anytime 迭代策略

该框架支持两种不同的迭代图构建的策略：

• Anytime-GTMP（固定预算，随机重启）：

  • 保持图参数 $(M, N, s)$ 固定。
  • 执行随机重启，生成带有全新样本的新图。
  • 维护一个针对每个发现的同伦类的最低代价路径存档。
  • 目标： 实现对所有 $\delta$-清晰同伦类的 几乎处处覆盖 (Almost-sure coverage)。

• AO-GTMP（启发式扩张，增长预算）：

  • 保持局部规划器预算 $s$ 固定，但单调增加层数 $M$ 和样本数 $N$。
  • 样本从 启发式集合 (Informed set) 中抽取（一个由当前最佳代价界限定义的椭球体），该集合随着代价的改善而缩小。
  • 目标： 实现对最优路径代价的 几乎处处收敛 (Almost-sure convergence)。

核心贡献与理论保证

1. 泛化性与覆盖性

作者证明，单个采样图可以覆盖每一个允许具有有限长度 $\delta$-清晰代表元的端点固定同伦类。具体而言，随着样本数 $N$ 和局部规划器预算 $s$ 的增加（对于固定的层数 $M$），覆盖概率趋于 1。

• 管状论证 (Tube Argument)： 在参考路径周围半径为 $r < \delta$ 的管状区域内的样本链保证了与该参考路径的同伦性。
• 概率界限： 错过某一类的概率随每层样本数 $N$ 的增加呈指数级下降。相反，增加局部规划器预算 $s$ 仅会亚线性地减少所需的层数 $M$。

2. 收敛保证

• Anytime-GTMP： 证明了在给定固定预算和随机重启的情况下，它能几乎处处覆盖每个 $\delta$-清晰类（定理 2）。
• AO-GTMP： 证明了当 $M, N \to \infty$ 时，它能几乎处处收敛到最优代价 $c^*$（定理 3），该定理应用了 AO-x 元算法框架于分层 DAG。

3. 算法效率

该方法利用张量运算来并行化边实现和价值迭代。搜索复杂度由层间边评估的数量（$O(MN^2)$）主导，这通过批处理张量收缩进行高效处理。

实验结果

1. 机械臂基准测试 (MotionBenchMaker)

在 6–8 自由度机械臂（Panda, UR5, Fetch）上进行了评估：

• 可行性： Anytime-GTMP（使用直线边）达到了与最先进的 FCIT 规划器相当的最终成功率（~85%），但由于图构建的开销，其寻找第一个解的速度较慢。
• 代价： 在大多数解决的问题中，其变体匹配或优于最低平均路径代价（例如，在 60 秒预算内，AO-GTMP 在 7/7 个 UR5 问题中表现优异）。
• 局部规划器影响： 实验表明，超过约 400–600 次迭代后，增加局部规划器预算（RRT-Connect 迭代）的收益递减，这表明在固定时间预算下，适度的局部努力结合广泛的全局采样更为有效。

2. 2D 导航

在街景高度图中进行了评估：

• 拓扑多样性： Anytime-GTMP 返回了具有拓扑多样性的解集，覆盖了最高平均数量的同伦类。
• 对比： 相比之下，启发式基准方法（如 AO-GTMP 和 FCIT）将样本集中在一个或两个近优类上，未能探索替代的拓扑路径。
• 权衡： 结果在经验上展示了这种权衡：随机重启（Anytime-GTMP）最大化多样性，而启发式扩张（AO-GTMP）则最大化最优性。

意义与主张

本文声称提供了第一个满足以下条件的运动规划框架：

1. 泛化了 GTMP，使其能够接受任何黑盒局部规划器，同时保持严谨的理论保证。
2. 保证了同伦覆盖： 证明了单个图可以覆盖所有具有有限长度 $\delta$-清晰代表元的同伦类，且随着 $N$ 和 $s$ 的增加，该概率趋于 1，而这一特性是顺序路标构建方法无法保证的。
3. 提供了截然不同的 Anytime 保证： 明确地将“多样性”（通过随机重启）与“最优性”（通过启发式扩张）的目标分离，并提供了相应的形式化证明。
4. 可扩展性： 证明了基于张量的并行化使该方法能够在处理高维操作任务时，达到与最先进技术相当的性能，同时提供生成拓扑多样化解集这一独特能力。

作者总结道，该方法有效地平衡了全局探索与局部连接，为需要多样化备选方案或最优路径的应用场景提供了一个灵活的工具。