Sampling-Based Planning: RRT and PRM

A uniform grid in $d$-dimensional C-space requires $(1/\epsilon)^d$ cells. At $d = 7$ (a Franka Panda arm) and $\epsilon = 5°$ resolution, that is roughly $72^7 \approx 10^{13}$ cells — impossible to store, let alone search. Grids pay for every cell regardless of whether it is reachable or interesting.

Sampling-based planners take the opposite approach: draw configurations $q$ uniformly at random from $\mathcal{C}$, discard those in $\mathcal{C}_{\text{obs}}$, and connect neighbours. No grid is stored. Memory grows with the number of useful nodes, not with resolution. The key insight is that you do not need to cover $\mathcal{C}_{\text{free}}$ — you only need to find one valid path (or the optimal one). Random samples achieve dense coverage of $\mathcal{C}_{\text{free}}$ as their count grows, enabling probabilistic completeness.

Two dominant families emerged in the 1990s: PRM (multi-query roadmaps) and RRT (single-query trees). Both are standard tools in every serious motion planning stack.

PRM (Kavraki et al., 1996) has two phases:

Learning phase: sample $N$ configurations uniformly from $\mathcal{C}$. Keep those in $\mathcal{C}_{\text{free}}$. For each valid sample, attempt to connect it to its $k$ nearest neighbours with a local planner (typically straight-line in C-space + collision check). Successful connections become graph edges.

Query phase: connect $q_s$ and $q_g$ to the nearest roadmap nodes, then run Dijkstra/A* on the resulting graph.

PRM is a multi-query method: once built, the roadmap answers many $(q_s, q_g)$ pairs sharing the same environment — ideal for robot arms that repeatedly replan in a fixed workspace. The cost is upfront: $O(N k)$ collision checks during construction.

Weakness: narrow passages. A doorway thinner than the typical nearest-neighbour distance is rarely bridged by straight-line connections. Fixes include bridge sampling (sample near obstacle boundaries) and visibility-based PRM, but narrow passages remain the canonical hard case.

RRT (LaValle, 1998) grows a tree rooted at $q_s$ using a simple loop:

1. Sample a random configuration $q_{\text{rand}}$ (with probability $p_{\text{goal}}$, sample the goal instead).
2. Find the tree node $q_{\text{near}}$ nearest to $q_{\text{rand}}$.
3. Extend from $q_{\text{near}}$ toward $q_{\text{rand}}$ by a step of size $\delta$: $q_{\text{new}} = q_{\text{near}} + \delta \cdot \frac{q_{\text{rand}} - q_{\text{near}}}{\|q_{\text{rand}} - q_{\text{near}}\|}$.
4. If the segment $[q_{\text{near}}, q_{\text{new}}]$ is collision-free, add $q_{\text{new}}$ to the tree.
5. If $q_{\text{new}}$ is within $\delta$ of the goal, the path is found.

RRT is single-query: the tree does not persist across planning problems. It excels in high-DOF spaces and kinodynamic problems because the extend step can respect dynamics. The tree's Voronoi bias ensures uniform exploration: large Voronoi regions attract more samples, driving the tree outward.

A self-contained RRT for a 2-D point robot illustrates the core loop:

import random, math

class RRT:
    def __init__(self, q_start, q_goal, checker,
                 step=0.05, goal_bias=0.1, max_iter=5000):
        self.tree = [q_start]      # list of nodes
        self.parent = {q_start: None}
        self.q_goal = q_goal
        self.checker = checker     # callable: q -> bool (True = free)
        self.step = step
        self.goal_bias = goal_bias
        self.max_iter = max_iter

    def _nearest(self, q):
        return min(self.tree, key=lambda n: math.dist(n, q))

    def _extend(self, q_near, q_rand):
        d = math.dist(q_near, q_rand)
        if d < 1e-9:
            return None
        alpha = min(self.step / d, 1.0)
        q_new = tuple(a + alpha*(b-a) for a,b in zip(q_near, q_rand))
        if self.checker(q_new):    # collision check at endpoint
            return q_new
        return None

    def plan(self):
        for _ in range(self.max_iter):
            q_rand = (self.q_goal if random.random() < self.goal_bias
                      else (random.uniform(0,1), random.uniform(0,1)))
            q_near = self._nearest(q_rand)
            q_new  = self._extend(q_near, q_rand)
            if q_new is None:
                continue
            self.tree.append(q_new)
            self.parent[q_new] = q_near
            if math.dist(q_new, self.q_goal) < self.step:
                return self._extract_path(q_new)
        return None  # timeout

    def _extract_path(self, q):
        path = []
        while q is not None:
            path.append(q); q = self.parent[q]
        return path[::-1]

