Overview of Part IV:
Planning Under Differential Constraints

Part IV is a continuation of Part II. It is generally not necessary to read Part III before starting Part IV. In the models and methods studied in Part II, it was assumed that a path can be easily determined between any two configurations in the absence of obstacles. For example, the sampling-based roadmap approach assumed that two nearby configurations could be connected by a ``straight line'' in the configuration space. The constraints on the path are global in the sense that the restrictions are on the set of allowable configurations.

The next few chapters introduce differential constraints, which restrict the allowable velocities at each point. These can be considered as local constraints, in contrast to the global constraints that arise due to obstacles. Some weak differential constraints, such as smoothness requirements, arose in Chapter 8. Part IV goes much further by covering differential consraints in full detail and generality.

Differential constraints arise everywhere. In robotics, most problems involve differential constraints that arise from the kinematics and dynamics of a robot. One approach is to ignore them in the planning process and hope that the differential constraints can be appropriately handled in making refinements. This corresponds to applying the techniques of Part II in robotics applications and then using control techniques to ensure that a computed path is executed as closely as possible. If it is practical, a better approach is to consider differential constraints in the planning process. This yields plans that directly comply with the natural motions of a mechanical system.

Chapter 13 is similar in spirit to Chapter 3. It explains how to construct and represent models that have differential constraints, whereas Chapter 3 did the same for geometric models. It also provides background and motivation for Part IV by giving a catalog of numerous models that can be used in planning algorithms. Differential models are generally expressed as ${\dot x}= f(x,u)$, which is the continuous-time counterpart of the state transition equation, $x_{k+1} = f(x_k,u_k)$. Thus, the focus of Chapter 13 it to define transition functions.

Chapter 14 covers sampling-based planning algorithms for problems that involve differential constraints. There is no chapter on combinatorial algorithms in this context because they exist only in extremely limited cases. Differential constraints seem to destroy most of the nice properties that are needed by combinatorial approaches. Rather than develop complete algorithms, the focus is on resolution-complete planning algorithms. This is complicated by the discretization of three spaces (state space, action space, and time), whereas in Chapter 5 resolution completeness only involved discretization of the C-space. The main topics are extending the incremental sampling and searching framework of Section 5.4, extending feedback motion planning of Chapter 8, and developing decoupled methods for trajectory planning.

Chapter 15 overviews powerful ideas and tools that come mainly from control theory. The planning methods of Chapter 14 can be greatly enhanced by utilizing the material from Chapter 15. The two chapters are complementary in that Chapter 14 is mainly algorithmic and Chapter 15 is mainly about mathematical techniques. The main topics of Chapter 15 are system stability, optimality concepts (Hamilton-Jacobi-Bellman equation and Pontryagin's minimum principle), shortest paths for wheeled vehicles, nonholonomic system theory, and nonholonomic steering methods. The term nonholonomic comes from mechanics and refers to differential constraints that cannot be fully integrated to remove time derivatives of the state variables.