Manipulation Planning with Sensing Un- certainty

One of the richest sources of interesting I-spaces is manipulation planning. As robots interact with obstacles or objects in the world, the burden of estimating the state becomes greater. The classical way to address this problem is to highly restrict the way in which the robot can interact with obstacles. Within the manip-

ulation planning framework of Section 7.3.2, this means that a robot must grasp and carry objects to their desired destinations. Any object must be lying in a sta- ble configuration upon grasping, and it must be returned to a stable configuration after grasping.

As the assumptions on the classical manipulation planning framework are lifted, it becomes more difficult to predict how the robot and other bodies will behave. This immediately leads to the challenges of uncertainty in predictability, which was the basis of Chapter 10. The next problem is to design sensors that enable plans to be achieved in spite of this uncertainty. For each sensing model, an I-space arises.

Section 12.5.1 covers the preimage planning framework [311, 659], under which many interesting issues covered in Chapters 10 and 11 are addressed for a specific manipulation planning problem. I-states, forward projections, backprojections, and termination actions were characterized in this context. Furthermore, several algorithmic complexity results regarding planning under uncertainty have been proved within this framework.

Section 12.5.2 covers methods that clearly illustrate the power of reasoning directly in terms of the I-space. The philosophy is to allow nonprehensile forms of manipulation (e.g., pushing, squeezing, throwing) and to design simple sensors, or even to avoid sensing altogether. This dramatically reduces the I-space while still allowing feasible plans to exist. This contradicts the intuition that more information is better. Using less information leads to greater uncertainty in the state, but this is not important in some problems. It is only important is that the I-space becomes simpler.

• • 1. Preimage Planning

The preimage planning framework (or LMT framework, named after its developers, Lozano-P´erez, Mason, and Taylor) was developed as a general way to perform manipulation planning under uncertainty [311, 659]. Although the concepts apply to general configuration spaces, they will be covered here for the case in which

2

C = R and Cobs is polygonal. This is a common assumption throughout most of

the work done within this framework. This could correspond to a simplified model

of a robot hand that translates in = R2, while possibly carrying a part. A popular illustrative task is the peg-in-hole problem, in which the part is a peg that must be inserted into a hole that is slightly larger. This operation is frequently performed as manufacturing robots assemble products. Using the configuration space representation of Section 4.3.2, the robot becomes a point moving in R2

W

among polygonal obstacles.

The distinctive features of the models used in preimage planning are as follows:

• • • 1. The robot can execute compliant motions, which means that it can slide along the boundary of obs. This differs from the usual requirement in Part II that the robot must avoid obstacles.

C

• • • 1. There is nondeterministic uncertainty in prediction. An action determines a motion direction, but nature determines how much error will occur during execution. A bounded error model is assumed.
      2. There is nondeterministic uncertainty in sensing, and the true state cannot be reliably estimated.
      3. The goal region is usually an edge of Cobs, but it may more generally be any subset of cl(Cfree), the closure of Cfree.
      4. A hierarchical planning model is used, in which the robot is issued a sequence of motion commands, each of which is terminated by applying uT based on the I-state.

Each of these will now be explained in more detail.

Compliant motions It will be seen shortly that the possibility of executing

compliant motions is crucial for reducing uncertainty in the robot position. Let

Ccon denote the obstacle boundary, ∂Cobs (also, Ccon = ∂Cfree). A model of robot

motion while q con needs to be formulated. In general, this is complicated by friction. A simple Coulomb friction model is assumed here; see [681] for more details on modeling friction in the context of manipulation planning. Suppose that the net force F is applied by a robot at some q con. The force could be maintained by using the generalized damper model of robot control [966].

∈ C

∈ C

The resulting motion is characterized using a friction cone, as shown in Figure 12.44a. A basic principle of Newtonian mechanics is that the obstacle applies a reaction force (it may be helpful to look ahead to Section 13.3, which introduces mechanics). If F points into the surface and is normal to it, then the reaction force provided by the obstacle will cancel F, and there will be no motion. If F is not perpendicular to the surface, then sliding may occur. At one extreme, F may be parallel to the surface. In this case, it must slide along the boundary. In general, F can be decomposed into parallel and perpendicular components. If the parallel component is too small relative to the perpendicular component, then the robot becomes stuck. The friction cone shown in Figure 12.44a indicates precisely the conditions under which motion occurs. The parameter α captures the amount of friction (more friction leads to larger α). Figure 12.44b indicates the behaviors that occur for various directions of F. The diagram is obtained by inverting the friction cone. If F points into the bottom region, then sticking occurs, which means that the robot cannot move. If F points away from the obstacle boundary, then contact is broken (this is reasonable, unless the boundary is sticky). For the remaining two cases, the robot slides along the boundary.

