RRT*

• 又称: RRT star, RRT-star, optimal RRT
• 类别: Planning & manipulation › Motion planning
• 标签: motion-planning, sampling-based-planning, path-planning, optimization, manipulation

快速扩展随机树规划器的一种渐近最优版本，它在生长过程中对树进行重连，使其返回的路径不断向代价最低的路径改进。

定义

RRT\（读作“RRT star”）是一种基于采样的运动规划算法，它能找到无碰撞路径，并且在样本足够多时收敛到最优路径。它由 Sertac Karaman 和 Emilio Frazzoli 于 2011 年提出，是 Steven LaValle 于 1998 年提出的快速扩展随机树（Rapidly-exploring Random Tree，RRT）算法的扩展。

原始的 RRT 从起点构型开始生长一棵树：反复在构型空间中随机采样一个点，找到树中最近的节点，如果朝该样本的运动无碰撞，就向它延伸一小步。RRT 能很快找到可行路径，即使在机械臂关节空间这样的高维空间中也是如此，但它的路径通常曲折，远非最短，而且不会随着样本增加而改善。

RRT* 改变了两点。添加新节点时，它会检查邻域半径内的所有树节点，并连接到从起点出发代价最低的那个节点，而不只是最近的节点。然后它进行重连：对于每个邻居，如果经过新节点能得到更低代价的路径，就更换该邻居的父节点。Karaman 和 Frazzoli 证明，只要邻域半径随树的生长适当缩小，当样本数量趋于无穷时，解的代价就会收敛到最优值，这一性质称为渐近最优性。

代价是每个样本需要额外的计算，因此 RRT 找到第一个解的速度比 RRT 慢。Informed RRT 和 BIT* 等变体通过集中采样来加快收敛。

为何重要

许多机器人需要的不只是任意一条路径，而是一条好的路径：更短、更平滑或更节能。RRT* 为可扩展到高维构型空间的基于采样的规划器提供了一条有理论依据的路径质量提升途径，它也是运动规划研究和软件中的标准基线。

主要应用

• 杂乱工作空间中机械臂的无碰撞运动规划
• 移动机器人和无人机的全局运动规划
• 在栅格搜索不切实际的高维构型空间中进行规划
• 为轨迹优化生成参考路径

实际应用

机器人团队通常通过规划库来使用 RRT，而不是自己编写。MoveIt 用于机械臂的开放运动规划库（Open Motion Planning Library，OMPL）包含 RRT 及其若干变体，还有 RRT、RRT-Connect 和 PRM。一种常见做法是在固定的时间预算内运行 RRT，在时间用完时取已找到的最佳路径，然后对其进行捷径化和平滑处理，再转换为带时间参数的轨迹。对于移动机器人和无人机，团队也会在 2D 或 3D 占据地图上把 RRT 用作全局规划器，通过选择规划时间和步长在路径质量与响应时间之间进行权衡。

常见误解

• RRT* 返回最优路径 — 它是渐近最优的，因此只有当样本数量无限增长时，路径代价才会趋近最优值
• RRT* 的路径是平滑的 — 它们是分段线性的，在执行前通常需要捷径化和平滑处理
• RRT* 总是比 RRT 好 — 当只需要快速得到一条可行路径时，普通的 RRT 或 RRT-Connect 往往是更好的选择

谁需要了解

• 运动规划工程师
• 机械臂和操作软件开发者
• 自主无人机和移动机器人开发者
• 学习规划算法的机器人专业学生

相关技术

• OMPL
• MoveIt
• RRT-Connect
• Informed RRT*
• BIT*
• 碰撞检测（Collision Checking）

相关术语

• Motion Planning
• Probabilistic Roadmap
• Configuration Space
• Trajectory Planning

相关项目

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

视频

• Path Planning with A* and RRT | Autonomous Navigation, Part 4: MATLAB