Rapidly-Exploring Random Trees: Progress and Prospects

Abstract

We present our current progress on the design and analysis of path planning algorithms based on Rapidlyexploring Random Trees (RRTs). The basis for our methods is the incremental construction of search trees that attempt to rapidly and uniformly explore the state space, offering benefits that are similar to those ob­ tained by other successful randomized planning meth­ ods. In addition, RRTs are particularly suited for prob­ lems that involve differential constraints. Basic the­ oretical properties of RRT-based planners are estab­ lished. Several planners based on RRTs are discussed and compared. Experimental results are presented for planning problems that involve holonomic constraints for rigid and articulated bodies, manipulation, nonholonomic constraints, kinodynamic constraints, kinematic closure constraints, and up to twelve degrees of free­ dom. Key open issues and areas of future research are also discussed.