RRT*

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."

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.

<!-- {{c_layout_comment}} -->
<div class="toolbar">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="stats">
  <span>{{label_samples}}: <b id="count">0</b></span>
  <span>{{label_path_len}}: <b id="pathlen">—</b></span>
</div>
<canvas id="canvas" width="480" height="360"></canvas>
<div class="legend">
  <span class="dot green"></span> {{legend_start}}
  <span class="dot red"></span> {{legend_goal}}
  <span class="dot gray"></span> {{legend_obstacle}}
</div>
<p class="hint">{{hint_rewire}}</p>

/* {{c_base_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; }

// Code not found

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.

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

• Asymptotic optimality: Karaman and Frazzoli proved that as the sample count $n \to \infty$, the cost of the path returned by RRT* converges almost surely to the optimal cost $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 $r_n = \gamma \left(\frac{\log n}{n}\right)^{1/d}$, where $d$ is the dimension of the space. This radius shrinks as $n$ grows, but slowly enough that the algorithm still finds every shortcut. The number of neighbors checked per step is $O(\log n)$.
• Computational cost: each sample takes $O(\log n)$ time for the nearest-neighbor search and rewiring. Over $n$ samples the total work is $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.

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.

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.