RRT, RRT*, and variants

Rapidly-exploring Random Trees (RRT) solved a problem grid search couldn't: plan motion in 7-dimensional configuration spaces where enumerating a grid is impossible. Since 2011 (RRT*) these planners are also asymptotically optimal. Here's the algorithm, the variants, and why MoveIt's default planner is a descendant.

Plain RRT

The algorithm in six lines:

1. Initialize a tree with the start configuration.
2. Sample a random configuration q_rand from C-space.
3. Find the nearest tree node q_near.
4. Step from q_near toward q_rand a fixed distance, producing q_new.
5. If the edge q_near → q_new is collision-free, add q_new to the tree.
6. If q_new is close to the goal, done. Otherwise go to 2.

Why the "rapid" in the name

The genius of RRT is the sampling step. Nearest-neighbor + step-toward-sample biases the tree to grow into unexplored regions of free space. A random walk would stay near the start; a grid search would visit everywhere equally. RRT extends preferentially into the frontier. That's what makes it work in 7D where grids can't.

RRT's problem: suboptimal paths

Plain RRT returns some path, not a good one. The path is whatever the tree happened to grow first — usually zigzag, wasteful, and far from the shortest route.

RRT*: asymptotically optimal

Karaman & Frazzoli (2011) fixed this with two modifications:

1. Choose parent: when adding q_new, pick the nearby tree node that gives the lowest total cost-to-reach, not just the nearest one.
2. Rewire: check all nearby tree nodes to see if connecting through q_new would give them a lower cost. If yes, rewire.

As the number of samples → ∞, the best path in the tree converges to the global optimum. That's what "asymptotically optimal" means — you can run longer for a better path.

The variants worth knowing

RRT-Connect

Grows two trees — one from start, one from goal — and tries to connect them. Much faster to find a path, at the cost of optimality guarantees. MoveIt's default planner is a descendant.

Informed RRT*

Once a first path is found, sample only from the ellipsoid of configurations that could possibly improve it. Dramatically accelerates convergence to the optimum.

BIT* (Batch Informed Trees)

Combines sampling-based exploration with heuristic graph search. Practical state of the art for motion planning in 2026 — used in MoveIt's OMPL stack and many production systems.

Kinodynamic RRT

Plain RRT assumes you can connect any two configurations with a straight line in C-space. For systems with dynamics (drones, cars), use kinodynamic RRT: edges are integrations of the dynamics, and nearest-neighbor uses a cost-to-go heuristic instead of Euclidean distance.

Hyperparameters that matter

• Step size. Too small: tree grows slowly. Too big: edges frequently collide and get rejected. For arms, 0.05–0.15 rad per step is typical.
• Goal bias. Periodically (5–10% of samples) sample the goal directly. Speeds up convergence dramatically.
• Rewire radius (RRT*). Theory says it should shrink with tree size; in practice, a fixed reasonable value works.
• Termination. Plain RRT stops at first solution. RRT* keeps refining until a budget (time or sample count) is exhausted.

Writing a minimal RRT in 50 lines

import numpy as np

class RRT:
    def __init__(self, start, goal, collision_fn, bounds, step=0.1):
        self.tree = [start]
        self.parent = [None]
        self.goal = goal
        self.collision_fn = collision_fn
        self.bounds = bounds   # (lo, hi) arrays
        self.step = step

    def extend(self):
        if np.random.random() < 0.1:
            q_rand = self.goal
        else:
            q_rand = np.random.uniform(self.bounds[0], self.bounds[1])

        # nearest neighbor
        dists = [np.linalg.norm(q_rand - q) for q in self.tree]
        idx = int(np.argmin(dists))
        q_near = self.tree[idx]

        # step toward q_rand
        direction = q_rand - q_near
        norm = np.linalg.norm(direction)
        if norm < 1e-9:
            return False
        q_new = q_near + (self.step / norm) * direction

        # collision check
        if not self.collision_fn(q_near, q_new):
            self.tree.append(q_new)
            self.parent.append(idx)
            if np.linalg.norm(q_new - self.goal) < self.step:
                self.tree.append(self.goal)
                self.parent.append(len(self.tree) - 2)
                return True
        return False

    def path(self):
        if not np.allclose(self.tree[-1], self.goal):
            return None
        idx = len(self.tree) - 1
        path = []
        while idx is not None:
            path.append(self.tree[idx])
            idx = self.parent[idx]
        return list(reversed(path))

Use any collision-checker (FCL, your own simple one for toy C-spaces). Loop extend() until it returns True or you hit a budget.

Where this is going

In modern practice, you rarely write RRT from scratch. You configure MoveIt with OMPL, which ships dozens of planner variants (RRT-Connect, RRT*, BIT*, LBKPIECE, LazyPRM*). The value of this lesson is knowing what's inside — so when MoveIt returns a weird path, you can diagnose whether it's a planner issue, a C-obstacle issue, or a goal-reachability issue.

Next

Trajectory optimization — the alternative to sampling-based planning that scales differently. Good at smooth fine-grained motion; bad at escaping narrow passages.