Sampling-Based Planning: RRT and RRT*
RRT finds a feasible path fast but the path is usually ugly — RRT* fixes this asymptotically, and both fail in narrow passages at rates that practitioners find unacceptable.
🎯 By the end you'll understand
How RRT grows a tree through configuration space by random sampling and nearest-neighbor extension, and why that gives probabilistic completeness but not optimality. How RRT* adds a rewiring step that guarantees asymptotic optimality. Why path cost monotonically decreases for RRT* but not RRT. When sampling-based planners outperform grid search — specifically in high-dimensional spaces. How PRM amortizes planning cost over many queries. And the narrow passage problem: why both algorithms require exponentially more samples to connect through a tight corridor, making them unreliable in corridors without workspace-specific biasing.
KEY INSIGHTRandomness buys you coverage without exhaustion
A grid planner checks every cell. A sampling-based planner checks random cells and hopes the right ones turn up — but it can formally prove that hope converges to a guarantee.
Configuration space can be astronomically large. A 7-DOF arm has a 7-dimensional C-space; a mobile manipulator has 9 or more. A grid fine enough to represent obstacle boundaries at centimeter resolution across 7 dimensions contains on the order of 1014 cells — far too many to enumerate. The core insight of sampling-based planning is that you do not need to enumerate C-space; you only need to sample it densely enough that some samples land in the free region and form a connected graph. RRT does this incrementally, growing a tree one random sample at a time. The tree is biased toward unexplored space, so it expands efficiently without precomputing the whole space.
Sampling-based planners trade completeness for scalability. A grid A* planner is complete (if a path exists it will find it, given a fine enough grid) but scales exponentially with dimensionality. An RRT is only probabilistically complete — the probability of finding a path approaches 1 as the number of samples approaches infinity — but it scales polynomially with dimensionality. In practice, for a 7-DOF arm in a cluttered workspace, RRT finds a feasible path in milliseconds while grid search is intractable. The cost: the path is not optimal, and some environments (narrow passages) defeat the sampler unless you work much harder.
HOW IT WORKSHow RRT grows a tree
The RRT algorithm is elegant and short. Here is the full procedure, then the intuition.
Initialize the tree at the start
The tree T starts with a single node: the start configuration qstart. Nothing else is in the tree yet. The goal is to eventually connect the tree to a region near qgoal.
Sample a random configuration
Draw qrand uniformly at random from the entire C-space (with a small probability — typically 5–10% — of sampling qgoal directly, a "goal bias" that accelerates convergence). This is the only random step. Everything else is deterministic given qrand.
Find the nearest node in the tree
Compute qnear = argminq ∈ T d(q, qrand), where d is a distance metric in C-space (often Euclidean for positions, with careful weighting of angular joints). This is the nearest-neighbor lookup — the dominant computational cost for large trees.
Extend toward the sample
Take a step of fixed size ε from qnear in the direction of qrand. The new node is qnew = qnear + ε · (qrand − qnear) / |qrand − qnear|. This "step-limited extension" ensures each addition to the tree is small enough to collision-check efficiently. Alternatively, in the "connect" variant, extend all the way to qrand until a collision is hit.
Collision check the new edge
Check whether the straight-line path from qnear to qnew lies entirely in Cfree by discretizing the edge and testing each sample. If clear, add qnew to T and record (qnear, qnew) as a tree edge. If in collision, discard and return to step 2.
Check for goal connection
If d(qnew, qgoal) < goal radius rgoal, connect qnew to qgoal and trace back through the parent pointers to extract the path. Otherwise, go to step 2 and repeat.
There is a subtle but important bias baked into RRT that is not obvious from the pseudocode. When you draw qrand uniformly and then find the nearest tree node, nodes with large Voronoi regions — those that are spatially isolated from other tree nodes — are selected as qnear more often. This is the Voronoi bias: the tree preferentially expands toward unexplored regions of C-space, without any explicit exploration bookkeeping. It is why RRT covers space efficiently even without A*-style heuristics.
CORE CONCEPTProbabilistic completeness — what it means and what it doesn't
RRT is probabilistically complete: if a solution path exists, the probability that the algorithm finds it approaches 1 as the number of samples n → ∞. This is a formal guarantee, but it is weaker than the completeness guarantee of A* on a grid. Here is why.
Probabilistic completeness says: given enough samples, you will find a path. It says nothing about how many samples that requires. In an open C-space, RRT typically finds a path in a few hundred samples. In a C-space with a narrow passage — a corridor whose width in C-space is δ — the probability of any single sample landing inside the passage is proportional to δ/Vol(Cfree). If δ is small, this probability is tiny, and you need roughly 1/δ samples before the passage is bridged. For a passage 1 cm wide in a C-space that spans 1 m, that is 100× more samples. For a 1 mm passage, 1000×. This is the narrow passage problem, and it is the dominant practical failure mode of sampling-based planners.
Complete: if a solution exists, the algorithm finds it (in finite time, or with probability 1). Optimal: among all solutions, the algorithm finds the best one. Asymptotically optimal: as the number of samples approaches infinity, the cost of the found solution approaches the cost of the globally optimal solution. RRT is probabilistically complete but not optimal — it finds some feasible path and stops. RRT* is both probabilistically complete and asymptotically optimal — it keeps improving the path cost indefinitely.
RRT is also not optimal in a stronger sense than just "not finding the shortest path." The path it finds is usually jagged — the step-limited tree extensions produce many small edges that collectively take a long route around obstacles. Post-processing with path shortcutting (randomly pick two nodes on the path, check if direct connection is collision-free, replace the segment if so) typically reduces path length by 20–40%, but still does not approach the optimum.
CORE CONCEPTRRT* — one extra step, asymptotic optimality
RRT* (pronounced "RRT star") adds two operations to the basic RRT loop that together guarantee asymptotic optimality. The rest of the algorithm is identical.
Choose the best parent (not just the nearest)
Instead of connecting qnew to qnear (the nearest node in the tree), RRT* considers all nodes within a ball of radius r(n) centered on qnew, where r(n) = γ · (log n / n)1/d (γ is a problem-dependent constant, n is the current tree size, d is the C-space dimension). Among all nodes in this ball that can be connected to qnew without collision, it picks the one that minimizes the total cost from the root: cost(qmin) + d(qmin, qnew). This is the "choose parent" step. It directly reduces path cost at each insertion.
Rewire the tree through the new node
After inserting qnew with its best parent, RRT* checks every node q' in the same ball: can q' reach its current parent more cheaply via qnew? That is, is cost(qnew) + d(qnew, q') < cost(q')? If so, and if the edge (qnew, q') is collision-free, rewire q' so that its parent becomes qnew. Update the subtree cost recursively. This is the "rewire" step — it propagates cost improvements backward through the tree.
These two steps cost O(log n) additional nearest-neighbor lookups per sample and O(log n) additional collision checks — the algorithm remains nearly as fast per iteration as plain RRT, while guaranteeing that path cost decreases monotonically over time. There is a formal proof (Karaman and Frazzoli, 2011) that the cost converges to the optimum as n → ∞, and that without rewiring (plain RRT) the cost converges to a suboptimal value with probability 1.
Every time a new node is added, either (a) the new node provides a shorter route to the goal via rewiring, in which case the recorded path cost decreases, or (b) no improvement is found, in which case the cost stays the same. The path cost can never increase because we never remove a viable connection — we only add better alternatives. This is the mechanism that makes RRT* asymptotically optimal: the cost trajectory is a monotone decreasing sequence bounded below by the true optimum, so it must converge.
SEE ITRRT vs. RRT* live comparison
Both trees grow from the same start, use the same random seed, and navigate the same cluttered C-space. Watch how the path cost evolves. Toggle rewiring to switch between RRT and RRT*. Drag the narrow passage obstacle to make it thinner and observe the sample count spike.
IN PRACTICEKinodynamic planning for non-holonomic robots
FollowBot is a differential-drive robot. It cannot move sideways — its velocity is constrained: vy = 0 in the robot frame. This is a non-holonomic constraint. A kinodynamic RRT respects these constraints by replacing the straight-line extension step with a forward simulation of the robot's dynamics.
Instead of stepping from qnear toward qrand in a straight line, kinodynamic RRT samples a random control input u (e.g., left/right wheel velocities in some range) and simulates the robot's equations of motion for a short duration Δt. The resulting state qnew = f(qnear, u, Δt) is added to the tree if collision-free. This means every edge in the tree is a dynamically feasible trajectory segment — the robot can actually execute it without violating its motion constraints.
import numpy as np def diff_drive_simulate(q, u, dt): # q = (x, y, theta), u = (v_left, v_right), wheel_base = 0.24 m v_l, v_r = u wb = 0.24 # FollowBot wheel base v = (v_l + v_r) / 2.0 # linear velocity omega = (v_r - v_l) / wb # angular velocity x, y, th = q x_new = x + v * np.cos(th) * dt y_new = y + v * np.sin(th) * dt th_new = th + omega * dt return np.array([x_new, y_new, th_new]) def kinodynamic_extend(q_near, u_samples, dt, collision_fn): # try several random controls, keep the best non-colliding result best = None for u in u_samples: q_new = diff_drive_simulate(q_near, u, dt) if not collision_fn(q_near, q_new): best = (q_new, u) break # first valid; or score all and pick closest to q_rand return best
The cost of kinodynamic planning is higher: each collision check now requires simulating a trajectory rather than checking a straight line. In practice, ROS 2's Nav2 stack avoids full kinodynamic RRT for mobile bases — the DWA local planner handles kinematic constraints at the control level, while the global planner (typically A* or Dijkstra on a costmap) works with a simplified kinematic model. Kinodynamic RRT is most common in arm motion planning and aerial vehicle planning where the dynamics are tightly coupled to feasibility.
COMPARISONWhen sampling beats grid search (and when it doesn't)
The choice between sampling-based and grid-based planning is not aesthetic — it is driven by the dimensionality of the C-space and the query pattern.
| Property | Grid / A* | RRT / RRT* | PRM |
|---|---|---|---|
| Dimensionality scaling | Exponential — infeasible >4D | Polynomial — tractable to 10+D | Polynomial — preprocessing cost |
| Completeness | Complete (fine enough grid) | Probabilistically complete | Probabilistically complete |
| Optimality | Optimal (A*) | Not optimal (RRT); asymptotically (RRT*) | Depends on roadmap density |
| Narrow passages | Handles with fine grid | Requires many more samples | Very difficult without bridge sampling |
| Multi-query | Recompute or cache | Single-query only | Roadmap reused across queries |
| Kinodynamic constraints | Requires lattice planner | Natural via forward simulation | Edges can store control sequences |
| Typical use case | 2D costmap navigation | Arm planning, first query | Arm planning, repeated queries |
The practical rule of thumb: use a grid planner for any 2D mobile base problem (Nav2's default A* on a costmap is hard to beat for FollowBot's use case). Use RRT or RRT* for arm planning, where C-space is 6–7D and grid search is intractable. Use PRM when you will be planning many queries in the same static environment — the upfront cost of building the roadmap is amortized over hundreds of queries.
FollowBot's C-space for base navigation is 3D: (x, y, θ). At centimeter resolution over a 10 m × 10 m room, a grid has roughly 106 cells — entirely tractable for A*. The costmap already encodes this grid. RRT would find a path in this space, but A* finds the optimal path in comparable time and without the randomness. The case for RRT on a mobile base only arises when the environment is very large (a warehouse), when kinodynamic constraints dominate (aggressive car-like steering), or when the planning must be done in a higher-dimensional space jointly with an arm.
IN PRACTICEPRM — amortizing planning over repeated queries
The Probabilistic Roadmap (PRM) builds a graph of random collision-free configurations and connects nearby pairs with straight-line edges. Once this roadmap is built, any query (start → goal) connects both endpoints to the roadmap and runs A* on the resulting graph. For repeated queries in the same static environment, this is dramatically faster than re-running RRT from scratch each time.
PRM has two phases:
- Learning phase: sample N configurations uniformly from Cfree. For each, attempt to connect it to its k nearest neighbors (typically k = 10–15) using straight-line edges. Discard edges in collision. Repeat until the roadmap covers the workspace.
- Query phase: connect start and goal to their nearest roadmap nodes (or use a local planner to reach them), then run A* on the roadmap graph. Millisecond-scale for a prebuilt roadmap.
A PRM roadmap is built for a fixed obstacle set. If obstacles move — furniture is pushed, a door closes, a person stands in a previously clear path — the roadmap is invalid. Either edges that were collision-free are now blocked, or new free space is not in the roadmap. For FollowBot following a person through a changing environment, PRM is inappropriate for the global navigation problem. It is appropriate in fixed-configuration problems like arm motion planning in a known workcell.
A key practical variant is the Lazy PRM: build the roadmap without any collision checking during the learning phase. Only check edge validity when A* selects an edge during query. This dramatically speeds up roadmap construction; lazy evaluation defers the expensive checks to the query phase where only relevant edges need verification.
FOLLOWBOTWhere RRT fits in FollowBot's Nav2 stack
FollowBot's planning stack is now fully configured with Nav2. The global planner is A* on a 2D costmap derived from the SLAM map. The local planner is DWA (covered in Lesson 6.4) with FollowBot's differential-drive constraints. This lesson's planners — RRT and RRT* — are not FollowBot's primary path planners, but they matter in two places.
First, if FollowBot's 6-DOF arm needs to perform a handoff or gesture while navigating, arm motion planning is needed. The MoveIt 2 integration for FollowBot uses OMPL (Open Motion Planning Library), which includes RRT-Connect (a bidirectional RRT that runs two trees and connects them when they meet — typically 10× faster than single-tree RRT) as its default. Understanding why RRT-Connect works — and when its narrow-passage failure mode appears in arm configurations — is directly load-bearing for FollowBot's manipulation capability.
Second, the narrow passage problem in FollowBot's 2D navigation is handled by the global planner's costmap inflation, not by RRT. But when you encounter a doorway that Nav2's A* cannot route through (because the inflation radius makes the gap infeasible in the costmap), the correct fix is to reduce the inflation radius for that doorway, not to switch to RRT. Understanding the distinction — grid planner infeasibility vs. sampling planner narrow-passage failure — tells you which knob to turn.
# Nav2 uses plugin-based planners — default is A* (NavfnPlanner) # SMAC Planner (also available) adds kinodynamic constraints for car-like bases planner_server: ros__parameters: planner_plugins: ["GridBased"] GridBased: plugin: "nav2_navfn_planner/NavfnPlanner" # Dijkstra/A* on costmap tolerance: 0.5 use_astar: true # enable A* heuristic (faster than pure Dijkstra) allow_unknown: true # plan into unexplored cells (useful for person following) # For arm planning via MoveIt 2 + OMPL: # move_group.launch.py sets planning_plugin: ompl_interface/OMPLPlanner # Default OMPL planner: RRTConnect (bidirectional) — fast for free-space arm queries
With this lesson, FollowBot's Nav2 stack is conceptually complete: A* global planner on the SLAM map (Lesson 6.2), DWA local planner with FollowBot's dynamic constraints (Lesson 6.4 upcoming), costmap with LIDAR obstacle layer and inflation radius tuned for FollowBot's 0.3 m footprint, and the behavior tree orchestrating detect → navigate → maintain → handle occlusion → recover. The RRT* understanding here informs why Nav2's SMAC planner (which uses a lattice-based approach resembling kinodynamic RRT) exists as an alternative for car-like robots — FollowBot does not need it, but recognizing the design space matters.
WEAKNESSWhere sampling-based planners bite
The exponential dependence on passage width is not a theoretical curiosity — it appears routinely in practice. An arm reaching through a cage opening, a mobile robot squeezing between two desks, or a drone threading a forest of branches can all have effective C-space passage widths on the order of 1–5% of the space dimension. Standard RRT may require 10,000–100,000 samples to bridge such passages, taking seconds or minutes instead of milliseconds. Common mitigations include bridge sampling (sample uniformly, check collision, if in obstacle sample a second point nearby and use the midpoint if that is free — this biases samples toward narrow corridors), visibility-based PRM (samples concentrated near obstacle boundaries), and retraction-based planners. None is universally effective. If narrow passages appear frequently in your problem, sampling-based planners require significant workspace-specific tuning.
RRT* is asymptotically optimal, but "asymptotically" means the path quality is poor with few samples and only converges to the optimum as n → ∞. With 100 samples, an RRT* path may be only marginally better than RRT. With 10,000 samples, it is substantially better. The rewiring radius r(n) = γ(log n / n)1/d shrinks as n grows, meaning each new node can rewire fewer existing nodes — rewiring becomes less effective as the tree densifies. In practice, if you need a good path in a bounded computation time, variants like Informed RRT* (which focuses sampling in an ellipsoidal subset of C-space that can contain paths cheaper than the current best) converge much faster. Standard RRT* with generous time budgets is most practical in offline planning contexts; informed variants (Informed RRT*, BIT*, AIT*) are designed for online anytime use and are available in MoveIt 2's OMPL interface when near-optimal online replanning is required.
Both RRT and RRT* produce paths consisting of small straight-line segments in C-space. In workspace, these appear as jagged trajectories with sharp direction changes. A robot executing such a trajectory naively will decelerate, stop, rotate, and re-accelerate at each waypoint — slow, mechanically stressful, and visually incoherent to any person observing. Post-processing is mandatory: path shortcutting (randomized subdivision), B-spline smoothing, or velocity profiling with jerk limits. In Nav2, the Smoother Server plugin applies B-spline or gradient-descent smoothing before the path is handed to the local planner. Treating the raw planner output as an executable trajectory is a common mistake that produces poor real-world behavior.
KEY INSIGHTHow it connects
- 6.1 · Configuration Space: The Correct Abstraction for Planning — C-space is the space RRT samples. Without understanding C-space, the nearest-neighbor step and collision checking are opaque. The obstacles in the widget above are obstacles in C-space, not workspace — a distinction that only makes sense after Lesson 6.1.
- 6.2 · Graph Search: A*, Heuristics, and Costmap Planning — A* on a costmap is FollowBot's actual global planner; RRT is the arm planner. Both operate on C-space representations built from the same underlying SLAM map. Understanding why A* is preferred for 2D navigation and RRT for 7D arm planning requires holding both algorithms in mind simultaneously.
- 6.4 · Local Planners: DWA, TEB, and Real-Time Obstacle Avoidance — the local planner executes what the global planner produces. Path quality from RRT* directly affects local planner performance: a smoother global path requires less reactive correction from DWA.
Sampling-based planning sits at a junction: it inherits the C-space abstraction from Lesson 6.1, competes with grid search from Lesson 6.2 for the global planning slot, and hands off to local planners in Lesson 6.4. The narrow passage problem connects directly to costmap inflation — both are ways the planning problem becomes geometrically tight, and both require environment-specific tuning that no algorithm automatically handles.
GLOSSARYKey terms
- Probabilistic completeness
- A planner property: the probability of finding a solution path (if one exists) approaches 1 as the number of samples approaches infinity. Weaker than resolution-complete (which finds a solution for any finitely representable environment), but achievable without enumerating C-space.
- Asymptotic optimality
- A planner property: the cost of the found solution converges to the globally optimal cost as the number of samples grows without bound. RRT* satisfies this; plain RRT does not — RRT converges to a suboptimal cost with probability 1.
- Voronoi bias
- The implicit tendency of RRT to extend toward unexplored regions of C-space. Nodes with large Voronoi regions (far from other tree nodes) are selected as q_near more often by the nearest-neighbor step, driving the tree into uncharted territory without explicit bookkeeping.
- Rewiring
- The RRT* operation that checks whether newly added nodes provide cheaper paths to existing tree nodes and, if so, updates the tree's parent pointers. Rewiring propagates cost improvements backward through the tree and is the mechanism that enables asymptotic optimality.
- Narrow passage problem
- The failure mode of sampling-based planners in environments where C_free contains bottleneck regions of small volume. The probability of a random sample landing in a narrow passage is proportional to the passage width, requiring exponentially more samples as the passage narrows.
- Kinodynamic planning
- Motion planning that respects the robot's dynamic constraints (velocity limits, non-holonomic constraints, inertia). Kinodynamic RRT replaces straight-line extensions with short forward simulations of the robot's differential equations, ensuring every tree edge is dynamically feasible.
- PRM (Probabilistic Roadmap)
- A two-phase sampling-based planner. In the learning phase, random collision-free configurations are sampled and connected to form a graph. In the query phase, start and goal are connected to this graph and A* finds a path. PRM is efficient for repeated queries in a static environment; invalid when obstacles change.
- Bridge sampling
- A sampling strategy for narrow passages: sample a random configuration, check if it is in collision; if so, sample a second configuration nearby and use the midpoint. The midpoint is more likely to fall in a narrow corridor adjacent to obstacles. Biases the sampler toward passage interiors without requiring explicit passage detection.
ACTIVE RECALLCheck your understanding
Answer in your own words first, then reveal.
1RRT is probabilistically complete. Why does this not guarantee it will find a path quickly?›
Probabilistic completeness says the probability of finding a solution approaches 1 as the number of samples n → ∞. It makes no statement about the rate of convergence — only that it converges eventually. In a free C-space, convergence is fast (a few hundred samples). In a C-space with narrow passages, convergence is slow: the probability of a sample landing in a passage of width δ is proportional to δ / Vol(C_free), so the expected number of samples before bridging the passage is proportional to 1/δ. A 1 mm passage in a 1 m C-space requires roughly 1000× more samples than an open space. Probabilistic completeness is a necessary minimum guarantee, not a sufficient one for practical planning.
2What two operations does RRT* add to plain RRT, and why does each one help?›
Choose best parent: instead of connecting the new node to the nearest tree node, RRT* considers all nodes within a ball of radius r(n) and connects to the one that minimizes total path cost from the root. This ensures each new node is inserted with the cheapest possible connection, directly reducing path cost. Rewire: after inserting the new node, RRT* checks whether any node in the same ball can reach its current parent more cheaply by routing through the new node. If so, the tree's parent pointers are updated and costs propagate downstream. Together, these operations ensure path cost is monotonically non-increasing and converges to the true optimum as n → ∞. Neither operation changes the fundamental sampling loop — the added cost per iteration is O(log n) neighbor lookups and collision checks.
3For FollowBot's 2D navigation problem, why is A* on a costmap preferred over RRT?›
FollowBot's base navigation C-space is 3D: (x, y, θ). At centimeter resolution over a typical indoor environment, the costmap grid has on the order of 106 cells — well within A*'s reach. A* on this grid is complete, finds the optimal path relative to the costmap, and runs in milliseconds. RRT on the same space would also find a path, but with random behavior, no optimality guarantee, and post-processing requirements for path smoothing. The case for RRT on a mobile base arises only when the C-space is high-dimensional (e.g., a full mobile manipulator with arm joints included) or when kinodynamic constraints dominate (aggressive vehicle dynamics). For a differential-drive indoor navigation problem, grid A* is the right tool.
4Why is PRM inappropriate as FollowBot's global planner for the person-following task?›
PRM builds a roadmap during a learning phase, assuming the obstacle set is static. FollowBot operates in a dynamic indoor environment: people move, furniture is rearranged, doors open and close. When an obstacle moves into a PRM roadmap edge, that edge is no longer valid but the roadmap does not know this — the query phase would attempt to route through a blocked edge. Additionally, the goal in person-following changes constantly (the person moves), requiring frequent replanning. PRM amortizes planning cost over many queries in a fixed environment; FollowBot has many queries in a changing environment, so the amortization benefit is small while the invalidity risk is high. PRM is appropriate for FollowBot's arm planning in a fixed workcell, not for base navigation in a live environment.