RRT-connect: An efficient approach to single-query path planning

TLDR

The algorithm was originally developed for planning collision‑free motions of a 7‑DOF human arm for graphic animation, and has since been applied to diverse path‑planning tasks. The paper presents a simple, efficient randomized algorithm for single‑query path planning in high‑dimensional configuration spaces. The method incrementally builds two rapidly‑exploring random trees rooted at the start and goal, expands them toward each other using a greedy heuristic, and includes basic theoretical analysis. The algorithm successfully generated collision‑free motions for rigid objects in 2D and 3D and for a 6‑DOF PUMA arm in a 3D workspace, demonstrating its applicability to diverse path‑planning problems.

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 plan 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.