The Role of Visibility in Pursuit-Evasion GamesReport as inadecuate

The Role of Visibility in Pursuit-Evasion Games - Download this document for free, or read online. Document in PDF available to download.


Department of Electrical and Computer Engineering, Aristotle University, GR 54248, Thessaloniki, Greece


Laboratoire J. A. Dieudonné, UMR CNRS-UNS No 7351, Université de Nice Sophia-Antipolis, Parc Valrose 06108 Nice Cedex 2, France


Department of Mathematics, Ryerson University, 350 Victoria St., Toronto, ON, M5B 2K3, Canada


Author to whom correspondence should be addressed.

Abstract The cops-and-robber CR game has been used in mobile robotics as a discretized model played on a graph G of pursuit-evasion problems. The -classic- CR version is a perfect information game: the cops’ pursuer’s location is always known to the robber evader and vice versa. Many variants of the classic game can be defined: the robber can be invisible and also the robber can be either adversarial tries to avoid capture or drunk performs a random walk. Furthermore, the cops and robber can reside in either nodes or edges of G. Several of these variants are relevant as models or robotic pursuit-evasion. In this paper, we first define carefully several of the variants mentioned above and related quantities such as the cop number and the capture time. Then we introduce and study the cost of visibility COV, a quantitative measure of the increase in difficulty from the cops’ point of view when the robber is invisible. In addition to our theoretical results, we present algorithms which can be used to compute capture times and COV of graphs which are analytically intractable. Finally, we present the results of applying these algorithms to the numerical computation of COV. View Full-Text

Keywords: mobile robotics; robot coordination; pursuit-evasion mobile robotics; robot coordination; pursuit-evasion

Author: Athanasios Kehagias 1,* , Dieter Mitsche 2 and Paweł Prałat 3



Related documents