Rapidly-exploring random trees

August 12, 2026

Every planner up to this point needs the free space written down before the search begins. A grid needs cells. A visibility graph needs the corners of every grown obstacle. Both are fine in the plane and both get worse fast: a grid fine enough for smooth motion has an enormous number of cells, and an arm with six joints has a six-dimensional configuration space that no one is going to enumerate.

A rapidly-exploring random tree never enumerates anything. It samples a configuration, finds the nearest node already in its tree, and steps a short way from that node toward the sample. If the step is clear, it keeps it.

The obstacles here are the ones the planner actually works against, which for a robot that translates without turning are the obstacles grown by the robot’s own shape. That construction is configuration space, and it is what lets everything below treat the robot as a point.

The loop

Four operations, repeated:

1. Sample. Draw $q_{\text{rand}}$ uniformly from the space. With some small probability, return the goal instead.

2. Find the nearest node. $q_{\text{near}} = \arg\min_{q \in V} \lVert q - q_{\text{rand}} \rVert$.

3. Steer. Move from $q_{\text{near}}$ toward $q_{\text{rand}}$ by at most the step size $\eta$:

   $$q_{\text{new}} = q_{\text{near}} + \min\!\left(\eta,\ \lVert q_{\text{rand}} - q_{\text{near}} \rVert\right) \frac{q_{\text{rand}} - q_{\text{near}}}{\lVert q_{\text{rand}} - q_{\text{near}} \rVert}$$

4. Check and add. If $q_{\text{new}}$ is in free space and the segment from $q_{\text{near}}$ to it is clear, add it with $q_{\text{near}}$ as its parent.

The only thing this asks of the world is a collision check. It never asks for a list of free configurations, or a neighbourhood structure, or a discretisation. That is the entire reason the method survives in high dimensions.

Why it explores

Nothing in that loop points the tree outward, and yet it goes outward. The sampler is uniform, so the reason has to be in step 2.

Partition the space by which node is nearest. That is the Voronoi diagram of the tree, and a uniform sample lands in a given cell with probability proportional to that cell’s area. Nodes on the frontier own the unbounded, sprawling cells facing unexplored space. Nodes buried inside the tree own slivers. So the node most likely to be extended is the one facing the largest unexplored region, and the bias toward unexplored space is a consequence of nearest-neighbour lookup rather than anything anyone designed in.

Watch the sample dot for a while with the tree switched off and back on. Most samples land far from anything and pull the frontier outward. As the tree fills the arena, the Voronoi cells even out and growth slows into refinement.

Goal bias, and how much is too much

Step 1 returns the goal itself with probability $p$. This is not a heuristic in the A* sense, since it does not order anything. It is a second sampler mixed into the first, and it does the job of aiming the tree.

The trade only becomes visible in a world that punishes aiming. Press New obstacles once to get the pocket: the start sits inside a box whose mouth faces away from the goal, so every route has to go backwards before it can go forwards. Sampling the goal walks the tree into the back wall of that pocket, and the samples that escape are the uniform ones.

Measured on that world, the samples needed to find a first route go

A little bias helps and a lot hurts, with the penalty mild until roughly a fifth and severe past a half. At eighty percent the planner is doing greedy descent with occasional exploration, and it takes five times as long as doing almost none at all. On the open worlds the same sweep is nearly flat until 50%, which is the more useful lesson: goal bias is close to free when the world is easy, and the worlds where you would want to turn it up are exactly the ones where it costs.

What RRT guarantees, and what it does not

RRT is probabilistically complete: if a solution exists with some clearance, the probability of finding it goes to one as samples go to infinity. That is weaker than the completeness A* has on a grid, and it is the price of not enumerating the space.

It is not optimal, and not nearly optimal. The route is whatever chain of steps happened to arrive first, and the tool freezes it the moment it connects. Karaman and Frazzoli sharpened this: the probability that RRT converges to an optimal solution is zero. Not merely unlikely. The event has measure zero, because the first connection fixes a homotopy and a set of parents that nothing later disturbs.

Run RRT a few times on the same world and read the cost. It scatters, and it scatters upward.

RRT*, which fixes the cost

RRT* changes what happens after step 3, in two places. Both operate on the neighbours of the new node within a radius $r$.

Choose the parent by cost, not by proximity. The nearest node is what found $q_{\text{new}}$, but the cheapest route to $q_{\text{new}}$ may run through a different neighbour:

over neighbours with a clear edge.

