RRT & RRT* motion planning

Planning a path for anything with more than a few degrees of freedom defeats grid search: a 6-DoF arm discretised at 20 values per joint has $20^6 = 6.4\times10^7$ cells, and a 12-DoF system is hopeless. Rapidly-exploring Random Trees sidestep the problem entirely by never building a grid — they sample the configuration space and grow a tree toward the unexplored parts of it. This page derives the Voronoi bias that makes RRT work, the rewiring that makes RRT* optimal, and the specific places both of them fail.

Symbols used on this page are defined in the Nomenclature → planning.

The sampling-and-consensus idea here is closely related to RANSAC: both replace an intractable search with randomised sampling plus a cheap test.

1 · Configuration space

1.1 The abstraction

Planning happens not in the workspace but in configuration space $\mathcal C$, where one point is one complete pose of the robot. For a planar mobile base $\mathcal C = \mathbb R^2$ or $SE(2)$; for a 7-DoF arm it is a 7-torus; for a free-flying rigid body it is $SE(3)$.

$$ \mathcal C = \mathcal C_{\text{free}} \;\cup\; \mathcal C_{\text{obs}}, \qquad \text{find } \sigma : [0,1] \to \mathcal C_{\text{free}} \ \text{ with } \sigma(0) = \mathbf q_{\text{init}},\ \sigma(1) \in \mathcal Q_{\text{goal}} . $$

The crucial point is that $\mathcal C_{\text{obs}}$ is never built explicitly. Computing the exact obstacle region for an articulated robot is intractable; instead the planner only ever asks a collision checker whether a specific configuration is free. Everything in this family is organised around making as few of those queries as possible, because the checker is the expensive part.

1.2 Why sampling beats discretisation

Sampling methods trade a guarantee for tractability: they give up resolution-completeness and gain independence from $d$ in the representation (though not entirely in the sample complexity). PRM builds an undirected roadmap once and answers many queries; RRT grows a tree from one start toward one goal and is the right choice when the query is one-shot, which is the usual robotics case.

2 · RRT

2.1 The algorithm

Four primitives, and each one is a design decision:

2.2 The Voronoi bias — why it explores

This is the insight that makes RRT work, and it is easy to miss. Consider the Voronoi diagram of the existing vertices. A uniformly drawn sample lands in a given vertex's Voronoi region with probability proportional to that region's volume — and the vertices with the largest Voronoi regions are exactly those on the frontier of the explored area.

So uniform sampling in $\mathcal C$ produces a tree that preferentially extends from its frontier without any explicit frontier bookkeeping. The expansion is biased toward unexplored space as a free consequence of the nearest-neighbour rule. That is why the tree fans outward rather than densifying near the root, and it is the origin of "rapidly exploring" in the name.

2.3 Probabilistic completeness

If a feasible path exists with some clearance, the probability that RRT has found a solution after $n$ samples satisfies

$$ P(\text{failure after } n) \le a\,e^{-b n} \quad \longrightarrow \quad \lim_{n\to\infty} P(\text{success}) = 1 , $$

i.e. failure probability decays exponentially in the number of samples. The constants depend on the clearance of the solution corridor, which is where the practical caveat lives: a path through a narrow passage has small clearance, $b$ is tiny, and "exponential convergence" can still mean millions of samples (§5.2).

2.4 Goal bias

With probability $p$ (typically 5–10%) sample the goal instead of a random configuration. This pulls the tree toward the target and often reduces time-to-solution by an order of magnitude. The danger is over-biasing: at high $p$ the planner behaves like a greedy potential-field method and gets stuck behind the first obstacle between it and the goal, because it stops exploring. The uniform samples are what preserve completeness, so $p$ must stay well below 1.

3 · RRT*

3.1 What changes

RRT* keeps the sampling and steering but adds two steps, both operating on the set of vertices within a radius $r_n$ of the new node:

Step ① says: having decided where to put a node, choose its parent to minimise total path cost rather than edge length. Step ② is the important one — it lets already-placed nodes change their minds. That single capability is the difference between a planner that is stuck with its history and one that keeps improving, and it is why an RRT* tree visibly straightens as it runs.

3.2 The connection radius

The radius cannot be a constant. If it is too large, every new node checks every other node and cost becomes quadratic; too small and the rewiring never connects anything, losing optimality. The radius that preserves both properties shrinks with $n$:

$$ r_n = \min\left\{ \gamma \left(\frac{\log n}{n}\right)^{1/d},\ \eta \right\}, \qquad \gamma \gt \gamma^\star = 2\left(1 + \tfrac1d\right)^{1/d} \left(\frac{\mu\!\left(\mathcal C_{\text{free}}\right)}{\zeta_d}\right)^{1/d} $$

with $\mu(\mathcal C_{\text{free}})$ the volume of free space, $\zeta_d$ the volume of the unit $d$-ball, and $d$ the dimension. The $\log n / n$ form is the key: it shrinks fast enough that the expected number of neighbours stays $O(\log n)$ — keeping the per-iteration cost logarithmic — but slowly enough that the graph remains connected in the limit, which is what the optimality proof needs. This is the same $\log n / n$ threshold that appears in random geometric graph connectivity.

A common variant, k-nearest RRT*, connects to the $k = k_{\text{RRT}}\log n$ nearest neighbours instead of using a radius, with $k_{\text{RRT}} \gt e(1 + 1/d)$. It avoids having to estimate $\mu(\mathcal C_{\text{free}})$, which is awkward in practice, and is usually the easier implementation.

3.3 Asymptotic optimality

$$ \lim_{n\to\infty} c\!\left(\sigma_n^{\text{RRT*}}\right) = c^\star \quad \text{almost surely}, \qquad\text{while}\qquad P\!\left(\lim_{n\to\infty} c\!\left(\sigma_n^{\text{RRT}}\right) = c^\star\right) = 0 . $$