Sources of uncertainty Nature interferes with both the configuration transi- tions and with the sensor. Let U = [0, 2π), which indicates the direction in R2 that the robot is commanded to head. Nature interferes with this command, and

• • • • 1. (b)

Figure 12.44: The compliant motion model. If a force F is applied by the robot at q con, then it moves along the boundary only if F points outside of the friction cone.

∈ C −

(a) (b)

Figure 12.45: Nature interferes with both the configuration transitions and the sensor observations.

the actual direction lies within an interval of S1. As shown in Figure 12.45a, the forward projection (recall from Section 10.1.2) for a fixed action u U yields a cone of possible future configurations. (A precise specification of the motion model

∈

is given using differential equations in Example 13.15.) The sensing model, shown in Figure 12.45b, was already given in Section 11.5.1. The nature sensing actions form a disc given by (11.67), and y = q + ψ, in which q is the true configuration, ψ is the nature sensing action, and y is the observation. The result appears in Figure 11.11.

Goal region Since contact with the obstacle is allowed, the goal region can be defined to include edges of Cobs in addition to points in Cfree. Most often, a single edge of Cobs is chosen as the goal region.

Motion commands The planning problem can now be described. It may be tempting to express the model using continuous time, as opposed to discrete stages. This is a viable approach, but leads to planning under differential con- straints, which is the topic of Part IV and is considerably more complicated. In the preimage-planning framework, a hierarchical approach is taken. A restricted kind of plan called a motion command, µ, will be defined, and the goal is achieved by constructing a sequence of motion commands. This has the effect of convert- ing the continuous-time decision-making problem into a planning problem that involves discrete stages. Each time a motion command is applied, the robot must apply a termination action to end it. At that point another motion command can be issued. Thus, imagine that a high-level module issues motion commands, and a low-level module executes each until a termination condition is met.

For some action u ∈ U, let Mu = {u, uT }, in which uT is the termination

action. A motion command is a feedback plan, µ : hist Mu, in which hist is the standard history I-space, based on initial conditions, the action history, and the sensing history. The motion command is executed over continuous time. At t = 0, µ(η0) = u. Using a history I-state η gathered during execution, the motion command will eventually yield µ(η) = uT , which terminates it. If the goal was not achieved, then the high-level module can apply another motion command.

I → I

Preimages Now consider how to construct motion commands. Using the hier- archical approach, the main task of terminating in the goal region can be decom- posed into achieving intermediate subgoals. The preimage P(µ, G) of a motion command µ and subgoal G cl( free) is the set of all history I-states from which

⊂ C

µ is guaranteed to be achieved in spite of all interference from nature. Each motion

command must recognize that the subgoal has been achieved so that it can apply its termination action. Once a subgoal is achieved, the resulting history I-state must lie within the required set of history I-states for the next motion command in the plan. Let denote the set of all allowable motion commands that can be defined. This can actually be considered as an action space for the high-level module.

M

Planning with motion commands A high-level open-loop plan,6

π = (µ1, µ2, . . . , µk), (12.34)

can be constructed, which is a sequence of k motion commands. Although the precise path executed by the robot is unpredictable, the sequence of motion com- mands is assumed to be predictable. Each motion command µi for 1 < i < k must

terminate with an I-state η ∈ P(µi+1, Gi+1). The preimage of µ1 must include η0,

the initial I-state. The goal is achieved by the last motion command, µk.

More generally, the particular motion command chosen need not be predictable, and may depend on the I-state during execution. In this case, the high-level

6Note that this open-loop plan is composed of closed-loop motion commands. This is perfectly acceptable using hierarchical modeling.

feedback plan π : hist can be developed, in which a motion command

I → M

µ = π(η) is chosen based on the history I-state η that results after the previous motion command terminates. Such variations are covered in [281, 311, 588].

