斯坦福大学AA274A机器人自主原理课程：基于采样的运动规划（2019年秋季）

（原标题：Stanford AA274A Principles of Robotic Autonomy | Autumn 2019 | Motion Planning Sampling-Based）

🧠 核心概述与算法范式

采样式运动规划算法通过随机或确定性序列在配置空间中生成样本点，并调用碰撞检测器隐式表示障碍物，从而避免了组合式规划中显构建高维障碍物的复杂性。该范式以概率路线图（PRM）和快速扩展随机树（RRT）为代表，具有概念简单、实现灵活且适用于动力学及不确定性场景的优势。尽管算法在有限时间内无法严格证明路径不存在或保证最优解，但其具备渐近完备性，即随着样本数量趋于无穷，找到可行解的概率趋近于 1。通过特定的参数缩放与局部重连机制，如 PRM 半径缩放和 RRT* 优化，算法可实现渐近最优性，在理论上收敛至全局最优解。

📊 隐式表示与配置空间挑战

配置空间的转换是运动规划的核心难点，其复杂度随维度增加而剧增。例如，当三角形机器人从二维平移扩展至包含旋转角度的三维空间时，障碍物映射为复杂的三维对象，显式构建变得极其困难。采样算法通过不存储障碍物边界，而是对随机生成的配置样本调用碰撞检测器（在工作空间中检查几何交集），仅保留无碰撞样本来构建路线图或树结构，从而实现了障碍物的隐式表示。这种机制使得算法能够处理高维空间中的复杂约束，但同时也引入了“维度灾难”问题：所需样本数随维度指数增长，通常适用于 3-8 维场景，而在 12 维以上算法效能显著下降。此外，稀疏采样可能导致算法误判无解（Bug Traps），需增加样本密度以突破配置空间中的狭窄通道或障碍陷阱。

🌲 PRM 与 RRT 的机制差异

概率路线图（PRM）由 Lydia Kavraki 等人提出，属于多查询规划算法。它通过限制连接半径 $r$ 平衡计算量与图密度，利用 Dijkstra 或 A* 在生成的路线图上求解路径。PRM 作为批量算法，路径质量较高但计算密集，适合需要多次查询同一环境的应用场景。快速扩展随机树（RRT）由 Lavalle 于 2001 年提出，属于单查询规划，针对特定起点和终点对进行路径搜索。RRT 具有增量特性，速度快且内存占用低，但其生成的路径往往呈锯齿状且非最优。RRT 在树前沿的 Voronoi 单元面积较大，使采样概率偏向未探索区域，实现了快速的空间覆盖（Voronoi Bias）。为了克服基础 RRT 的路径质量缺陷，RRT* 通过局部重连机制消除锯齿，而 FMT* 则结合 PRM 的路径质量与 RRT 的单次碰撞检查效率，通过惰性碰撞检测与贪心连接实现计算复杂度与解质量的平衡。

📈 渐近最优性与理论收敛

采样算法的渐近最优性依赖于严格的参数缩放条件。对于 PRM，实现渐近最优需将半径缩放为 $O(\log n / n^{1/d})$，其中 $d$ 为维度。修正后的理论证明指出，RRT* 因涉及时间变量，需采用 $1/(d+1)$ 指数进行缩放。若采样序列的分散性缩放比例为 $n^{-1/d}$，且连接球半径衰减不慢于 $n^{1/d}$，PRM 算法可确定性收敛至最优路径。传统观点认为随机性是 PRM/RRT 成功的关键，但研究表明，精心构造的低分散性（Low Dispersion）确定性序列在理论和实践中均表现更优。点集的 $L_2$ 分散性定义为空间中任意点到最近采样点的最小距离的最大值，低分散性意味着对环境的良好覆盖。实验数据表明，在维度为 2 到 8 的各种系统中，确定性序列的性能通常优于随机序列，且能提供更小的连接半径和明确的收敛速率保证。

⚙️ 动力学约束与轨迹优化

在动力学约束下的规划中，需将轨迹优化与障碍物规避解耦。处理动力学主要分为前向传播（Forward Propagation）和轨迹优化两种方法。前者简单但低效，通过逐步模拟状态演化来检查可行性；后者通过求解连接两点的轨迹优化问题，利用领域知识减少采样浪费，但计算强度更大。在动力学系统中，邻居搜索不再使用球形区域，而是基于时间或成本限制的“可达集”（Reachable Sets）。例如，汽车横向移动比纵向更耗时，导致可达集形状非对称。若问题复杂度过高无法快速求解轨迹优化，则回退至前向传播作为基线方法；否则应优先采用结合可达集的轨迹优化策略，以确保在满足动力学约束的同时实现高效规划。

🛠️ 工程实现与性能瓶颈

采样算法的主要计算瓶颈在于碰撞检测与最近邻搜索，需依赖专用数据结构（如 KD-Tree）进行优化。实际应用中需平衡实时性与精度，通常要求算法在 200 毫秒至数秒内完成重规划以应对环境变化。碰撞检测依赖现有库（如 Bullet）在工作空间执行几何交集判断。使用确定性序列可简化认证过程、允许离线预计算（如复用路线图），并适用于对安全性要求极高的系统（如自动驾驶飞行器）。多机器人规划因配置空间维度叠加而复杂度激增，现有算法主要适用于单机器人或低维场景。采样式算法在工程实践中优于组合式方法，因其无需显式几何分解且易于集成机器学习优化采样分布，例如基于先验知识或数据驱动的非均匀采样，从而进一步提升规划效率与成功率。