We study versions of cop and robber pursuit-evasion games on the visibility graphs of polygons, and inside polygons with straight and curved sides. Each player has full information about the other player's location, players take turns, and the robber is captured when the cop arrives at the same point as the robber. In visibility graphs we show the cop can always win because visibility graphs are dismantlable, which is interesting as one of the few results relating visibility graphs to other known graph classes. We extend this to show that the cop wins games in which players move along straight line segments inside any polygon and, more generally, inside any simply connected planar region with a reasonable boundary. Essentially, our problem is a type of pursuit-evasion using the link metric rather than the Euclidean metric, and our result provides an interesting class of infinite cop-win graphs.
Pursuit-Evasion. In the cops and robbers game, space is discrete. For continuous spaces, a main focus has been on polygonal regions, i.e., a region bounded by a polygon with polygonal holes removed. The seminal 1999 paper by @cite_4 concentrated on visibility-based'' pursuit-evasion where the evader is arbitrarily fast and the pursuers do not know the evader's location and must search the region until they make line-of-sight contact. This models the scenario of agents searching the floor-plan of a building to find a smart, fast intruder that can be zapped from a distance. @cite_4 showed that @math pursuers are needed in a simple polygyon, and more generally they bounded the number of pursuers in terms of the number of holes in the region. If the pursuers have the power to make random choices, @cite_23 showed that only one guard is needed for a polygon. For a survey on pursuit-evasion in polygonal regions, see @cite_19 .
@cite_19 @cite_4 @cite_23
40650588 2163841363 1976698879
This paper surveys recent results in pursuit-evasion and autonomous search relevant to applications in mobile robotics. We provide a taxonomy of search problems that highlights the differences resulting from varying assumptions on the searchers, targets, and the environment. We then list a number of fundamental results in the areas of pursuit-evasion and probabilistic search, and we discuss field implementations on mobile robotic systems. In addition, we highlight current open problems in the area and explore avenues for future work. In this survey article, we present open problems and conjectures on visibility graphs of points, segments, and polygons along with necessary backgrounds for understanding them. This paper contains two main results. First, we revisit the well-known visibility-based pursuit-evasion problem, and show that in contrast to deterministic strategies, a single pursuer can locate an unpredictable evader in any simply connected polygonal environment, using a randomized strategy. The evader can be arbitrarily faster than the pursuer, and it may know the position of the pursuer at all times, but it does not have prior knowledge of the random decisions made by the pursuer. Second, using the randomized algorithm, together with the solution to a problem called the "lion and man problem" as subroutines, we present a strategy for two pursuers (one of which is at least as fast as the evader) to quickly capture an evader in a simply connected polygonal environment. We show how this strategy can be extended to obtain a strategy for a polygonal room with a door, two pursuers who have only line-of-sight communication, and a single pursuer (at the expense of increased capture time).