The high-level planning problem can be solved using discrete planning algo- rithms from Chapters 2 and 10. The most popular method within the preimage planning framework is to perform a backward search from the goal. Although this sounds simple enough, the set of possible motion commands is infinite, and it is difficult to sample µ in a way that leads to completeness. Another complication is that termination is based on the history I-state. Planning is therefore quite challenging. It was even shown in [311], by a reduction from the Turing machine halting problem [891], that the preimage in general is uncomputable by any algo- rithm. It was shown in [732] that the 3D version of preimage planning, in which the obstacles are polyhedral, is PSPACE-hard. It was then shown in [172] that it is even NEXPTIME-hard.7

Backprojections Erdmann proposed a practical way to compute effective mo- tion commands by separating the reachability and recognizability issues [311, 312]. Reachability refers to characterizing the set of points that are guaranteed to be reachable. Recognizability refers to knowing that the subgoal has been reached based on the history I-state. Another way to interpret the separation is that the effects of nature on the configuration transitions is separated from the effects of nature on sensing.

For reachability analysis, the sensing uncertainty is neglected. The notions of forward projections and backprojections from Section 10.1.2 can then be used. The only difference here is that they are applied to continuous spaces and mo- tion commands (instead of u). Let S denote a subset of cl( free). Both weak backprojections, WB(S, µ), and strong backprojections, SB(S, µ), can be defined. Furthermore, nondirectional backprojections [283], WB(S) and SB(S), can be de- fined, which are analogous to (10.25) and (10.26), respectively.

C

Figure 12.46 shows a simple problem in which the task is to reach a goal edge with a motion command that points downward. This is inspired by the peg-in- hole problem. Figure 12.47 illustrates several backprojections from the goal region for the problem in Figure 12.46. The action is u = 3π/2; however, the actual motion lies within the shown cone due to nature. First suppose that contact with the obstacle is not allowed, except at the goal region. The strong backprojection is given in Figure 12.47a. Starting from any point in the triangular region, the goal is guaranteed to be reached in spite of nature. The weak backprojection is the unbounded region shown in Figure 12.47b. This indicates configurations from which it is possible to reach the goal. The weak backprojection will not be considered further because it is important here to guarantee that the goal is reached. This is accomplished by the strong backprojection. From here onward, it will be assumed that backprojection by default means a strong backprojection.

7NEXPTIME is the complexity class of all problems that can be solved in nondeterministic exponential time. This is beyond the complexity classes shown in Figure 6.40.

Figure 12.46: A simple example that resembles the peg-in-hole problem.

Using weak backprojections, it is possible to develop an alternative framework of

error detection and recovery (EDR), which was introduced by Donald in [281].

Now assume that compliant motions are possible along the obstacle boundary. This has the effect of enlarging the backprojections. Suppose for simplicity that there is no friction (α = 0 in Figure 12.44a). The backprojection is shown in Figure 12.47c. As the robot comes into contact with the side walls, it slides down until the goal is reached. It is not important to keep track of the exact configuration while this occurs. This illustrates the power of compliant motions in reducing uncertainty. This point will be pursued further in Section 12.5.2. Figure 12.47d shows the backprojection for a different motion command.

Now consider computing backprojections in a more general setting. The back- projection can be defined from any subset of cl( free) and may allow a friction cone with parameter α. To be included in a backprojection, points from which sticking is possible must be avoided. Note that sticking is possible even if α = 0. For ex- ample, in Figure 12.46, nature may allow the motion to be exactly perpendicular to the obstacle boundary. In this case, sticking occurs on horizontal edges because there is no tangential motion. In general, it must be determined whether sticking is possible at each edge and vertex of obs. Possible sticking from an edge depends on u, α, and the maximum directional error contributed by nature. The robot can become stuck at a vertex if it is possible to become stuck at either incident edge.

C

C

Computing backprojections Many algorithms have been developed to com- pute backprojections. The first algorithm was given in [311, 312]. Assume that the goal region is one or more segments contained in edges of con. The algorithm proceeds for a fixed motion command, µ, which is based on a direction u U as follows:

∈

C

1. Mark every obstacle vertex at which sticking is possible. Also mark any point on the boundary of the goal region if it is possible to slide away from the goal.

2. 1. (b)

(c) (d)

