Sample-Based Planning

In the previous lessons we planned on grids: lay down cells, run Dijkstra or A*, get an optimal path. Beautiful in two dimensions. Catastrophic in seven.

The curse that breaks the grid

Add one dimension and the grid doesn't get a little bigger; it gets bigger by a factor. The number of cells is roughly $r^d$: resolution $r$ raised to the power of the dimension $d$. A floor-cleaning robot rolling around a room has $d = 3$ (its $x$, $y$, and heading), and a grid is fine. A robot arm reaching into a dishwasher has $d = 6$ or $7$. A humanoid has dozens. Each joint multiplies the others, and the search space detonates.

This is the curse of dimensionality, and it is not a coding problem you can optimize away. It is geometry. You cannot afford to even visit every cell, let alone store them.

So we give up on completeness-by-brute-force. Instead of methodically checking every square, we throw random darts into the configuration space and connect the ones that land in free, collision-free regions. Sample, test, connect. The structure that emerges is good enough, and we never touch most of the space.

RRT: a tree that reaches

The Rapidly-exploring Random Tree, introduced by Steven LaValle in 1998, is the canonical sampler. Watch it work and the name explains itself.

Grow one yourself. The tree rushes to fill empty space first, then threads through the gaps toward the goal. Drag the start and goal markers, click to drop obstacles, and watch it re-grow around them.

The loop is almost insultingly simple:

1. Sample a random point $q_{\text{rand}}$ somewhere in the configuration space.
2. Find the node already in the tree that is nearest to it, $q_{\text{near}}$.
3. Steer a small step from $q_{\text{near}}$ toward $q_{\text{rand}}$, landing on $q_{\text{new}}$.
4. If the path from $q_{\text{near}}$ to $q_{\text{new}}$ is collision-free, add $q_{\text{new}}$ to the tree.
5. Repeat until a branch reaches the goal.

The genius is in step 2. Because every random sample reaches for the nearest existing node, the branches with the most empty space around them get picked most often. The tree is biased, automatically, toward the frontier: it rushes outward to fill the void rather than thrashing around where it already is. Nobody told it to explore efficiently; the math just does.

There is one cheap hack almost every real RRT uses. If you only ever sample at random, the tree explores beautifully but can dawdle on its way to the actual goal. So implementations slip in a small chance, often a few percent, of pretending the random dart landed exactly on the goal. Turn that probability up and the tree lunges greedily at the target. Turn it down and the tree wanders more but covers tricky corners better. That single knob, the goal bias, is one of the first things you tune when an RRT is being stubborn.

PRM: build the map once, reuse it forever

RRT is a sprinter: it builds one tree for one query and discards it. Its cousin, the Probabilistic Roadmap (PRM), is a city planner. PRM scatters samples across the whole free space up front, connects each to its neighbors with collision-free edges, and stitches together a reusable graph: a roadmap.

The trade-off is clean. RRT is single-query: one start, one goal, plan fast, throw it away. PRM is multi-query: pay a hefty cost once to build the roadmap, then answer thousands of start-goal questions cheaply by snapping each onto the existing graph. A warehouse with a fixed floor plan loves PRM. A surgical arm in a body it has never seen wants RRT.

Will it actually find a path?

Here is the unsettling part: with random sampling, you have no hard guarantee a solution shows up by any particular moment. What you have instead is probabilistic completeness: a promise that if a valid path exists, the probability of finding it approaches 1 as the number of samples goes to infinity. Throw enough darts and you will, eventually, hit the dartboard.

That's a weaker promise than the grid's "I will check every cell." But it's the promise that scales. And it comes with a sharp footnote: if no path exists, a sampling planner will keep throwing darts forever, never able to prove the impossible. It cannot say "no." It can only fail to say "yes."

↘ RRT* and the price of optimal paths

Vanilla RRT finds a path, not the best one, and its routes are notoriously jagged and detour-prone. RRT*, published by Karaman and Frazzoli in 2011, fixes this by adding a rewiring step.

When a new node $q_{\text{new}}$ joins the tree, RRT* doesn't just attach it to the nearest neighbor. It looks at all nodes within a radius and:

• chooses the parent that gives $q_{\text{new}}$ the lowest total cost-to-come, and
• rewires nearby nodes to route through $q_{\text{new}}$ if doing so shortens their own path back to the start.

Let $c(q)$ be the cost from the start to node $q$. A neighbor $q_i$ is rewired to adopt $q_{\text{new}}$ as its parent whenever

$$c(q_{\text{new}}) + \lVert q_{\text{new}} - q_i \rVert < c(q_i)$$

Each rewiring locally pays down cost, and the connection radius shrinks as the tree grows roughly like

$$r(n) \propto \left( \frac{\log n}{n} \right)^{1/d}$$

balancing thoroughness against the cost of checking neighbors. The result is asymptotic optimality: the path doesn't just exist, it keeps improving toward the true optimum as samples accumulate. The longer you let RRT* run, the straighter and shorter its answer gets.

Key takeaways

• Grids die in high dimensions. Cell count scales as $r^d$, so the curse of dimensionality makes exhaustive search impossible past a few degrees of freedom.
• Sampling sidesteps the curse. Throw random darts, test for collisions, connect the survivors. You never have to enumerate the whole space.
• RRT grows one tree per query, biased toward unexplored frontier (Voronoi bias). PRM builds a reusable roadmap for many queries.
• RRT* adds rewiring for asymptotic optimality: the path improves toward optimal as it samples.
• Sampling buys probabilistic completeness, not certainty: find a path if one exists, given infinite samples, but never able to prove that none does.