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


Abstract

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