Skip to content

Rapidly-exploring Random Trees: A New Tool for Path Planning

Authors: Steven M. LaValle

Published: 1998 (Technical Report)

Source: University of Illinois

Algorithm: RRT

Summary

Introduces RRTs for sampling-based motion planning in high-dimensional configuration spaces.

Abstract

We introduce the concept of a Rapidly-exploring Random Tree (RRT) as a randomized data structure that is designed for a broad class of path planning problems. While they share many of the beneficial properties of existing randomized planning techniques, RRTs are specifically designed to handle nonholonomic constraints (including dynamics) and high degrees of freedom. An RRT is iteratively expanded by applying control inputs that drive the system slightly toward randomly-selected points, as opposed to requiring point-to-point convergence, as in the probabilistic roadmap approach. Several desirable properties and a basic implementation of RRTs are discussed. To date, we have successfully applied RRTs to holonomic, nonholonomic, and kinodynamic planning problems of up to twelve degrees of freedom.

Primary

Paper msl.cs.uiuc.edu

Alternate

lavalle.pl lavalle.pl en.wikipedia.org en.wikipedia.org

Tags

  • Motion planning

  • Path planning

  • Sampling-based

  • RRT

  • Rapidly-exploring random trees