Sampling-based planning: RRT in plain words

TL;DR:

• An RRT (rapidly-exploring random tree) plans by growing a tree from the start: pick a random configuration, step from the nearest tree node toward it, and keep the step if it is collision free.

• Planning happens in configuration space, whose axes are the robot's joint angles, so a six-joint arm has six dimensions.

• RRT finds a path quickly in high dimensions, but the path is rough and not the shortest.

You ask a robot arm to reach into a box without touching the edge. The arm has six joints. How do you search for a path in a space of six angles at once? A grid is hopeless there, but a patient random explorer can do it. That explorer is the RRT.

Why grids fail for arms

A path planner for a robot arm does not search the room. It searches configuration space: the space of all joint angles. A two-joint arm has a 2D configuration space, with θ1 on one axis and θ2 on the other. Each point in that space is a complete pose of the arm. Obstacles in the room become forbidden regions in this space: any set of angles that makes the arm touch something is blocked.

A grid in configuration space needs a number of cells that multiplies with every joint. If each joint angle is divided into 100 values, a six-joint arm has 100⁶ = 10¹² cells, a trillion. Searching that with A* is out of the question. This is sometimes called the curse of dimensionality.

The RRT idea

An RRT does not build a grid. It builds a tree. The tree starts with one node, the start configuration. Then it repeats these steps:

1. Sample a random configuration q_rand anywhere in the space.

2. Find the nearest node q_near already in the tree.

3. Steer: take a small step of fixed length (the step size) from q_near toward q_rand, giving q_new.

4. Check that the short segment from q_near to q_new is collision free. If it is, add q_new to the tree with q_near as its parent. If not, throw it away.

5. Stop when a new node lands within some tolerance of the goal. Follow parents back to the start for the path.

The nearest-node rule means that random samples far from the tree pull it toward unexplored regions, so the tree spreads quickly into open space. Often the algorithm picks the goal itself as the sample a small fraction of the time (a goal bias) to pull the tree toward the goal.

Worked example: an arm reaching around an obstacle

Take a two-joint arm, with configuration (θ1, θ2) in radians, and a step size of 0.3. The tree starts at q0 = (0, 0).

Iteration 1. The random sample is q_rand = (1.0, 0.5).

1. The tree has only q0, so q_near = q0.

2. The direction is (1.0, 0.5) with length √(1.0² + 0.5²) = √1.25 = 1.118. The unit vector is (0.894, 0.447).

3. Step: q_new = (0, 0) + 0.3 × (0.894, 0.447) = (0.268, 0.134).

4. Collision check along the segment (compute the arm's pose at a few points between the two configurations and test it against the obstacle). Say it is free, so q1 = (0.268, 0.134) joins the tree.

Iteration 2. The sample is q_rand = (0.2, −1.0).

1. Distance to q0: √(0.2² + 1.0²) = √1.04 = 1.020. Distance to q1: √((0.2 − 0.268)² + (−1.0 − 0.134)²) = √(0.0046 + 1.286) = 1.136. The nearest node is q0.

2. The unit vector from q0 toward the sample: (0.2, −1.0) / 1.020 = (0.196, −0.981).

3. q_new = 0.3 × (0.196, −0.981) = (0.059, −0.294).

4. Say the collision check fails because this pose of the arm touches the box. The node is discarded and the tree stays as it was.

Repeat this thousands of times. The tree grows into the free space, the obstacle's region gets no nodes, and eventually a branch curls around the blocked region and ends near the goal. In a real run, the check in step 4 asks the arm model: does any link overlap the obstacle at this pose?

Strengths and weaknesses

• Fast in high dimensions. It never builds the whole space, only the part it needs.

• Probabilistically complete. If a path exists, the chance of finding it approaches 1 as the number of samples grows. If none exists, it never says so.

• Not optimal. The first path found is usually crooked and longer than needed. A variant called RRT* improves the path as it keeps sampling. Many systems post-process the path by cutting corners where it is safe to do so (shortcutting or smoothing).

• Random. Two runs give two different paths.

• Narrow passages. A gap that is a tiny fraction of the space is hard to hit by random samples, so the planner may take long to get through.

Where it goes wrong

• Collision checking is the bottleneck. Most of the planning time goes into testing poses. An inaccurate model of the robot or the world gives unsafe paths.

• Step too large. The check between nodes can miss a thin obstacle. Check at finer intervals along the segment.

• Step too small. The tree grows slowly.

• Ignoring dynamics. The path is geometric. The robot must still follow it within its speed and torque limits.

• Joint limits and wrapping. Angles wrap around at 2π, and distance in configuration space must account for it.

Safety: A planned path is only as good as the model of the robot and its surroundings. Before running a planned motion on a real arm, replay it in simulation, run the first test at very low speed with the emergency stop in reach, keep people outside the arm's workspace, and add a margin around obstacles so a small error cannot cause contact.

How real robots use it

Motion planning libraries for robot arms, mobile manipulators and even vehicles use RRT and its variants. Often a planner finds a rough path with RRT and then a second step smooths it. Where the world is simple and low-dimensional, a grid and A* (see Dijkstra and A*) are better. A very different approach, covered in obstacle avoidance with a potential field, reacts to obstacles without planning the whole path.

Try it yourself

On graph paper, draw a square 10 by 10 with a block in the middle. Pick a start and goal on opposite sides. Roll a die twice to choose random points (use a 6 by 6 grid), find the nearest tree node by eye, and step 1 unit toward the sample. Discard steps that cross the block. After 30 or so iterations you should have a branching tree that has found its way around.

Frequently asked questions

Why is RRT random?

Random samples let the tree reach every part of a large space without a grid. They pull the tree toward unexplored areas, which gives a fast, rough solution in high dimensions.

Does RRT find the shortest path?

No. It finds a path, usually a rough one. Variants such as RRT* and smoothing steps shorten it.