Informed RRT* (Informed Sampling)

After finding a path once, sampling only inside the ellipsoidal region that could still shorten it, so RRT* converges faster.

Informed RRT* was proposed by Gammell, Srinivasa, and Barfoot at IROS 2014. After RRT* finds a feasible path, it keeps sampling and rewiring branches to push the path toward the shortest one, but it still samples uniformly over the whole space, and most samples have no chance of improving the result. Let c_best be the length of the current best path; a point x that could shorten the path must satisfy ‖x−x_s‖ + ‖x−x_g‖ < c_best (x_s, x_g the start and goal) — in 2D this is an ellipse with the start and goal as foci, and a long, thin ellipsoid in higher dimensions. Informed RRT* samples only inside that ellipsoid and prunes nodes outside it; the shorter the path gets, the thinner the ellipsoid, and the more concentrated the search becomes. It keeps RRT*'s asymptotic optimality while converging noticeably faster in high dimensions and large maps, and later algorithms such as BIT* build on the same idea.

ExampleThe open-source motion-planning library OMPL provides an InformedRRTstar planner, which can be wired into frameworks like MoveIt through OMPL, letting an arm keep shortening its trajectory in any remaining time after first finding a feasible one.

Also called

Informed Sampling

Related

Rapidly-exploring Random Tree · Rapidly-exploring Random Tree · Batch Informed Trees · Sampling-Based Planning · Open Motion Planning Library (OMPL) · Probabilistic Completeness

Sources

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