基于采样的运动规划：比较性综述报告

本文由Andreas Orthey（Realtime Robotics, Boston）、Constantinos Chamzas和Lydia E. Kavraki（Rice University）合作完成，发表于2024年的《Annual Review of Control, Robotics, and Autonomous Systems》。文章标题为《Sampling-Based Motion Planning: A Comparative Review》，是一篇系统性综述，旨在为基于采样的运动规划（SBMP, Sampling-Based Motion Planning）领域提供全面的技术指南和比较分析。

研究背景与目标

运动规划是机器人领域的核心问题，其目标是为机器人找到从起点到目标区域的可行路径。基于采样的方法（如PRM、RRT）通过随机采样构型空间来高效解决高自由度问题，但缺乏对算法选择、历史发展及与其他框架对比的系统性总结。本文填补了这一空白，提出四个核心贡献：
1. 历史梳理（1979–2023年）：将运动规划分为四个时代——前采样时代（1979–1989）、采样兴起时代（1990–1999）、采样巩固时代（2000–2009）以及最优性与学习时代（2010至今）。
2. 算法分类：分析不同规划器的特性（如概率完备性、渐进最优性）及扩展功能（如动态环境、接触约束）。
3. 框架对比：与运动优化、运动基元、搜索规划和控制规划等方法对比优劣。
4. 大规模实验：在24个场景中比较多种规划器的性能（成功率、耗时、路径质量）。

主要观点与论据

1. 运动规划的历史演进

• 前采样时代：Lozano-Pérez提出构型空间理论（1979），奠定问题基础；Canny证明运动规划是NP难问题（1988）。
  
• 采样兴起时代：PRM（概率路线图法）和RRT（快速探索随机树）成为主流，通过随机采样实现高效路径搜索。
  
• 最优性与学习时代：PRM*和RRT*（2010）首次实现渐进最优性；机器学习被用于优化采样分布（如深度学习驱动的偏置采样）。
  

支持证据：引用经典论文（如Kavraki et al. 1996的PRM、Karaman & Frazzoli 2011的RRT*）及关键突破（如势场法、窄通道采样技术）。

2. 算法分类与特性

• 图规划器（如PRM）：适用于多查询场景，构建可复用的路线图。
  
• 树规划器（如RRT）：适用于单查询场景，通过增量生长树快速求解。
  
• 改进策略：
  
  • 惰性检查（Lazy Checking）：延迟碰撞检测以提升效率。
    
  • 双向搜索：通过双树生长加速收敛。
    
  • 稀疏性：通过可见性半径减少冗余节点。
    

实验支持：在“家庭钢琴搬运”场景中，FMT*因稀疏性表现优异；BIT*在路径质量上优于RRT*。

3. 特殊场景与扩展

• 无界空间：通过自适应目标区域处理时间依赖问题（如ST-RRT*）。
  
• 动力学约束：SST*（稳定稀疏RRT*）结合剪枝策略保证渐进最优。
  
• 接触约束：投影法将高维问题简化至低维流形（如隐式链场景）。
  

案例：在“无人机单推进器”动态模型中，仅Kinodynamic RRT能成功规划。

4. 与其他框架的对比

• 运动优化（如CHOMP）：依赖梯度信息，易陷入局部最优，但收敛快。
  
• 运动基元：适合反应式控制（如避障），但缺乏全局最优性保证。
  
• 搜索规划（如A*）：网格分辨率限制其在高维空间的应用。
  

结论：SBMP在复杂环境中更通用，而优化方法在局部调优中更高效。

实验比较与性能分析

在24个场景中测试7类规划器（如RRT-Connect、PRM*、BIT*），关键发现包括：
- 经典场景：BIT*在5/6场景中路径质量最优，FMT*在“家庭”场景成功率最高（50%）。
- 窄通道问题：RRT-Connect和TRRT在3/6场景中成功率近100%。
- 动力学问题：仅Kinodynamic RRT能解决“单推进器无人机”问题。

数据支持：成功率-成本曲线显示，PRM*在4个操作场景中快速收敛至低成本解。

意义与价值

1. 学术价值：首次系统梳理SBMP的发展脉络，提出算法分类学，并为扩展问题（如接触约束）提供解决方案。
   
2. 应用价值：指导工业机器人、自动驾驶等领域选择规划器，例如RRT-Connect适合快速求解，而BIT*适合高精度需求。
   
3. 未来方向：参数调优（如贝叶斯优化）和机器学习结合是提升性能的关键。

亮点

• 历史全景：45年研究历程的阶段性总结。
  
• 算法创新：如SST*的剪枝策略、投影法的分层规划。
  
• 实验规模：24个场景涵盖几何、动力学、接触约束等复杂条件。
  

本文不仅是研究者的参考手册，也为实践者提供了算法选择的科学依据。