Rewire. Then check the same neighbours in the other direction. If reaching one of them through $q_{\text{new}}$ is cheaper than its current route, re-parent it onto $q_{\text{new}}$ and push the saving down to everything hanging off it.

That second half is why the cost keeps falling after a route exists. The tree is continuously reorganising itself into a shortest-path tree, and the route to the goal inherits every improvement made anywhere along it. Switch the tool to RRT* and watch the path snap tighter, sometimes long after it first connected.

The size of the effect is not subtle. Mean route cost over twelve runs on each world, every planner stopped at the same budget of 1500 nodes:

Rewiring is worth about a quarter to a third of the route, on the same samples, in the same time. Note also how little separates the last two columns, which is addressed below.

The radius

The neighbourhood radius shrinks as the tree grows:

with $d$ the dimension, $\mu(X_{\text{free}})$ the volume of the free space and $\zeta_d$ the volume of the unit ball. Both directions matter. Shrink faster than this and neighbourhoods stop overlapping, so improvements stop propagating and the guarantee is lost. Shrink slower and every new node pays for a neighbour check against an ever larger share of the tree. At that rate RRT* is asymptotically optimal: the cost converges to the optimum almost surely.

The $\log n / n$ is the interesting part. It says the number of neighbours per node should grow like $\log n$, not stay constant, which is the same threshold that governs connectivity in random geometric graphs.

Informed RRT*, which stops wasting samples

RRT* has a bad habit that is obvious once you watch for it. Long after a good route exists, it is still sampling the far corner of the arena, still running collision checks there, still adding nodes that cannot possibly end up on the answer.

Ask which points could improve on a route of cost $c_{\text{best}}$. A route through $x$ costs at least the two straight legs, so $x$ is worth sampling only if

That is the definition of an ellipse with focal points at the start and the goal. Everything outside it is provably useless. In $d$ dimensions it is a prolate hyperspheroid, with

where $c_{\text{min}}$ is the straight-line distance. Sampling it directly is a uniform draw from the unit ball, scaled by $a$ and $b$ and rotated onto the axis from start to goal.

The behaviour this produces is worth watching, and it is not quite the one the idea suggests. Before a first solution there is no ellipse at all and the planner is ordinary RRT*. When one arrives it is usually poor, and a poor route makes a large ellipse: across the four worlds here, the first one covers 75 to 94 percent of the arena, which rules out almost nothing. Only as the route improves does the region tighten, to somewhere between a quarter and a half of the arena once the cost settles.

So the benefit arrives second, not first, and it compounds: a better route shrinks the ellipse, a smaller ellipse concentrates the samples, and concentrated samples find a better route. The status line reports the current fraction, and watching that number fall is watching the loop close.

Why the table above barely moves

Informed RRT* beats plain RRT* by three or four units of cost here, which is nothing. It is worth being clear about why, because the paper reports large gains and both things are true.

The saving from restricting the search scales with how much volume gets excluded, and volume ratios in two dimensions are mild. The same ellipse in higher dimensions removes vastly more: the fraction of a $d$-dimensional box left inside a fixed hyperspheroid falls off exponentially in $d$. A planar arena with an obvious route is close to the worst case for demonstrating the idea, and the best case for seeing it, which is the trade this tool makes deliberately.

What the tool does show honestly is the mechanism: the ellipse appears, tightens, and stops the sampler from touching regions that provably cannot help. Whether that is worth anything depends on how much of the space it manages to exclude.

Note what happens as the route approaches optimal: $c_{\text{best}} \to c_{\text{min}}$ forces $b \to 0$ and the ellipse degenerates toward the straight line. The search narrows onto the answer it is converging to. Note also what does not happen: nothing is gained before the first solution, and in a world where finding any route is the hard part, informed sampling has nothing to offer until that route exists.

An arm, where none of this can be drawn

Everything above happens in a plane, which is convenient and slightly misleading. The plane is where a grid is affordable and a visibility graph is exact, so it is the case where sampling has the least to offer. The argument for RRT is about the case where those are not options.

Here is that case. A UR10 has to put its tool tip on a point without sweeping any part of itself through anything.

The planner is the same code. Not the same idea implemented again for arms: the same module, running the same loop, given a different description of what a configuration is and what makes one legal. Everything specific to the arm lives behind five functions, and the search does not know which of them it is calling.

What changed

