TABLE OF CONTENTS Steven M. LaValle, Iowa State University, Ames, IA
James J. Kuffner, Jr., University of Tokyo, Tokyo, Japan
We present our current progress on the design and analysis of path planning algorithms based on Rapidly-exploring 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 obtained by other successful randomized planning methods. In addition, RRTs are particularly suited for problems that involve differential constraints. Basic theoretical properties of RRT-based planners are established. 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 freedom. Key open issues and areas of future research are also discussed.
Given the vast, growing collection of applications that involve the design of motion strategies, the successes of motion planning algorithms have just begun to scratch its surface. The potential for automating motions is now greater than ever as similar problems continue to emerge in seemingly disparate areas. The traditional needs of roboticists continue to expand in efforts to automate mobile robots, manipulators, humanoids, spacecraft, etc. Researchers in computer graphics and virtual reality have increasing interests in automating the animations of life-like characters or other moving bodies. In the growing field of computational biology, many geometric problems have arisen, such as studying the configuration spaces...
