Informed RRT*

找到一条路径后，只在「可能更短」的椭球区域里采样，从而更快收敛的 RRT*。

Informed RRT* 由 Gammell、Srinivasa、Barfoot 在 IROS 2014 提出。RRT* 找到可行路径后会继续采样、重连树枝，让路径逼近最短，但它仍在全空间均匀撒点，多数样本不可能改进结果。设当前最好路径长 c_best，能让路径变短的点 x 必须满足 ‖x−x_s‖ + ‖x−x_g‖ < c_best（x_s、x_g 为起点、终点），这在二维是以起终点为焦点的椭圆，高维是长椭球。Informed RRT* 只在该椭球内采样并剪掉椭球外节点；路径越短椭球越瘦，搜索越集中。它保留 RRT* 的渐近最优性，在高维和大地图中收敛更快，BIT* 等后续算法沿用了这一思路。

例子开源运动规划库 OMPL 提供 InformedRRTstar 规划器，可通过 OMPL 接入 MoveIt 等框架，让机械臂在找到可行轨迹后继续在剩余时间内缩短路径。

也叫

知情 RRT*、启发式采样 RRT*、Informed Sampling

相关

快速扩展随机树、快速扩展随机树、BIT*、基于采样的规划、OMPL、概率完备性

来源

Gammell, Srinivasa, Barfoot: Informed RRT* (arXiv:1404.2334, IROS 2014)
OMPL: ompl::geometric::InformedRRTstar Class Reference