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
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
- Proven to ultimately converge to uniform coverage of any
non-convex space (provided the sampling distribution in
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
"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.
Random Trees (RRTs) were initially designed to plan open-loop
trajectories for systems with nonholonomic constraints induced by
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.