A central theme throughout motion planning is to transform the
continuous model into a discrete one. Due to this transformation,
many algorithms from Chapter 2 are embedded in motion
planning algorithms. There are two alternatives to achieving this
transformation, which are covered in Chapters 5 and
6, respectively. Chapter 6 covers *combinatorial motion planning*, which means that from the input model
the algorithms build a discrete representation that *exactly*
represents the original problem. This leads to *complete*
planning approaches, which are guaranteed to find a solution when it
exists, or correctly report failure if one does not exist. Chapter
5 covers *sampling-based motion planning*, which
refers to algorithms that use collision detection methods to sample
the configuration space and conduct discrete searches that utilize
these samples. In this case, completeness is sacrificed, but it is
often replaced with a weaker notion, such as *resolution
completeness* or *probabilistic completeness*. It is important to
study both Chapters 5 and 6 because each
methodology has its strengths and weaknesses. Combinatorial methods
can solve virtually any motion planning problem, and in some
restricted cases, very elegant solutions may be efficiently
constructed in practice. However, for the majority of
``industrial-grade'' motion planning problems, the running times and
implementation difficulties of these algorithms make them unappealing.
Sampling-based algorithms have fulfilled much of this need in recent
years by solving challenging problems in several settings, such as
automobile assembly, humanoid robot planning, and conformational
analysis in drug design. Although the completeness guarantees are
weaker, the efficiency and ease of implementation of these methods
have bolstered interest in applying motion planning algorithms to a
wide variety of applications.

Two additional chapters appear in Part II. Chapter 7 covers several extensions of the basic motion planning problem from the earlier chapters. These extensions include avoiding moving obstacles, multiple robot coordination, manipulation planning, and planning with closed kinematic chains. Algorithms that solve these problems build on the principles of earlier chapters, but each extension involves new challenges.

Chapter 8 is a transitional chapter that involves many elements of motion planning but is additionally concerned with gracefully recovering from unexpected deviations during execution. Although uncertainty in predicting the future is not explicitly modeled until Part III, Chapter 8 redefines the notion of a plan to be a function over state space, as opposed to being a path through it. The function gives the appropriate actions to take during exection, regardless of what configuration is entered. This allows the true configuration to drift away from the commanded configuration. In Part III such uncertainties will be explicitly modeled, but this comes at greater modeling and computational costs. It is worthwhile to develop effective ways to avoid this.

Steven M LaValle 2012-04-20