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.
There is also a vast literature on graph-based pursuit-evasion games, where players move continuously and have no knowledge of other players' positions. The terms graph searching'' and graph sweeping'' are used, and the concept is related to tree-width. For surveys see @cite_0 @cite_20 .
@cite_0 @cite_20
2154788235 1971322941 2597894505 1566624605
T. Parsons originally proposed and studied the following pursuit-evasion problem on graphs: Members of a team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number s ( G ) of searchers that will suffice for guaranteeing capture of the fugitive? It is shown that determining whether s ( G ) ≤ K , for a given integer K , is NP-complete for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs G with s ( G ) ≤ K for K = 1, 2, 3. In this paper, we present a game-theoretic analysis of a visibility-based pursuit-evasion game in a planar environment containing obstacles. The pursuer and the evader are holonomic having bounded speeds. Both players have a complete map of the environment. Both players have omnidirectional vision and have knowledge about each other's current position as long as they are visible to each other. The pursuer wants to maintain visibility of the evader for the maximum possible time and the evader wants to escape the pursuer's sight as soon as possible. Under this information structure, we present necessary and sufficient conditions for surveillance and escape. We present strategies for the players that are in Nash equilibrium. The strategies are a function of the value of the game. Using these strategies, we construct a value function by integrating the adjoint equations backward in time from the termination situations provided by the corners in the environment. From these value functions we recompute the control strategies for the players to obtain optimal trajectories for the players near the termination situation. This is the first work that presents the necessary and sufficient conditions for tracking for a visibility based pursuit-evasion game and presents the equilibrium strategies for the players. In a pursuit-evasion game, a team of pursuers attempt to capture an evader. The players alternate turns, move with equal speed, and have full information about the state of the game. We consider the most restrictive capture condition: a pursuer must become colocated with the evader to win the game. We prove two general results about this adversarial motion planning problem in geometric spaces. First, we show that one pursuer has a winning strategy in any compact CAT(0) space. This complements a result of Alexander, Bishop and Ghrist, who provide a winning strategy for a game with positive capture radius. Second, we consider the game played in a compact domain in Euclidean two-space with piecewise analytic boundary and arbitrary Euler characteristic. We show that three pursuers always have a winning strategy by extending recent work of Bhadauria, Klein, Isler and Suri from polygonal environments to our more general setting. Graph searching is the game of capturing a fugitive by a team of searchers in a network. There are equivalent characterizations in terms of path-width, interval thickness, and vertex separation. So far the interest has mainly focused on the search number of a graph, which is the minimal the number of searchers to win the game, and accordingly on the width and the thickness. These parameters measure the needed resources and correspond to space complexity. As its dual, we introduce the search time, which has not yet been studied in graph searching. We prove that all main results on graph searching can be generalized to include search time, such as monotone or recontamination free graph searching, and the characterizations in terms of path-width, interval graphs, and vertex separation, for which we introduce appropriate length parameters. We establish the NP-completeness of both search-width and search-time. Finally we investigate the speed-up by an extra searcher. There are ’good’ classes of graphs where a single extra searcher reduces the search time to one half and ’bad’ ones where some extra searchers are no real help.