12.4.1 Problem Formulation

The problem considered in this section is formulated as follows.

Formulation 12..1 (Visibility-Based Pursuit-Evasion)
1. A given, continuous environment region , which is an open set that is bounded by a simple closed curve. The boundary is often a polygon, but it may be any piecewise-analytic closed curve.
2. An unbounded time interval .
3. An evader, which is a moving point in . The evader position at time is determined by a continuous position function, .12.4
4. A pursuer, which is a moving point in . The evader position function is unknown to the pursuer.
5. A visibility sensor, which defines a set for each .

The task is to find a path, , for the pursuer for which the evader is guaranteed to be detected, regardless of its position function. This means that such that . The speed of the pursuer is not important; therefore, the time domain may be lengthened as desired, if the pursuer is slow.

It will be convenient to solve the problem by verifying that there is no evader. In other words, find a path for the pursuer that upon completion guarantees that there are no remaining places where the evader could be hiding. This ensures that during execution of the plan, the pursuer will encounter any evader. In fact, there can be any number of evaders, and the pursuer will find all of them. The approach systematically eliminates any possible places where evaders could hide.

The state yields the positions of the pursuer and the evader, , which results in the state space . Since the evader position is unknown, the current state is unknown, and I-spaces arise. The observation space is a collection of subsets of . For each , the sensor yields a visibility polygon, (this is denoted by using notation of Section 11.1.1). Consider the history I-state at time . The initial pursuer position is given (any position can be chosen arbitrarily, if it is not given), and the evader may lie anywhere in . The input history can be expressed as the pursuer history .12.5 Thus, the history I-state is

 (12.33)

in which reflects the initial condition in which is known, and the evader position may lie anywhere in .

Consider the nondeterministic I-space, . Since the pursuer position is always known, the interesting part of is the subset in which the evader may lie. Thus, the nondeterministic I-state can be expressed as , in which is the set of possible evader positions given . As usual for nondeterministic I-states, is the smallest set that is consistent with all of the information in .

Consider how varies over time. After the first instant of time, is observed, and it is known that the evader lies in , which is the shadow region (defined in Section 12.3.4) from . As the pursuer moves, varies. Suppose you are told that the pursuer is now at position , but you are not yet told . What options seem possible for ? These depend on the history, but the only interesting possibilities are that each shadow component may or may not contain the evader. For some of these components, we may be certain that it does not. For example, consider Figure 12.38. Suppose that the pursuer initially believes that the end of the corridor may contain the evader. If it moves along the smaller closed-loop path, the nondeterministic I-state gradually varies but returns to the same value when the loop is completed. However, if the pursuer traverses the larger loop, it becomes certain upon completing the loop that the corridor does not contain the evader. The dashed line that was crossed in this example may inspire you to think about cell decompositions based on critical boundaries, as in the algorithm in Section 6.3.4. This idea will be pursued shortly to develop a complete algorithm for solving this problem. Before presenting a complete algorithm, however, first consider some interesting examples.

Example 12..7 (When Is a Problem Solvable?)   Figure 12.39 shows four similar problems. The evader position is never shown because the problem is solved by ensuring that no evader could be left hiding. Note that the speed of the pursuer is not relevant to the nondeterministic I-states. Therefore, a solution can be defined by simply showing the pursuer path. The first three examples are straightforward to solve. However, the fourth example does not have a solution because there are at least three distinct hiding places (can you find them?). Let denote the set of all points visible from at least one point in . The condition that prevents the problem from being solved is that there exist three positions, , , , such that for each with . As one hiding place is reached, the evader can sneak between the other two. In the worst case, this could result in an endless chase with the evader always eluding discovery. We would like an algorithm that systematically searches and determines whether a solution exists.

Since one pursuer is incapable of solving some problems, it is tempting to wonder whether two pursuers can solve any problem. The next example gives an interesting sequence of environments that implies that for any positive integer , there is an environment that requires exactly pursuers to solve.

Example 12..8 (A Sequence of Hard Problems)   Each environment in the sequence shown in Figure 12.40 requires one more pursuer than the previous one [414]. The construction is based on recursively ensuring there are three isolated hiding places, as in the last problem of Figure 12.39. Each time this occurs, another pursuer is needed. The sequence recursively appends three environments that require pursuers, to obtain a problem that requires . An extra pursuer is always needed to guard the junction where the three environments are attached together. The construction is based on the notion of 3-separability, from pursuit-evasion on a graph, which was developed in [773].

The problem can be made more challenging by considering multiply connected environments (environments with holes). A single pursuer cannot solve any of the these problems. Determining the minimum number of pursuers required to solve such a problem is NP-hard [414].

Steven M LaValle 2012-04-20