Rapidly-exploring Random Tree

A planning algorithm that grows a tree from the start by repeatedly sampling random points and reaching toward them, until a branch reaches the goal.

Proposed by Steven LaValle in 1998 and further developed with James Kuffner, the rapidly-exploring random tree is one of the most widely used sampling-based planning algorithms. Each round does four things: sample a random point in configuration space; find the tree's nearest existing node to it; step a small distance from that node toward the sample; and add the new point to the tree if that step is collision-free. Large unexplored regions are more likely to be sampled, so the tree naturally grows fastest toward unexplored space. It needs only collision checking, not an explicit description of free space, which suits arms with six or seven degrees of freedom and systems with dynamics constraints. Basic RRT is probabilistically complete, but its paths are usually jagged and not optimal; common improvements include the bidirectionally growing RRT-Connect and the asymptotically optimal RRT*, and results are typically smoothed afterward.

ExampleIn a 2D maze, RRT grows random branches from the entrance; once a branch nears the exit, tracing it back to the root gives a jagged path, which shortcutting then straightens and shortens.

Also called

RRT, RRT Algorithm

Related

Rapidly-exploring Random Tree · RRT-Connect · Probabilistic Roadmap · Sampling-Based Planning · Path Smoothing (Shortcutting) · Collision Checking

Sources

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