About RRTs

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, ${\cal C}$ (this can be considered as a general state space that might include position and velocity information). An RRT that is rooted at a configuration q_init and has K vertices is constructed using the following:

BUILD_RRT( $q_{init},K,\Delta q$ )

1 G.init(q_init);

2 for k = 1 to K

3 $q_{rand} \leftarrow \;$ RAND_CONF();

4 $q_{near} \leftarrow \;$ NEAREST_VERTEX(q_rand,G);

5 $q_{new} \leftarrow \;$ NEW_CONF $(q_{near},\Delta q)$ ;

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 ${\cal C}$ . Alternatively, one could replace RAND_CONF with RAND_FREE_CONF, and sample configurations in ${\cal C}_{free}$ (by using a collision detection algorithm to reject samples in ${\cal C}_{obs}$ ).

It is assumed that a metric $\rho$ has been defined over ${\cal C}$ . 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 $d \leftarrow \infty$ ;

2 for each $v \in V$

3 if $\rho(q,v) < d$ then

4 v_new = v; $d \leftarrow \rho(q,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, $\Delta q$ , 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 ${\cal C}$ is a square region in the plane. Let $\rho$ represent the Euclidean metric. The frames below show the construction of an RRT for the case of ${\cal C}= [0,100] \times [0,100]$ , $\Delta q = 1$ , and q_init = (50,50):

$\psfig {file=figs/out3.ps,height=2.0truein}$ $\psfig {file=figs/out10.ps,height=2.0truein}$ $\psfig {file=figs/out30.ps,height=2.0truein}$

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.

Return to main RRT page

Web page maintained by Steve LaValle
Partial support provided by NSF CAREER Award IRI-970228 (LaValle)

1	G.init(q_init);
2	for k = 1 to K
3	$q_{rand} \leftarrow \;$ RAND_CONF();
4	$q_{near} \leftarrow \;$ NEAREST_VERTEX(q_rand,G);
5	$q_{new} \leftarrow \;$ NEW_CONF $(q_{near},\Delta q)$ ;
6	G.add_vertex(q_new);
7	G.add_edge(q_near,q_new);
8	Return G

1	$d \leftarrow \infty$ ;
2	for each $v \in V$
3	if $\rho(q,v) < d$ then
4	v_new = v; $d \leftarrow \rho(q,v)$ ;
5	Return q;