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

Visualization

References