RRT Path Planning

How RRT works

Picture a robot arm or a drone that has to get from a start pose to a goal pose without hitting anything. The set of all poses it can hold is its configuration space (C-space) — and for a 6-joint arm that space has six dimensions. Drawing a map of every legal pose is hopeless. RRT skips the map entirely. It plants a single node at the start and then grows a tree, one random branch at a time, until a branch lands close enough to the goal.

Each iteration is four short steps. They are the whole algorithm:

loop:
  q_rand  = sample a random configuration   (uniform, or goal with prob p_goal)
  q_near  = the node in the tree nearest to q_rand   (Euclidean / C-space metric)
  q_new   = q_near + step·(q_rand - q_near)/|q_rand - q_near|   (clamp to step length ε)
  if edge q_near → q_new is collision-free:
      add q_new to the tree with parent q_near
      if |q_new - q_goal| < goal_radius:  return path by walking parents back to start

The single most important line is the nearest-node step. Because we always extend whatever node is closest to a uniformly random sample, the tree is biased to grow toward the largest unexplored regions — formally, toward the largest Voronoi cells. That is the "rapidly-exploring" property: a few hundred samples spread out and fill open space instead of clustering near the start. The fixed step length ε keeps branches short enough that the straight-line collision check between q_near and q_new is trustworthy.

The math: completeness, not optimality

RRT makes a precise promise and refuses to make a different one. The promise it keeps is probabilistic completeness: if a collision-free path exists, the probability that RRT has found one after n samples goes to 1 as n grows.

P(found path after n samples) → 1   as n → ∞     (probabilistic completeness)

Failure-to-connect probability decays roughly:
    P(fail | n) ≤ a · e^(−b·n)        for constants a,b > 0 set by free-space geometry

The promise RRT does NOT keep:
    cost(RRT path)  is NOT → cost(optimal path)     even as n → ∞
    Typical RRT path is 1.1× to 1.5× the optimal length, with jagged corners.

The reason plain RRT is not optimal is that once a node is added, its parent is fixed forever. RRT* fixes this by spending more work per node:

RRT* extra steps after creating q_new:
  Near = nodes within radius r_n of q_new,   r_n = γ·(log n / n)^(1/d)
  1. CHOOSE-PARENT: pick parent in Near minimizing  cost(parent) + dist(parent, q_new)
  2. REWIRE:       for each x in Near, if cost(q_new)+dist(q_new,x) < cost(x):
                       make q_new the new parent of x

Result:  cost(RRT* path) → cost(optimal path)   as n → ∞   (asymptotically optimal)

The shrinking radius r_n = γ·(log n / n)^(1/d) is the heart of the optimality proof (Karaman & Frazzoli, 2011): it shrinks slowly enough that the tree stays connected, but fast enough that the per-iteration neighbor count stays bounded, keeping the amortized cost only a logarithmic factor above plain RRT.

Worked example: a drone in a 10 m room

Take a quadrotor flying through a 10 m × 10 m × 4 m room cluttered with shelving. We plan in the 3-D position space (treating the drone as a point with a safety radius baked into the obstacles).

Workspace diagonal:   √(10² + 10² + 4²) ≈ 14.7 m
Step length ε:         0.03 × 14.7 ≈ 0.44 m   (3% of the diagonal)
Goal bias p_goal:      0.05  (sample the goal directly 1 time in 20)
Goal radius:           0.30 m
Collision resolution:  check edge every 0.05 m  (finer than the 0.6 m thinnest gap)

Path requires roughly 9 m of travel ≈ 20 hops of 0.44 m, but the tree
explores sideways too, so a typical solve adds ~400–900 nodes before
a branch lands inside the goal radius.

Now the cost knob most people get wrong: nearest-neighbor lookup. The naive nearest-node search is O(n) per iteration, so 900 iterations cost ≈ 900 × 900 / 2 ≈ 400,000 distance evaluations — fine. But scale to a 7-DOF arm needing 50,000 nodes and the linear search becomes the bottleneck: 50,000² / 2 = 1.25 billion comparisons. Swapping in a k-d tree drops each query to O(log n), turning that 1.25 billion into about 50,000 × 16 ≈ 800,000 — a roughly 1,500× speedup. Production planners (OMPL, MoveIt) all use a spatial index for exactly this reason.

RRT vs other motion planners

	RRT	RRT*	RRT-Connect	PRM	A* on grid	Potential field
Strategy	Single growing tree	Tree + rewiring	Two trees, greedy connect	Roadmap of samples	Exhaustive grid search	Gradient descent on a field
Query type	Single-query	Single-query	Single-query	Multi-query (reuse map)	Single-query	Single-query (reactive)
Optimal?	No	Asymptotically	No	No (PRM) / asymptotic (PRM*)	Yes (on the grid)	No
Completeness	Probabilistic	Probabilistic	Probabilistic	Probabilistic	Resolution-complete	None (local minima)
Scales to high DOF?	Yes	Yes	Yes (fastest)	Yes	No (curse of dimension)	Yes but unreliable
Per-iteration cost	Low	2–5× RRT	Low	Map build is heavy	High in high-D	Very low
Typical home	Quick feasible paths	Cost-optimal arm/vehicle paths	Real-time arm planning	Static factory cells	2-D mobile robots, games	Local obstacle avoidance

