Introduction

A robot needs to move from A to B without hitting obstacles. One elegant approach is to grow a random tree: pick a random point in space, connect it to the nearest node already in the tree, and repeat until the tree reaches the goal. This is the idea behind RRT (Rapidly-exploring Random Tree), introduced by Steven LaValle in 1998.

RRT is fast and handles high-dimensional spaces well — but the path it finds is not particularly good. The tree grows in random directions and the route it eventually reaches the goal by is typically jagged and far from optimal. You can run RRT for as long as you like and it will never improve the path it already found.

RRT* (pronounced "RRT-star"), introduced by Sertac Karaman and Emilio Frazzoli in 2011, adds a single crucial insight: after each new node is inserted, rewire the tree so that nearby nodes adopt the new node as their parent whenever that gives them a shorter path from the start. This tiny change makes the algorithm asymptotically optimal — as the number of samples grows, the path length is guaranteed to converge to the true shortest path.

The difference between RRT and RRT* is the difference between "finds a path" and "finds the best path."

Try It

The canvas below runs RRT* in 2D. A start (green) and goal (red) are fixed; obstacles are the gray rectangles. Press Step to add one sample at a time or Run to animate continuously.

<!-- RRT* demo: toolbar + stats + canvas + legend -->
<div class="toolbar">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="stats">
  <span>Samples: <b id="count">0</b></span>
  <span>Path length: <b id="pathlen">—</b></span>
</div>
<canvas id="canvas" width="480" height="360"></canvas>
<div class="legend">
  <span class="dot green"></span> Start
  <span class="dot red"></span> Goal
  <span class="dot gray"></span> Obstacle
</div>
<p class="hint">Each sample may <b>rewire</b> nearby nodes to shorter paths. Watch the orange path shorten as the tree grows.</p>

