1.5 Organization of the Book
Here is a brief overview of the book. See also the overviews at the
beginning of Parts II-IV.
PART I: Introductory Material
provides very basic background for the rest of the book.
- Chapter 1: Introductory Material
chapter offers some general perspective and includes some motivational
examples and applications of planning algorithms.
- Chapter 2: Discrete Planning
chapter covers the simplest form of planning and can be considered as
a springboard for entering into the rest of the book. From here, you
can continue to Part II, or even head straight to Part
III. Sections 2.1 and 2.2 are most
important for heading into Part II. For Part III,
Section 2.3 is additionally useful.
PART II: Motion Planning
source of inspiration for the problems and algorithms covered in this
part is robotics. The methods, however, are general enough for use in
other applications in other areas, such as computational biology,
computer-aided design, and computer graphics. An alternative title
that more accurately reflects the kind of planning that occurs is
``Planning in Continuous State Spaces.''
- Chapter 3: Geometric Representations and
The chapter gives important background for
expressing a motion planning problem. Section 3.1 describes
how to construct geometric models, and the remaining sections indicate
how to transform them. Sections 3.1 and 3.2 are
important for later chapters.
- Chapter 4: The Configuration Space
chapter introduces concepts from topology and uses them to formulate
the configuration space, which is the state space that arises in
motion planning. Sections 4.1, 4.2,
and 4.3.1 are important for understanding most of the
material in later chapters. In addition to the previously mentioned
sections, all of Section 4.3 provides useful background
for the combinatorial methods of Chapter 6.
- Chapter 5: Sampling-Based Motion Planning
This chapter introduces motion planning algorithms that have
dominated the literature in recent years and have been applied in
fields both in and out of robotics. If you understand the basic idea
that the configuration space represents a continuous state space, most
of the concepts should be understandable. They even apply to other
problems in which continuous state spaces emerge, in addition to
motion planning and robotics. Chapter 14 revisits
sampling-based planning, but under differential constraints.
- Chapter 6: Combinatorial Motion Planning
The algorithms covered in this section are sometimes called exact
algorithms because they build discrete representations without losing
any information. They are complete, which means that they must
find a solution if one exists; otherwise, they report failure. The
sampling-based algorithms have been more useful in practice, but they
only achieve weaker notions of completeness.
- Chapter 7: Extensions of Basic Motion
This chapter introduces many problems and algorithms that
are extensions of the methods from Chapters 5 and
6. Most can be followed with basic understanding of the
material from these chapters. Section 7.4 covers
planning for closed kinematic chains; this requires an understanding
of the additional material, from Section 4.4
- Chapter 8: Feedback Motion Planning
This is a transitional chapter that introduces feedback into the
motion planning problem but still does not introduce differential
constraints, which are deferred until Part IV. The
previous chapters of Part II focused on computing open-loop plans, which means that any errors that might occur during
execution of the plan are ignored, yet the plan will be executed as
planned. Using feedback yields a closed-loop plan that responds
to unpredictable events during execution.
PART III: Decision-Theoretic Planning
An alternative title to Part III is ``Planning Under
Uncertainty.'' Most of Part III addresses discrete state
spaces, which can be studied immediately following Part I.
However, some sections cover extensions to continuous spaces; to
understand these parts, it will be helpful to have read some of Part
- Chapter 9: Basic Decision Theory
main idea in this chapter is to design the best decision for a
decision maker that is confronted with interference from other
decision makers. The others may be true opponents in a game or may be
fictitious in order to model uncertainties. The chapter focuses on
making a decision in a single step and provides a building block for
Part III because planning under uncertainty can be
considered as multi-step decision making.
- Chapter 10: Sequential Decision Theory
This chapter takes the concepts from Chapter 9 and
extends them by chaining together a sequence of basic decision-making
problems. Dynamic programming concepts from Section 2.3
become important here. For all of the problems in this chapter, it is
assumed that the current state is always known. All uncertainties
that exist are with respect to prediction of future states, as opposed
to measuring the current state.
- Chapter 11: Sensors and Information Spaces
extends the formulations of Chapter 10 into a framework
for planning when the current state is unknown during execution.
Information regarding the state is obtained from sensor observations
and the memory of actions that were previously applied. The
information space serves a similar purpose for problems with sensing
uncertainty as the configuration space has for motion planning.
- Chapter 12: Planning Under Sensing
This chapter covers several planning problems and
algorithms that involve sensing uncertainty. This includes problems
such as localization, map building, pursuit-evasion, and manipulation.
All of these problems are unified under the idea of planning in
information spaces, which follows from Chapter 11.
PART IV: Planning Under Differential
This can be considered as a continuation of Part
II. Here there can be both global (obstacles) and local
(differential) constraints on the continuous state spaces that arise
in motion planning. Dynamical systems are also considered, which
yields state spaces that include both position and velocity
information (this coincides with the notion of a state space in
control theory or a phase space in physics and differential
- Chapter 13: Differential Models
chapter serves as an introduction to Part IV by introducing
numerous models that involve differential constraints. This includes
constraints that arise from wheels rolling as well as some that arise
from the dynamics of mechanical systems.
- Chapter 14: Sampling-Based Planning Under
Algorithms for solving planning problems
under the models of Chapter 13 are presented. Many
algorithms are extensions of methods from Chapter 5.
All methods are sampling-based because very little can be accomplished
with combinatorial techniques in the context of differential
- Chapter 15: System Theory and Analytical
This chapter provides an overview of the concepts and
tools developed mainly in control theory literature. They are
complementary to the algorithms of Chapter 14 and often
provide important insights or components in the development of
planning algorithms under differential constraints.
Steven M LaValle