Rapidly exploring random trees: grow a collision-free path

A robot needs a route around an obstacle. A clear start and goal leave an open question: which motions can connect them?

A rapidly exploring random tree, or RRT, grows possible motions from the start. Each sample suggests where to extend. Each collision check decides whether that branch can join the tree.

Grow the graph as you search

A* search chooses which node to explore in an existing graph. A geometric RRT creates nodes at sampled positions and adds valid connections as it runs. This avoids choosing a fixed grid spacing across the whole configuration space.

A node records a robot configuration. Its parent records the earlier node that connects it to the start. Following parents backward recovers a path through the tree.

The experiment uses a translating disk in a plane. More complex robots need a configuration distance and a way to propose motions that match their joints and movement constraints. Straight lines in this example describe only the disk center's motion.

Describe the robot and forbidden centers

The room spans 0 to 6 m on both axes. The robot has radius ρ = 0.2 m, start center (0.6, 3) m, and goal center (5.4, 3) m. The main obstacle has center (3, 3) m and radius R = 1 m.

The disk clears that obstacle when its center distance exceeds R + ρ = 1.2 m. Its center must also stay more than 0.2 m from every wall. The configuration-space explanation shows why moving shapes become forbidden configuration points.

For this model, contact counts as collision. The code treats clearance at most 10⁻¹⁰ m as contact to handle roundoff. That tolerance supplies no allowance for uncertain maps, robot flex, or tracking error.

Uniform samples come from the inset square [0.2, 5.8] × [0.2, 5.8] m. Sampling inside it avoids most wall rejections, but every proposed motion still checks the wall condition. Samples can lie inside an obstacle; the motion checker handles those attempts.

Extend the tree one sample at a time

Start with a tree containing only the start node. Repeat these steps until a path succeeds or the sample budget ends:

1. Draw a target configuration. With the chosen goal bias, use the goal itself.
2. Find the existing tree node nearest to that target.
3. Propose a short motion from that node toward the target.
4. Check the entire proposed motion for collision.
5. If it is clear and moves a nonzero distance, add its endpoint and parent.
6. If the new node is close enough, check a final connection to the exact goal.

A rejected extension adds no node. The next attempt can choose a different direction. This lesson uses a single tree and stops at its first complete solution.

Find a nearby node and limit the step

For points in this room, use Euclidean distance. The nearest-node search checks each stored node and keeps the smallest distance. An exact tie goes to the earlier node, making seeded runs repeatable.

Let q_near be that node, q_rand the sample, and η the maximum extension length. For nonzero d = q_rand − q_near, steering gives:

A sample closer than η becomes the proposed endpoint. A farther sample sets the direction for an η-long step. If the sample equals the nearest node, the extension adds nothing.

The nearest-node scan costs O(n) distance checks for n stored nodes. Practical planners can use spatial indexes. The small tree here keeps the scan visible in the Python code.

Calculate one proposed extension

Take q_near = (1, 1) m, q_rand = (4, 5) m, and η = 0.5 m. Then d = (3, 4) m and ‖d‖₂ = 5 m. The scale factor is 0.5/5 = 0.1, so q_new = (1.3, 1.4) m.

For the room's central obstacle, the closest point on this short segment is its new endpoint. Its center distance is √(1.7² + 1.6²) = √5.45 ≈ 2.334524 m. Subtracting 1.2 m gives minimum clearance 1.134524 m, so this extension clears the obstacle and the walls.

A later step needs its own check. Clear endpoints alone cannot establish that their connecting segment is clear. The continuous collision-checking lesson derives the clamped projection that finds the minimum distance anywhere along a segment.

Check the final connection to the goal

A nearby node can still have an obstacle between it and the goal. This planner attempts the final segment only when its length is at most η. It applies the same continuous collision and wall checks before declaring success.

If that segment passes, the tree stores the exact goal and its parent. If a sample already landed exactly on the goal, that node completes the path without adding a duplicate. A failed goal connection leaves the accepted branch available for later exploration.

Path length adds the lengths of all edges on the parent chain, including the final goal connection. It excludes branches that do not belong to that chain. The experiment reports this length in meters.

Compare seeds and planning budgets

Sampling-based path planning

Grow a tree around the obstacles

A disk of radius 0.2 m moves inside a 6 m square. Each accepted branch checks the entire straight motion, including the final connection to the goal.

Planning exampleRoom around one obstacleSmall budget, same roomSolid barrierNarrow passageCustom settings

Maximum extension length (m)

0.50 m

Sample budget

200 attempts

Sample seed1742

