RRT and RRT*

A rapidly-exploring random tree grows from the start by repeatedly picking a random point and extending the nearest branch a short step toward it. It explores large open areas quickly and works in many dimensions. RRT* adds a rewiring step that keeps improving the path, so it gets closer to the shortest one over time.

Algorithm Step size Goal bias Growth speed

Growing the tree

Each iteration samples a random point $\mathbf{x}_{\text{rand}}$, finds the nearest tree node $\mathbf{x}_{\text{near}}$, and steps toward it by at most $\eta$:

$$\mathbf{x}_{\text{new}} = \mathbf{x}_{\text{near}} + \eta\,\frac{\mathbf{x}_{\text{rand}} - \mathbf{x}_{\text{near}}}{\lVert \mathbf{x}_{\text{rand}} - \mathbf{x}_{\text{near}} \rVert}$$

RRT* then picks the cheapest parent for $\mathbf{x}_{\text{new}}$ among nodes within a radius, and rewires nearby nodes through $\mathbf{x}_{\text{new}}$ if that makes their path shorter. With enough samples, RRT* converges to the optimal path, while plain RRT does not.

What to notice

RRT finds a path fast, but it is jagged and stays that way. RRT* keeps shortening the path as the tree grows, and the plot shows its length dropping. A small goal bias, trying the goal directly now and then, speeds up the first connection. RRT-style planners are the default for robot arms in tools like MoveIt, usually followed by path smoothing.