Capturing an Evader in a Polygonal Environment with Obstacles

1 Introduction

Pursuit-evasion games in which one or more pursuers try to capture an adversarial evader have numerous robotics applications such as surveillance and search-and-rescue. Due to its practical importance, there has been significant interest in solving pursuit-evasion games in complex environments. Such environments are usually represented either topologically with graphs or geometrically using polygons.

One of the earliest games on graphs is the game introduced by Parsons [Parsons, 1978]. In this game, pursuers try to capture an arbitrarily fast evader on a graph by "clearing" the vertices and surrounding the evader. In the cops-and-robbers game [Nowakowski and Winkler, 1983], the evader and the pursuers move in turns. At each turn, players can move to an adjacent vertex. The pursuers try to capture the evader by moving onto its current vertex.

The visibility-based pursuit-evasion game [Suzuki and Yamashita, 1992; Guibas et al., 1999] takes place in a polygon. Similar to Parson's game, the evader in this game is arbitrarily fast. The pursuers try to capture the evader by finding it (i.e., by establishing line of sight). The lion-and-man game [Alonso et al., 1992; Sgall, 2001] can be considered as a geometric version of the cops-and-robbers game. In the original version of this game, a lion tries to capture a man in a circular arena by moving on to his current location. Both players have equal maximum velocities. In this paper, we study this game in polygonal environments with obstacles, and show that three pursuers can capture the evader in any polygonal environment.

In addition to its theoretical importance, our result provides a pursuit strategy in a number of practical settings. One example is the scenario studied by [Vieira et al., 2009]. In this scenario, pursuers try to capture an evader in an environment where a sensor network is deployed. The sensor network provides the location of the evader to the pursuers. It also facilitates communication among the pursuers. Since the underlying domain in this game is polygonal, our results imply that only three pursuers would suffice regardless of the floor plan. Another example in which the evader's location is revealed to the pursuers is when an aerial vehicle supports the ground-based pursuit team as illustrated in Figure 1.

We build on the results by Aigner and Fromme who study the cops-and-robbers game and show that three cops can capture the robber on any planar graph [Aigner and Fromme, 1984]. It turns out that this result does not directly translate into pursuit-evasion in a polygonal environment due to the continuous nature of the underlying domain. One might think that this difficulty can be overcome simply by discretizing the domain perhaps by placing a grid with resolution comparable to the step-size of the players. Unfortunately, playing the game on such a grid does not guarantee capture in the original problem since the evader can not be restricted to stay on the vertices of the grid. Further, computing strategies using this representation can be extremely costly in terms of running time. To see this, imagine scaling the environment while keeping the step size constant. This way, the size of the grid can be made arbitrarily large. Instead, an algorithm whose complexity is proportional to the geometric parameters of the environment (e.g. number of vertices of the polygon) is desirable. One might try to circumvent this issue by playing the game on a graph that captures the topology of the underlying polygon (e.g. the triangulation graph or its dual). However, since the evader can not be restricted to stay on the edges of this graph as well, it can not be captured using the strategy by Aigner and Fromme.

Since there is no obvious way of using the graph-based pursuit strategy for pursuit in polygonal domains, we developed a new strategy which captures the continuous nature of the domain. In our strategy, the pursuers restrict the evader to smaller and smaller polygons with fewer number of obstacles or vertices. Once the evader is restricted to a simplyconnected polygon (with no holes) it gets captured by using a modification of the strategy presented by Isler et al. [Isler et al., 2005]. We show that capture takes a finite number of steps.

The paper is organized as follows. In Section 2 we describe the game model. We present preliminary results adapted from previous work in Section 3. Section 4 gives the details of our three-cop strategy and its analysis. We conclude the paper in Section 5 with directions for future research.

2 Game Model

The game is played in a simple polygon P which has finite number of polygonal obstacles (or holes) in it. An instance of the game is shown in Figure 2. There are two types of players in the game: cops and a robber. The following rules are used to play the game: At the beginning of the game, each cop picks a location in P . Next, the robber chooses its location in P . Afterwards, the game is played in alternate turns. All cops move simultaneously in a turn. If anytime during the game a cop can move to the current position of the robber, then the cops win the game.

We assume that the maximum speeds of all the cops and the robber are the same. We normalize the distances such that a cop or a robber can move at most one unit in its turn. The players know each others' positions throughout the game. The cops can communicate with each other at all times during the game. By communicating they can coordinate their moves.

3 Preliminaries

In this section, we present two results that will be used in our strategy. The first result is from [Aigner and Fromme, 1984] and shows that a single cop can guard a shortest path in the sense that whenever the robber crosses it, it will be captured. The second result is adapted from [Isler et al., 2005] and shows that a single cop can capture the robber in any simply-connected polygon (a simply-connected polygon is a polygon with no holes).

