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.
Input: Initial configuration qinit, number of vertices in RRT K, incremental distance Δq)
Output: RRT graph G
for k = 1 to K
qrand ← RAND_CONF()
qnear ← NEAREST_VERTEX(qrand, G)
qnew ← NEW_CONF(qnear, Δq)
In the algorithm above, "RAND_CONF" grabs a random configuration qrand in C. This may be replaced with a function "RAND_FREE_CONF" that uses samples in Cfree, while rejecting those in Cobs using some collision detection algorithm.
"NEAREST_VERTEX" is a straight-forward function that runs through all vertexes v in graph G, calculates the distance between qrand and v using some measurement function thereby returning the nearest vector.
"NEW_CONF" selects a new configuration qnew by moving an incremental distance Δq from qnear in the direction of qrand.