Rapidly exploring random tree

File:RRT graph2.png

A dense RRT graph, after 2345 iterations, demonstrating its capability of "space filling"

A Rapidly-exploring Random Tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional state spaces by building a tree. The tree is constructed by drawing random samples from the state space and attempting to connect them to the nearest state in the tree. The length of this connection is capped by a user-tuned parameter, resulting in a tree that is biased to incrementally grow towards large unsearched space. RRTs were developed by Steven M. LaValle and James Kuffner and have been widely used in autonomous robotic path planning.

Introduction

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.

Algorithm

For a general configuration space C, the algorithm in pseudocode is as follows:

Algorithm BuildRRT
  Input: Initial configuration qinit, number of vertices in RRT K, incremental distance Δq)
  Output: RRT graph G

  G.init(qinit)
  for k = 1 to K
    qrand ← RAND_CONF()
    qnear ← NEAREST_VERTEX(qrand, G)
    qnew ← NEW_CONF(qnear, Δq)
    G.add_vertex(qnew)
    G.add_edge(qnear, qnew)
  return G

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

In the algorithm above, "RAND_CONF" grabs a random configuration q_rand in C. This may be replaced with a function "RAND_FREE_CONF" that uses samples in C_free, while rejecting those in C_obs using some collision detection algorithm.

"NEAREST_VERTEX" is a straightforward function that runs through all vertexes v in graph G, calculates the distance between q_rand and v using some measurement function thereby returning the nearest vertex.

"NEW_CONF" selects a new configuration q_new by moving an incremental distance Δq from q_near in the direction of q_rand. (According to in holonomic problems, this should be omitted and q_rand used instead of q_new.)

Visualization

A visualization of a RRT graph after 45 and 390 iterations

An animation of a RRT starting from iteration 0 till 10000

See also

• Probabilistic roadmap
• Space-filling tree
• Motion planning
• Randomized algorithm

External links

• Java visualizer of RRT and RRT* including map editor