Both planners have the same asymptotic complexity, $O(n\log n)$, so RRT* buys optimality for a constant factor — roughly 2–5× in practice, from the extra collision checks in the near set. Note what asymptotic optimality does not promise: nothing about the path at any finite $n$. The convergence is often slow, with most of the improvement arriving early and a long tail of diminishing refinement.

3.4 The simulation

This is a real planner — sampling, k-d-free nearest search, steering, discrete edge collision checking, and for RRT* the choose-parent and rewire loops with cost propagation. The experiments that make the point:

• Toggle the mode. In RRT the cost curve is flat after the first solution; in RRT* it keeps descending. Same samples, same obstacles.
• Watch the amber rewired edges flash as neighbours re-parent through a new node, and the tree straighten over time.
• Compare ratio to bound — RRT* approaches the straight-line lower bound where geometry allows; RRT typically plateaus 20–50% above it.
• Set goal bias to 0 and watch time-to-solution grow; set it to 30% and watch it get stuck behind obstacles on some seeds (§2.4).
• Raise the step size and the rejection count climbs — large steps are more likely to cross an obstacle.

4 · Collision checking

This is where the time goes — typically 90%+ of planner runtime — so it is where optimisation belongs.

5 · Where these planners struggle

5.1 The metric

NEAREST needs a distance, and the Euclidean norm on configuration coordinates is usually the wrong one. For $SE(2)$ you must combine translation and rotation — which have different units — so a weighting is required and that weighting changes the planner's behaviour. For a manipulator, equal joint distances produce very different end-effector motions. Worse, for a system with dynamics the relevant distance is the cost-to-go of the underlying control problem, not any geometric norm. A poor metric degrades the Voronoi bias and the planner explores badly for reasons that look like bad luck.

5.2 Narrow passages

The probability of sampling into a corridor is proportional to its volume fraction, so a passage occupying $10^{-6}$ of $\mathcal C$ needs on the order of $10^6$ samples to enter. This is the canonical hard case for all sampling planners. Mitigations: bridge-test sampling (deliberately seek configurations between two obstacles), medial-axis or retraction sampling, obstacle-based sampling, or a workspace decomposition that biases samples into likely corridors.

5.3 Other practical issues

• Jagged paths. Raw RRT output is not smooth and not directly executable. Post-process with shortcutting (repeatedly try to connect non-adjacent waypoints directly) then fit splines. Shortcutting is cheap and removes most of the visual ugliness — it is standard practice, and worth doing even with RRT*.
• Memory. The tree grows without bound; RRT* also stores costs and must propagate them.
• No anytime guarantee at finite $n$. Asymptotic optimality says nothing about the path you have when the time budget expires.
• Dynamic environments. Both are single-shot planners. Replanning from scratch is often acceptable; otherwise use RRTX or a dynamic variant that repairs the tree.
• High dimension. RRT* degrades as $d$ grows because $r_n \propto (\log n/n)^{1/d}$ shrinks very slowly, so near-sets stay large and rewiring gets expensive.

6 · The variant landscape

7 · Practical checklist

• Use a k-d tree for nearest-neighbour queries; naive linear search dominates at scale.
• Set the collision-check resolution from the thinnest obstacle, or inflate obstacles to make the check conservative (§4).
• Goal bias 5–10%. Enough to help, not enough to destroy exploration.
• Step size $\eta$ around 5–10% of the environment scale: too small is slow, too large raises rejection rates.
• Choose the distance metric deliberately, and weight rotation against translation explicitly (§5.1).
• Use k-nearest rather than radius for RRT* unless you can estimate the free-space volume.
• Always post-process with shortcutting then smoothing.
• Seed deterministically in tests. These are randomised algorithms, so an unseeded planner gives irreproducible failures.
• Report cost against a lower bound (straight-line or a relaxed problem), not in isolation.
• Validate the returned path with an independent checker at fine resolution before executing it. This catches tunnelling and off-by-one errors in the planner's own checks.

8 · Further reading

• LaValle (1998), "Rapidly-Exploring Random Trees: A New Tool for Path Planning." The original technical report.
• LaValle & Kuffner (2001), "Randomized Kinodynamic Planning," IJRR. RRT with dynamics, and the clearest statement of the Voronoi bias.
• Kuffner & LaValle (2000), "RRT-Connect: An Efficient Approach to Single-Query Path Planning," ICRA.
• Karaman & Frazzoli (2011), "Sampling-based Algorithms for Optimal Motion Planning," IJRR 30(7). The key paper — proves RRT's suboptimality, introduces RRT* and PRM*, and derives the $r_n$ radius of §3.2.
• Gammell, Srinivasa & Barfoot (2014), "Informed RRT*," IROS.
• Gammell et al. (2015), "Batch Informed Trees (BIT*)," ICRA.
• LaValle, Planning Algorithms (Cambridge, 2006). Freely available online; chapter 5 is the definitive treatment of sampling-based planning.
• Choset et al., Principles of Robot Motion. Strong on configuration space and collision detection.
• Hsu, Latombe & Motwani (1997) on the narrow-passage problem; Hsu et al. (2003) on bridge-test sampling.
• Otte & Frazzoli (2016), "RRTX: Asymptotically optimal single-query sampling-based motion planning with quick replanning," IJRR.
• OMPL (Open Motion Planning Library) — the reference implementations of essentially every planner in §6, and worth reading for the abstractions as much as the algorithms.

Related pages: RANSAC (the other randomised-sampling algorithm) · GraphSLAM (the map a planner consumes) · ICP · Perception stack