Rapidly-Exploring Random Trees · Sample-Based Planning in Continuous Space

Abstract

RRT (LaValle, 1998) grows a tree from the start configuration into the free space by repeatedly drawing a random sample, finding the nearest existing node, and extending toward the sample by a fixed step. The tree expands quickly into unexplored regions. RRT is probabilistically complete (the probability of finding a feasible path approaches 1 as the number of samples grows), but the path it returns is generally not optimal. A goal-bias of 0.10 (sampling the goal directly with 10 % probability) collapses the search dramatically once the goal is reachable.

Algorithm

T  ←  {x_start}
loop:
    x_rand   ←  goal     with probability  p_bias
                random   otherwise
    x_near   ←  nearest node in T to x_rand
    x_new    ←  x_near + step · (x_rand − x_near) / ‖x_rand − x_near‖
    if  segment(x_near, x_new)  is collision-free:
        add  x_new  to  T  with parent  x_near
    if  ‖x_new − goal‖ < step  and  segment(x_new, goal) is free:
        connect to goal, return path

Implementation parameters: step size 2.0 grid units, goal-bias probability 0.10, maximum 2000 nodes, collision check by 20-sample interpolation along each candidate edge.

Diagnostic: Tree Growth and Final Path

The faint red lines are tree edges grown by sampling. The dark line is the path back from goal to start through the tree's parent pointers. Note the characteristic Voronoi-bias of RRT: the tree's frontier expands toward unexplored regions because random samples are more likely to land near unexplored Voronoi cells.

Headline Numbers Across Four Environments

RRT pays a 13–26 % path-length premium over A* because it follows the tree topology rather than the metric-optimal route. The maze environment is RRT's worst case here: 381 nodes and 81 ms because the algorithm has to grow a long thin tree through narrow channels, with frequent rejections.

When RRT earns its place

RRT is the right tool when:

• The configuration space is continuous and high-dimensional (a robotic arm with 6-7 DOF, a non-holonomic vehicle in SE(2)). A* on a discretised grid would explode in expanded-node count; RRT's complexity grows with the difficulty of the corridors, not the dimensionality.
• The robot has steering constraints. With a steering function that respects kinematics, RRT extends with feasible motions only: Hybrid A* and Kinodynamic RRT solve similar problems with different mechanics.
• You need any feasible path quickly. RRT is anytime-friendly: at any moment after the first connection to goal, you have a valid path that improves only marginally with more samples.

For path optimality on top of probabilistic completeness, the natural extension is RRT*: rewire the tree on each insertion so the path-cost from start through any node is minimised. RRT* converges to the optimal path almost surely as samples grow.

Cross-Planner Comparison on env 0