Figure 12.47: Several backprojections are shown for the peg-in-hole problem.

1. For every marked vertex, extend two rays with directions based on the max- imum possible deviations allowed by nature when executing u. This inverts the cone shown in Figure 12.45a. The extended rays are shown in Figure

12.48 for the frictionless case (α = 0).

1. Starting at every goal edge, trace out the boundary of the backprojection region. Every edge encountered defines a half-plane of configurations from which the robot is guaranteed to move into. In Figure 12.48, this corresponds to being below a ray. When tracing out the backprojection boundary, the direction at each intersection vertex is determined based on including the points in the half-plane.

The resulting backprojection is shown in Figure 12.49. A more general algorithm that applies to goal regions that include polygonal regions in free was given in

C

[283] (some details are also covered in [588]). It uses the plane-sweep principle

(presented in Section 6.2.2) to yield an algorithm that computes the backprojection in time O(n lg n), in which n is the number of edges used to define obs. The backprojection itself has no more than O(n) edges. Algorithms for computing

C

Figure 12.48: Erdmann’s backprojection algorithm traces out the boundary after constructing cones based on friction.

nondirectional backprojections are given in [140, 283]. One difficulty in this case is that the backprojection boundary may be quite complicated. An incremental algorithm for computing a nondirectional backprojection of size O(n2) in time O(n2 lg n) is given in [140].

Once an algorithm that computes backprojections has been obtained, it needs to be adapted to compute preimages. Using the sensing model shown in Figure 12.45b, a preimage can be obtained by shrinking the subgoal region G. Let ǫ denote the radius of the ball in Figure 12.45b. Let G′ G denote a subset of the subgoal in which a strip of thickness ǫ has been removed. If the sensor returns y G′, then it is guaranteed that q G. This yields a method of obtaining preimages by shrinking the subgoals. If ǫ is too large, however, this may fail to yield a successful plan, even though one exists.

⊂

∈ ∈

The high-level plan can be found by performing a backward search that com- putes backprojections from the goal region (reduced by ǫ). There is still the difficulty of being too large, which controls the branching factor in the search. One possibility is to compute nondirectional backprojections. Another possibility is to discretize . For example, in [588, 590], is reduced to four principle directions, and plans are computed for complicated environments by using stick- ing edges as subgoals. Using discretization, however, it becomes more difficult to ensure the completeness of the planning algorithm.

M

M M

The preimage planning framework may seem to apply only to a very specific model, but it can be extended and adapted to a much more general setting. It was extended to semi-algebraic obstacle models in [174], which gives a planning method that runs in time doubly exponential in the C-space dimension (based on cylindrical algebraic decomposition, which was covered in Section 6.4.2). In [147],

Figure 12.49: The computed backprojection. Sliding is guaranteed from the steeper edge of the triangle; hence, it is included in the backprojection. From the other top edge, sticking is possible.

probabilistic backprojections were introduced by assigning a uniform probability density function to the nature action spaces considered in this section. This was in turn generalized further to define backprojections and preimages as the level sets of optimal cost-to-go functions in [597, 605]. Dynamic programming methods can then be applied to compute plans.

• • 1. Nonprehensile Manipulation

Manipulation by grasping is very restrictive. People manipulate objects in many interesting ways that do not involve grasping. Objects may be pushed, flipped, thrown, squeezed, twirled, smacked, blown, and so on. A classic example from the kitchen is flipping a pancake over by a flick of the wrist while holding the skillet. These are all examples of nonprehensile manipulation, which means manipulation without grasping.

The temptation to make robots grasp objects arises from the obsession with estimating and controlling the state. This task is more daunting for nonprehen- sile manipulation because there are times at which the object appears to be out of direct control. This leads to greater uncertainty in predictability and a larger sensing burden. By planning in the I-space, however, it may be possible to avoid all of these problems. Several works have emerged which show that manipulation goals can be achieved with little or no sensing at all. This leads to a form of minimalism [175, 321, 681], in which the sensors are designed in a way that sim- plifies the I-space, as opposed to worrying about accurate estimation. The search for minimalist robotic systems is completely aligned with trying to find derived I-spaces that are as small as possible, as mentioned in Section 11.2.1. Sensing systems should be simple, yet still able to achieve the task. Preferably, com- pleteness should not be lost. Most work in this area is concerned primarily with finding feasible solutions, as opposed to optimal solutions. This enables further simplifications of the I-space.

