Rapidly-exploring random tree

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

Part of a series on
Probabilistic data structures
Bloom filter · Skip list
Random trees
Random binary tree · Treap Rapidly-exploring random tree
Related
Randomized algorithm
Computer science Portal

A Rapidly-exploring random tree (RRT) is a data structure and algorithm designed for efficiently searching nonconvex, high-dimensional search spaces. The tree is constructed in such a way that any sample in the space is added by connecting it to the closest sample already in the tree.

RRTs, developed by Steven M. LaValle and James Kuffner, have been widely used in robotics 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

• "←" is a loose shorthand for "changes to". For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the value that follows.

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 straight-forward 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 vector.

"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