Cops, a cheating robot, bodyguards and presidents

Abstract

Pursuit-evasion games are models that mathematicians use to study scenarios in which a group of pursuers are chasing an evader in a fixed environment. The main application for these games is in robotics where the algorithms developed from solving these games are translated into algorithms robots can use to accomplish important tasks. This allows pursuit-evasion games to be useful in a wide range of fields, such as in emergency response to optimize search and rescue missions and in aeronautics to optimize flight paths. Among pursuit-evasion games that are played in discrete environments, the most well studied is the game of Cops and Robber. The pursuers in this model are cops and the evader is a robber. If any of the cops are able to reach the location of the robber, then the cops win. If the robber can indefinitely avoid the cops, then the robber wins. In this thesis, we study a variation of Cops and Robber where the cops and the robber move simultaneously but the robber is given intelligence on how the cops will move throughout the game. The parameter of interest for this game is the fewest number of cops needed to capture this knowledgeable robber on a given playing field. We study this parameter on various playing fields. Studying this parameter on certain playing fields naturally produces a new pursuit-evasion game where the pursuers’ goal is to indefinitely surround the evader. We study this new pursuit-evasion game and show how this game relates to the model with a knowledgeable robber.