To find a path through a cluttered world, reach randomly into the unknown. Grow a tree from the start: pick a random point, take one small step from the nearest branch toward it — if the step is clear — and repeat. The tree floods free space, pulled by a Voronoi bias toward the large unexplored regions, until a branch touches the goal. Down the center the data flows: the map goes in, the engine grows the tree, a collision-free path comes out. The blue team builds and proves it; the red team tries to break it.
source S. M. LaValle, Rapidly-Exploring Random Trees: A New Tool for Path Planning, TR 98-11, Computer Science Dept., Iowa State University (October 1998) — lavalle.pl/rrtpubs.html. Rendered, not quoted.
One tree, grown from the start by a five-line loop, repeated until it reaches the goal:
1 SAMPLE a random configuration q (with a small goal bias). 2 find the NEAREST tree node to q. 3 STEER: take one step of length ε from that node toward q. 4 if that step is COLLISION-FREE, add it as a new leaf. 5 if a leaf lands near the goal and connects cleanly, walk the parent pointers back for the PATH.
Live on the current tree:
The nearest-node rule is the whole trick: it makes new samples land beyond the frontier, so the tree is pulled toward the big empty regions — the Voronoi bias.
Before RRT, a planner either gridded the whole space (dies in high dimensions) or slid downhill on a potential field (Khatib, 1986) — and got stuck in local minima behind concave obstacles.
LaValle's move: don't descend a gradient, reach at random and let a tree biased toward the unknown fill the space. It scales to many dimensions and honours motion constraints — the sampling-based planner. Each sphere is the next one's premise; the neighbouring planners sit in THE FOLD.
The blue team's live check: rebuild the fixed-seed tree, confirm the returned path is continuous, obstacle-free, and joins start to goal, and re-confirm the exploration trend. If red skips the collision check, this badge is where it shows.
A planning problem: a configuration space (here the unit square, 100×100), two axis-aligned obstacles forming a wall with an off-diagonal gap, a start at (10,10) and a goal at (90,90). The straight line between them is blocked — the planner must detour left through the gap.
| parameter | value |
|---|---|
| step ε | 4.0 |
| goal bias | 0.08 |
| goal reach | 7.0 |
| gap (x) | 14 → 34 at y≈50 |
These constants are fixed; the only knobs are the seed and the sample budget, fed to the engine below.
■ start ■ goal ■ obstacle ■ tree ■ path
Move the seed or budget — the tree is grown live from the algorithm, every edge collision-checked; nothing is looked up.
What the machine produces, proven on the fixed seed: a sequence of waypoints from start to goal, each hop no longer than a step, and every segment obstacle-free. Over many seeds the chance of finding a path rises with the budget toward 1 — probabilistic completeness.
The blue team's witness (left) re-checks this path live; the red team (right) tries to make it pass through a wall.
It also cannot certify that no path exists — it only keeps failing to find one. Nearest-neighbour cost grows with the tree, and in nonholonomic spaces a bad metric wrecks the Voronoi bias entirely.
"RRT finds the shortest path." Cut. It finds a feasible path, not an optimal one. Asymptotic optimality needed RRT* (Karaman & Frazzoli, 2011) — a different algorithm.
"RRT is complete — if a path exists it finds it." Cut. It is probabilistically complete: P(found) → 1 as samples → ∞. At any finite budget it can miss, and it never proves none exists.
"The tree explores by sampling uniformly." Kept, corrected. Sampling is uniform, but the nearest-node rule makes growth Voronoi-biased toward the unexplored — that bias, not the sampler, is the engine.
The red team's move: skip the obstacle check when extending, so the tree grows straight through walls and the returned path cuts across an obstacle. The blue team's witness (window 7) is watching.
Skip the check and the goal-biased tree beelines through the wall; the path-is-collision-free test in the witness fails and turns red. Nothing is faked — the attack is real, and it is caught.