A Rapidly-exploring random tree (RRT) is a data structure

Data structure

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...

 and algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 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

Steven M. LaValle

Steven M. LaValle is an American roboticist and a Professor of Computer Science at the University of Illinois at Urbana-Champaign. He is best known for his work on RRT's and his book Planning Algorithms, one of the most highly cited texts in the field.-External links:*...

 and James Kuffner, have been widely used in robotics

Robotics

Robotics is the branch of technology that deals with the design, construction, operation, structural disposition, manufacture and application of robots...

 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

Monte Carlo method

Monte Carlo methods are a class of computational algorithms that rely on repeated random sampling to compute their results. Monte Carlo methods are often used in computer simulations of physical and mathematical systems...

 way of biasing search into largest Voronoi regions

Voronoi diagram

In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...

. Some variations can be considered as stochastic

Stochastic

Stochastic refers to systems whose behaviour is intrinsically non-deterministic. A stochastic process is one whose behavior is non-deterministic, in that a system's subsequent state is determined both by the process's predictable actions and by a random element. However, according to M. Kac and E...

 fractal

Fractal

A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...

s. 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

Configuration space

- Configuration space in physics :In classical mechanics, the configuration space is the space of possible positions that a physical system may attain, possibly subject to external constraints...

 C, the algorithm in pseudocode

Pseudocode

In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...

 is as follows:
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
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

See also

• Probabilistic roadmap
• Space-filling tree
  Space-filling tree
  Space-filling trees are geometric constructions that are analogous to space-filling curves, but have a branching, tree-like structure and are rooted. A space-filling tree is defined by an incremental process that results in a tree for which every point in the space has a finite-length path that...
  
  
• Motion planning
  Motion planning
  Motion planning is a term used in robotics for the process of detailing a task into discrete motions....
  
  
• Randomized algorithm
  Randomized algorithm
  A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...