A configuration is now a list of joint angles, and the space is a box in radians. Planning three joints makes that box three-dimensional; planning all six makes it six-dimensional, and there is no drawing of either that would help you. The faint lines in the view are not the tree. They are where the tool tip went for each edge of the tree, which is a shadow of the tree cast into the workspace by forward kinematics. Two configurations that sit next to each other in joint space can put the tip in completely different places, and the shadow is not a faithful picture of anything. It is only the best available.

Three things behave differently as a result.

Distance is in radians, not millimetres. The cost RRT* drives down is total joint motion. What gets shorter is how far the motors turn, which is not the same as how far the tip travels, and the tip path can get visibly longer while the cost falls.

Rewiring also matters far more here than it did in the plane. Mean route cost in radians over ten runs per target, everything stopped at 4000 nodes:

In the plane, rewiring bought about a quarter of the route. Here it routinely buys three quarters. Plain RRT’s first route is not merely inelegant, it is several times more joint motion than necessary, because a chain of short steps taken in whatever direction the samples happened to fall does not resemble a sensible arm motion at all. The straight-line column is what the move would cost with nothing in the way, and it is the floor none of them can beat.

The other column worth noticing is the last one. In the plane, informed sampling was worth almost nothing. Here it beats plain RRT* on every target, by a small but consistent margin, which is the dimensional effect from the previous section starting to show up.

None of that says anything about how long the answers took. RRT-Connect costs about what plain RRT costs, which should be no surprise, because neither improves on the first route it finds. What separates them is when that route turns up. Mean samples to the first one, from the same runs:

Growing a tree from each end is worth five to nineteen times fewer samples on these targets. That is the whole trade. It arrives sooner and then stops, so what it hands over is a route nothing has tidied, which is why in practice it is usually followed by a smoothing pass rather than trusted as it comes.

The three other columns being identical is not a mistake. Until a route exists, all three draw the same samples in the same order from the same seed. Rewiring changes what becomes of the tree, not the moment it first touches the goal, and informed sampling has no ellipse to aim at until there is a cost to build one from. The three part company only after the first success.

A straight line is a curve. The planner interpolates between two configurations, and the tip traces an arc through the workspace. That is why the route is drawn densely rather than as a polyline between waypoints.

Collision checking dominates. In the plane, testing an edge is a handful of segment-polygon tests. Here it means subdividing the motion, running forward kinematics at every subdivision, and testing every link against every obstacle and the floor. The step size and the subdivision resolution decide how much of that happens, and there is no exact test to fall back on: too coarse and a link slips through a shelf between two checks.

The dimension is the whole point

Switch from three joints to six. The problem looks identical and the arm is doing the same job, but the space the planner searches has gone from a box in $\mathbb{R}^3$ to one in $\mathbb{R}^6$.

Measured on the shelf workspace, the same first route takes roughly an order of magnitude more samples in six dimensions than in three. The wrist joints are held to a quarter turn each rather than the full revolution a real UR allows, for exactly this reason: opening them costs almost nothing in feasibility, about three quarters of the space stays legal either way, and it takes the solve rate from eight runs in eight down to three.

That is the case sampling exists for, and it is worth being precise about why a grid is not an option rather than merely slow. Ten divisions per joint is a coarse grid for a robot, coarse enough to miss a gap. In six dimensions it is $10^6$ cells, which is affordable. A useful resolution is more like a hundred divisions, which is $10^{12}$, which is not. And this arm has six joints because that is what a UR has; a dual-arm robot has fourteen. The tree above will happily run in fourteen dimensions. It will just need more samples, and it will never need the grid.

The code

The loop in C++, with the world behind an interface the search never looks through. That indirection is the claim the method makes, not tidiness: nothing between the sample and the goal check knows whether a configuration is a point in a plane or six joint angles.

using Config = std::vector<double>;

// Everything geometric lives here.
struct Space {
    int dimension;
    double measure;                     // free volume, for the RRT* radius below
    std::function<double()> random;     // one seeded source, so a run replays
    std::function<double(const Config&, const Config&)> distance;
    std::function<Config(const Config&, const Config&, double)> interpolate;  // t from 0 to 1
    std::function<Config()> sample;                              // uniform over the space
    std::function<bool(const Config&)> free;                     // may the robot be here
    std::function<bool(const Config&, const Config&)> edgeFree;  // may it move along all of this
};

struct Params {
    double stepSize = 30.0;      // eta, the furthest one edge may reach
    double goalBias = 0.05;      // chance a sample is the goal itself
    double goalRadius = 24.0;    // close enough to try connecting
};