Variants: Connect, *, kinodynamic, informed

• RRT-Connect (LaValle & Kuffner, 2000). Grows two trees — one from the start, one from the goal — and on each iteration greedily extends one tree all the way toward the other's newest node until it hits an obstacle. Bidirectional + greedy makes it dramatically faster on hard problems; it is the workhorse inside MoveIt for robot arms. The trade-off: it gives up even the loose path quality of plain RRT.
• RRT* (Karaman & Frazzoli, 2011). The asymptotically-optimal version with choose-parent and rewire steps. Costs more per iteration but the path keeps improving the longer you let it run, so it suits planners that have a time budget to spend.
• Informed RRT* (Gammell, 2014). Once a first solution of cost c is found, restrict all future samples to the prolate-hyperspheroid (the ellipse with the start and goal as foci) that could possibly contain a shorter path. This stops wasting samples on regions that can't help, and converges to optimal far faster.
• Kinodynamic RRT. Plain RRT assumes a holonomic robot that can move in any direction instantly. A car can't slide sideways; a drone has momentum. Kinodynamic RRT samples in the state space (position + velocity) and extends by forward-simulating the robot's dynamics for a short control input, so every edge is a physically executable maneuver.
• RRT* with goal biasing. Nearly every real implementation samples the goal directly with probability 5–10% to pull the tree toward the target without losing the Voronoi space-filling behavior.

Where RRT is used

System	Variant	Configuration space	Notes
DARPA Urban Challenge (MIT "Talos", 2007)	Closed-loop kinodynamic RRT	Vehicle state (x, y, heading, speed)	Planned executable maneuvers in traffic; an early flagship use of RRT (Talos finished 4th; the winning CMU "Boss" used a lattice planner)
MoveIt / OMPL on industrial arms	RRT-Connect (default)	6–7 joint angles	The out-of-the-box planner for ROS manipulation
Autonomous-car motion planning	Informed RRT* / Hybrid-A*	2-D pose + curvature	RRT* used for smooth, near-optimal lane-change and parking trajectories
Quadrotor flight through clutter	RRT* + trajectory smoothing	3-D position (+ velocity)	RRT gives a feasible corridor; a smoother fits a minimum-snap polynomial
Surgical / assembly robots	RRT-Connect, PRM	High-DOF arm in tight cavities	Narrow-passage problems where grid search is infeasible
Protein folding & molecular docking	RRT variants	Backbone dihedral angles (very high-D)	RRT's dimension-agnostic sampling transfers from robotics to computational biology

When to use RRT

• The configuration space is high-dimensional. Any robot with more than ~4 degrees of freedom — arms, humanoids, multi-body systems — where a uniform grid blows up combinatorially. This is RRT's home turf.
• You need a feasible path fast, not necessarily the best one. Plain RRT or RRT-Connect returns a path in milliseconds to a few seconds; use it when "good enough, now" beats "optimal, eventually."
• Obstacles are described by a collision checker, not a closed-form map. RRT only ever asks "is this edge collision-free?" so it works with arbitrary mesh-based or swept-volume collision tests.
• Single-query problems. If you plan one path and discard the structure, RRT beats PRM (which amortizes a heavy roadmap build across many queries).

Reach for something else when: the space is low-dimensional and you want a provably optimal path (use A* or Dijkstra on a grid); you will run thousands of queries in the same static environment (build a PRM once); or the robot must react to moving obstacles in real time (a local potential-field or DWA controller running under a global RRT plan).

Common misconceptions and pitfalls

• "RRT finds the shortest path." No. Plain RRT stops at the first path it reaches, which is typically 10–50% longer than optimal and visibly jagged. If you want short paths you need RRT* (and patience) or a post-processing smoothing/shortcutting pass. Confusing RRT with RRT* is the single most common error in write-ups.
• Skipping edge collision-checking. Checking only the endpoint q_new for collision is a classic bug: a straight extension can pass clean through a thin wall while both endpoints are in free space. Always interpolate along the edge at a resolution finer than the thinnest obstacle.
• Linear nearest-neighbor search at scale. The naive O(n) nearest-node loop is fine for a few hundred nodes and catastrophic for tens of thousands. Use a k-d tree or GNAT; the nearest-neighbor query, not collision checking, is the asymptotic bottleneck in large planning problems.
• Goal bias set too high. Setting p_goal to 30–50% turns RRT into a greedy charge at the goal that gets pinned behind the first obstacle and loses the space-filling Voronoi property. Keep it at 5–10%.
• Expecting RRT to prove no path exists. RRT can confirm a path by finding one, but it can never declare "infeasible" — it just keeps sampling. You must impose an iteration or time cap and treat the cap as a (non-definitive) failure.
• Planning holonomically for a non-holonomic robot. Running plain RRT in position space for a car produces paths the car physically cannot follow (instant sideways jumps). Cars and drones need a kinodynamic RRT that respects the equations of motion on every edge.