RRT-Connect: An Efficient Approach to Single-Query Path Planning

James Kuffner, Jr.

Department of Computer Science
Stanford University
Stanford, CA 94305, USA
Steven M. LaValle

Department of Computer Science
Iowa State University
Ames, IA 50011, USA


A simple and efficient randomized algorithm is presented for solving single-query path planning problems in high-dimensional configuration spaces. The method works by incrementally building two Rapidly-exploring Random Trees (RRTs) rooted at the start and the goal configurations. The trees each explore space around them, and also advance towards each other through the use of a simple greedy heuristic. Although originally designed to quickly synthesize motions for a human arm (modeled as a 7-DOF kinematic chain) for the automatic graphic animation of collision-free grasping and manipulation tasks, the algorithm has been successfully applied to a variety of path planning problems. Computed examples include generating collision-free motions for rigid objects in 2D and 3D, and collision-free manipulation motions for a 6-DOF PUMA arm in a 3D workspace. Some basic theoretical analysis is also presented.

Back to Publications index