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).
## 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. |