RRT*

An extension of RRT that adds parent selection and rewiring so path cost converges to optimal as sampling increases.

RRT* was proposed by MIT researchers Sertac Karaman and Emilio Frazzoli, with the systematic treatment appearing in their 2011 IJRR paper. They proved that the path returned by plain RRT converges almost surely to a non-optimal cost, and fixed this with two added steps: when a new node is added, among its neighbors within a certain radius, RRT* picks whichever one minimizes the total cost from the start to the new node as its parent; it then checks those same neighbors and rewires any of them to the new node if that path turns out cheaper. The neighborhood radius shrinks as the node count n grows, following γ(log n / n)^{1/d}, where d is the dimension of the space and γ is a constant tied to its size. As a result, path cost converges almost surely to the optimum as sampling increases — called asymptotic optimality — while the extra computation over plain RRT is only a constant factor. The downside is that convergence can be slow in practice, so implementations are usually just given a fixed time budget and run until it expires. Follow-up methods such as Informed RRT* and BIT* are designed specifically to speed up this convergence.

ExampleOMPL's RRTstar planner doesn't return as soon as it finds a first feasible path — it keeps sampling and rewiring, continuously shortening the path within the given time budget. If a cost threshold is set, it can also stop early once the path cost drops below it.

Also called

RRT-star, RRTstar, Optimal RRT

Related

Rapidly-exploring Random Tree · Informed RRT* (Informed Sampling) · Batch Informed Trees · Probabilistic Completeness · Probabilistic Roadmap · RRT-Connect

Sources

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