[Aigner and Fromme, 1984] introduced the concept of "guarding" a path in graphs. Their result applies to any metric space, which gives us the following lemma.

Lemma 3.1 (Guarding a shortest path [Aigner and Fromme, 1984]). In a finite number of moves, a single cop C can position itself on any shortest path π in such a way that for any point x ∈ π, the distance between x and C is less than or equal to the distance between x and the robber R's location. Afterwards, C can move in such a way that if R crosses π, it will be captured by C.

Note that this guarding strategy involves an initialization phase in which the cop positions itself on π to make sure that no point on π is closer to the robber than the cop. During the initialization phase, the robber can cross π. However, once the initialization phase is over, the robber can no longer cross π without being captured. The length of the initialization phase is bounded by the length of π.

[Isler et al., 2005] studied the visibility-based version of the cops-and-robbers game in simply-connected polygons. In their model, a cop can see the robber only if the line segment connecting the two players does not intersect the boundary of the polygon. They showed that a single cop can locate the robber, and two cops can capture the robber in any simply-connected polygon. In the two-cop strategy, one cop starts from an arbitrary point o and moves so that it stays on the shortest path between the robber's current location and o. Further, whenever the cop moves, its distance from o increases at least by a constant amount. Since the cop can not see the robber when it is occluded from his field of view, the second cop is used to determine the motion direction when the robber is not visible. They also bound the number of searches necessary. Since in our model the players know each other's locations at all times, the second cop is not necessary, giving us the following result:

Lemma 3.2 (Capture in a simply connected polygon [Isler et al., 2005]). A single cop can capture the robber in any simply-connected polygon in finite time.

Using these two results as subroutines, we now present a strategy for three cops to capture the robber in any polygonal environment (possibly with obstacles).

4 Three-Cop Strategy

In this section we present a strategy for three cops to catch a robber in finite time. We will divide the cops' strategy into rounds. In each round, the cops will coordinate their moves and restrict the robber to a smaller polygon.

The game starts with the cops and the robber situated at their initial positions. Then the robber makes the first move and the cops respond with their moves. In each round cops pick a shortest path in the polygon to guard 1 . Guarding this path essentially partitions the current polygon, and restricts the robber to a region which is smaller than the robber's region at the beginning of the round.

In any round, the cops' strategy will ensure that at most two paths will need to be guarded by the cops. Therefore in any round, at most two cops will be guarding these two paths (by Lemma 3.1) and one cop will be free. In each subsequent round, the free cop will guard a new path and relieve one of the other cops.

Before presenting the full strategy, we describe two types of moves. In each round cops will perform either a slicing move and/or an obstacle move. Each of the two moves is a sequence of steps taken by a single cop. Before presenting the details, we introduce the notation we will use throughout the paper.

At round i, the robber will be restricted to a polygonal region Pi. We denote the boundary of Pi by δPi. Let n(Pi) be the total number vertices in Pi (including the obstacle vertices). The boundary δPi will consist of at most two shortest paths, π1 and π2, each guarded by a dedicated cop. The rest of the boundary will either consist of a portion of δP, the original polygon's boundary, or the boundaries of the obstacles. Hence if robber tries to escape from Pi it has to cross either π1 or π2 which will result in capture by Lemma 3.1. We label the vertices of π1 and π2 in the order they are encountered while traversing δPi in clockwise direction. Without loss of generality, let π1 = u1, . . . , uk and let π2 = ul, . . . , um.

At the end of each round, the strategy will maintain the following invariants:

1. n(Pi) > n(Pi+1), the number of vertices in Pi+1 are strictly smaller than the number of vertices in Pi.
2. Pi+1 ⊂ Pi, i.e., the new polygon is a subset of the previous one.
3. the paths guarded by the cops forming the boundary of Pi+1 are both the shortest paths in Pi+1.

We are now ready to present the two types of moves and analyze their properties.

4.1 Obstacle Move

This move is performed when an obstacle is touching either π1 or π2. First consider the case where there is an obstacle touching exactly one of π1 or π2. Suppose there is an obstacle touching π1 but not π2 as shown in Figure 3-Top. In this case, the obstacle move is performed by finding a shortest path from u1 to uk in the interior of Pi excluding the points on π1. Let this new path be π3. The third cop starts guarding π3. Since the robber can be either between π3 and π1 or between π3 and π2, one of the cops from π1 or π2 will be free and the robber will be restricted to a smaller region.

1 The move will be over when the initialization phase of Lemma 3.1 is complete.

