Definitions

# Rapidly-exploring random tree

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.

RRT has 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:

`  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`

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.

## References

Search another word or see rapidlyon Dictionary | Thesaurus |Spanish