This section gives an example that represents an extreme version of this min- imalism. A sensorless manipulation system is developed. At first this may seem absurd. From the forward projections in Section 10.1.2, it may seem that uncer- tainty can only grow if nature causes uncertainty in the configuration transitions and there are no sensors. To counter the intuition, compliant motions have the ability to reduce uncertainty. This is consistent with the discussion in Section

• • 1. Simply knowing that some motion commands have been successfully ap- plied may reduce the amount of uncertainty. In an early demonstration of sensor- less manipulation, it was shown that an Allen wrench (L-shaped wrench) resting in a tray can be placed into a known orientation by simply tilting the tray in a few directions [321]. The same orientation is achieved in the end, regardless of the initial wrench configuration. Also, no sensors are needed. This can be considered as a more complicated extension of the ball rolling in a tray that was shown in Figure 11.29. This is also an example of compliant motions, as shown in Figure 12.44; however, in the present setting F is caused by gravity.

Squeezing parts Another example of sensorless manipulation will now be de- scribed, which was developed by Goldberg and Mason in [394, 395, 396]; see also [681]. A Java implementation of the algorithm appears in [131]. Suppose that con- vex, polygonal parts arrive individually along a conveyor belt in a factory. They are to be used in an assembly operation and need to be placed into a given ori- entation. Figure 12.50 shows a top view of a parallel-jaw gripper. The robot can perform a squeeze operation by bringing the jaws together. Figure 12.50a shows the part before squeezing, and Figure 12.50b shows it afterward. A simple model is assumed for the mechanics. The jaws move at constant velocity toward each other, and it is assumed that they move slowly enough so that dynamics can be neglected. To help slide the part into place, one of the jaws may be considered as a frictionless contact (this is a real device; see [175]). The robot can perform a squeeze operation at any orientation in [0, 2π) (actually, only [0, π) is needed due to symmetry). Let U = [0, 2π) denote the set of all squeezing actions. Each squeezing action terminates on its own after the part can be squeezed no further (without crushing the part).

The planning problem can be modeled as a game against nature. The initial orientation, x [0, 2π), of the part is chosen by nature and is unknown. The state space is S1. For a given part, the task is to design a sequence,

∈

π = (u1, u2, . . . , un), (12.35)

of squeeze operations that leads to a known orientation for the part, regardless of its initial state. Note that there is no specific requirement on the final state. After i motion commands have terminated, the history I-state is the sequence

η = (u1, u2, . . . , ui) (12.36)

of squeezes applied so far. The nondeterministic I-space ndet will now be used. The requirement can be stated as obtaining a singleton, nondeterministic I-state

I

• • • 1. (b)

Figure 12.50: A parallel-jaw gripper can orient a part without using sensors.

(includes only one possible orientation). If the part has symmetries, then the task is instead to determine a single symmetry class (which includes only a finite number of orientations)

Consider how a part in an unknown orientation behaves. Due to rotational symmetry, it will be convenient to describe the effect of a squeeze operation based on the relative angle between the part and the robot. Therefore, let α = u x, assuming arithmetic modulo 2π. Initially, α may assume any value in [0, 2π). It turns out that after one squeeze, α is always forced into one of a finite number of values. This can be explained by representing the diameter function d(α), which indicates the maximum thickness that can be obtained by taking a slice of the part at orientation α. Figure 12.51 shows the slice for a rectangle. The local minima of the distance function indicate orientations at which the part will stabilize as shown in Figure 12.50b. As the part changes its orientation during the squeeze operation, the α value changes in a way that gradually decreases d(α). Thus, [0, 2π) can be divided into regions of attraction, as shown in Figure 12.52. These behave much like the funnels in Section 8.5.1.

−

The critical observation to solve the problem without sensors is that with each squeeze the uncertainty can grow no worse, and is usually reduced. Assume u is fixed. For the state transition equation x′ = f(x, u), the same x′ will be produced for an interval of values for x. Due to rotational symmetry, it is best to express this in terms of α. Let s(α) denote relative orientation obtained after a squeeze. Since α is a function of x and u, this can be expressed as a squeeze function, s : S1 S1, defined as

→

s(α) = f(x, u) − u. (12.37)

