Overview of Part II: Motion planning

Planning in continuous spaces

Part II makes the transition from discrete to continuous state spaces. Two alternative titles are appropriate for this part: 1) motion planning, or 2) planning in continuous state spaces. Chapters 3–8 are based on research from the field of motion planning, which has been building since the 1970s; therefore, the name motion planning is widely known to refer to the collection of models and algorithms that will be covered. On the other hand, it is convenient to also think of Part II as planning in continuous spaces because this is the primary distinction with respect to most other forms of planning.

In addition, motion planning will frequently refer to motions of a robot in a 2D or 3D world that contains obstacles. The robot could model an actual robot, or any other collection of moving bodies, such as humans or flexible molecules. A motion plan involves determining what motions are appropriate for the robot so that it reaches a goal state without colliding into obstacles. Recall the examples from Section 1.2.

Many issues that arose in Chapter 2 appear once again in motion planning. Two themes that may help to see the connection are as follows.

Implicit representations

A familiar theme from Chapter 2 is that planning algorithms must deal with implicit representations of the state space. In motion planning, this will become even more important because the state space is uncountably infinite.