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 $R \subset {\mathbb{R}}^2$, which is an open set that is bounded by a simple closed curve. The boundary $\partial R$ is often a polygon, but it may be any piecewise-analytic closed curve.
2. An unbounded time interval $T = [0,\infty)$.
3. An evader, which is a moving point in $R$. The evader position $e(t)$ at time $t \in T$ is determined by a continuous position function, ${\tilde{e}}: [0,1] \rightarrow R$.^12.4
4. A pursuer, which is a moving point in $R$. The evader position function ${\tilde{e}}$ is unknown to the pursuer.
5. A visibility sensor, which defines a set $V(r) \subseteq R$ for each $r \in R$.

The task is to find a path, ${\tilde{p}}: [0,1] \rightarrow R$, for the pursuer for which the evader is guaranteed to be detected, regardless of its position function. This means that $\exists t \in T$ such that $e(t) \in V(p(t))$. 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, $x = (p,e)$, which results in the state space $X = R \times R \subset {\mathbb{R}}^4$. Since the evader position is unknown, the current state is unknown, and I-spaces arise. The observation space $Y$ is a collection of subsets of $R$. For each $p \in R$, the sensor yields a visibility polygon, $V(p) \subseteq R$ (this is denoted by $y = h(p,e)$ using notation of Section 11.1.1). Consider the history I-state at time $t$. The initial pursuer position $p(0)$ is given (any position can be chosen arbitrarily, if it is not given), and the evader may lie anywhere in $R$. The input history ${\tilde{u}_t}$ can be expressed as the pursuer history ${\tilde{p}_t}$.^12.5 Thus, the history I-state is

$${\eta}_t = ((p(0),R),{\tilde{p}_t},{\tilde{y}_t}),$$ (12.33)

in which $(p(0),R) \subset X$ reflects the initial condition in which $p(0)$ is known, and the evader position $e(0)$ may lie anywhere in $R$.

Consider the nondeterministic I-space, ${\cal I}_{ndet}$. Since the pursuer position is always known, the interesting part of $R$ is the subset in which the evader may lie. Thus, the nondeterministic I-state can be expressed as $X_t({\eta}_t) = (p(t),E({\eta}_t))$, in which $E({\eta}_t)$ is the set of possible evader positions given ${\eta}_t$. As usual for nondeterministic I-states, $E({\eta}_t)$ is the smallest set that is consistent with all of the information in ${\eta}_t$.

Consider how $E({\eta}_t)$ varies over time. After the first instant of time, $V(p(0))$ is observed, and it is known that the evader lies in $R \setminus V(p(0))$, which is the shadow region (defined in Section 12.3.4) from $p(0)$. As the pursuer moves, $E({\eta}_t)$ varies. Suppose you are told that the pursuer is now at position $p(t)$, but you are not yet told ${\eta}_t$. What options seem possible for $E({\eta}_t)$? 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.

Figure 12.38: (a) Suppose the pursuer comes near the end of a contaminated corridor. (b) If the pursuer moves in a loop path, the nondeterministic I-state gradually changes, but returns to its original value. (c) However, if a critical boundary is crossed, then the nondeterministic I-state fundamentally changes.

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 $V(V(p))$ denote the set of all points visible from at least one point in $V(p)$. The condition that prevents the problem from being solved is that there exist three positions, $p_1$, $p_2$, $p_3$, such that $V(V(p_i)) \cap V(V(p_j)) = \emptyset$ for each $i,j \in \{1,2,3\}$ with $i \not = j$. 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 ${\cal I}_{ndet}$ and determines whether a solution exists. $\blacksquare$

Figure 12.39: Three problems that can be easily solved with one pursuer, and a minor variant for which no 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 $k$, there is an environment that requires exactly $k$ 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 $k$ pursuers, to obtain a problem that requires $k+1$. 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]. $\blacksquare$

Figure 12.40: Each collection of corridors requires one more pursuer than the one before it because a new pursuer must guard the junction.

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].