The forward projection with respect to an interval, A, of α values can also be

b d(α)

a a

0 π/_2 π 3π/2 2π α_

Figure 12.51: The diameter function for a rectangle.

b d(α)

a

0 π/_2 π 3π/2 2π α_

Figure 12.52: There are four regions of attraction, each of which represents an interval of orientations.

defined:

S(A) = s(α). (12.38)

I

α∈A

Any interval A [0, 2π) can be interpreted as a nondeterministic I-state, based on the history of squeezes that have been performed. It is defined, however, with respect to relative orientations, instead of the original states. The algorithms discussed in Section 12.1.2 can be applied to ndet. A backward search algorithm is given in [395] that starts with a singleton, nondeterministic I-state. The planning proceeds by performing a backward search on ndet. In each iteration, the interval,

⊂

I

I

A, of possible relative orientations increases until eventually all of S1 is reached

(or the period of symmetry, if symmetries exist).

The algorithm is greedy in the sense that it attempts to force A to be as large as possible in every step. Note from Figure 12.52 that the regions of attraction are maximal at the minima of the diameter function. Therefore, only the minima values are worth considering as choices for α. Let B denote the preimage of the function s. In the first step, the algorithm finds the α for which B(α) is largest (in

terms of length in S1). Let α0 denote this relative orientation, and let A0 = B(α0). For each subsequent iteration, let Ai denote the largest interval in [0, 2π) that satisfies

|S(Ai−1)| < |Ai|, (12.39)

in which | · | denotes interval length. This implies that there exists a squeeze

operation for which any relative orientation in S(Ai−1) can be forced into Ai by a single squeeze. This iteration is repeated, generating A−1, A−2, and so on, until the condition in (12.39) can no longer be satisfied. It was shown in [395] that for any polygonal part, the Ai intervals increase until all of S1 (or the period of symmetry) is obtained.

Suppose that the sequence (A−k, . . . , A0) has been computed. This must be transformed into a plan that is expressed in terms of a fixed coordinate frame for the robot. The k-step action sequence (u1, . . . , uk) is recovered from

ui = s(βi−1) − ai − 2 (|Ai−k| − |S(Ai−k−1)|) + ui−1 (12.40)

1

and u−k = 0 [395]. Each ai in (12.40) is the left endpoint of Ai. There is some freedom of choice in the alignment, and the third term in (12.40) selects actions in the middle to improve robustness with respect to orientation errors. By exploiting a proof in [195] that no more than O(n) squeeze operations are needed for a part with n edges, the complete algorithm runs in time O(n2).

Example 12.9 (Squeezing a Rectangle) Figure 12.53 shows a simple example of a plan that requires two squeezes to orient the rectangular part when placed in any initial orientation. Four different executions of the plan are shown, one in each column. After the first squeeze, the part orientation is a multiple of π/2. After the second squeeze, the orientation is known. Even though the execution looks different every time, no feedback is necessary because the I-state contains

no sensor information. ．

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

Iprob, 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 local- ization 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

Figure 12.53: A two-step squeeze plan [395].