Note: this extend checks only the endpoint, not the full segment. Production planners call segment_free(q_near, q_new) for safety.

RRT and PRM are probabilistically complete: the probability that they fail to find a path (when one exists) converges to zero as the number of samples $N \to \infty$. Formally, for RRT:

$P(\text{failure after } N \text{ iters}) \leq (1 - p_{\text{connect}})^N \to 0$

where $p_{\text{connect}} > 0$ is a lower bound on the probability that a single iteration makes progress toward the goal.

This is not the same as completeness. A complete planner terminates in finite time and either finds a path or proves none exists. RRT does neither: it can run forever without finding a path (though probability decays), and it cannot certify infeasibility.

Practical implication: if RRT times out, you do not know whether no path exists or you just need more samples. For safety-critical applications (surgical robots, aerospace), probabilistic completeness is often not sufficient — exact methods or certified planners are required despite their higher cost.

Plain RRT finds a path but has no quality guarantee. The path typically has redundant detours and jerky turns. RRT* (Karaman & Frazzoli, 2011) adds two operations after each extend:

1. Rewire near-nodes: within a ball of radius $r_n = \gamma (\log n / n)^{1/d}$ around $q_{\text{new}}$, check whether routing through $q_{\text{new}}$ reduces each near-node's cost. If so, redirect the parent.
2. Choose the best parent: when inserting $q_{\text{new}}$, connect it to the near-node with the lowest $g$-cost, not the nearest node.

The radius $r_n$ shrinks as the tree grows (ensuring finite vertex degree) but shrinks slowly enough that the tree remains connected. The result is asymptotic optimality: the path cost returned by RRT* converges to the optimal path cost $c^*$ almost surely as $N \to \infty$:

$\lim_{N\to\infty} c_{\text{RRT}^*}(N) = c^* \quad \text{(a.s.)}$

In contrast, RRT's path cost converges to a suboptimal value and stays there — it is not asymptotically optimal.

No single algorithm dominates all scenarios. Here is an honest comparison:

Rule of thumb: use A* for 2-D navigation (well-understood, fast, reliable); PRM for high-DOF arms in fixed environments; RRT for single-query high-DOF or kinodynamic problems; RRT* when path quality matters and planning time is available.

Vanilla RRT and PRM have well-known failure modes that production planners address:

BiRRT (bidirectional RRT): grow two trees — one from $q_s$, one from $q_g$ — and attempt to connect them. Halves the effective search depth, giving order-of-magnitude speedups in cluttered environments.

Goal biasing: set $p_{\text{goal}} = 0.05$–$0.10$. Without it, RRT explores uniformly and rarely reaches the goal in practice. Too high ($p > 0.3$) and the tree gets stuck on local obstacles.

Informed RRT:* once any path of cost $c_{\text{best}}$ is found, restrict future samples to the prolate hyperspheroid $\{q : \|q - q_s\| + \|q - q_g\| \leq c_{\text{best}}\}$. This focuses effort where improvements are still possible.

CHOMP / STOMP / TrajOpt: optimise a trajectory in continuous space using gradient descent or stochastic perturbation. Often used to smooth an RRT* path post-planning rather than plan from scratch.

For real robots, always add a post-processing step: shortcut the path (try direct connections between non-adjacent waypoints), then smooth with a spline or elastic band.