// Parallel arrays rather than nodes holding pointers: rewiring needs a
// node's children as readily as its parent.
struct Tree {
    std::vector<Config> nodes;
    std::vector<int> parents;
    std::vector<double> costs;
    std::vector<std::vector<int>> children;
    std::vector<int> goalLinks;    // nodes with a clear edge to the goal
};

// A tree begins with just the start: one node, its own root, parent -1.
// attach() cannot place it, since children[-1] does not exist.
Tree makeTree(const Config& start) {
    Tree tree;
    tree.nodes = {start};
    tree.parents = {-1};
    tree.costs = {0.0};
    tree.children = {{}};
    return tree;
}

int attach(Tree& tree, const Config& point, int parent, double cost) {
    const int index = static_cast<int>(tree.nodes.size());
    tree.nodes.push_back(point);
    tree.parents.push_back(parent);
    tree.costs.push_back(cost);
    tree.children.emplace_back();
    tree.children[parent].push_back(index);
    return index;
}

// The line that makes the tree explore, though nothing about it says so.
int nearest(const Space& space, const Tree& tree, const Config& q) {
    int best = 0;
    double bestDistance = std::numeric_limits<double>::infinity();
    for (int i = 0; i < static_cast<int>(tree.nodes.size()); i++) {
        const double d = space.distance(tree.nodes[i], q);
        if (d < bestDistance) {
            bestDistance = d;
            best = i;
        }
    }
    return best;
}

// One step of at most eta from `from` toward `to`. Within one step it
// returns `to` itself, so arrival is exact rather than close enough.
Config steer(const Space& space, const Config& from, const Config& to, double eta) {
    const double d = space.distance(from, to);
    if (d <= eta) return to;
    return space.interpolate(from, to, eta / d);
}

// One iteration. Returns the new node, or -1 if the step was blocked.
int step(const Space& space, Tree& tree, const Config& goal, const Params& params) {
    const Config target = space.random() < params.goalBias ? goal : space.sample();

    const int nearIndex = nearest(space, tree, target);
    const Config near = tree.nodes[nearIndex];    // a copy: attach reallocates
    const Config point = steer(space, near, target, params.stepSize);

    // Two questions, and not the same one. The endpoint can sit in free
    // space with the motion to it passing through an obstacle.
    if (!space.free(point) || !space.edgeFree(near, point)) return -1;

    const double cost = tree.costs[nearIndex] + space.distance(near, point);
    const int index = attach(tree, point, nearIndex, cost);

    // The goal is not a node. A route ends at any node with a clear edge
    // to it, and plain RRT stops at the first one there is.
    if (space.distance(point, goal) <= params.goalRadius && space.edgeFree(point, goal)) {
        tree.goalLinks.push_back(index);
    }

    return index;
}

RRT* replaces the one call to attach with the function below. Nothing else in the loop moves, which is worth noticing: the sampling, the nearest lookup and the steering are all still the plain version.

constexpr double kPi = 3.14159265358979323846;
constexpr double kEps = 1e-9;

// Volume of the unit ball in n dimensions, by V(n) = (2 pi / n) V(n - 2),
// which avoids needing a gamma function. It peaks at n = 5 and falls away
// after, a fact worth having before trusting any intuition about volumes
// in a six-joint space.
double unitBallVolume(int n) {
    double v = n % 2 == 0 ? 1.0 : 2.0;
    for (int k = n % 2 == 0 ? 2 : 3; k <= n; k += 2) v *= 2.0 * kPi / k;
    return v;
}

// gamma > 2 (1 + 1/d)^(1/d) (mu / zeta_d)^(1/d). The bound is strict, so
// the 1.2 is margin.
double gammaFor(double measure, int d) {
    return 1.2 * 2.0 * std::pow(1.0 + 1.0 / d, 1.0 / d)
         * std::pow(std::max(measure, 1e-9) / unitBallVolume(d), 1.0 / d);
}

// r(n) = gamma (log n / n)^(1/d), capped. The bound describes the regime
// where the tree is large. While it is small the radius it asks for is
// most of the arena, which buys a neighbour check against every node and
// edges that span the space.
double connectionRadius(int count, int d, double gamma, double stepSize) {
    const double n = std::max(count, 2);
    return std::min(gamma * std::pow(std::log(n) / n, 1.0 / d), stepSize * 2.5);
}

std::vector<int> neighbours(const Space& space, const Tree& tree,
                            const Config& q, double radius) {
    std::vector<int> out;
    for (int i = 0; i < static_cast<int>(tree.nodes.size()); i++) {
        if (space.distance(tree.nodes[i], q) < radius) out.push_back(i);
    }
    return out;
}

