The characterization and computation of reachable sets has been
growing in interest
[100,102,706,707,916,955].
One motivation for studying reachability is *verification*, which
ensures that a control system behaves as desired under all possible
disturbances. This can actually be modeled as a game against nature,
in which nature attempts to bring the system into an undesirable state
(e.g., crashing an airplane). For recent progress on characterizing
, see [355]. The triangularization argument for
completeness appears in a similar context in [292]. The
precise rate of convergence, expressed in terms of dispersion and
Lipschitz conditions, for resolution-complete sampling-based motion
planning methods under differential constraints is covered in
[196]. For the computational complexity of control problems,
see [114,766]. For further reading on motion
primitives in the context of planning, see
[360,362,363,393,787,794,848].
For further reading on dynamical simulation and numerical integration,
see [331,440,863].

Section 14.4.1 was based on [288,290,441]. For more works on kinodynamic planning, see [203,237,289,356,360,611,780,999]. Section 14.4.2 was inspired by [73]. Section 14.4.3 was drawn from [611]. For more work on RRTs under differential constraints, see [138,199,224,324,360,393,509,949]. For other works on nonholonomic planning, see the survey [596] and [67,277,334,335,354,357,482,579,633,672]. Combinatorial approaches to nonholonomic planning have appeared in [13,128,347].

Section 14.5 was developed by adapting value iteration to motion planning problems. For general convergence theorems for value iteration with interpolation, see [168,292,400,565,567]. In [168], global constraints on the phase space are actually considered. The use of these techniques and the development of Dijkstra-like variants are covered in [607]. Related work exists in artificial intelligence [722] and control theory [946].

Decoupled approaches to planning, as covered in Section 14.6, are very common in robotics literature. For material related to the plan-and-transform method, see [333,596,859]. For more on decoupled trajectory planning and time scaling, see [353,456,457,843,876,877,880,881], and see [104,120,121,785,879,894,878] for particular emphasis on time-optimal trajectories.

For more on gradient-based techniques in general, see [98] and references therein. Classical texts on the subject are [151,664]. Gradient-based approaches to path deformation in the context of nonholonomic planning appear in [197,343,575].

The techniques presented in this chapter are useful in other fields
beyond robotics. For aerospace applications of motion planning, see
[86,202,436,437,786].
Motion planning problems and techniques have been gaining interest in
computer graphics, particularly for generating animations of virtual
humans (or digital actors); works in this area include
[35,86,393,498,544,554,557,591,617,649,712,802,980].
In many of these works, *motion capture* is a popular way to
generate a database of recorded motions that serves as a set of motion
primitives in the planning approach.

Steven M LaValle 2012-04-20