Further Reading

The material from this chapter could easily be expanded into an entire book on planning under sensing uncertainty. Several key topics were covered, but numerous others remain. An incomplete set of suggestions for further reading is given here.

Since Section 12.1 involved converting the I-space into an ordinary state space, many methods and references in Chapter 10 are applicable. For POMDPs, a substantial body of work has been developed in operations research and stochastic control theory [564,655,714,899] and more recently in artificial intelligence [494,647,648,737,772,791,803,805,835,1002,1003]. Many of these algorithms compress or approximate ${\cal I}_{prob}$, possibly yielding nonoptimal solutions, but handling problems that involve dozens of states.

Localization, the subject of Section 12.2, is one of the most fundamental problems in robotics; therefore, there are hundreds of related references. Localization in a graph has been considered [297,342]. The combinatorial localization presentation was based on [298,415]. Ambiguities due to symmetry also appeared in [78]. Combinatorial localization with very little sensing is presented in [752]. For further reading on probabilistic localization, see [43,258,421,447,485,493,549,621,622,754,825,887,888,962]. In [935,936], localization uncertainty is expressed in terms of a sensor-uncertainty field, which is a derived I-space.

Section 12.3 was synthesized from many sources. For more on the maze searching method from Section 12.3.1 and its extension to exploring a graph, see [119]. The issue of distinguishability and pebbles arises again in [87,286,287,668,840,944]. For more on competitive ratios and combinatorial approaches to on-line navigation, see [116,260,270,332,375,507,537,674,768,811].

For more on Stentz's algorithm and related work, see [543,913]. A multi-resolution approach to terrain exploration appears in [761]. For material on bug algorithms, see [505,568,592,666,667,809,882]. Related sensor-based planning work based on generalized Voronoi diagrams appears in [218,219]; also related is [828]. Gap navigation trees were introduced in [943,944,945]. For other work on minimal mapping, see [484,824,873]. Landmark-based navigation is considered in [369,590,884].

There is a vast body of literature on probabilistic methods for mapping and localization, much of which is referred to as SLAM [942]; see also [182,221,275,717,771,982]. One of the earliest works is [897]. An early application of dynamic programming in this context appears in [584]. A well-known demonstration of SLAM techniques is described in [159]. For an introduction to the EM algorithm, see [106]; its convergence is addressed in [269,977,978]. For more on mobile robotics in general, see [134,296].

The presentation of Section 12.4 was based mainly on [414,612]. Pursuit-evasion problems in general were first studied in differential game theory [59,422,477]. Pursuit-evasion in a graph was introduced in [773], and related theoretical analysis appears in [105,580,715]. Visibility-based pursuit-evasion was introduced in [932], and the first complete algorithm appeared in [612]. An algorithm that runs in $O(n^2)$ for a single pursuer in a simple polygon was given in [770]. Variations that consider curved environments, beams of light, and other considerations appear in [208,254,304,603,618,745,889,890,931,933,981]. Pursuit-evasion in three dimensions is discussed in [614]. For versions that involve minimal sensing and no prior given map, see [416,503,809,840,988]. The problem of visually tracking a moving target both with [81,401,402,602,723,728] and without [323,470,869] obstacles is closely related to pursuit-evasion. For a survey of combinatorial algorithms for computing visibility information, see [756]. Art gallery and sensor placement problems are also related [141,755,874]. The bitangent events also arise in the visibility complex [796] and in aspect graphs [782], which are related visibility-based data structures.

Section 12.5 was inspired mostly by the works in [283,311,321,396,659,967]. Many works are surveyed in [681]. A probabilistic version of preimage planning was considered in [148,149,605]. Visual preimages are considered in [349]. Careful analysis of manipulation uncertainty appears in [145,146]. For more on preimage planning, see [588,590]. The error detection and recovery (EDR) framework uses many preimage planning ideas but allows more problems to be solved by permitting fixable errors to occur during execution [281,284,285]. Compliant motions are also considered in [140,283,486,678,680,776]. The effects of friction in the C-space are studied in [316]. For more work on orienting parts, see [175,322,394,395,810,969]. For more forms of nonprehensile manipulation, see [12,14,110,318,670,671,921]. A humorous paper, which introduces the concept of the ``principle of virtual dirt,'' is [679]; the idea later appears in [839] and in the Roomba autonomous vacuum cleaner from the iRobot Corporation.