James Kuffner, Jr.
Rapidly-Exploring Random Trees: Progress and Prospects
Steven M. LaValle
We present our current progress on the design and analysis of path
planning algorithms based on Rapidly-exploring Random Trees (RRTs).
The basis of our methods is the incremental construction fo search
trees that attempt to rapidly and uniformly explore the state space,
offering benefits that are similar to those obtained by other
successful randomized planning methods; however, RRTs are particularly
suited for problems that invoke differential constraints. Basic
properties of RRTs are established, including convergence to a uniform
coverage of nonconvex spaces. Several planners based on RRTs are
discussed and compared. Experimental results are presented for
planning problems that invoke holonomic constraints for rigid and
articulated bodies, manipulation, nonholonomic constraints,
kinodynamic constraints, kinematic closure constraints, and up to
twelve degrees of freedom. Key open issues and areas of furture
research are also discussed.