A Rapidly-exploring Random Tree (RRT) is a data structure and algorithm that is designed for efficiently searching nonconvex high-dimensional spaces. RRTs are constructed incrementally in a way that quickly reduces the expected distance of a randomly-chosen point to the tree. RRTs are particularly suited for path planning problems that involve obstacles and differential constraints (nonholonomic or kinodynamic). RRTs can be considered as a technique for generating open-loop trajectories for nonlinear systems with state constraints. An RRT can be intuitively considered as a Monte-Carlo way of biasing search into largest Voronoi regions. Some variations can be considered as stochastic fractals. Usually, an RRT alone is insufficient to solve a planning problem. Thus, it can be considered as a component that can be incorporated into the development of a variety of different planning algorithms.

Here is a brief description of the method for a general configuration space, (this can be considered as a general state space that might include position and velocity information). An RRT that is rooted at a configuration

BUILD_RRT()

1 | G.init(q_{init}); |

2 | for k = 1 to K |

3 | RAND_CONF(); |

4 | NEAREST_VERTEX(q_{rand},G); |

5 | NEW_CONF; |

6 | G.add_vertex(q_{new}); |

7 | G.add_edge(q_{near},q_{new}); |

8 | Return G |

Step 3 chooses a random configuration, *q*_{rand}, in . Alternatively, one
could replace RAND_CONF with RAND_FREE_CONF, and sample
configurations in (by using a collision detection
algorithm to reject samples in ).

It is assumed that a metric has been defined over . Step 4
selects the vertex, *x*_{near}, in the RRT, *G*, that is closest to
*q*_{rand}. This can be implemented as shown below.

NEAREST_VERTEX(*q*,G)

1 | ; |

2 | for each |

3 | if then |

4 | v_{new} = v; ; |

5 | Return q; |

In Step 5 of BUILD_RRT, NEW_CONF selects a new configuration,
*q*_{new}, by moving from *q*_{near} an incremental distance, , in the direction of *q*_{rand}.
This assumes that motion in any direction is possible.
If differential constraints exist, then inputs are applied to the
corresponding control system, and new configurations are
obtained by numerical integration.
Finally, a new vertex, *q*_{new},
and is added, and a new edge is added from *q*_{near} to *q*_{new}.

To gain a better understanding of RRTs, consider the special case in
which is a square region in the plane. Let represent the
Euclidean metric. The frames below show the construction of an RRT
for the case of , , and
*q*_{init} = (50,50):

The RRT quickly expands in a few directions to quickly explore the
four corners of the square. Although the construction method is
simple, it is no easy task to find a method that yields such desirable
behavior. Consider, for example, a naive random tree that is
constructed incrementally by selecting a vertex at random, an input at
random, and then applying the input to generate a new vertex.
Although one might intuitively expect the tree to ``randomly'' explore
the space, there is actually a very strong bias toward places already
explored (simulation experiments yield an extremely high density of
vertices near *q*_{init}, with little other
exploration). A random walk also suffers from a bias toward places
already visited. An RRT works in the opposite manner by being biased
toward places not yet visited. This can be seen by considering the
Voronoi diagram of the RRT vertices. Larger Voronoi regions occur on
the ``frontier'' of the tree. Since vertex selection is based on
nearest neighbors, this implies that vertices with large Voronoi
regions are more likely to be selected for expansion. On average, an
RRT is constructed by iteratively breaking large Voronoi regions into
smaller ones.

Web page maintained by Steve LaValle

Partial support provided by NSF CAREER Award IRI-970228 (LaValle)