Introduction

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 71007^{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.

Grow the Tree

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.

<!-- RRT demo: maze canvas + controls -->
<div class="toolbar">
  <label>Step size: <input id="stepSize" type="range" min="10" max="40" value="20"> <span id="stepVal">20</span>px</label>
  <label>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">Click Run to grow the RRT tree.</div>
<div class="btns">
  <button id="btnRun" type="button">Run</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>

/* RRT demo styles */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// RRT algorithm: grows a tree by sampling random points and extending toward them
// Maze as a 10x12 grid of cells
const ROWS = 10, COLS = 12;
// Cell values:
// 1 = wall, 0 = free
const MAZE = [
  [1,1,1,1,1,1,1,1,1,1,1,1],
  [1,0,0,0,1,0,0,0,0,0,0,1],
  [1,0,1,0,1,0,1,1,1,1,0,1],
  [1,0,1,0,0,0,0,0,1,0,0,1],
  [1,0,1,1,1,1,1,0,1,0,1,1],
  [1,0,0,0,0,0,1,0,0,0,1,1],
  [1,1,1,0,1,0,1,1,1,0,1,1],
  [1,0,0,0,1,0,0,0,1,0,0,1],
  [1,0,1,1,1,1,0,0,1,1,0,1],
  [1,1,1,1,1,1,1,1,1,1,1,1]
];

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const CW = W / COLS, CH = H / ROWS;

// Start (green) and goal (red circle) positions in canvas pixels
const START = { x: 1.5 * CW, y: 1.5 * CH };
const GOAL  = { x: 10.5 * CW, y: 7.5 * CH };
const GOAL_RADIUS = 18;

// Tree state: nodes array, parent index array, found path, animation handle
let nodes = [], parents = [], pathNodes = null, running = false, animId = null;

// Returns true if pixel (x,y) falls inside a wall cell
function isWall(x, y) {
  const col = Math.floor(x / CW);
  const row = Math.floor(y / CH);
  if (row < 0 || row >= ROWS || col < 0 || col >= COLS) return true;
  return MAZE[row][col] === 1;
}

// Check if the straight segment from (x1,y1) to (x2,y2) is collision-free
function segmentFree(x1, y1, x2, y2) {
  const steps = Math.ceil(Math.hypot(x2 - x1, y2 - y1) / 4);
  for (let i = 0; i <= steps; i++) {
    const t = i / steps;
    if (isWall(x1 + t * (x2 - x1), y1 + t * (y2 - y1))) return false;
  }
  return true;
}

// Find index of the nearest tree node to point (x,y)
function nearest(x, y) {
  let best = 0, bestDist = Infinity;
  for (let i = 0; i < nodes.length; i++) {
    const d = Math.hypot(nodes[i].x - x, nodes[i].y - y);
    if (d < bestDist) { bestDist = d; best = i; }
  }
  return best;
}

// Render maze, tree edges, path and start/goal markers
function draw() {
  ctx.clearRect(0, 0, W, H);
  // Draw maze cells
  for (let r = 0; r < ROWS; r++) for (let c = 0; c < COLS; c++) {
    ctx.fillStyle = MAZE[r][c] ? '#6b8099' : '#f5f8fa';
    ctx.fillRect(c * CW, r * CH, CW, CH);
  }
  // Draw tree edges in translucent blue
  ctx.strokeStyle = 'rgba(29,53,87,0.35)';
  ctx.lineWidth = 1;
  for (let i = 1; i < nodes.length; i++) {
    const p = nodes[parents[i]];
    ctx.beginPath(); ctx.moveTo(p.x, p.y); ctx.lineTo(nodes[i].x, nodes[i].y); ctx.stroke();
  }
  // Draw found path in red
  if (pathNodes) {
    ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2.5;
    ctx.beginPath(); ctx.moveTo(pathNodes[0].x, pathNodes[0].y);
    for (let i = 1; i < pathNodes.length; i++) ctx.lineTo(pathNodes[i].x, pathNodes[i].y);
    ctx.stroke();
  }
  // Draw goal circle
  ctx.beginPath(); ctx.arc(GOAL.x, GOAL.y, GOAL_RADIUS, 0, 2 * Math.PI);
  ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2; ctx.stroke();
  ctx.fillStyle = 'rgba(230,57,70,0.15)'; ctx.fill();
  // Draw start dot
  ctx.beginPath(); ctx.arc(START.x, START.y, 6, 0, 2 * Math.PI);
  ctx.fillStyle = '#2a9d8f'; ctx.fill();
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg; el.className = 'status ' + (cls || '');
}

// One RRT iteration: sample, find nearest, extend, check goal
function rrtStep() {
  // Sample a random point in the canvas
  let rx = Math.random() * W, ry = Math.random() * H;
  // 10% goal bias: occasionally aim directly at the goal
  if (Math.random() < 0.1) { rx = GOAL.x; ry = GOAL.y; }

  const ni = nearest(rx, ry);
  const nx = nodes[ni].x, ny = nodes[ni].y;
  const dist = Math.hypot(rx - nx, ry - ny);
  const step = +document.getElementById('stepSize').value;
  // Compute the new node position, capped at step distance
  const ex = dist < step ? rx : nx + (rx - nx) / dist * step;
  const ey = dist < step ? ry : ny + (ry - ny) / dist * step;

  if (!segmentFree(nx, ny, ex, ey)) return; // Skip this sample if the extension hits a wall

  nodes.push({ x: ex, y: ey });
  parents.push(ni);

  // Check if the new node is within reach of the goal
  if (Math.hypot(ex - GOAL.x, ey - GOAL.y) < GOAL_RADIUS) {
    // Trace parent pointers back to start
    const path = [];
    let idx = nodes.length - 1;
    while (idx !== -1) { path.unshift(nodes[idx]); idx = parents[idx] ?? -1; }
    if (parents[0] === undefined) path; // root sentinel
    pathNodes = path;
    return true; // Signal path found
  }
  return false;
}

let iters = 0;
function loop() {
  const speed = +document.getElementById('speed').value;
  for (let s = 0; s < speed; s++) {
    iters++;
    if (rrtStep()) {
      draw();
      setStatus(i18nFmt('Path found in %n% iterations!', { n: iters }), 'ok');
      running = false;
      document.getElementById('btnRun').disabled = false;
      return;
    }
    if (iters > 8000) {
      draw();
      setStatus('Could not reach the goal. Try resetting.', 'fail');
      running = false;
      document.getElementById('btnRun').disabled = false;
      return;
    }
  }
  draw();
  setStatus(i18nFmt('Growing tree… %n% nodes', { n: iters }), 'running');
  animId = requestAnimationFrame(loop);
}

function run() {
  if (running) return;
  if (pathNodes) return; // stop if path already found
  running = true;
  document.getElementById('btnRun').disabled = true;
  setStatus('Growing tree…', 'running');
  animId = requestAnimationFrame(loop);
}

function reset() {
  if (animId) cancelAnimationFrame(animId);
  nodes = [{ x: START.x, y: START.y }]; parents = [undefined];
  pathNodes = null; running = false; iters = 0;
  document.getElementById('btnRun').disabled = false;
  draw();
  setStatus('Click Run to grow the RRT tree.', '');
}

// Keep slider value labels in sync
document.getElementById('stepSize').addEventListener('input', function() {
  document.getElementById('stepVal').textContent = this.value;
});
document.getElementById('speed').addEventListener('input', function() {
  document.getElementById('speedVal').textContent = this.value;
});

document.getElementById('btnRun').addEventListener('click', run);
document.getElementById('btnReset').addEventListener('click', reset);

reset();
Result
Console

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.

The Real Complexity

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→∞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(nlog⁡n)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/rrt/Content licensed under CC BY-NC 4.0.