Skip to content

RRT (Rapidly-exploring Random Tree)

◀ Go to A-Star

Go to RRT* ▶

RRT is a sampling-based planning algorithm built for problems where the search space is too large or complex for grid-based methods like A*. Instead of checking every possible position, it grows a tree by randomly throwing darts at the space and stepping toward wherever they land — making it especially powerful in high-dimensional environments.

The Challenge: High-Dimensional Spaces

Imagine a robot arm with 7 joints. Each joint can rotate to any angle, so there are endless ways the arm can be positioned. The full set of all possible poses is called the Configuration Space (or C-space).

In 2D, C-space is just a flat grid — a robot's position is described by two numbers (x, y). But a 7-joint arm needs 7 angles to describe its pose, giving it a 7-dimensional C-space. Methods like A* work by slicing the space into a grid and checking each cell. In 2D, that's fine. In 7D, the number of cells explodes into the trillions — it would take longer than the age of the universe to check them all. This is known as the curse of dimensionality.

RRT solves this by never building a grid at all. It samples random points and grows a tree toward them, exploring efficiently without ever enumerating the full space.

Image placeholder — C-space / robot arm diagram
A robot arm's joint angles map every pose to a single point in Configuration Space.

The Key Idea: Random Sampling

Rather than exhaustively mapping the space, RRT works like throwing darts:

  1. Pick a completely random point anywhere in the space
  2. Find the nearest node already in the tree
  3. Take one small step from that node toward the random point
  4. Add the new position to the tree — as long as it doesn't land inside an obstacle
  5. Repeat

Over thousands of iterations, the tree rapidly explores the entire space — which is exactly how it got its name.

RRT tree growing through space
An RRT tree growing from a start node, branching out to explore the space.
What is the main goal of the RRT algorithm?
Answer explanation
RRT's primary goal is to find any valid, collision-free path — not necessarily the shortest one. It achieves this by randomly sampling the space and growing a tree toward those samples. Unlike A*, which scores every path by cost and guarantees the optimal result, RRT is satisfied as soon as it finds a route from start to goal. If you also want the shortest path, you'd use RRT* — the optimizing variant covered in the next section.

Key Parameters

Step Size

This controls how far each new branch extends toward a random sample — think of it as the length of each twig on the tree.

  • Too small: the tree grows extremely slowly, taking tiny steps to get anywhere
  • Too large: branches leap over narrow gaps between obstacles, missing valid routes

A good step size depends on the scale of your environment and how tight the obstacles are.

Goal Bias

Most of the time, RRT samples a fully random point. But occasionally — say 5–10% of the time — it aims the sample directly at the goal instead. This nudges the tree toward the goal without losing the broad exploration that makes RRT powerful.

Maximum Iterations

This is a safety cap. If the tree hasn't reached the goal after this many tries, the algorithm stops. Without it, an impossible problem (goal completely blocked) would run forever.

How RRT Works

  1. Initialize the tree with the start node.
  2. Repeat up to the maximum number of iterations:
    • Sample a random point in the space (or, with small probability, use the goal directly).
    • Find the nearest node in the existing tree.
    • Step from that node toward the random point by one step size.
    • If the new node collides with a wall, discard it and move to the next iteration.
    • Otherwise, add the new node to the tree.
    • If the new node is close enough to the goal, connect it to the goal and stop.
  3. Trace the path back from the goal to the start by following parent pointers.

Step-by-Step Walkthrough

The slideshow below shows RRT growing a tree through a 2D space with two wall obstacles. Blue = start, purple = goal, orange = newly added node, red × = random sample, gray × = rejected (inside a wall), green = final path.

What happens when a tree node gets close enough to the goal?
Answer explanation
After each new node is added, RRT checks whether it falls within a set goal radius — a small threshold distance from the goal. The moment a node passes that check, the algorithm directly connects it to the goal and terminates. The final path is then recovered by following parent pointers back from the goal all the way to the start — each node remembers which node it was extended from, so tracing them in reverse gives the complete route.

Probabilistic Completeness

RRT doesn't guarantee finding a path after exactly N iterations. Since it relies on random sampling, it might get unlucky and miss a narrow corridor for a long time. But here's the key insight:

The more iterations you run, the more likely RRT is to find a path — if one exists.

As the number of iterations grows toward infinity, the probability of finding a solution approaches 1. This property is called probabilistic completeness. In practice, it means:

  • Give RRT enough iterations and it will almost certainly find a path
  • Failing after 500 iterations doesn't mean no path exists — it may just need more time
  • If the goal is truly unreachable (completely walled off), RRT will always fail regardless of iterations — probabilistic completeness only applies when a valid path exists

This is different from Dijkstra's or A, which are *deterministically complete** — they always find a path if one exists, and always report failure if one doesn't, in a bounded amount of time. RRT trades that hard guarantee for the ability to operate in high-dimensional spaces where those methods can't.

Image placeholder — RRT at low vs. high iteration counts
More iterations = denser tree = higher probability of finding a path through tight spaces.
A robot runs RRT for 500 iterations but no path is found. What is the most appropriate next step?
Answer explanation
Because RRT is probabilistically complete, not finding a path in 500 iterations does not mean no path exists — it just means the random samples haven't covered the right region yet. The probability of finding a valid path approaches 1 as iterations increase, so the correct move is to allow more iterations.

Contrast this with A* or Dijkstra, which are deterministically complete: if they finish without a solution, you can be certain no path exists. RRT cannot make that guarantee — the only way to be sure a path is truly impossible is if the goal is geometrically sealed off with no gap at all.

Demo

See this Jupyter notebook for an example of RRT in action:

colab