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 , which is the continuous-time counterpart of the state transition equation, . 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.

Steven M LaValle 2012-04-20