Visibility-Based Pursuit-Evasion
This section considers visibility-based pursuit-evasion [612, 932], which was de- scribed in Section 1.2 as a game of hide-and-seek. The topic provides an excellent illustration of the power of I-space concepts.
- Problem Formulation
The problem considered in this section is formulated as follows.
Formulation 12.1 (Visibility-Based Pursuit-Evasion)
- A given, continuous environment region R R2, which is an open set that is bounded by a simple closed curve. The boundary ∂R is often a polygon, but it may be any piecewise-analytic closed curve.
⊂
- An unbounded time interval T = [0, ∞).
- An evader, which is a moving point in R. The evader position e(t) at time
t ∈ T is determined by a continuous position function, e˜ : [0, 1] → R.4
- A pursuer, which is a moving point in R. The evader position function e˜ is unknown to the pursuer.
- A visibility sensor, which defines a set V (r) ⊆ R for each r ∈ R.
The task is to find a path, p˜ : [0, 1] R, for the pursuer for which the evader is guaranteed to be detected, regardless of its position function. This means that t T such that e(t) 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.
4Following from standard function notation, it is better to use e˜(t) instead of e(t) to denote the position at time t; however, this will not be followed.
The state yields the positions of the pursuer and the evader, x = (p, e), which results in the state space X = R R R4. 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 R, the sensor yields a visibility poly- gon, V (p) 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 u˜t can be expressed as the pursuer history p˜t.5 Thus, the history I-state is
⊆
∈
× ⊂
ηt = ((p(0), R), p˜t, y˜t), (12.33)
in which (p(0), R) 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, ndet. Since the pursuer position is al- ways known, the interesting part of R is the subset in which the evader may lie. Thus, the nondeterministic I-state can be expressed as Xt(ηt) = (p(t), E(ηt)), in which E(ηt) is the set of possible evader positions given ηt. As usual for non- deterministic I-states, E(ηt) is the smallest set that is consistent with all of the information in ηt.
I
Consider how E(η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 \ V (p(0)), which is the
shadow region (defined in Section 12.3.4) from p(0). As the pursuer moves, E(ηt) varies. Suppose you are told that the pursuer is now at position p(t), but you are not yet told ηt. What options seem possible for E(η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.
Example 12.7 (When Is a Problem Solvable?) Figure 12.39 shows four sim- ilar problems. The evader position is never shown because the problem is solved by
5To follow the notation of Section 11.4 more closely, the motion model p˙ = u can be used, in which u represents the velocity of the pursuer. Nature actions can be used to model the velocity of the evader to obtain e˙. By integrating p˙ over time, p(t) can be obtained for any t. This means that p˜t can be used as a simpler representation of the input history, instead of directly referring to velocities.
- (b) (c)
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.
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, p1, p2, p3, such that V (V (pi)) V (V (pj )) = for each i, j 1, 2, 3 with i = 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 discov- ery. We would like an algorithm that systematically searches ndet and determines
I
∩ ∅ ∈ { } /
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 k, there is an environment that requires exactly k pursuers to solve.
Example 12.8 (A Sequence of Hard Problems) Each environment in the se- quence 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, an- other 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]. ．
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
Figure 12.39: Three problems that can be easily solved with one pursuer, and a minor variant for which no solution exists.
Figure 12.40: Each collection of corridors requires one more pursuer than the one before it because a new pursuer must guard the junction.
such a problem is NP-hard [414].
- A Complete Algorithm
Now consider designing a complete algorithm that solves the problem in the case of a single pursuer. To be complete, it must find a solution if one exists; otherwise, it correctly reports that no solution is possible. Recall from Figure 12.38 that the nondeterministic I-state changed in an interesting way only after a critical boundary was crossed. The pursuit-evasion problem can be solved by carefully analyzing all of the cases in which these critical changes can occur. It turns out that these are exactly the same cases as considered in Section 12.3.4: crossing inflection rays and bitangent rays. Figure 12.38 is an example of crossing an inflection ray. Figure 12.41 indicates the connection between the gaps of Section
- and the parts of the environment that may contain the evader.
Recall that the shadow region is the set of all points not visible from some
e?
wall
P
wall
e?
wall
e? e?
e?
wall
wall
e?
wall
- (b)
Figure 12.41: Recall Figure 11.15. Beyond each gap is a portion of the environment that may or may not contain the evader.
p(t); this is expressed as R V (p(t)). Every critical event changes the number of shadow components. If an inflection ray is crossed, then a shadow component either appears or disappears, depending on the direction. If a bitangent ray is crossed, then either two components merge into one or one component splits into two. To keep track of the nondeterministic I-state, it must be determined whether each component of the shadow region is cleared, which means it certainly does not contain the evader, or contaminated, which means that it might contain the evader. Initially, all components are labeled as contaminated, and as the pursuer moves, cleared components can emerge. Solving the pursuit-evasion problem amounts to moving the pursuer until all shadow components are cleared. At this point, it is known that there are no places left where the evader could be hiding.
\
If the pursuer crosses an inflection ray and a new shadow component appears, it must always be labeled as cleared because this is a portion of the environment that was just visible. If the pursuer crosses a bitangent ray and a split occurs, then the labels are distributed across the two components: A contaminated shadow com- ponent splits into two contaminated components, and a cleared component splits into two cleared components. If the bitangent ray is crossed in the other direction, resulting in a merge of components, then the situation is more complicated. If one component is cleared and the other is contaminated, then the merged component is contaminated. The merged component may only be labeled as cleared if both of the original components are already cleared. Note that among the four critical cases, only the merge has the potential to undo the work of the pursuer. In other words, it may lead to recontamination.
Consider decomposing R into cells based on inflection rays and bitangent rays, as shown in Figure 12.42. These cells have the following information-conservative property: If the pursuer travels along any loop path that stays within a 2D cell, then the I-state remains the same upon returning to the start. This implies that
Environment Inflection rays
Bitangent rays Cell decomposition
Figure 12.42: The environment is decomposed into cells based on inflections and bitangents, which are the only critical visibility events.
the particular path taken by the pursuer through a cell is not important. A solution to the pursuit-evasion problem can be described as a sequence of adjacent 2D cells that must be visited. Due to the information-conservative property, the particular path through a sequence of cells can be chosen arbitrarily.
Searching the cells for a solution is more complicated than searching for paths in Chapter 6 because the search must be conducted in the I-space. The pursuer may visit the same cell in R on different occasions but with different knowledge about which components are cleared and contaminated. A directed graph, I , can be constructed as follows. For each 2D cell in R and each possible labeling of shadow
G
components, a vertex is defined in GI . For example, if the shadow region of a cell has three components, then there are 23 = 8 corresponding vertices in GI . An edge
exists in I between two vertices if: 1) their corresponding cells are adjacent, and
G
2) the labels of the components are consistent with the changes induced by crossing the boundary between the two cells. The second condition means that the labeling rules for an appear, disappear, split, or merge must be followed. For example, if
crossing the boundary causes a split of a contaminated shadow component, then the new components must be labeled contaminated and all other components must retain the same label. Note that I is directed because many motions in the ndet are not reversible. For example, if a contaminated region disappears, it cannot reappear as contaminated by reversing the path. Note that the information in this directed graph does not improve monotonically as in the case of lazy discrete localization from Section 12.2.1. In the current setting, information is potentially worse when shadow components merge because contamination can spread.
G I
To search I , start with any vertex for which all shadow region components are labeled as contaminated. The particular starting cell is not important. Any of the search algorithms from Section 2.2 may be applied to find a goal vertex, which is any vertex of I for which all shadow components are labeled as cleared. If no such vertices are reachable from the initial state, then the algorithm can correctly declare that no solution exists. If a goal vertex is found, then the path in I gives the sequence of cells that must be visited to solve the problem. The actual path through R is then constructed from the sequence of cells. Some of the cells may not be convex; however, their shape is simple enough that a sophisticated motion planning algorithm is not needed to construct a path that traverses the cell sequence.
G
G
G
The algorithm presented here is conceptually straightforward and performs well in practice; however, its worst-case running time is exponential in the number of inflection rays. Consider a polygonal environment that is expressed with n edges. There can be as many as O(n) inflections and O(n2) bitangents. The number of cells is bounded by O(n3) [412]. Unfortunately, I has an exponential number of vertices because there can be as many as O(n) shadow components, and there are 2n possible labelings if there are n components. Note that I does not need to be computed prior to the search. It can be revealed incrementally during the planning process. The most efficient complete algorithm, which is more complicated, solves the pursuit-evasion problem in time O(n2) and was derived by first proving that any problem that can be solved by a pursuer using the visibility polygon can be solved by a pursuer that uses only two beams of light [770]. This simplifies V (p(t)) from a 2D region in R to two rotatable rays that emanate from p(t) and dramatically reduces the complexity of the I-space.
G
G
12.4.3 Other Variations
Numerous variations of the pursuit-evasion problem presented in this section can be considered. The problem becomes much more difficult if there are multiple pur- suers. A cell decomposition can be made based on changing shadow components; however, some of the cell boundaries are algebraic surfaces due to complicated interactions between the visibility polygons of different pursuers. Thus, it is dif- ficult to implement a complete algorithm. On the other hand, straightforward heuristics can be used to guide multiple pursuers. A single pursuer can use the complete algorithm described in this section. When this pursuer fails, it can move
(a) (b) (c) (d) (e)
Figure 12.43: Several evader detection models: (a) omnidirectional sensing with unlimited distance; (b) visibility with a limited field of view; (c) a single visibility ray that is capable of rotating; (d) limited distance and a rotating viewing cone, which corresponds closely to a camera model; and (e) three visibility rays that are capable of rotating.
to some part of the environment and then wait while a second pursuer applies the complete single-pursuer algorithm on each shadow component. This idea can be applied recursively for any number of robots.
The problem can be made more complicated by placing a velocity bound on the evader. Even though this makes the pursuer more powerful, it is more difficult to design a complete algorithm that correctly exploits this additional information. No complete algorithms currently exist for this case.
Figure 12.43 shows several alternative detection models that yield different definitions of V (p(t)). Each requires different pursuit-evasion algorithms because the structure of the I-space varies dramatically across different sensing models. For example, using the model in Figure 12.43c, a single pursuer is required to move along the ∂X. Once it moves into the interior, the shadow region always becomes a single connected component. This model is sometimes referred to as a flashlight. If there are two flashlights, then one flashlight may move into the interior while the other protects previous work. The case of limited depth, as shown in Figure 12.43, is very realistic in practice, but unfortunately it is the most challenging. The number of required pursuers generally depends on metric properties of the environment, such as its minimum “thickness.” The method presented in this section was extended to the case of a limited field of view in [381]; critical curves are obtained that are similar to those in Section 6.3.4. See the literature overview at the end of the chapter for more related material.