Rapidly-Exploring Random Trees

A robot arm has seven joints. Each joint can rotate independently, so its configuration space — the set of all possible poses — has seven dimensions. A grid fine enough to be useful would need $7^{100}$ cells. No computer on Earth could hold it.

That is the curse of dimensionality that haunted path-planning research through the 1980s and 1990s. Then in 1998 the computer scientist Steven LaValle proposed a disarmingly simple escape: instead of building a grid, just throw random samples into the space and connect them into a tree.

The algorithm is called the Rapidly-Exploring Random Tree, or RRT. It starts with a single node at the robot's start position, then repeats three steps forever: pick a random point in the space, find the nearest node already in the tree, and take a small step from that node toward the random point. The resulting tree sprawls outward like lightning, flooding every reachable corner of the space. When a branch touches the goal, the path is found — just walk back up the tree.

No grid. No exhaustive search. Just randomness, and a voracious branching appetite that scales to dozens of dimensions.

The canvas below shows a maze (gray walls) with a start (green dot) and a goal (red dot). Each step of RRT picks a random point, finds the nearest tree node, and extends toward it — stopping early if a wall is in the way.

<!-- {{c_html_intro}} -->
<div class="toolbar">
  <label>{{lbl_step_size}} <input id="stepSize" type="range" min="10" max="40" value="20"> <span id="stepVal">20</span>px</label>
  <label>{{lbl_speed}} <input id="speed" type="range" min="1" max="20" value="8"> <span id="speedVal">8</span></label>
</div>
<canvas id="canvas" width="360" height="300"></canvas>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btnRun" type="button">{{btn_run}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; margin: 0; }
body { font-family: system-ui, sans-serif; color: #222; padding: 14px; }
.toolbar { display: flex; gap: 1rem; flex-wrap: wrap; margin-bottom: .5rem; font-size: .82rem; color: #444; }
.toolbar label { display: flex; align-items: center; gap: .35rem; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 6px; background: #f5f8fa;
         width: 100%; max-width: 360px; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .45rem 0; }
.status.ok { color: #0a7d33; }
.status.running { color: #1d3557; }
.status.fail { color: #c92f3c; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }

// Code not found

Watch how the tree spreads rapidly even in tight corridors. It never backtracks; every new branch locks in a small piece of explored space. Once a branch reaches the goal, the highlighted path is the route the robot would follow. Hit Reset to run a fresh exploration — the random samples change every time, but the tree always finds the goal eventually.

RRT is elegant, but it comes with caveats worth understanding.

• Probabilistic completeness. RRT will find a path if one exists — but only in the limit of infinitely many samples. In practice, after a few thousand iterations it almost always succeeds. This is weaker than the completeness of exact planners, but it is good enough for most engineering uses.
• Not optimal. The path found by a plain RRT is rarely the shortest. It zigzags through the random samples and can be far longer than necessary.
• RRT* (2011). Sertac Karaman and Emilio Frazzoli showed that adding one extra step — rewiring nearby nodes to use the new node if it shortens their path — turns RRT into an asymptotically optimal planner. As the number of samples $n \to \infty$, the path cost converges to the true optimum.
• Curse of dimensionality, tamed. Unlike grid search, RRT's run time grows far more gently with dimension. The expected number of samples needed scales roughly as $O(n \log n)$ for RRT*, making it practical even in 10- or 20-dimensional spaces where dynamic programming would be hopeless.

The trade-off is that RRT gives up determinism for scalability — a bargain most roboticists are happy to make.

Sampling-based planning with RRT now touches almost every field where a system must navigate a complex space:

• Robot arms and manipulation: industrial arms use RRT to plan motions around obstacles in seconds without precomputing a grid of the workspace.
• Autonomous vehicles: motion planners in self-driving cars adapt RRT variants to plan smooth, safe trajectories in real time as the environment changes.
• Spacecraft and drones: trajectory planning for satellites and UAVs uses RRT to handle dynamic constraints (fuel, attitude, collision) in very high-dimensional spaces.
• Protein and drug design: the configuration space of a folding protein is absurdly high-dimensional; sampling-based methods borrowed from RRT help explore viable conformations.
• Video-game AI: character navigation through complex 3-D environments uses RRT-style online exploration when precomputed navigation meshes are too costly or too rigid.

What unifies all of these is the same insight LaValle had in 1998: when the space is too large to enumerate, let randomness do the exploring — and trust that the tree will find its way.

The Rapidly-Exploring Random Tree is one of the most beautifully simple ideas in modern computer science: when the space is too large to grid, sample it randomly, connect the dots into a tree, and watch it flood every corner.

The core RRT is not optimal, and its path is sometimes long and jagged. But RRT* tightens that up with a single rewiring step, and a vast family of variants — bidirectional RRT, informed RRT*, kinodynamic RRT — have extended the idea to cover almost every planning scenario engineers face.

The deeper lesson is about how to think when a problem is too large for exhaustive search. Random sampling, done carefully, can be as powerful as systematic exploration — and far more scalable. That insight connects RRT to Monte Carlo methods, randomized graph search, and the broader story of algorithms that trade certainty for reach.