In the remaining case, there is an obstacle which is touching the boundary of Pi in multiple connected regions (see Figure 3-Bottom). This means that the interior of Pi is composed of multiple connected components. In this case the robber is already restricted to the connected component it lies in. The obstacle move is to simply switch to guarding the portion of π1 and π2 which are part of the boundary of this region. For example, on the right side of the Figure 3, if the evader is in region 2 then the new π1 (resp. π2) is the path from ui to uk (resp. ul to uj).

Lemma 4.1. After an obstacle move, all the invariants mentioned above are maintained.

Proof. We verify that each invariant is maintained.

1. In each obstacle move, we remove an obstacle from Pi and at least one vertex of this obstacle is not included in Pi+1 .
2. An obstacle move divides Pi into at least two regions, and we pick one. Therefore, Pi+1 ⊂ Pi.
3. π3 is a shortest path in Pi+1. So are π1 and π2. Hence, the two guarded paths in Pi+1 are both shortest paths.

4.2 SlicingMove

The slicing move is used to restrict the robber to a smaller polygon when no obstacle touches the guarded paths. In a slicing move two points ua and ub are picked from δPi such that ua (respectively ub) lies on the boundary portion between uk and ul (respectively u1 and um). We compute a shortest path between ua and ub and use the third cop to guard this path as shown in Figure 4. Note that if there is no path between ua and ub in Pi, this means that ua and ub are in two different components (i.e. Pi is disconnected). This can happen only when there is an obstacle whose boundary is touching δPi in multiple connected regions making it disconnected. In this case we can use the obstacle move presented in the previous section (Figure 3-right).

We now describe how ua and ub are chosen. There are a few variants of the slicing move based on the number of vertices between the endpoints of π1 and π2 (Figures 5 and 6).

Case 1: If π1 and π2 share no common endpoints, π3 is chosen as the shortest path connecting uk and um (i.e. we pick uk as ua and um as ub). This case is illustrated in Figure 5 (left).

Case 2: In the second case, π1 and π2 share a common endpoint (say uk), and there is at least one vertex on the boundary between the other endpoints (um and u1). In this case π3 is chosen as the shortest path connecting uk = ul and an arbitrary vertex between the other two endpoints. This case is illustrated in Figure 5 (right).

Case 3: In the third case, π1 and π2 have exactly one common endpoint and the other endpoints are adjacent (See Figure 6). Since an obstacle move is not possible, π1 and π2 are not touching any obstacles. In this case, π1 and π2 along with the polygonal edge, (uk, ul) form a structure called a funnel [Guibas et al., 1987]. The common end-point (u1 in Figure 6) is the apex of the funnel. Both π1 and π2 are inwardly convex: when walking from the apex to uk, one would always turn locally left. This is because π1 is a shortest path and no obstacle is touching it from the inside. Therefore, if there was a right turn (i.e. an inward convex vertex), one can find a shorter path from u1 to uk which is a contradiction. A symmetric argument holds for π2.

When there are no obstacles inside the funnel, the inward convex structure of π1 and π2 yields a simple partition of the funnel which can be used for computing shortest paths easily. The partition is obtained by extending each edge of π1 and π2 toward the edge (uk, ul) as shown in Figure 6. Suppose edge e on π1 was extended to form the boundary of a partition cell. The shortest path from u1 to point a in this partition cell continues along π1 until it leaves e, followed by a line segment from the last vertex of e to a. For example, in Figure 6, the shortest paths from u1 to a and b continue along π1 until x followed by the line segment xa and xb respectively. We refer the last vertex on the boundary as the corner vertex of a point. Hence x is the corner vertex of both a and b.

We now describe the slicing move for this case. If there are no obstacles inside the funnel, the third cop can capture the robber by Lemma 3.2. Otherwise, we show that there exists a point on the edge (ul, uk) whose shortest path from u1 touches an obstacle.

Remove all the obstacles from the funnel and compute the partition described above. We start from the leftmost partition and move toward right. For each partition we order all the obstacle vertices in that partition in anti-clockwise direction with respect to their corner vertex. We extend the line segment from the corner vertex to the first obstacle vertex in this ordering until it hits edge (ul, uk). In Figure 7, for partition tx2x3 we extend the line segment from t to the first vertex in the ordering until it hits (ul, uk) at o. Therefore the shortest path π3 from u1 to o touches the obstacle. The third cop guards this path. We now consider the part of the funnel the evader is restricted to. If the part contains no obstacles, the free cop guarding either π1 or π2 can capture the robber (Lemma 3.2). Otherwise, π3 is touching an obstacle. Therefore, we can perform an obstacle move.

Observe that in forming π3 we introduced a new vertex in Pi (at o in Figure 7). However, in computing Pi+1 we removed at least two vertices (either uk or ul plus the obstacle vertex touching π3). Hence the invariant n(Pi+1) < n(Pi) is maintained.

u1

