Download pdf
Cops and robbers game and applications of its variant
- 1 Boston University
* Author to whom correspondence should be addressed.
Abstract
Pursuit-evasion game is a game with a pursuer player and an evader player, it has numerous applications including artificial intelligence, robot motion planning and so on. The cops and robbers game is a type of pursuit-evasion game played on graphs, and its variant is a very fruitful research area in graph theory. The purpose of this paper is to find the specific relations between pursuit-evasion game applications and different types of variants of the cops and robbers game. The research method is to find variants with different game rules and winning strategies and classify them. Then compare these rules and strategies with the applications of pursuit-evasion games to find their relationships. The comparison result shows that there are many differences between the variants and the applications, which lead to their inability to be directly related. The application of the pursuit-evasion game is mainly based on route planning and object distance, and generally contains multiple variant types, which is different from the current research direction of variant.
Keywords
Cops and Robbers game, pursuit-evasion game, machine learning
[1]. Nowakowski, R. and Winkler, P. (1983) Vertex to vertex pursuit in a graph. Discrete Math. 43: 235–239.
[2]. Fromme, M. A. M., & Aigner, M. (1984). A game of cops and robbers. Discrete Appl. Math, 8, 1-12.
[3]. Mehrabian, A. (2011). Cops and robber game with a fast robber (Master's thesis, University of Waterloo).
[4]. González Hermosillo de la Maza, S. (2019). Cops and robbers with speed restrictions.
[5]. Yang, B. (2022). One-visibility cops and robber on trees: optimal cop-win strategies. Theoretical Computer Science, 928, pp.27-47.
[6]. Gahlawat, H., & Zehavi, M. (2023). Parameterized analysis of the cops and robber problem. arXiv:2307.04594.
[7]. Michaud, H. Cops and Robbers on Graph and Winning Strategy. https://www.cs.kent.edu/~dragan/ST-Spring2016/cops%20vs%20robbers.pdf
[8]. Lu, L. & Peng, X. (2012). On Meyniel's conjecture of the cop number. Journal of Graph Theory, 71(2), 192-205.
[9]. Şahin, İ. & Kumbasar, T. (2020). Catch me if you can: A pursuit-evasion game with intelligent agents in the unity 3d game environment. 2020 International Conference on Electrical Engineering (ICEE), IEEE, pp. 1-6.
[10]. Qi, Qi. Zhang, X. & Guo, X. (2020). A deep reinforcement learning approach for the pursuit evasion game in the presence of obstacles. 2020 IEEE International Conference on Real-time Computing and Robotics (RCAR), IEEE, pp. 68-73.
[11]. Lozano, E. Becerra, I. Ruiz, U. et al. (2022). A visibility-based pursuit-evasion game between two nonholonomic robots in environments with obstacles. Autonomous Robot. 46: 349–371.
[12]. Sani, M. Robu, B. & Hably, A. (2020). Pursuit-evasion game for nonholonomic mobile robots with obstacle avoidance using NMPC. 2020 28th Mediterranean conference on control and automation (MED), IEEE, pp. 978-983.
Cite this article
Bao,R. (2024). Cops and robbers game and applications of its variant. Applied and Computational Engineering,69,129-133.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of the 6th International Conference on Computing and Data Science
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).