[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 gen- eralized 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 localiza- tion, 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(n2) for a single pursuer in a simple polygon was given in [770]. Variations that consider curved

N

W E

S

Figure 12.54: An environment for grid-based localization.

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.

Exercises

1. For the environment in Figure 12.1a, give the nondeterministic I-states for the action sequence (L, L, F, B, F, R, F, F), if the initial state is the robot in position 3 facing north and the initial I-state is η0 = X.
2. Describe how to apply the algorithm from Figure 10.6 to design an information- feedback plan that takes a map of a grid and performs localization.
3. Suppose that a robot operates in the environment shown in Figure 12.54 using the same motion and sensing model as in Example 12.1. Design an information- feedback plan that is as simple as possible and successfully localizes the robot, regardless of its initial state. Assume the initial condition η0 = X.
4. Prove that the robot can use the latitude and orientation information to detect the unique point of each obstacle boundary in the maze searching algorithm of Section 12.3.1.

Figure 12.55: A path followed by the robot in an initially unknown environment. The robot finishes in the lower right.

1. Suppose once again that a robot is placed into one of the six environments shown in Figure 12.12. It is initially in the upper right cell facing north; however, the initial condition is η0 = X. Determine the sequence of sensor observations and nonde- terministic I-states as the robot executes the action sequence (F, R, B, F, L, L, F).
2. Prove that the counter in the maze searching algorithm of Section 12.3.1 can be replaced by two pebbles, and the robot can still solve the problem by simulating the counter. The robot can place either pebble on a tile, detect them when the robot is on the same tile, and can pick them up to move them to other tiles.
3. Continue the trajectory shown in Figure 12.23 until the goal is reached using the Bug2 strategy.
4. Show that the competitive ratio for the doubling spiral motion applied to the lost-cow problem of Figure 12.26 is 9.
5. Generalize the lost-cow problem so that there are n fences that emanate from the current cow location (n = 2 for the original problem).
   1. If the cow is told that the gate is along only one unknown fence and is no more than one unit away, what is the competitive ratio of the best plan that you can think of?
   2. Suppose the cow does not know the maximum distance to the gate. Propose a plan that solves the problem and establish its competitive ratio.
6. Suppose a point robot is dropped into the environment shown in Figure 12.42. Indicate the gap navigation trees that are obtained as the robot moves along the path shown in Figure 12.55.

7. Construct an example for which the worst case bound, (12.25), for Bug1 is ob- tained.

8. 1. (b)

Figure 12.56: Two pursuit-evasion problems that involve recontamination.

1. Some environments are so complicated that in the pursuit-evasion problem they require the same region to be visited multiple times. Find a solution for a single pursuer with omnidirectional visibility to the problem in Figure 12.56a.
2. Find a pursuit-evasion solution for a single pursuer with omnidirectional visibility to the problem in Figure 12.56b, in which any number of pairs of “feet” may appear on the bottom of the polygon.
3. Prove that for a polygonal environment, if there are three points, p1, p2, and p3, for which V (V (p1)), V (V (p2)), and V (V (p3)) are pairwise-disjoint, then the problem requires more than one pursuer.
4. Prove that the diameter function for the squeezing algorithm in Section 12.5.2 has no more than O(n2) vertices. Give a sequence of polygons that achieves this bound. What happens for a regular polygon?
5. Develop versions of (12.8) and (12.9) for state-nature sensor mappings.
6. Develop versions of (12.8) and (12.9) for history-based sensor mappings.
7. Describe in detail the I-map used for maze searching in Section 12.3.1. Indicate how this is an example of dramatically reducing the size of the I-space, as described in Section 11.2. Is a sufficient I-map obtained?
8. Describe in detail the I-map used in the Bug1 algorithm. Is a sufficient I-map obtained?
9. Suppose that several teams of point robots move around in a simple polygon. Each robot has an omnidirectional visibility sensor and would like to keep track of information for each shadow region. For each team and shadow region, it would like to record one of three possibilities: 1) There are definitely no team members in the region; 2) there may possibly be one or more; 3) there is definitely at least one.
   1. Define a nondeterministic I-space based on labeling gaps that captures the appropriate information. The I-space should be defined with respect to one robot (each will have its own).
   2. Design an algorithm that keeps track of the nondeterministic I-state as the robot moves through the environments and observes others.
10. Recall the sequence of connected corridors shown in Figure 12.40. Try to adapt the polygons so that the same number of pursuers is needed, but there are fewer polygon edges. Try to use as few edges as possible.

Implementations

1. Solve the probabilistic passive localization problem of Section 12.2.3 for 2D grids. Implement your solution and demonstrate it on several interesting examples.
2. Implement the exact value-iteration method described in Section 12.1.3 to compute optimal cost-to-go functions. Test the implementation on several small examples. How large can you make K, Θ, and Ψ?
3. Develop and implement a graph search algorithm that searches on Indet to perform robot localization on a 2D grid. Test the algorithm on several interesting examples. Try developing search heuristics that improve the performance.
4. Implement the Bug1, Bug2, and VisBug (with unlimited radius) algorithms. De- sign a good set of examples for illustrating their relative strengths and weaknesses.
5. Implement software that computes probabilistic I-states for localization as the robot moves in a grid.
6. Implement the method of Section 12.3.4 for simply connected environments and demonstrate it in simulation for polygonal environments.
7. Implement the pursuit-evasion algorithm for a single pursuer in a simple polygon.
8. Implement the part-squeezing algorithm presented in Section 12.5.2.