Rapidly exploring random tree

Part of a series on
Probabilistic
data structures
Random trees
Related
A visualization of an RRT graph after 45 and 390 iterations
An animation of an RRT starting from iteration 0 to 10000

A rapidly exploring random tree (RRT) is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. RRTs were developed by Steven M. LaValle and James J. Kuffner Jr.[1][2] They easily handle problems with obstacles and differential constraints (nonholonomic and kinodynamic) and have been widely used in autonomous robotic motion planning.

RRTs can be viewed as a technique to generate open-loop trajectories for nonlinear systems with state constraints. An RRT can also be considered as a Monte-Carlo method to bias search into the largest Voronoi regions of a graph in a configuration space. Some variations can even be considered stochastic fractals.[3]

RRTs can be used to compute approximate control policies to control high dimensional nonlinear systems with state and action constraints.

  1. ^ LaValle, Steven M. (October 1998). "Rapidly-exploring random trees: A new tool for path planning" (PDF). Technical Report (TR 98–11). Computer Science Department, Iowa State University.
  2. ^ LaValle, Steven M.; Kuffner Jr., James J. (2001). "Randomized Kinodynamic Planning" (PDF). The International Journal of Robotics Research. 20 (5): 378–400. doi:10.1177/02783640122067453. S2CID 40479452.
  3. ^ http://msl.cs.uiuc.edu/rrt/about.html Archived 2007-10-21 at the Wayback Machine About RRTs, by Steve LaValle