Classical Path Planning with RRTs

Overview

RRT-Connect is a simple and efficient algorithm for solving single-query path planning problems in high-dimensional configuration spaces. Inspired by classical AI bidirectional search, 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 greedy heuristic. (See algorithm animations)

The algorithm was designed to be both general and practical, and has been successfully applied to a variety of challenging planning problems. Some of the key advantages of RRT-Connect include:

• No preprocessing of the environment.
• The free configuration space is explored in a greedy fashion, yet high-dimensional local minima are gracefully overcome.
• Computation time scales with problem difficulty (i.e. simple queries will be solved very efficiently).
• Easy to implement effectively (no complicated parameter tuning is required).
• Proven to ultimately converge to uniform coverage of any non-convex space (provided the sampling distribution in uniform).

Algorithm Description	Computed Examples	Software	Other Related Info

Path Planning

The "basic path planning problem" involves computing a collision-free path between two configurations in a static environment of known obstacles. In this case, the constraints on the solution path arise from the geometry of both the obstacles and the "robot" (the object for which a path is being computed). If the robot can be represented as a single 3D rigid object that rotates and translates in a 3D environment, then the problem is sometimes referred to as "the piano-mover's problem".

"Path Planning" vs. "Motion Planning"

Rapidly-exploring Random Trees (RRTs) were initially designed to plan open-loop trajectories for systems with nonholonomic constraints induced by system dynamics("kinodynamic planning").

Subsequently, RRT-Connect was developed to efficiently solve instances of the "basic path planning problem" involving holonomic systems. It was first used for automatically generating collision-free object manipulation motions for animated characters in interactive 3D virtual environments. Since then, the algorithm has been refined and applied to a broad class of interesting and challenging planning problems.