/* base layout styles */
* { box-sizing: border-box; margin: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: #fff; padding: .5rem; }
.toolbar { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.stats { font-size: .9rem; display: flex; gap: 1.4rem; margin-bottom: .4rem; color: #333; }
canvas { display: block; border: 1px solid #d0d7de; border-radius: 6px; max-width: 100%; }
.legend { display: flex; gap: 1rem; font-size: .82rem; margin-top: .35rem; align-items: center; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; margin-right: 3px; }
.dot.green { background: #2a9d2a; }
.dot.red { background: #d62828; }
.dot.gray { background: #aaa; }
.hint { font-size: .85rem; color: #555; margin-top: .5rem; line-height: 1.5; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* RRT* (Karaman & Frazzoli 2011) — asymptotically optimal sampling-based planner. */
/* Key insight: after inserting a node, rewire nearby nodes through it if that lowers their cost. */

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;

/* Scene constants */
const START = { x: 40, y: 320 };
const GOAL  = { x: 440, y: 40 };
const GOAL_RADIUS = 20;
const STEP_SIZE = 28;
const REWIRE_RADIUS_FACTOR = 2.5; /* rewire ball = factor * STEP_SIZE */

/* Rectangular obstacles {x,y,w,h} */
const OBSTACLES = [
  { x: 120, y: 80,  w: 60, h: 180 },
  { x: 270, y: 140, w: 60, h: 180 },
  { x: 190, y: 20,  w: 50, h: 80  }
];

/* Tree state */
let nodes = [];   /* each node: {x,y,parent,cost} */
let edges = [];   /* pairs [parentNode, childNode] */
let path  = [];   /* current best path from start to goal */
let goalNode = null;
let animId = null;
let running = false;

/* Initialise / reset tree */
function init() {
  nodes = [{ x: START.x, y: START.y, parent: null, cost: 0 }];
  edges = [];
  path = [];
  goalNode = null;
  document.getElementById('count').textContent = '0';
  document.getElementById('pathlen').textContent = '—';
  draw();
}

/* Collision detection helpers */
function segmentHitsRect(ax, ay, bx, by, rect) {
  /* Parametric line-AABB intersection (slab method) */
  const rx1 = rect.x, ry1 = rect.y, rx2 = rect.x + rect.w, ry2 = rect.y + rect.h;
  const dx = bx - ax, dy = by - ay;
  let tmin = 0, tmax = 1;
  if (Math.abs(dx) < 1e-9) { if (ax < rx1 || ax > rx2) return false; }
  else {
    const t1 = (rx1 - ax) / dx, t2 = (rx2 - ax) / dx;
    tmin = Math.max(tmin, Math.min(t1, t2));
    tmax = Math.min(tmax, Math.max(t1, t2));
    if (tmin > tmax) return false;
  }
  if (Math.abs(dy) < 1e-9) { if (ay < ry1 || ay > ry2) return false; }
  else {
    const t1 = (ry1 - ay) / dy, t2 = (ry2 - ay) / dy;
    tmin = Math.max(tmin, Math.min(t1, t2));
    tmax = Math.min(tmax, Math.max(t1, t2));
    if (tmin > tmax) return false;
  }
  return true;
}

function pointInRect(px, py, rect) {
  return px >= rect.x && px <= rect.x + rect.w && py >= rect.y && py <= rect.y + rect.h;
}

function collides(ax, ay, bx, by) {
  return OBSTACLES.some(r => segmentHitsRect(ax, ay, bx, by, r) || pointInRect(bx, by, r));
}

/* Euclidean distance */
function dist(a, b) { return Math.hypot(a.x - b.x, a.y - b.y); }

/* Steer from 'from' toward 'to' by at most STEP_SIZE */
function steer(from, to) {
  const d = dist(from, to);
  if (d <= STEP_SIZE) return { x: to.x, y: to.y };
  const t = STEP_SIZE / d;
  return { x: from.x + (to.x - from.x) * t, y: from.y + (to.y - from.y) * t };
}

/* One RRT* iteration */
function step() {
  /* Sample a random point and find nearest node */
  const rx = Math.random() * W, ry = Math.random() * H;
  const nearest = nodes.reduce((a, b) => dist(b, { x: rx, y: ry }) < dist(a, { x: rx, y: ry }) ? b : a);
  const np = steer(nearest, { x: rx, y: ry });

  if (collides(nearest.x, nearest.y, np.x, np.y)) return; /* skip if path to new point collides */

  /* Choose best parent within rewire ball */
  const rewireR = REWIRE_RADIUS_FACTOR * STEP_SIZE;
  const near = nodes.filter(n => dist(n, np) < rewireR && !collides(n.x, n.y, np.x, np.y));
  let bestParent = nearest, bestCost = nearest.cost + dist(nearest, np);
  for (const n of near) {
    const c = n.cost + dist(n, np);
    if (c < bestCost) { bestParent = n; bestCost = c; }
  }

  const newNode = { x: np.x, y: np.y, parent: bestParent, cost: bestCost };
  nodes.push(newNode);
  edges.push([bestParent, newNode]);

  /* Rewire: try to improve nearby nodes through newNode */
  for (const n of near) {
    if (n === bestParent) continue;
    const c = bestCost + dist(newNode, n);
    if (c < n.cost && !collides(newNode.x, newNode.y, n.x, n.y)) {
      /* reparent this neighbor through newNode */
      edges.splice(edges.findIndex(e => e[1] === n), 1);
      n.parent = newNode;
      n.cost = c;
      edges.push([newNode, n]);
      /* propagate updated cost to descendants */
      propagate(n);
    }
  }

  document.getElementById('count').textContent = nodes.length;

  /* Check if new node reached goal */
  if (dist(newNode, GOAL) < GOAL_RADIUS) {
    if (!goalNode || newNode.cost < goalNode.cost) {
      goalNode = newNode;
      updatePath();
    }
  } else if (goalNode) {
    updatePath(); /* refresh path in case rewiring shortened it */
  }

  draw();
}

/* Recursively update costs of descendants */
function propagate(node) {
  /* when a node's cost changes, propagate to all children */
  const children = nodes.filter(n => n.parent === node);
  for (const child of children) {
    child.cost = node.cost + dist(node, child);
    propagate(child);
  }
}

function updatePath() {
  path = [];
  let n = goalNode;
  while (n) { path.unshift(n); n = n.parent; }
  const len = goalNode ? Math.round(goalNode.cost) : 0;
  document.getElementById('pathlen').textContent = len;
}

/* Render everything */
function draw() {
  ctx.clearRect(0, 0, W, H);

  /* draw obstacles */
  ctx.fillStyle = '#c8cdd4';
  OBSTACLES.forEach(r => ctx.fillRect(r.x, r.y, r.w, r.h));

  /* draw tree edges */
  ctx.strokeStyle = '#8dabbe';
  ctx.lineWidth = 1;
  edges.forEach(([a, b]) => {
    ctx.beginPath(); ctx.moveTo(a.x, a.y); ctx.lineTo(b.x, b.y); ctx.stroke();
  });

  /* draw current best path in orange */
  if (path.length > 1) {
    ctx.strokeStyle = '#e07b00';
    ctx.lineWidth = 2.5;
    ctx.beginPath();
    path.forEach((n, i) => i === 0 ? ctx.moveTo(n.x, n.y) : ctx.lineTo(n.x, n.y));
    ctx.stroke();
  }

  /* draw goal circle (dashed) */
  ctx.strokeStyle = '#d62828';
  ctx.lineWidth = 1.5;
  ctx.setLineDash([4, 3]);
  ctx.beginPath(); ctx.arc(GOAL.x, GOAL.y, GOAL_RADIUS, 0, Math.PI * 2); ctx.stroke();
  ctx.setLineDash([]);

  /* draw start (green) and goal (red) dots */
  [{ pt: START, color: '#2a9d2a' }, { pt: GOAL, color: '#d62828' }].forEach(({ pt, color }) => {
    ctx.fillStyle = color;
    ctx.beginPath(); ctx.arc(pt.x, pt.y, 6, 0, Math.PI * 2); ctx.fill();
  });
}

/* Run / Pause toggle */
function toggleRun() {
  running = !running;
  document.getElementById('btn-run').textContent = running ? 'Pause' : 'Run';
  document.getElementById('btn-step').disabled = running;
  if (running) loop();
}

function loop() {
  if (!running) return;
  for (let i = 0; i < 3; i++) step(); /* add 3 nodes per animation frame for smooth animation */
  animId = requestAnimationFrame(loop);
}

document.getElementById('btn-step').addEventListener('click', step);
document.getElementById('btn-run').addEventListener('click', toggleRun);
document.getElementById('btn-reset').addEventListener('click', () => {
  running = false;
  cancelAnimationFrame(animId);
  document.getElementById('btn-run').textContent = 'Run';
  document.getElementById('btn-step').disabled = false;
  init();
});

init();
Result
Console

Watch the path length counter: it decreases every time a rewiring finds a shorter route. Early on the path is long and zigzaggy; as more samples land near the direct line, the tree rewires and the path straightens. This is asymptotic optimality made visible.

The Real Complexity

RRT* is one of the rare algorithms where theoretical guarantees are tight.

  • Asymptotic optimality: Karaman and Frazzoli proved that as the sample count n→∞n \to \infty, the cost of the path returned by RRT* converges almost surely to the optimal cost c∗c^*. Basic RRT is not asymptotically optimal — it gets stuck at the first path it finds.
  • Rewiring radius: at each step, RRT* considers rewiring within a ball of radius rn=γ(log⁡nn)1/dr_n = \gamma \left(\frac{\log n}{n}\right)^{1/d}, where dd is the dimension of the space. This radius shrinks as nn grows, but slowly enough that the algorithm still finds every shortcut. The number of neighbors checked per step is O(log⁡n)O(\log n).
  • Computational cost: each sample takes O(log⁡n)O(\log n) time for the nearest-neighbor search and rewiring. Over nn samples the total work is O(nlog⁡n)O(n \log n) — only a logarithmic overhead over basic RRT.
  • The catch: in high dimensions (think a 7-DOF robot arm), filling the space with enough samples to see meaningful improvement is expensive. The curse of dimensionality means the rewiring radius shrinks too fast and convergence slows dramatically.
  • Optimality vs. real-time: RRT* is an anytime algorithm — it can be interrupted at any point and still returns a valid path, just not yet optimal. Getting a certifiably optimal path in finite time is a harder open problem related to non-convex optimization.

Where It Matters

The gap between "a path" and "a good path" is enormous in the real world, and RRT* closes it:

  • Autonomous vehicles: lane changes and parking maneuvers are planned with RRT*-family algorithms where jerkiness costs energy and comfort.
  • Robotic arms: industrial and surgical manipulators use RRT* to find joint-space trajectories that minimize travel time or energy while avoiding collisions.
  • Drone and UAV navigation: 3D obstacle avoidance at high speed requires paths that are both feasible and short; RRT* variants handle kinodynamic constraints natively.
  • Game AI: character navigation in large 3D environments benefits from anytime planners that can be interrupted when the game needs the CPU elsewhere.
  • Informed RRT*: a later variant biases sampling toward an ellipsoidal region that can only contain shorter paths, speeding up convergence without sacrificing the optimality guarantee.

Compared with classical grid search like Dijkstra's algorithm, RRT* scales to continuous, high-dimensional spaces where a grid would be computationally impossible. The trade-off is that convergence is probabilistic rather than exact.

Conclusion

RRT* is a beautiful example of how a single algorithmic idea can change a problem's character entirely. Basic RRT is satisficing — it stops the moment it finds a path. RRT* is optimizing — it never stops looking for a shorter one.

The rewiring step costs only a logarithmic overhead, yet it delivers an asymptotic optimality guarantee that took years to prove and that basic RRT can never have. Every sample that lands near the direct route nudges the path a little straighter, and in the limit the tree converges to the true shortest path through the obstacle field.

The next time you see a self-driving car smoothly navigate a parking lot, there is a good chance a descendant of RRT* is the reason the maneuver looks effortless — and not just possible.

Share this article

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

Comments

Loading comments...

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