A Leapfrog Strategy for Pursuit-Evasion in a Polygonal Environment
Authors:
- Stephen RagainSRStephen Ragain
Preprint
Abstract
We study pursuit-evasion in a polygonal environment with polygonal obstacles. In this turn based game, an evader $e$ is chased by pursuers $p_1, p_2, \ldots, p_{\ell}$. 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 $p_i$ 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 (possibly with polygonal obstacles). We contribute two new results to this field. First, we fully characterize when an environment with a single obstacles is one-pursuer-win 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 \emph{leapfrog strategy} in which the two cops alternately guard/increase the currently controlled area. The running time of this algorithm is $O(n \cdot h \cdot \mbox{diam}(P))$ where $n$ is the number of vertices, $h$ is the number of obstacles and $\mbox{diam}(P)$ is the diameter of $P$. More concretely, for an environment with $n$ vertices, we describe an $O(n^2)$ algorithm that (1) determines whether the obstacles are well-separated, and if so, (2) constructs the required partition for a leapfrog strategy.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Capturing an evader in polygonal environments with obstacles: The full visibility caseThe International Journal of Robotics Research, 2012
- The Game of Cops and Robbers on Graphs2011
- Search and pursuit-evasion in mobile roboticsAutonomous Robots, 2011
- Randomized Pursuit-Evasion with Local VisibilitySIAM Journal on Discrete Mathematics, 2006
- GENERALIZING MONOTONICITY: ON RECOGNIZING SPECIAL CLASSES OF POLYGONS AND POLYHEDRAInternational Journal of Computational Geometry & Applications, 2005
- Randomized pursuit-evasion in a polygonal environmentIEEE Transactions on Robotics, 2005
- Solution of David Gale's lion and man problemTheoretical Computer Science, 2001
- “Lion and Man”: Upper and Lower BoundsINFORMS Journal on Computing, 1992
- A game of cops and robbersDiscrete Applied Mathematics, 1984