TY - JOUR

T1 - A Leapfrog Strategy for Pursuit-Evasion in a Polygonal Environment

AU - Ames, Brendan

AU - Beveridge, Andrew

AU - Carlson, Rosalie

AU - Djang, Claire

AU - Isler, Volkan

AU - Ragain, Stephen

AU - Savage, Maxray

PY - 2015/6/23

Y1 - 2015/6/23

N2 - We study pursuit-evasion in a polygonal environment with polygonal obstacles. In this turn based game, an evader e is chased by pursuers p1,p2,...,p. The players have full information about the environment and the location of the other players. The pursuers are allowed to coordinate their actions. On the pursuer turn, each pi can move to any point at distance at most 1 from his current location. On the evader turn, he moves similarly. The pursuers win if some pursuer becomes co-located with the evader in finite time. The evader wins if he can evade capture forever. It is known that one pursuer can capture the evader in any simply-connected polygonal environment, and that three pursuers are always sufficient in any polygonal environment P (possibly with polygonal obstacles). We contribute two new results to this field. First, we fully characterize when an environment with a single obstacle is one-pursuerwin or two-pursuer-win. Second, we give sufficient (but not necessary) conditions for an environment to have a winning strategy for two pursuers. Such environments can be swept by a leapfrog strategy in which the two cops alternately guard/increase the currently controlled area. The running time of this algorithm is O(ndiam(P)) where n is the number of vertices, h is the number of obstacles and diam(P)) is the diameter of the polygonal environment P. More concretely, for an environment with n vertices, we describe an O(n2) algorithm that (1) determines whether the obstacles are well-separated, and if so, (2) constructs the required partition for a leapfrog strategy.

AB - We study pursuit-evasion in a polygonal environment with polygonal obstacles. In this turn based game, an evader e is chased by pursuers p1,p2,...,p. The players have full information about the environment and the location of the other players. The pursuers are allowed to coordinate their actions. On the pursuer turn, each pi can move to any point at distance at most 1 from his current location. On the evader turn, he moves similarly. The pursuers win if some pursuer becomes co-located with the evader in finite time. The evader wins if he can evade capture forever. It is known that one pursuer can capture the evader in any simply-connected polygonal environment, and that three pursuers are always sufficient in any polygonal environment P (possibly with polygonal obstacles). We contribute two new results to this field. First, we fully characterize when an environment with a single obstacle is one-pursuerwin or two-pursuer-win. Second, we give sufficient (but not necessary) conditions for an environment to have a winning strategy for two pursuers. Such environments can be swept by a leapfrog strategy in which the two cops alternately guard/increase the currently controlled area. The running time of this algorithm is O(ndiam(P)) where n is the number of vertices, h is the number of obstacles and diam(P)) is the diameter of the polygonal environment P. More concretely, for an environment with n vertices, we describe an O(n2) algorithm that (1) determines whether the obstacles are well-separated, and if so, (2) constructs the required partition for a leapfrog strategy.

KW - Pursuit-evasion

KW - sweepable polygon

UR - http://www.scopus.com/inward/record.url?scp=84937682202&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84937682202&partnerID=8YFLogxK

U2 - 10.1142/S0218195915500065

DO - 10.1142/S0218195915500065

M3 - Article

AN - SCOPUS:84937682202

VL - 25

SP - 77

EP - 100

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

SN - 0218-1959

IS - 2

ER -