Further Reading

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 $ {X_{ric}}$, 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