// Re-parenting a node changes the cost of everything hanging off it.
// Without this the tree keeps costs that were true before the rewire and
// the saving is never passed on.
void propagate(const Space& space, Tree& tree, int root) {
    std::vector<int> queue{root};
    for (size_t at = 0; at < queue.size(); at++) {
        const int node = queue[at];
        for (const int child : tree.children[node]) {
            tree.costs[child] = tree.costs[node]
                              + space.distance(tree.nodes[node], tree.nodes[child]);
            queue.push_back(child);
        }
    }
}

int insert(const Space& space, Tree& tree, const Config& point, int nearIndex,
           double gamma, double stepSize) {
    const double radius = connectionRadius(static_cast<int>(tree.nodes.size()),
                                           space.dimension, gamma, stepSize);
    const std::vector<int> near = neighbours(space, tree, point, radius);

    // The cheapest parent, not the closest one. The nearest node is what
    // found this point; it is not always the cheapest way back to the
    // start. The edge check sits second in the condition on purpose, so
    // it only runs for a candidate that has already won on cost.
    int parent = nearIndex;
    double cost = tree.costs[nearIndex] + space.distance(tree.nodes[nearIndex], point);
    for (const int i : near) {
        const double candidate = tree.costs[i] + space.distance(tree.nodes[i], point);
        if (candidate < cost && space.edgeFree(tree.nodes[i], point)) {
            cost = candidate;
            parent = i;
        }
    }

    const int index = attach(tree, point, parent, cost);

    // And the reverse, which is the half that keeps paying after a route
    // already exists: a neighbour cheaper to reach through the new node
    // is re-parented onto it. The epsilon asks for a real improvement
    // rather than a last-bit one. A* on a grid needs that guard, where
    // costs are sums of 1 and sqrt(2) and two routes can tie exactly;
    // here the edge lengths are continuous and it never once fires.
    for (const int i : near) {
        if (i == parent) continue;
        const double candidate = cost + space.distance(point, tree.nodes[i]);
        if (candidate >= tree.costs[i] - kEps) continue;
        if (!space.edgeFree(point, tree.nodes[i])) continue;

        const int previous = tree.parents[i];
        if (previous >= 0) {
            auto& siblings = tree.children[previous];
            siblings.erase(std::find(siblings.begin(), siblings.end(), i));
        }
        tree.parents[i] = index;
        tree.children[index].push_back(i);
        tree.costs[i] = candidate;
        propagate(space, tree, i);
    }

    return index;
}

The other two variants are each one further change. Informed RRT* alters sample and nothing else: once a route exists, draw from the hyperspheroid above rather than the whole space. RRT-Connect leaves insert alone and alters the loop, growing a second tree from the goal and having each reach for whatever the other just grew.

Things to try

Step size. The obvious guess is that long edges get rejected more often, since an edge has to be clear along its whole length. On these worlds that is not what happens: the rejection rate sits near 53 percent in the pocket and near 41 percent in the open worlds whatever the step size, because it is set by how cluttered the world is and not by how far each edge reaches. What the step size buys is samples, and what it costs is resolution. Going from 8 to 90 in the pocket cuts the samples needed for a first route from about 1670 to about 184, and makes the route about 5 percent worse. The tree gets there faster and arrives coarser.

Node budget. Lower it and watch how much of the improvement happens early. Most of the gap between RRT and RRT* is closed within a few hundred nodes; the rest of the budget buys progressively less. The curve is the shape of asymptotic optimality, which promises the optimum eventually and says nothing kind about how fast.

Pause and step one sample at a time. The single most useful thing the tool does. Watch which node the sample attaches to, and how often it is not the one you would have guessed.

Drag the start inside the pocket, then drag the goal in with it. Both ends in the same enclosed region turns a hard problem into a trivial one, which is worth seeing precisely because the planner has no notion that anything changed.

Where this leaves you

The trade against A* is clean. A* on a grid is complete and optimal on the graph it was handed, and the graph is the problem: you paid for it in advance, at a resolution you chose before you knew what you needed. RRT pays nothing in advance, gives up on optimality entirely, and works in dimensions where the grid does not exist. RRT* buys optimality back in the limit, at the cost of running forever to get it. Informed sampling does not change that limit, only how much of the space is searched on the way, which matters more the more dimensions there are to waste.

Which means the practical question is rarely which algorithm is best. It is how much time there is before the robot has to move, and what quality of route that much sampling buys.