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

This provides very basic background for the rest of the book.

Chapter 1: Introductory Material

•

This chapter offers some general perspective and includes some motivational examples and applications of planning algorithms.

Chapter 2: Discrete Planning

•

This 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

The main source of inspiration for the problems and algorithms covered in this part is robotics. The methods, however, are general enough for use in other appli- cations 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 Transformations

•

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

•

This chapter introduces concepts from topology and uses them to formu- late 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.

1.5. ORGANIZATION OF THE BOOK 25

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 Planning

•

This chapter introduces many problems and algorithms that are extensions of the methods from Chapters 5 and 6. Most can be followed with basic un- derstanding 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 plan- ning problem but still does not introduce differential constraints, which are deferred until Part IV. The previous chapters of Part II focused on comput- ing open-loop plans, which means that any errors that might occur during ex- ecution of the plan are ignored, yet the plan will be executed as planned. Us- ing 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

1. However, some sections cover extensions to continuous spaces; to understand these parts, it will be helpful to have read some of Part II.

Chapter 9: Basic Decision Theory

•

The 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 chain- ing together a sequence of basic decision-making problems. Dynamic pro- gramming 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

•

The chapter 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 Uncertainty

•

This chapter covers several planning problems and algorithms that involve sensing uncertainty. This includes problems such as localization, map build- ing, pursuit-evasion, and manipulation. All of these problems are unified under the idea of planning in information spaces, which follows from Chap- ter 11.

PART IV: Planning Under Differential Constraints

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

Chapter 13: Differential Models

•

This 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 Differential Con- straints

•

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 constraints.

Chapter 15: System Theory and Analytical Techniques

•

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.