RRT*

在 RRT 上加入选父节点和重连两步，使路径随采样增多收敛到最优。

RRT* 由 MIT 的 Karaman 和 Frazzoli 提出，系统论述见 2011 年的 IJRR 论文。他们证明普通 RRT 返回的路径代价几乎必然收敛到一个非最优值，于是在 RRT 上改了两步：新节点加入时，在一定半径内的邻居里挑一个使「起点到新节点总代价」最小的当父节点；再检查这些邻居，若改经新节点到达更便宜，就把它们重连到新节点下。邻域半径随节点数 n 按 γ(log n / n)^{1/d} 缩小，d 是空间维数，γ 是与空间大小有关的常数。这样路径代价会随采样增多几乎必然收敛到最优，即渐近最优，而计算量只比 RRT 多常数倍。缺点是收敛可能很慢，实际常给固定时间、用到超时为止。Informed RRT*、BIT* 等后续方法专门加速这一收敛。

例子OMPL 的 RRTstar 规划器找到第一条可行路径后不会马上返回，而是继续采样、重连，在给定时间内不断缩短路径；如果设置了代价阈值，路径代价降到阈值以下就提前结束。

也叫

RRT-star、RRTstar、最优 RRT、Optimal RRT

相关

快速扩展随机树、Informed RRT*、BIT*、概率完备性、概率路线图、RRT-Connect

来源

Karaman & Frazzoli, Sampling-based Algorithms for Optimal Motion Planning (arXiv:1105.1186, IJRR 2011)
OMPL: ompl::geometric::RRTstar
MoveIt 2 Documentation: OMPL Planner