快速扩展随机树

从起点出发随机撒点、不断向新点长枝，直到树枝够到终点的规划算法。

快速扩展随机树由 Steven LaValle 于 1998 年提出，后与 James Kuffner 进一步发展，是最常用的基于采样的规划算法之一。每一轮做四件事：在构型空间里随机采一个点；找树上离它最近的节点；从该节点朝采样点走一小步；这一步不碰撞就把新点加进树。大片空白区域更容易被采中，所以树会自然地往未探索的方向快速伸展。它只需碰撞检测，不必显式算出整个无碰撞空间，适合六七个自由度的机械臂，也能处理带动力学约束的系统。基础 RRT 概率完备，但路径通常曲折、不是最优，常见改进有双向生长的 RRT-Connect 和渐近最优的 RRT*，结果一般还要再做路径平滑。

例子在二维迷宫里，RRT 从入口开始随机长枝，某根树枝进入出口附近后，沿树回溯到根就得到一条折线路径，再用捷径平滑把它拉直缩短。

也叫

快速探索随机树、快速搜索随机树、RRT 算法

相关

RRT*、RRT-Connect、概率路线图、基于采样的规划、路径平滑、碰撞检查

来源

Wikipedia: Rapidly exploring random tree
Lynch & Park, Modern Robotics（§10.5.1 The RRT Algorithm）