Rapidly-exploring random tree

From Wikipedia, the free encyclopedia

A dense RRT graph, after 2345 iterations, demonstrating it's capability of "space filling"

A Rapidly-exploring Random Tree (RRT) is a data structure and algorithm designed for efficiently searching nonconvex, high-dimensional search spaces. Simply put, 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.

1 Introduction
2 Algorithm
- 2.1 Visualization
3 References

[edit] 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.^[1]

[edit] Algorithm

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

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

  G.init(q_init)
  for k = 1 to K
    q_rand ← RAND_CONF()
    q_near ← NEAREST_VERTEX(q_rand, G)
    q_new ← NEW_CONF(q_near, Δq)
    G.add_vertex(q_new)
    G.add_edge(q_near, q_new)
  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.