Goal-sampling bias (%)

10%

Each change starts a fresh tree. The seed repeats the same sample sequence. A larger budget extends that sequence until the first solution; it does not improve a solution the planner has already found.

Tree and robot-center path in world axes (m)

• Gray disk: physical obstacle; dashed blue circle: forbidden robot centers
• Thin blue branch: accepted extension; thick amber line: complete solution
• S: start; G: goal; diamond: last sample; cross: last proposed center

Planning result

Path found

Sample attempts

54

Tree nodes

41

Accepted extensions

39

Rejected extensions

15

Rejected goal connections

0

Solution length (m)

6.745708

Nearest goal distance (m)

0.000000

Start center (m)

(0.600000, 3.000000)

Goal center (m)

(5.400000, 3.000000)

Last sample (m)

(5.400000, 3.000000)

Last proposed center (m)

(5.155703, 3.026301)

Last extension

Accepted

Path found. The first complete path has length 6.745708 m. Basic RRT does not certify the shortest path.

Accepted extensions count successful sample attempts. Tree nodes also include the starting node and, when needed, one extra node for the checked final goal connection. Collision checks use a contact tolerance of 10⁻¹⁰ m; this is separate from a physical safety margin.

Reset RRT experiment

The default room run finds a path after 54 attempts with seed 7. It accepts 39 sampled extensions and rejects 15. Its 41 nodes include the start and an extra goal node, and its solution length is 6.745708 m.

Choose Small budget, same room. The first ten samples produce eight nodes and no complete path. Returning to the larger budget extends the same sample sequence and finds the route, demonstrating why an early failure cannot establish impossibility.

Change the seed, step length, or goal bias to start a fresh run. A larger step can reject motions that cut across obstacles; a smaller step needs more branches to travel the same distance. More goal samples can pull toward the destination while repeatedly hitting a blocking obstacle.

The sample generator uses an unsigned 32-bit state s: s ← (1664525s + 1013904223) mod 2³². Each draw returns s/2³². Every attempt consumes three draws for the goal choice and the two uniform coordinates, even when it chooses the goal, so comparisons stay aligned by attempt.

Understand exploration and narrow passages

Sampling a target anywhere in the room favors nodes with large regions in which they are the nearest node. These regions are Voronoi cells. Exposed branches have more chances to grow toward unexplored space; LaValle's original RRT report develops this exploration idea.

Narrow passages occupy little sampling area and can require several well-placed extensions. The Narrow passage preset places obstacle centers at (3, 1.4) and (3, 4.5) m, each with radius 1.25 m. Inflation increases each radius to 1.45 m.

At x = 3 m, the lower forbidden disk reaches y = 2.85 m and the upper one begins at y = 3.05 m. Robot centers therefore have a 0.20 m gap between them. The preset succeeds after 39 attempts with seed 7; that single result does not predict how all narrow passages compare with the room.

The Solid barrier preset uses six overlapping circles that join the lower and upper walls after inflation. Geometry establishes that this map separates the start from the goal. The planner still reports only Budget exhausted, because its search did not prove that separation.

Read success and failure carefully

Path found means every edge of the returned route passed this model's motion check. Basic RRT does not certify the shortest path. More samples after the first success do nothing here because this implementation stops immediately.

RRT* changes how the tree chooses and revises connections to improve path cost. Karaman and Frazzoli analyze its asymptotic optimality under stated assumptions. The widget implements basic RRT without rewiring.

Budget exhausted means the selected run found no solution within its allotted attempts. A narrow opening, an unlucky sequence, or a genuinely disconnected free space can all produce that result.

Probabilistic completeness is a limiting statement: under suitable sampling, local-motion, and feasible-path assumptions, the probability of finding a solution approaches one as the number of attempts grows. LaValle explains the distinction from a complete decision procedure. It gives no finite deadline, and the finite-state pseudorandom generator in this lesson does not itself establish that theorem.

A geometric route also leaves execution work. This disk can translate in any direction; a car cannot. Real motion planning must account for the robot's allowed motions, uncertain geometry, and the timing constraints along a chosen path.

Reproduce the planner in Python

This Python 3 example uses only the standard library. It repeats the default room, the ten-attempt limit, the solid barrier, and the narrow passage. Coordinates and random draws follow the widget's rules; output rounds lengths to six decimal places.

from math import hypot

START, GOAL = (0.6, 3.0), (5.4, 3.0)
RHO, EPS = 0.2, 1e-10


def distance(a, b):
    return hypot(a[0] - b[0], a[1] - b[1])


