Parallel multi-speed Pursuit-Evasion Game algorithms

Chung, 2011, Search and pursuit-evasion in mobile robotics, Auton. Robots, 31, 299, 10.1007/s10514-011-9241-4 Bopardikar, 2008, On discrete-time pursuit-evasion games with sensing limitations, IEEE Trans. Robot., 24, 1429, 10.1109/TRO.2008.2006721 Pan, 2012, Pursuit, evasion and defense in the plane, 4167 Vieira, 2009, Scalable and practical pursuit-evasion with networked robots, Intell. Serv. Robot., 2, 247, 10.1007/s11370-009-0050-y Makkapati, 2019, Optimal evading strategies and task allocation in multi-player pursuit–evasion problems, Dynam. Games Appl., 9, 1168, 10.1007/s13235-019-00319-x Nowakowski, 1983, Vertex-to-vertex pursuit in a graph, Discrete Math., 43, 235, 10.1016/0012-365X(83)90160-7 Adler, 2003, Randomized pursuit-evasion in graphs, Combin. Probab. Comput., 12, 225, 10.1017/S0963548303005625 Salimi, 2016, On a fixed duration pursuit differential game with geometric and integral constraints, Dynam. Games Appl., 6, 409, 10.1007/s13235-015-0161-3 Tekdas, 2010, Robotic routers: Algorithms and implementation, Int. J. Robot. Res., 29, 110, 10.1177/0278364909105053 Vieira, 2013, An autonomous wireless networked robotics system for backbone deployment in highly-obstructed environments, Ad Hoc Netw., 11, 1963, 10.1016/j.adhoc.2012.07.012 Isaacs, 1999 Yamaguchi, 1999, A Cooperative Hunting Behavior by Mobile-Robot Troops, Int. J. Robot. Res., 18, 931, 10.1177/02783649922066664 Parsons, 1978, Pursuit-evasion in a graph, 426 I.E. Weintraub, M. Pachter, E. Garcia, An Introduction to Pursuit-evasion Differential Games, in: 2020 American Control Conference, ACC, 2020, pp. 1049–1066, http://dx.doi.org/10.23919/ACC45564.2020.9147205. dos Santos, 2020, Pac-man is overkill, 11652 Pac-Man ThoughCo. 2019, https://www.thoughtco.com/pac-man-game-1779412. Goldstein, 1995, The complexity of pursuit on a graph, Theoret. Comput. Sci., 143, 93, 10.1016/0304-3975(95)80026-6 K. Krishnamoorthy, S. Darbha, P.P. Khargonekar, D. Casbeer, P. Chandler, M. Pachter, Optimal minimax pursuit evasion on a Manhattan grid, in: 2013 American Control Conference, 2013, pp. 3421–3428, http://dx.doi.org/10.1109/ACC.2013.6580360. H. Huang, W. Zhang, J. Ding, D.M. Stipanović, C.J. Tomlin, Guaranteed decentralized pursuit-evasion in the plane with multiple pursuers, in: 2011 50th IEEE Conference on Decision and Control and European Control Conference, 2011, pp. 4835–4840, http://dx.doi.org/10.1109/CDC.2011.6161237. Yan, 2017, Pursuing a faster evader based on an agent team with unstable speeds, 1766 Makkapati, 2020 Z. Zhang, J. Lee, J.M. Smereka, Y. Sung, L. Zhou, P. Tokekar, Tree Search Techniques for Minimizing Detectability and Maximizing Visibility, in: 2019 International Conference on Robotics and Automation, ICRA, 2019, pp. 8791–8797, http://dx.doi.org/10.1109/ICRA.2019.8794305. Zhou, 2016, Cooperative pursuit with Voronoi partitions, Automatica, 72, 64, 10.1016/j.automatica.2016.05.007 Kalyanam, 2015 Krishnamoorthy, 2016, Pursuit of a moving target with known constant speed on a directed acyclic graph under partial information, SIAM J. Control. Optim., 54, 2259, 10.1137/140994216 Makkapati, 2019, Optimal evading strategies and task allocation in multi-player pursuit–evasion problems, Dynam. Games Appl., 10.1007/s13235-019-00319-x E. Garcia, S.D. Bopardikar, Cooperative Containment of a High-speed Evader, in: 2021 American Control Conference, ACC, 2021, pp. 4698–4703, http://dx.doi.org/10.23919/ACC50511.2021.9483097. Pachter, 2020, Isaacs’ Two-on-One Pursuit-Evasion Game, 27 Z. Zhang, Y. Sung, L. Zhou, J.M. Smereka, J. Lee, P. Tokekar, Tree Search Techniques for Minimizing Detectability and Maximizing Visibility, 2019,. J. Bertram, P. Wei, An Efficient Algorithm for Multiple-Pursuer-Multiple-Evader Pursuit/Evasion Game, in: AIAA Scitech 2021 Forum, http://dx.doi.org/10.2514/6.2021-1862, URL. Yi, 2019, Indoor Pursuit-Evasion with Hybrid Hierarchical Partially Observable Markov Decision Processes for Multi-robot Systems, 251 Horák, 2016 Y. Guan, D. Maity, C.M. Kroninger, P. Tsiotras, Bounded-Rational Pursuit-Evasion Games, in: 2021 American Control Conference, ACC, 2021, pp. 3216–3221, http://dx.doi.org/10.23919/ACC50511.2021.9483152. Jansson, 2021, A parallelizable reachable set method for pursuit-evasion games using interior-point methods, 1 D. Shishika, V. Kumar, Local-game Decomposition for Multiplayer Perimeter-defense Problem, in: 2018 IEEE Conference on Decision and Control, CDC, 2018, pp. 2093–2100, http://dx.doi.org/10.1109/CDC.2018.8618879. D. Shishika, J. Paulos, M.R. Dorothy, M. Ani Hsieh, V. Kumar, Team Composition for Perimeter Defense with Patrollers and Defenders, in: 2019 IEEE 58th Conference on Decision and Control, CDC, 2019, pp. 7325–7332, http://dx.doi.org/10.1109/CDC40024.2019.9030082. Shishika, 2020, Cooperative team strategies for multi-player perimeter-defense games, IEEE Robot. Autom. Lett., 5, 2738, 10.1109/LRA.2020.2972818 Shishika, 2020, A Review of Multi Agent Perimeter Defense Games, 472 Yi, 2019, Indoor Pursuit-Evasion with Hybrid Hierarchical Partially Observable Markov Decision Processes for Multi-robot Systems, 251 M. Wang, L. Wang, T. Yue, An Application of Continuous Deep Reinforcement Learning Approach to Pursuit-Evasion Differential Game, in: 2019 IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference, ITNEC, 2019, pp. 1150–1156, http://dx.doi.org/10.1109/ITNEC.2019.8729310. B. Vlahov, E. Squires, L. Strickland, C. Pippin, On Developing a UAV Pursuit-Evasion Policy Using Reinforcement Learning, in: 2018 17th IEEE International Conference on Machine Learning and Applications, ICMLA, 2018, pp. 859–864, http://dx.doi.org/10.1109/ICMLA.2018.00138. Neufeld, 1998, A game of cops and robbers played on products of graphs, Discrete Math., 186, 253, 10.1016/S0012-365X(97)00165-9 H. Tang, W. Zhang, M. Sun, B. Lin, Z. Hu, A PE game with one superior hunter and multi-pursuer against an evader, in: 2021 40th Chinese Control Conference, CCC, 2021, pp. 5124–5130, http://dx.doi.org/10.23919/CCC52363.2021.9550708. Berarducci, 1993, On the cop number of a graph, Adv. Appl. Math., 14, 389, 10.1006/aama.1993.1019 Russell, 2009 Michael, 2002, High performance dynamic lock-free hash tables and list-based sets, 73 Herlihy, 1993, A methodology for implementing highly concurrent data objects, ACM Trans. Program. Lang. Syst., 15, 745, 10.1145/161468.161469 Marçais, 2011, A fast, lock-free approach for efficient parallel counting of occurrences of k-mers, Bioinformatics, 27, 764, 10.1093/bioinformatics/btr011 Devlin, 1979 Kleinberg, 2005 Python Software Foundation, 2019 Joblib Developers, 2008 Hill, 2008, Amdahl’s law in the multicore era, Computer, 41, 33, 10.1109/MC.2008.209