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.

RRT visualization
A robot arm's joint angles map every pose to a single point in Configuration Space.

Try it yourself!

You can download or fork the project here:

Open the RRT Arm Simulation GitHub Repository

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 numerous 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.

Step 1 — Picking the Random Point

RRT draws a point uniformly at random from the entire configuration space — every location in the bounded region has exactly equal chance of being chosen.

  • In a 2D map: randomly pick an (x, y) coordinate anywhere in the grid bounds.
  • In a 6-DOF robot arm: randomly pick 6 joint angles simultaneously, one per dimension.

Occasionally (typically 5–10% of the time), the algorithm skips the random draw and uses the goal position directly. This is called goal bias and nudges the tree toward the destination without sacrificing the broad exploration that makes RRT effective.

Step 2 — Finding the Nearest Node

Once a random point q_rand is sampled, RRT scans every node currently in the tree and picks the one closest to q_rand by Euclidean distance:

\[d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\]

This nearest node q_near becomes the parent from which the new branch will grow.

Step 3 — Steering Toward the Sample

Rather than jumping all the way to q_rand (which might leap over an obstacle), RRT takes one controlled step of size Δ (the step size) in the direction of q_rand:

\[q_{new} = q_{near} + \Delta \cdot \frac{q_{rand} - q_{near}}{\|q_{rand} - q_{near}\|}\]

The fraction is a unit vector pointing from the nearest node toward the random sample — it gives direction without magnitude. Multiplying by Δ caps the move to exactly one step size. If q_rand is already closer than Δ, the algorithm steps directly to it instead.

Step 4 — Collision Check

After computing q_new, RRT checks whether the straight-line segment from q_near to q_new passes through any obstacle. If it does, the node is rejected and the iteration is discarded — the tree simply tries again with the next random sample.

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 walks through one complete iteration in detail, then shows the tree growing to the goal. Blue = start, purple = goal, orange = newly added node, red × = random sample, gray × = rejected, orange ring = nearest node, orange dashed circle = ghost of proposed new node, 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 is probabilistically complete: as iterations increase, the probability of finding a path (if one exists) approaches 1. In practice:

  • More iterations = denser tree = higher chance of threading through narrow gaps
  • Not finding a path in 500 iterations does not mean no path exists — it may just need more time
  • If the goal is geometrically sealed off with no gap, RRT will always fail regardless of iterations

This differs from A* and Dijkstra, which are deterministically complete — they find a path if one exists and conclusively report failure if not, in bounded time. RRT trades that hard guarantee for the ability to work in high-dimensional spaces where grid-based methods can't.

Try It: Iterations vs. Tree Density

Adjust the sliders and click Run to see how each parameter affects the tree. A small step size grows a finer tree that can thread tight gaps; a large step size covers ground faster but may leap over narrow corridors.

50
28
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

A-Star Algorithm
◀ Go to A* Algorithm
RRT Star Algorithm
Go to Rapidly-exploring Random Tree Star (RRT*) ▶