Further Reading

This chapter covered some of the most direct extensions of the basic motion planning problem. Extensions that involve uncertainties are covered throughout Part III, and the introduction of differential constraints to motion planning is the main focus of Part IV. Numerous other extensions can be found by searching through robotics research publications or the Internet.

The treatment of time-varying motion planning in Section 7.1 assumes that all motions are predictable. Most of the coverage is based on early work [153,506,818,819]; other related work includes [367,368,532,812,875,905]. To introduce uncertainties into this scenario, see Chapter 10. The logic-based representations of Section 2.4 have been extended to temporal logics to allow time-varying aspects of discrete planning problems (see Part IV of [382]).

For more on multiple-robot motion planning, see [15,34,41,319,320,345,364,408,606,780,886]. Closely related is the problem of planning for modular reconfigurable robots [180,209,385,552,990]. In both contexts, nonpositive curvature (NPC) is an important condition that greatly simplifies the structure of optimal paths [139,385,386]. For points moving on a topological graph, the topology of ${\cal C}_{free}$ is described in [5]. Over the last few years there has also been a strong interest in the coordination of a team or swarm of robots [165,228,274,300,305,336,361,665].

The complexity of assembly planning is studied in [398,515,733,972]. The problem is generally NP-hard; however, for some special cases, polynomial-time algorithms have been developed [9,429,973,974]. Other works include [186,427,453,458,542].

Hybrid systems have attracted widespread interest over the past decade. Most of this work considers how to design control laws for piecewise-smooth systems [137,634]. Early sources of hybrid control literature appear in [409]. The manipulation planning framework of Section 7.3.2 is based on [16,17,166]. The manipulation planning framework presented in this chapter ignores grasping issues. For analyses and algorithms for grasping, see [256,487,681,781,799,800,826,827,920]. Manipulation on a microscopic scale is considered in [126].

To read beyond Section 7.4 on sampling-based planning for closed kinematic chains, see [244,246,432,979]. A complete planner for some closed chains is presented in [697]. For related work on inverse kinematics, see [309,693]. The power of redundant degrees of freedom in robot systems was shown in [158].

Section 7.5 is a synthesis of several applications. The application of motion planning techniques to problems in computational biology is a booming area; see [24,25,33,245,514,589,601,654,1001] for some representative papers. The knot-planning coverage is based on [572]. The box-folding presentation is based on [661]. A robotic system and planning technique for creating origami is presented in [65].

The coverage planning methods presented in Section 7.6 are based on [222] and [372,373]. A survey of coverage planning appears in [217]. Other references include [6,7,164,374,444,468,976]. For discrete environments, approximation algorithms for the problem of optimally visiting all states in a goal set (the orienteering problem) are presented and analyzed in [115,188].

Beyond two dimensions, optimal motion planning is extremely difficult. See Section 8.5.2 for dynamic programming-based approximations. See [215,763] for approximate shortest paths in ${\mathbb{R}}^3$. The weighted region problem is considered in [709,710]. Pareto-optimal coordination is considered in [212,386,606].