James Kuffner  

Classical Path Planning with RRTs


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

Path planning problems arise in such diverse fields as robotics, assembly analysis, virtual prototyping, pharmaceutical drug design, manufacturing, and computer animation. Path planning problems generally involve computing a continuous sequence ("a path") of configurations (generalized coordinates) between an initial configuration (start) and a final configuration (goal) while respecting certain constraints.

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"

The term "motion planning" is usually distinguished from "path planning" in that the computed path is parameterized by time (i.e. a trajectory). The consideration of "time" or "system dynamics" (physics) is often important for problems requiring time-parameterized solution trajectories.

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.

References and Further Information

1997 - 2009 © James Kuffner, Jr.