Case 4: The only remaining case is when π1 and π2 have common endpoints at both ends. Since π1 and π2 are both shortest paths, it must be that π1 = π2 and the evader has already been captured, otherwise we get a contradiction with the fact that neither π1 nor π2 is touching any obstacles.

Among the four cases mentioned above, case 4 yields capture. In remaining cases 1-3, ua and ub can be chosen accordingly and a free cop can be assigned to guard the shortest path π3 between ua and ub (recall that such a path exists because an obstacle move is not possible). The path π3 partitions Pi to at least two regions. The robber can be either between π3 and π1 or between π3 and π2, therefore one of the cops from π1 or π2 can be relieved from guarding the path.

We now prove a technical lemma.

Lemma 4.2. The paths π1 and π2 can be chosen so that they do not share an edge.

Proof. Let us assume that π1 and π2 overlap which implies that they share at least one edge. Also, there must be at least one edge in π1 which is not in π2, otherwise guarding π2 is redundant. We also know that both π1 and π2 lie on the boundary of Pi. But since Pi is simple, the shared edges will include one of the two edges at the end of the two paths. Therefore, without loss of generality, we can assume that the last edge of π1 and the first edge of π2 is shared. Equivalently, let π1 = u1, . . . , ul, uk and π2 = ul, uk, . . . , um, i.e., π1 and π2 share the edge (ul, uk).

Since π1 is a shortest path, a path π′1 = u1, . . . , ul will also be a shortest path between u1 and ul. If the two cops pick paths π′1 and π2 to guard, the edges guarded will be the same as before, but the paths will be non-overlapping. Hence, as a result, we can always find π1 and π2 such that they don't share a common edge.

By Lemma 4.2, π1 and π2 will not overlap. Further, cases 1-4 above cover all possible non-overlapping cases. Therefore we have:

Corollary 4.3. If an obstacle move does not exist, either the robber is captured or a slicing move exists.

For case 3, we have already shown that n(Pi+1) < n(Pi). In all other cases, similar to the proof of Lemma 4.1, it can be verified that the slicing move maintains the invariants giving us the following lemma.

Lemma 4.4. After a slicing move, all the invariants are maintained.

4.3 Complete Strategy and Analysis

We are now ready to describe the full strategy. At the beginning of the game, two cops pick two separate edges and guard them as π1 and π2. Afterwards, the cops perform an obstacle move if an obstacle is touching π1 or π2, or an obstacle is touching the boundary of Pi in two connected regions. If an obstacle move is not possible, a slicing move is performed which is always possible by Corollary 4.3.

We now present our main result which shows that the sequence of moves described above result in capture in finite number of steps.

Theorem 4.5. Three cops can capture the robber in a finite number of steps in any polygon with a finite number of obstacles.

Proof. Suppose the step size of the cops and the robber is one. Let P be the initial polygon and n be the number of vertices of P. After each round, the robber is restricted to a subset of the area before the move. Further, the new area has at least one less vertex than the previous area. Therefore, the number of rounds is bounded by the number of vertices (including obstacle vertices).

Next we bound the length of each round. Each slicing or obstacle move is comprised of picking a shortest path π in Pi and guarding it. Hence, the length of each round is bounded by the time to reach π followed by the initialization phase of guarding it. Each of these quantities is bounded by the diameter of Pi (i.e. the longest shortest path in Pi). Therefore, the length of round i bounded by 2diam(Pi).

Is there an upper bound on diam(Pi) in terms of the parameters of P? While it is not easy to obtain a tight bound on this quantity, it is easy to see that it is bounded by the area A of P because shortest paths are non-intersecting. This suggests an upper bound of 2nA for the capture time.

For a given polygon, this upper bound is likely to be loose when the shortest paths are much shorter than the area A. However, the capture time can be as large as A in general: imagine a long and thin rectangular environment with cops starting on one end and the robber on the other. We also note that the diameter of Pi can be larger than the diameter of P. We leave the problem of obtaining a tight bound on capture time as an interesting problem for future research.

5 Conclusion

We studied a new variant of the cops and robbers game, and showed that three cops can capture the robber in any polygonal environment. In our model the players have equal maximum velocities and have access to each others' locations at all times. As noted earlier, an immediate question for future research is to obtain a tight bound on capture time.

An important extension for future work is to relax the assumption about the information available to the players. For example, if the cops can obtain information about the robber's location only when they establish line-of-sight visibility, how many cops are necessary? How does the outcome change if there are communication limitations?

Another challenging extension is to study the case when the cops are subject to non-holonomic motion constraints as in the case of a car chase.

Acknowledgments

This material is based upon work supported by the National Science Foundation under Grants 0916209, 0917676 and 0936710. We thank Shaun Gosse, Joseph Pipp and members of the Robotic Sensor Networks Lab for useful discussions, and their help with the figures.