The Role of Visibility in Pursuit/Evasion Games

Robotics

Athanasios Kehagias²  Dieter Mitsche¹  Paweł Praᐪt³ 

[1] Laboratoire J. A. Dieudonné, UMR CNRS-UNS No 7351, Université de Nice Sophia-Antipolis, Parc Valrose 06108 Nice Cedex 2, France; E-Mail:;Department of Electrical and Computer Engineering, Aristotle University, GR 54248, Thessaloniki, Greece;Department of Mathematics, Ryerson University, 350 Victoria St., Toronto, ON, M5B 2K3, Canada; E-Mail:

关键词: mobile robotics;    robot coordination;    pursuit/evasion;   

DOI  :  10.3390/robotics3040371

来源: mdpi

【 摘 要 】

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.

【 授权许可】

CC BY   
© 2014 by the authors; licensee MDPI, Basel, Switzerland.