def clear(a, b, obstacles):
    if not all(RHO + EPS < v < 6 - RHO - EPS for p in (a, b) for v in p):
        return False
    dx, dy = b[0] - a[0], b[1] - a[1]
    length = hypot(dx, dy)
    for c, radius in obstacles:
        along = 0 if length == 0 else ((c[0] - a[0]) * dx + (c[1] - a[1]) * dy) / length
        t = 0 if length == 0 else max(0, min(1, along / length))
        closest = (a[0] + t * dx, a[1] + t * dy)
        if distance(closest, c) - radius - RHO <= EPS:
            return False
    return True


def plan(obstacles, budget, seed=7, step=0.5, bias=0.1):
    state = seed

    def random():
        nonlocal state
        state = (1664525 * state + 1013904223) % 2**32
        return state / 2**32

    nodes, parents = [START], [None]
    for attempt in range(1, budget + 1):
        choice, x, y = random(), 0.2 + 5.6 * random(), 0.2 + 5.6 * random()
        sample = GOAL if choice < bias else (x, y)
        nearest = min(range(len(nodes)), key=lambda i: distance(nodes[i], sample))
        a = nodes[nearest]
        gap = distance(a, sample)
        if gap == 0:
            continue
        scale = min(1, step / gap)
        b = (a[0] + scale * (sample[0] - a[0]), a[1] + scale * (sample[1] - a[1]))
        if not clear(a, b, obstacles):
            continue
        nodes.append(b)
        parents.append(nearest)
        if distance(b, GOAL) <= step and clear(b, GOAL, obstacles):
            if b != GOAL:
                nodes.append(GOAL)
                parents.append(len(nodes) - 2)
            length, index = 0.0, len(nodes) - 1
            while parents[index] is not None:
                parent = parents[index]
                length += distance(nodes[index], nodes[parent])
                index = parent
            return attempt, len(nodes), length
    return budget, len(nodes), None


room = [((3, 3), 1)]
barrier = [((3, i + 0.5), 0.65) for i in range(6)]
narrow = [((3, 1.4), 1.25), ((3, 4.5), 1.25)]
for name, obstacles, budget in [
    ("room", room, 200), ("small budget", room, 10),
    ("barrier", barrier, 200), ("narrow", narrow, 300),
]:
    attempts, nodes, length = plan(obstacles, budget)
    result = "No path found" if length is None else f"{length:.6f} m"
    print(f"{name}: attempts={attempts}, nodes={nodes}, length={result}")

Expected output:

room: attempts=54, nodes=41, length=6.745708 m
small budget: attempts=10, nodes=8, length=No path found
barrier: attempts=200, nodes=82, length=No path found
narrow: attempts=39, nodes=30, length=5.527330 m

Try it yourself

1. Steer and check. Use q_near = (1, 1) m and q_rand = (4, 5) m. Increase η to 1 m. Find the proposed endpoint and the minimum clearance from the room's central obstacle.

Show the extension and clearance solution

The direction has length 5 m, so scale it by 1/5. The proposed endpoint is (1.6, 1.8) m, exactly 1 m from the nearest node.

The obstacle's closest point on this segment is again the new endpoint. Its center distance is √(1.4² + 1.2²) = √3.4 ≈ 1.843909 m. Subtracting the inflated radius 1.2 m gives minimum clearance 0.643909 m; the segment also clears the walls.

2. Interpret a failed run. Select Small budget, same room, then return to Room around one obstacle. What does the ten-attempt result establish? Why does increasing the budget from 200 to 300 leave the default solution unchanged?

Show the search-budget solution

The ten-attempt run establishes only that this sequence has not yet connected the goal. The longer run finds a route on attempt 54, which rules out interpreting the earlier result as proof that the room has no path.

Both budgets exceed 54. This planner stops at the first solution and uses the same seed, so both runs return the same tree and 6.745708 m path. Finding a shorter route requires a method that continues searching or revises the route.

Sources and further study

• Steven LaValle, Rapidly-Exploring Random Trees: A New Tool for Path Planning (1998). The original report explains tree growth and its exploration bias.
• Steven LaValle, Planning Algorithms, Section 5.5. Tree exploration, nearest-point queries, and planning with one or more trees.
• OMPL: geometric RRT. A practical planner interface with goal bias and extension range controls.
• Sertac Karaman and Emilio Frazzoli, Sampling-based Algorithms for Optimal Motion Planning. The distinction between basic RRT and planners with asymptotic cost guarantees.

Compare the tree with A* search on a known graph. The graph representation, allowed connections, and stopping rule all shape what each result means.