追逃博弈问题研究综述

迟嵩禹; 李帅; 王晨; 谢广明

doi:10.16383/j.aas.c240396

追逃博弈问题研究综述

doi: 10.16383/j.aas.c240396 cstr: 32138.14.j.aas.c240396

迟嵩禹^1,,
李帅^1,,
王晨^{1, 2,},
谢广明^{1, 3,}

1.
北京大学工学院智能仿生设计实验室北京 100871
2.
北京大学软件工程国家工程研究中心北京 100871
3.
北京大学海洋研究院北京 100871

基金项目: 国家自然科学基金(12272008, U22A2062, U23B2037)资助

详细信息

作者简介:
迟嵩禹：北京大学工学院硕士研究生. 主要研究方向为多智能体博弈. E-mail: 2301213114@stu.pku.edu.cn

李帅：北京大学工学院博士后. 主要研究方向为多智能体系统, 多机器人控制, 人工智能和博弈论. E-mail: shuaier@pku.edu.cn

王晨：北京大学软件工程国家工程研究中心副研究员. 主要研究方向为仿生机器人, 多智能体系统和深度学习. E-mail: wangchen@pku.edu.cn

谢广明：北京大学工学院教授. 主要研究方向为智能群体理论, 仿生机器人, 网络控制系统和深度学习. 本文通信作者. E-mail: xiegming@pku.edu.cn

计量
- 文章访问数: 980
- HTML全文浏览量: 526
- 被引次数: 0
出版历程
- 收稿日期: 2024-06-28
- 录用日期: 2024-10-08
- 网络出版日期: 2024-12-19

A Review of Research on Pursuit-evasion Games

CHI Song-Yu^1
,,
LI Shuai^1
,,
WANG Chen^{1, 2
,},
XIE Guang-Ming^{1, 3
,}

1.
Intelligent Biomimetic Design Laboratory, College of Engineering, Peking University, Beijing 100871
2.
National Engineering Research Center of Software Engineering, Peking University, Beijing 100871
3.
Institute of Ocean Research, Peking University, Beijing 100871

Funds: Supported by National Natural Science Foundation of China (12272008, U22A2062, U23B2037)

More Information

Author Bio:
CHI Song-Yu　Master student at the College of Engineering, Peking University. His main research interest is multi-agent games

LI Shuai　 Postdoctor at the College of Engineering, Peking University. His research interest covers multi-agent systems, multi-robot control, artificial intelligence, and game theory

WANG Chen　 Associate researcher at the National Engineering Research Center of Software Engineering, Peking University. Her research interest covers biomimetic robotics, multi-agent systems, and deep learning

XIE Guang-Ming　 Professor at the College of Engineering, Peking University. His research interest covers smart swarm theory, biomimetic robotics, networked control systems, and deep learning. Corresponding author of this paper

摘要

摘要: 作为多智能体对抗博弈问题的重要分支, 追逃博弈(Pursuit-evasion, PE)问题在控制和机器人领域得到了广泛应用, 受到众多研究者的密切关注. 追逃博弈问题主要聚焦于追逐者和逃跑者双方为实现各自目标而展开的动态博弈: 追逐者试图在最短时间内抓到逃跑者, 逃跑者的目标则是避免被捕获. 本文概述追逃博弈问题的相关研究进展, 从空间环境、信息获取等五个方面介绍追逃博弈问题的各类设定; 简述理论求解、数值求解等四种当下主流的追逃博弈问题求解方法. 通过对现有研究的总结和分析, 给出几点研究建议, 对未来追逃博弈问题的发展具有一定指导意义.
- 追逃博弈问题 /
- 多智能体 /
- 对抗博弈 /
- 微分对策
Abstract: As an important branch of multi-agent adversarial games, pursuit-evasion (PE) games have found widespread applications in the fields of control and robotics, attracting considerable attention from researchers. PE games primarily focus on the dynamic games between pursuer and evader, each striving to achieve their respective objectives: The pursuer aims to capture the evader as quickly as possible, while the evader＇s goal is to avoid capture. This article provides an overview of the research progress in PE games, and introduces various settings of PE games across five key dimensions, including spatial environment, information acquisition, and so on. It briefly describes four mainstream methods for solving PE games, including theoretical approaches, numerical approaches, and so on. By summarizing and analyzing existing researches, this article offers several research suggestions, which are expected to provide significant guidance for future developments in PE games.
- Pursuit-evasion (PE) games /
- multi-agent /
- adversarial games /
- differential games

HTML全文

图 1 追逃博弈研究概况

Fig. 1 Research overview of PE games

下载: 全尺寸图片幻灯片

图 2 LVLH坐标系

Fig. 2 LVLH coordinate system

下载: 全尺寸图片幻灯片

图 3 有向无环图

Fig. 3 Directed acyclic graph

下载: 全尺寸图片幻灯片

图 4 散射曲面示例

Fig. 4 Dispersal surface example

下载: 全尺寸图片幻灯片

图 5 障碍物对等时线的影响

Fig. 5 Influence of obstacles on isochrones

下载: 全尺寸图片幻灯片

图 6 Voronoi分割示例

Fig. 6 Voronoi partition example

下载: 全尺寸图片幻灯片

A1 代表性追逃博弈文献分类

A1 Classification of representative literature on PE games

求解方法	文献	动态模型				追逃双方数量			维度		信息完整程度		状态空间
求解方法	文献	一阶积分器	二阶积分器	独轮车	其他	一对一	多对一	多对多	二维平面	三维空间	完全信息	不完全信息	连续	离散
理论求解法	[60]	$\checkmark $	$\checkmark $				$\checkmark $		$\checkmark $		$\checkmark $		$\checkmark $
	[57]	$\checkmark $		$\checkmark $		$\checkmark $			$\checkmark $		$\checkmark $		$\checkmark $
	[169]			$\checkmark $		$\checkmark $			$\checkmark $		$\checkmark $		$\checkmark $
	[96]	$\checkmark $						$\checkmark $	$\checkmark $			$\checkmark $		$\checkmark $
数值求解法	[73]	$\checkmark $					$\checkmark $		$\checkmark $			$\checkmark $	$\checkmark $
	[6]		$\checkmark $			$\checkmark $			$\checkmark $		$\checkmark $		$\checkmark $
	[86]	$\checkmark $						$\checkmark $		$\checkmark $		$\checkmark $	$\checkmark $
	[49]				$\checkmark $	$\checkmark $				$\checkmark $	$\checkmark $		$\checkmark $
	[44]			$\checkmark $			$\checkmark $		$\checkmark $			$\checkmark $	$\checkmark $
积分强化学习法	[147]	$\checkmark $						$\checkmark $	$\checkmark $			$\checkmark $	$\checkmark $
	[141]		$\checkmark $				$\checkmark $		$\checkmark $		$\checkmark $		$\checkmark $
	[46]			$\checkmark $			$\checkmark $			$\checkmark $	$\checkmark $		$\checkmark $
	[15]				$\checkmark $	$\checkmark $				$\checkmark $	$\checkmark $		$\checkmark $
	[40]			$\checkmark $				$\checkmark $		$\checkmark $	$\checkmark $		$\checkmark $
	[146]		$\checkmark $					$\checkmark $		$\checkmark $	$\checkmark $		$\checkmark $
几何法	[157]			$\checkmark $		$\checkmark $			$\checkmark $		$\checkmark $		$\checkmark $
	[95]				$\checkmark $	$\checkmark $			$\checkmark $			$\checkmark $		$\checkmark $
	[155]	$\checkmark $						$\checkmark $	$\checkmark $			$\checkmark $	$\checkmark $
	[161]	$\checkmark $					$\checkmark $		$\checkmark $		$\checkmark $		$\checkmark $
	[105]				$\checkmark $	$\checkmark $			$\checkmark $		$\checkmark $			$\checkmark $
	[23]	$\checkmark $					$\checkmark $			$\checkmark $	$\checkmark $		$\checkmark $
	[31]	$\checkmark $						$\checkmark $	$\checkmark $			$\checkmark $	$\checkmark $
	[39]		$\checkmark $			$\checkmark $			$\checkmark $		$\checkmark $		$\checkmark $

下载: 导出CSV

参考文献(169)

[1]	Domenici P, Blagburn J M, Bacon J P. Animal escapology Ⅱ: Escape trajectory case studies. Journal of Experimental Biology, 2011, 214(15): 2474−2494 doi: 10.1242/jeb.053801
[2]	Tay N E, Warburton N M, Moseby K E, Fleming P A. Predator escape behaviour in threatened marsupials. Animal Conservation, 2023, 26(4): 587−601 doi: 10.1111/acv.12847
[3]	FitzGibbon C D. The costs and benefits of predator inspection behaviour in Thomson's gazelles. Behavioral Ecology and Sociobiology, 1994, 34(2): 139−148 doi: 10.1007/BF00164184
[4]	Scheel D, Packer C. Group hunting behaviour of lions: A search for cooperation. Animal Behaviour, 1991, 41(4): 697−709 doi: 10.1016/S0003-3472(05)80907-8
[5]	Wang J N, Li G L, Liang L, Wang C Y, Deng F. Pursuit-evasion games of multiple cooperative pursuers and an evader: A biological-inspired perspective. Communications in Nonlinear Science and Numerical Simulation, 2022, 110: Article No. 106386 doi: 10.1016/j.cnsns.2022.106386
[6]	Li W. A dynamics perspective of pursuit-evasion: Capturing and escaping when the pursuer runs faster than the agile evader. IEEE Transactions on Automatic Control, 2017, 62(1): 451−457 doi: 10.1109/TAC.2016.2575008
[7]	Li W. The confinement-escape problem of a defender against an evader escaping from a circular region. IEEE Transactions on Cybernetics, 2016, 46(4): 1028−1039 doi: 10.1109/TCYB.2015.2503285
[8]	Weintraub I E, Pachter M, Garcia E. An introduction to pursuit-evasion differential games. In: Proceedings of the American Control Conference (ACC). Denver, USA: IEEE, 2020. 1049−1066
[9]	Mu Z X, Pan J, Zhou Z Y, Yu J Z, Cao L. A survey of the pursuit-evasion problem in swarm intelligence. Frontiers of Information Technology & Electronic Engineering, 2023, 24(8): 1093−1116
[10]	Isaacs R. Differential Games: A Mathematical Theory With Applications to Warfare and Pursuit, Control and Optimization. New York: John Wiley & Sons, Inc., 1965.
[11]	Starr A W, Ho Y C. Further properties of nonzero-sum differential games. Journal of Optimization Theory and Applications, 1969, 3(4): 207−219 doi: 10.1007/BF00926523
[12]	Ho Y C. Differential games, dynamic optimization, and generalized control theory. Journal of Optimization Theory and Applications, 1970, 6(3): 179−209 doi: 10.1007/BF00926600
[13]	张嗣瀛. 微分对策. 北京: 科学出版社, 1987. Zhang Si-Ying. Differential Games. Beijing: Science Press, 1987.
[14]	刘坤, 郑晓帅, 林业茗, 韩乐, 夏元清. 基于微分博弈的追逃问题最优策略设计. 自动化学报, 2021, 47(8): 1840−1854 Liu Kun, Zheng Xiao-Shuai, Lin Ye-Ming, Han Le, Xia Yuan-Qing. Design of optimal strategies for the pursuit-evasion problem based on differential game. Acta Automatica Sinica, 2021, 47(8): 1840−1854
[15]	耿远卓, 袁利, 黄煌, 汤亮. 基于终端诱导强化学习的航天器轨道追逃博弈. 自动化学报, 2023, 49(5): 974−984 Geng Yuan-Zhuo, Yuan Li, Huang Huang, Tang Liang. Terminal-guidance based reinforcement-learning for orbital pursuit-evasion game of the spacecraft. Acta Automatica Sinica, 2023, 49(5): 974−984
[16]	Pontryagin L S. On the theory of differential games. Russian Mathematical Surveys, 1966, 21(4): 193−246 doi: 10.1070/RM1966v021n04ABEH004171
[17]	Dobbie J M. Solution of some surveillance-evasion problems by the methods of differential games. In: Proceedings of the International Conference on Operational Research. New York, USA: John Wiley & Sons, 1966.
[18]	Tan M. Multi-agent reinforcement learning: Independent versus cooperative agents. In: Proceedings of the 10th International Conference on Machine Learning. Amherst, USA: Morgan Kaufmann Publishers Inc., 1993. 330−337
[19]	Guy R K. Unsolved problems in combinatorial games. Combinatorics Advances. Boston: Springer, 1995. 161−179
[20]	Vamvoudakis K G, Lewis F L. Multi-player non-zero-sum games: Online adaptive learning solution of coupled Hamilton-Jacobi equations. Automatica, 2011, 47(8): 1556−1569 doi: 10.1016/j.automatica.2011.03.005
[21]	Flynn J. Lion and man: The general case. SIAM Journal on Control, 1974, 12(4): 581−597 doi: 10.1137/0312043
[22]	Oyler D W, Kabamba P T, Girard A R. Pursuit-evasion games in the presence of a line segment obstacle. In: Proceedings of the 53rd IEEE Conference on Decision and Control (CDC). Los Angeles, USA: IEEE, 2014. 1149−1154
[23]	Garcia E, Casbeer D W, Pachter M. Optimal strategies for a class of multi-player reach-avoid differential games in 3D space. IEEE Robotics and Automation Letters, 2020, 5(3): 4257−4264 doi: 10.1109/LRA.2020.2994023
[24]	Nath S, Ghose D. A two-phase evasive strategy for a pursuit-evasion problem involving two non-holonomic agents with incomplete information. European Journal of Control, 2022, 68: Article No. 100677 doi: 10.1016/j.ejcon.2022.100677
[25]	Oyler D W, Girard A R. Dominance regions in the homicidal chauffeur problem. In: Proceedings of the American Control Conference (ACC). Boston, USA: IEEE, 2016. 2494−2499
[26]	Pachter M, Moll A V, Garcia E, Casbeer D, Milutinović D. Cooperative pursuit by multiple pursuers of a single evader. Journal of Aerospace Information Systems, 2020, 17(8): 371−389 doi: 10.2514/1.I010739
[27]	Bakolas E, Tsiotras P. Optimal pursuit of moving targets using dynamic Voronoi diagrams. In: Proceedings of the 49th IEEE Conference on Decision and Control (CDC). Atlanta, USA: IEEE, 2010. 7431−7436
[28]	Ramana M V, Kothari M. Pursuit-evasion games of high speed evader. Journal of Intelligent & Robotic Systems, 2017, 85: 293−306
[29]	Shishika D, Kumar V. Local-game decomposition for multiplayer perimeter-defense problem. In: Proceedings of the IEEE Conference on Decision and Control (CDC). Miami, USA: IEEE, 2018. 2093−2100
[30]	Liang L, Deng F, Lu M B, Chen J. Analysis of role switch for cooperative target defense differential game. IEEE Transactions on Automatic Control, 2021, 66(2): 902−909 doi: 10.1109/TAC.2020.2987701
[31]	Yan R, Shi Z Y, Zhong Y S. Task assignment for multiplayer reach-avoid games in convex domains via analytical barriers. IEEE Transactions on Robotics, 2020, 36(1): 107−124 doi: 10.1109/TRO.2019.2935345
[32]	Zhao Y, Tao Q L, Xian C X, Li Z K, Duan Z S. Prescribed-time distributed Nash equilibrium seeking for noncooperation games. Automatica, 2023, 151: Article No. 110933 doi: 10.1016/j.automatica.2023.110933
[33]	Xue L, Ye J F, Wu Y B, Liu J, Wunsch D C. Prescribed-time Nash equilibrium seeking for pursuit-evasion game. IEEE/CAA Journal of Automatica Sinica, 2024, 11(6): 1518−1520 doi: 10.1109/JAS.2023.124077
[34]	Bakolas E. Evasion from a group of pursuers with double integrator kinematics. In: Proceedings of the 52nd IEEE Conference on Decision and Control. Firenze, Italy: IEEE, 2013. 1472−1477
[35]	Selvakumar J, Bakolas E. Evasion from a group of pursuers with a prescribed target set for the evader. In: Proceedings of the American Control Conference (ACC). Boston, USA: IEEE, 2016. 155−160
[36]	Coon M, Panagou D. Control strategies for multiplayer target-attacker-defender differential games with double integrator dynamics. In: Proceedings of the 56th IEEE Annual Conference on Decision and Control (CDC). Melbourne, Australia: IEEE, 2017. 1496−1502
[37]	Chipade V S, Panagou D. IDCAIS: Inter-defender collision-aware interception strategy against multiple attackers. arXiv preprint arXiv: 2112.12098, 2021.
[38]	Chipade V S, Panagou D. Multiagent planning and control for swarm herding in 2-D obstacle environments under bounded inputs. IEEE Transactions on Robotics, 2021, 37(6): 1956−1972 doi: 10.1109/TRO.2021.3072026
[39]	Li S, Wang C, Xie G M. Optimal strategies for pursuit-evasion differential games of players with damped double integrator dynamics. IEEE Transactions on Automatic Control, 2024, 69(8): 5278−5293 doi: 10.1109/TAC.2023.3346815
[40]	Kokolakis N M T, Vamvoudakis K G. Bounded rational Dubins vehicle coordination for target tracking using reinforcement learning. Automatica, 2023, 149: Article No. 110732 doi: 10.1016/j.automatica.2022.110732
[41]	Patsko V S, Turova V L. Homicidal chauffeur game: History and modern studies. Advances in Dynamic Games: Theory, Applications, and Numerical Methods for Differential and Stochastic Games. Boston: Birkhäuser, 2011. 227−251
[42]	Pachter M, Coates S. The classical homicidal chauffeur game. Dynamic Games and Applications, 2019, 9(3): 800−850 doi: 10.1007/s13235-018-0264-8
[43]	Exarchos I, Tsiotras P, Pachter M. On the suicidal pedestrian differential game. Dynamic Games and Applications, 2015, 5(3): 297−317 doi: 10.1007/s13235-014-0130-2
[44]	Nath S, Ghose D. Worst-case scenario evasive strategies in a two-on-one engagement between Dubins' vehicles with partial information. IEEE Control Systems Letters, 2023, 7: 25−30 doi: 10.1109/LCSYS.2022.3186179
[45]	Sani M, Robu B, Hably A. Pursuit-evasion game for nonholonomic mobile robots with obstacle avoidance using NMPC. In: Proceedings of the 28th Mediterranean Conference on Control and Automation (MED). Saint-Rapha, France: IEEE, 2020. 978−983
[46]	Manoharan A, Thakur P, Singh A K. Multi-agent target defense game with learned defender to attacker assignment. In: Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS). Warsaw, Poland: IEEE, 2023. 297−304
[47]	祝海. 基于微分对策的航天器轨道追逃最优控制策略 [硕士学位论文], 国防科技大学, 中国, 2017. Zhu Hai. Optimal Control of Spacecraft Orbital Pursuit-evasion Based on Differential Game [Master thesis], National University of Defense Technology, China, 2017.
[48]	Clohessy W H, Wiltshire R S. Terminal guidance system for satellite rendezvous. Journal of the Aerospace Sciences, 1960, 27(9): 653−658 doi: 10.2514/8.8704
[49]	Zhang C M, Zhu Y W, Yang L P, Zeng X. An optimal guidance method for free-time orbital pursuit-evasion game. Journal of Systems Engineering and Electronics, 2022, 33(6): 1294−1308
[50]	Venigalla C, Scheeres D. Spacecraft rendezvous and pursuit/evasion analysis using reachable sets. In: Proceedings of the Space Flight Mechanics Meeting. Kissimmee, USA: American Institute of Aeronautics and Astronautics, Inc., 2018.
[51]	Li Z Y, Zhu H, Yang Z, Luo Y Z. A dimension-reduction solution of free-time differential games for spacecraft pursuit-evasion. Acta Astronautica, 2019, 163: 201−210 doi: 10.1016/j.actaastro.2019.01.011
[52]	Lin B, Qiao L, Jia Z H, Sun Z J, Sun M, Zhang W D. Control strategies for target-attacker-defender games of USVs. In: Proceedings of the 6th International Conference on Automation, Control and Robotics Engineering (CACRE). Dalian, China: IEEE, 2021. 191−198
[53]	Ho Y, Bryson A, Baron S. Differential games and optimal pursuit-evasion strategies. IEEE Transactions on Automatic Control, 1965, 10(4): 385−389 doi: 10.1109/TAC.1965.1098197
[54]	Kothari M, Manathara J G, Postlethwaite I. Cooperative multiple pursuers against a single evader. Journal of Intelligent & Robotic Systems, 2017, 86(3): 551−567
[55]	Yufereva O. Lion and man game in compact spaces. Dynamic Games and Applications, 2019, 9(1): 281−292 doi: 10.1007/s13235-018-0239-9
[56]	Oyler D W, Kabamba P T, Girard A R. Pursuit-evasion games in the presence of obstacles. Automatica, 2016, 65: 1−11 doi: 10.1016/j.automatica.2015.11.018
[57]	Exarchos I, Tsiotras P. An asymmetric version of the two car pursuit-evasion game. In: Proceedings of the 53rd IEEE Conference on Decision and Control (CDC). Los Angeles, USA: IEEE, 2014. 4272−4277
[58]	Das G, Dorothy M, Bell Z I, Shishika D. Guarding a non-maneuverable translating line with an attached defender. arXiv preprint arXiv: 2209.09318, 2022.
[59]	Liang L, Deng F, Wang J N, Lu M B, Chen J. A reconnaissance penetration game with territorial-constrained defender. IEEE Transactions on Automatic Control, 2022, 67(11): 6295−6302 doi: 10.1109/TAC.2022.3183034
[60]	Levchenkov A Y, Pashkov A G. Differential game of optimal approach of two inertial pursuers to a noninertial evader. Journal of Optimization Theory and Applications, 1990, 65(3): 501−518 doi: 10.1007/BF00939563
[61]	Chen J, Zha W, Peng Z H, Gu D B. Multi-player pursuit-evasion games with one superior evader. Automatica, 2016, 71: 24−32 doi: 10.1016/j.automatica.2016.04.012
[62]	Yan R, Shi Z Y, Zhong Y S. Cooperative strategies for two-evader-one-pursuer reach-avoid differential games. International Journal of Systems Science, 2021, 52(9): 1894−1912 doi: 10.1080/00207721.2021.1872116
[63]	Liu S Y, Zhou Z Y, Tomlin C, Hedrick K. Evasion as a team against a faster pursuer. In: Proceedings of the American Control Conference (ACC). Washington, USA: IEEE, 2013. 5368−5373
[64]	Wang D, Peng Z H. Pursuit-evasion games of multi-players with a single faster player. In: Proceedings of the 35th Chinese Control Conference (CCC). Chengdu, China: IEEE, 2016. 2583−2588
[65]	Scott W L, Leonard N E. Optimal evasive strategies for multiple interacting agents with motion constraints. Automatica, 2018, 94: 26−34 doi: 10.1016/j.automatica.2018.04.008
[66]	Garcia E, Casbeer D W, von Moll A, Pachter M. Multiple pursuer multiple evader differential games. IEEE Transactions on Automatic Control, 2021, 66(5): 2345−2350 doi: 10.1109/TAC.2020.3003840
[67]	Wei M, Chen G S, Cruz J B, Haynes L S, Pham K, Blasch E. Multi-pursuer multi-evader pursuit-evasion games with jamming confrontation. Journal of Aerospace Computing, Information, and Communication, 2007, 4(3): 693−706 doi: 10.2514/1.25329
[68]	Wei M, Chen G S, Cruz J B, Haynes L S, Chang M H, Blasch E. A decentralized approach to pursuer-evader games with multiple superior evaders in noisy environments. In: Proceedings of the IEEE Aerospace Conference. Big Sky, USA: IEEE, 2007. 1−10
[69]	Xu L, Hu B, Guan Z H, Cheng X M, Li T, Xiao J W. Multi-agent deep reinforcement learning for pursuit-evasion game scalability. In: Proceedings of the Chinese Intelligent Systems Conference. Haikou, China: Springer, 2019. 658−669
[70]	Li D X, Cruz J B, Chen G S, Kwan C, Chang M H. A hierarchical approach to multi-player pursuit-evasion differential games. In: Proceedings of the 44th IEEE Conference on Decision and Control (CDC). Seville, Spain: IEEE, 2005. 5674−5679
[71]	Li D X, Cruz Jr J B, Schumacher C J. Stochastic multi-player pursuit-evasion differential games. International Journal of Robust and Nonlinear Control, 2008, 18(2): 218−247 doi: 10.1002/rnc.1193
[72]	Yan R, Deng R L, Lai H W, Zhang W X, Shi Z Y, Zhong Y S. Multiplayer homicidal chauffeur reach-avoid games via guaranteed winning strategies. arXiv preprint arXiv: 2107.04709, 2021.
[73]	LaValle S M, Lin D, Guibas L J, Latombe J C, Motwani R. Finding an unpredictable target in a workspace with obstacles. In: Proceedings of the International Conference on Robotics and Automation. Albuquerque, USA: IEEE, 1997. 737−742
[74]	Razali S, Meng Q G, Yang S H. A refined immune systems inspired model for multi-robot shepherding. In: Proceedings of the Second World Congress on Nature and Biologically Inspired Computing (NaBIC). Kitakyushu, Japan: IEEE, 2010. 473−478
[75]	Bhadauria D, Gosse S, Pipp J. Capturing an evader in a polygonal environment with obstacles [Online], available: https://www.conservancy.umn.edu/items/256a22f6-ba8c-4b12-a80d-300b7cba947c, June 15, 2024 Bhadauria D, Gosse S, Pipp J. Capturing an evader in a polygonal environment with obstacles [Online], available: https://www.conservancy.umn.edu/items/256a22f6-ba8c-4b12-a80d-300b7cba947c, June 15, 2024
[76]	de Souza C, Newbury R, Cosgun A, Castillo P, Vidolov B, Kulić D. Decentralized multi-agent pursuit using deep reinforcement learning. IEEE Robotics and Automation Letters, 2021, 6(3): 4552−4559 doi: 10.1109/LRA.2021.3068952
[77]	Zhang R L, Zong Q, Zhang X Y, Dou L Q, Tian B L. Game of drones: Multi-UAV pursuit-evasion game with online motion planning by deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 2023, 34(10): 7900−7909 doi: 10.1109/TNNLS.2022.3146976
[78]	Liang X, Zhou B R, Jiang L P, Meng G L, Xiu Y. Collaborative pursuit-evasion game of multi-UAVs based on Apollonius circle in the environment with obstacle. Connection Science, 2023, 35(1): Article No. 2168253 doi: 10.1080/09540091.2023.2168253
[79]	Garcia E, Casbeer D W, Pachter M. Optimal strategies of the differential game in a circular region. IEEE Control Systems Letters, 2020, 4(2): 492−497 doi: 10.1109/LCSYS.2019.2963173
[80]	Casini M, Garulli A. A novel family of pursuit strategies for the lion and man problem. In: Proceedings of the 56th IEEE Annual Conference on Decision and Control (CDC). Melbourne, Australia: IEEE, 2017. 6436−6441
[81]	Yan R, Mi S, Duan X M, Chen J T, Ji X Y. Pursuit winning strategies for Reach-Avoid games with polygonal obstacles. IEEE Transactions on Automatic Control, DOI: 10.1109/TAC.2024.3438806
[82]	Flynn J O. Lion and man: The boundary constraint. SIAM Journal on Control, 1973, 11(3): 397−411 doi: 10.1137/0311032
[83]	Yan R, Shi Z Y, Zhong Y S. Defense game in a circular region. In: Proceedings of the 56th IEEE Annual Conference on Decision and Control (CDC). Melbourne, Australia: IEEE, 2017. 5590−5595
[84]	Ruiz U, Isler V. Capturing an omnidirectional evader in convex environments using a differential drive robot. IEEE Robotics and Automation Letters, 2016, 1(2): 1007−1013 doi: 10.1109/LRA.2016.2530854
[85]	Okabe A, Boots B, Sugihara K. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. New York: John Wiley, 1992.
[86]	Pierson A, Wang Z J, Schwager M. Intercepting rogue robots: An algorithm for capturing multiple evaders with multiple pursuers. IEEE Robotics and Automation Letters, 2017, 2(2): 530−537 doi: 10.1109/LRA.2016.2645516
[87]	Li S, Wang C, Xie G M. Pursuit-evasion differential games of players with different speeds in spaces of different dimensions. In: Proceedings of the American Control Conference (ACC). Atlanta, USA: IEEE, 2022. 1299−1304
[88]	Zhang R Q, Li S, Wang C, Xie G M. Optimal strategies for the game with two faster 3D pursuers and one slower 2D evader. In: Proceedings of the 41st Chinese Control Conference (CCC). Hefei, China: IEEE, 2022. 1767−1772
[89]	Zhi J X, Hao Y, Vo C, Morales M, Lien J M. Computing 3-D from-region visibility using visibility integrity. IEEE Robotics and Automation Letters, 2019, 4(4): 4286−4291 doi: 10.1109/LRA.2019.2931280
[90]	Chen N, Li L J, Mao W J. Equilibrium strategy of the pursuit-evasion game in three-dimensional space. IEEE/CAA Journal of Automatica Sinica, 2024, 11(2): 446−458 doi: 10.1109/JAS.2023.123996
[91]	Shen H X, Casalino L. Revisit of the three-dimensional orbital pursuit-evasion game. Journal of Guidance, Control, and Dynamics, 2018, 41(8): 1823−1831 doi: 10.2514/1.G003127
[92]	Yan R, Duan X M, Shi Z Y, Zhong Y S, Bullo F. Matching-based capture strategies for 3D heterogeneous multiplayer reach-avoid differential games. Automatica, 2022, 140: Article No. 110207 doi: 10.1016/j.automatica.2022.110207
[93]	Lewin J, Breakwell J V. The surveillance-evasion game of degree. Journal of Optimization Theory and Applications, 1975, 16(3): 339−353
[94]	Greenfeld I. A differential game of surveillance evasion of two identical cars. Journal of Optimization Theory and Applications, 1987, 52(1): 53−79 doi: 10.1007/BF00938464
[95]	Bopardikar S D, Bullo F, Hespanha J P. Sensing limitations in the lion and man problem. In: Proceedings of the American Control Conference (ACC). New York, USA: IEEE, 2007. 5958−5963
[96]	Lopez V G, Lewis F L, Wan Y, Sanchez E N, Fan L L. Solutions for multiagent pursuit-evasion games on communication graphs: Finite-time capture and asymptotic behaviors. IEEE Transactions on Automatic Control, 2020, 65(5): 1911−1923 doi: 10.1109/TAC.2019.2926554
[97]	Zemskov K A, Pashkow A G. Construction of optimal position strategies in a differential pursuit-evasion game with one pursuer and two evaders. Journal of Applied Mathematics and Mechanics, 1997, 61(3): 391−399 doi: 10.1016/S0021-8928(97)00050-6
[98]	Liu S Y, Zhou Z Y, Tomlin C, Hedrick J K. Evasion of a team of dubins vehicles from a hidden pursuer. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). Hong Kong, China: IEEE, 2014. 6771−6776
[99]	von Moll A, Garcia E, Casbeer D, Suresh M, Swar S C. Multiple-pursuer, single-evader border defense differential game. Journal of Aerospace Information Systems, 2020, 17(8): 407−416 doi: 10.2514/1.I010740
[100]	Kartal Y, Subbarao K, Dogan A, Lewis F. Optimal game theoretic solution of the pursuit-evasion intercept problem using on-policy reinforcement learning. International Journal of Robust and Nonlinear Control, 2021, 31(16): 7886−7903 doi: 10.1002/rnc.5719
[101]	Littlewood J E. A Mathematician's Miscellany. Cambridge: Cambridge University Press, 1953.
[102]	Kohlenbach U, López-Acedo G, Nicolae A. A uniform betweenness property in metric spaces and its role in the quantitative analysis of the “Lion-Man” game. Pacific Journal of Mathematics, 2021, 310(1): 181−212 doi: 10.2140/pjm.2021.310.181
[103]	Sgall J. Solution of David Gale's lion and man problem. Theoretical Computer Science, 2001, 259(1−2): 663−670 doi: 10.1016/S0304-3975(00)00411-4
[104]	Casini M, Garulli A. An improved lion strategy for the lion and man problem. IEEE Control Systems Letters, 2017, 1(1): 38−43 doi: 10.1109/LCSYS.2017.2702652
[105]	Casini M, Garulli A. A new class of pursuer strategies for the discrete-time lion and man problem. Automatica, 2019, 100: 162−170 doi: 10.1016/j.automatica.2018.11.015
[106]	Casini M, Criscuoli M, Garulli A. A discrete-time pursuit-evasion game in convex polygonal environments. Systems & Control Letters, 2019, 125: 22−28
[107]	Bopardikar S D, Bullo F, Hespanha J P. Cooperative pursuit with sensing limitations. In: Proceedings of the American Control Conference (ACC). New York, USA: IEEE, 2007. 5394−5399
[108]	Li D X, Cruz J B. Graph-based strategies for multi-player pursuit evasion games. In: Proceedings of the 46th IEEE Conference on Decision and Control. New Orleans, USA: IEEE, 2007. 4063−4068
[109]	Chen H, Kalyanam K, Zhang W, Casbeer D. Intruder isolation on a general road network under partial information. IEEE Transactions on Control Systems Technology, 2017, 25(1): 222−234 doi: 10.1109/TCST.2016.2550423
[110]	Kalyanam K, Casbeer D, Pachter M. Graph search of a moving ground target by a UAV aided by ground sensors with local information. Autonomous Robots, 2020, 44(5): 831−843 doi: 10.1007/s10514-019-09900-0
[111]	Sundaram S, Kalyanam K, Casbeer D W. Pursuit on a graph under partial information from sensors. In: Proceedings of the American Control Conference (ACC). Seattle, USA: IEEE, 2017. 4279−4284
[112]	Dong X, Zhang H G, Ming Z Y. Adaptive optimal control via Q-learning for multi-agent pursuit-evasion games. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2024, 71(6): 3056−3060 doi: 10.1109/TCSII.2024.3354120
[113]	Sugihara K, Suzuki I. Optimal algorithms for a pursuit-evasion problem in grids. SIAM Journal on Discrete Mathematics, 1989, 2(1): 126−143 doi: 10.1137/0402013
[114]	Dawes R W. Some pursuit-evasion problems on grids. Information Processing Letters, 1992, 43(5): 241−247 doi: 10.1016/0020-0190(92)90218-K
[115]	Bhattacharya S, Banerjee A, Bandyopadhyay S. CORBA-based analysis of multi agent behavior. Journal of Computer Science and Technology, 2005, 20(1): 118−124 doi: 10.1007/s11390-005-0013-5
[116]	Bhattacharya S, Paul G, Sanyal S. A cops and robber game in multidimensional grids. Discrete Applied Mathematics, 2010, 158(16): 1745−1751 doi: 10.1016/j.dam.2010.06.014
[117]	Das S, Gahlawat H. Variations of cops and robbers game on grids. Discrete Applied Mathematics, 2021, 305: 340−349 doi: 10.1016/j.dam.2020.02.004
[118]	Lewin J, Olsder G J. The isotropic rocket——A surveillance evasion game. Computers & Mathematics With Applications, 1989, 18(1−3): 15−34
[119]	Altaher M, Elmougy S, Nomir O. Intercepting a superior missile: A reachability analysis of an Apollonius circle-based multiplayer differential game. International Journal of Innovative Computing, Information and Control, 2019, 15(1): 369−381
[120]	Jang J S, Tomlin C. Control strategies in multi-player pursuit and evasion game. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit. San Francisco, USA: AIAA, 2005. Article No. 6239
[121]	Osborne M J, Rubinstein A. A Course in Game Theory. Cambridge: MIT Press, 1994.
[122]	Başar T, Olsder G J. Dynamic Noncooperative Game Theory (Second edition). New York: Academic Press Inc., 1998.
[123]	Krasovskii N N, Subbotin A I, Kotz S. Game-theoretical Control Problems. New York: Springer, 1988.
[124]	Mizukami K, Eguchi K. A geometrical approach to problems of pursuit-evasion games. Journal of the Franklin Institute, 1977, 303(4): 371−384 doi: 10.1016/0016-0032(77)90118-1
[125]	Samatov B T, Soyibboev U B. Differential game with a lifeline for the inertial movements of players. Ural Mathematical Journal, 2021, 7(2): 94−109 doi: 10.15826/umj.2021.2.007
[126]	Petrov N N. “Soft” capture in pontryagin's example with many participants. Journal of Applied Mathematics and Mechanics, 2003, 67(5): 671−680 doi: 10.1016/S0021-8928(03)90040-2
[127]	Blagodatskikh A I. On group pursuit problem in Pontryagin's nonstationary example. Vestn. Udmurt. Gos. Univ. Ser. Mat, 2007, 1: 17−24
[128]	Petrov N N, Solov'eva N A. Multiple capture in Pontryagin's recurrent example. Automation and Remote Control, 2016, 77(5): 855−861 doi: 10.1134/S0005117916050088
[129]	Lewin J. Differential Games: Theory and Methods for Solving Game Problems With Singular Surfaces. London: Springer, 2012.
[130]	Wise K A, Sedwick J L. Successive approximation solution of the HJI equation. In: Proceedings of the 33rd IEEE Conference on Decision and Control. Lake Buena Vista, USA: IEEE, 1994. 1387−1391
[131]	Yang X, Liu D R, Ma H W, Xu Y C. Online approximate solution of HJI equation for unknown constrained-input nonlinear continuous-time systems. Information Sciences, 2016, 328: 435−454 doi: 10.1016/j.ins.2015.09.001
[132]	Earl M G, D'Andrea R. Modeling and control of a multi-agent system using mixed integer linear programming. In: Proceedings of the 41st IEEE Conference on Decision and Control. Las Vegas, USA: IEEE, 2002. 107−111
[133]	Ni Y J, Gao S H, Huang S N, Xiang C, Ren Q Y, Lee T H. Multi-agent cooperative pursuit-evasion control using gene expression programming. In: Proceedings of the 47th Annual Conference of the IEEE Industrial Electronics Society. Toronto, Canada: IEEE, 2021. 1−6
[134]	Asgharnia A, Schwartz H M, Atia M. Multi-invader multi-defender differential game using reinforcement learning. In: Proceedings of the IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). Padua, Italy: IEEE, 2022. 1−8
[135]	Kachroo P, Shedied S A, Bay J S, Vanlandingham H. Dynamic programming solution for a class of pursuit evasion problems: The herding problem. IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2001, 31(1): 35−41 doi: 10.1109/5326.923266
[136]	Hespanha J P, Pappas G J, Prandini M. Greedy control for hybrid pursuit-evasion games. In: Proceedings of the European Control Conference (ECC). Los Angeles, USA: 2001. 2621−2626 Hespanha J P, Pappas G J, Prandini M. Greedy control for hybrid pursuit-evasion games. In: Proceedings of the European Control Conference (ECC). Los Angeles, USA: 2001. 2621−2626
[137]	Cristiani E, Falcone M. Fully-discrete schemes for the value function of pursuit-evasion games with state constraints. Advances in Dynamic Games and Their Applications: Analytical and Numerical Developments. Boston: Birkhäuser, 2009. 1−30
[138]	Anderson G. Feedback control for pursuit-evasion problems between two spacecraftbased on differential dynamic programming. In: Proceedings of the 15th Aerospace Sciences Meeting. Los Angeles, USA: AIAA, 1977. Article No. 34
[139]	Alexopoulos A, Schmidt T, Badreddin E. A pursuit-evasion game between unmanned aerial vehicles. In: Proceedings of the 11th International Conference on Informatics in Control, Automation and Robotics (ICINCO). Vienna, Austria: IEEE, 2014. 74−81
[140]	Xing J B, Zeng X L. A deep reinforcement learning method for lion and man problem. In: Proceedings of the 40th Chinese Control Conference (CCC). Shanghai, China: IEEE, 2021. 8366−8371
[141]	Qu X Q, Gan W H, Song D L, Zhou L Q. Pursuit-evasion game strategy of USV based on deep reinforcement learning in complex multi-obstacle environment. Ocean Engineering, 2023, 273: Article No. 114016 doi: 10.1016/j.oceaneng.2023.114016
[142]	Wan K F, Wu D W, Zhai Y W, Li B, Gao X G, Hu Z J. An improved approach towards multi-agent pursuit-evasion game decision-making using deep reinforcement learning. Entropy, 2021, 23(11): Article No. 1433 doi: 10.3390/e23111433
[143]	Li B, Wang J M, Song C, Yang Z P, Wan K F, Zhang Q F. Multi-UAV roundup strategy method based on deep reinforcement learning CEL-MADDPG algorithm. Expert Systems With Applications, 2024, 245: Article No. 123018 doi: 10.1016/j.eswa.2023.123018
[144]	Li X L, Li Z, Zheng X L, Yang X B, Yu X H. The study of crash-tolerant, multi-agent offensive and defensive games using deep reinforcement learning. Electronics, 2023, 12(2): Article No. 327 doi: 10.3390/electronics12020327
[145]	Kokolakis N M T, Kanellopoulos A, Vamvoudakis K G. Bounded rational unmanned aerial vehicle coordination for adversarial target tracking. In: Proceedings of the American Control Conference (ACC). Denver, USA: IEEE, 2020. 2508−2513
[146]	Xiong H, Zhang Y. Reinforcement learning-based formation-surrounding control for multiple quadrotor UAVs pursuit-evasion games. ISA Transactions, 2024, 145: 205−224 doi: 10.1016/j.isatra.2023.12.006
[147]	Zhou Z J, Xu H. Decentralized optimal large scale multi-player pursuit-evasion strategies: A mean field game approach with reinforcement learning. Neurocomputing, 2022, 484: 46−58 doi: 10.1016/j.neucom.2021.01.141
[148]	Vrabie D. Online Adaptive Optimal Control for Continuous-time Systems [Ph.D. dissertation], The University of Texas at Arlington, USA, 2010.
[149]	Gong Z F, He B, Liu G, Zhang X B. Solution for pursuit-evasion game of agents by adaptive dynamic programming. Electronics, 2023, 12(12): Article No. 2595 doi: 10.3390/electronics12122595
[150]	Gong Z F, He B, Hu C, Zhang X B, Kang W J. Online adaptive dynamic programming-based solution of networked multiple-pursuer and single-evader game. Electronics, 2022, 11(21): Article No. 3583 doi: 10.3390/electronics11213583
[151]	Sun J L, Liu C S. Finite-horizon differential games for missile-target interception system using adaptive dynamic programming with input constraints. International Journal of Systems Science, 2018, 49(2): 264−283 doi: 10.1080/00207721.2017.1401153
[152]	Zhang Z X, Zhang K, Xie X P, Sun J Y. Fixed-time zero-sum pursuit-evasion game control of multisatellite via adaptive dynamic programming. IEEE Transactions on Aerospace and Electronic Systems, 2024, 60(2): 2224−2235 doi: 10.1109/TAES.2024.3351810
[153]	Vamvoudakis K G, Lewis F L, Hudas G R. Multi-agent differential graphical games: Online adaptive learning solution for synchronization with optimality. Automatica, 2012, 48(8): 1598−1611 doi: 10.1016/j.automatica.2012.05.074
[154]	Peng C, Liu X M, Ma J J. Design of safe optimal guidance with obstacle avoidance using control barrier function-based actor-critic reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2023, 53(11): 6861−6873 doi: 10.1109/TSMC.2023.3288826
[155]	Oyler D W, Kabamba P T, Girard A R. Dominance in pursuit-evasion games with uncertainty. In: Proceedings of the 54th IEEE Conference on Decision and Control (CDC). Osaka, Japan: IEEE, 2015. 5859−5864
[156]	Agasti A, Reddy P V, Bhikkaji B. Optimal role assignment for multiplayer reach-avoid differential games in 3D space. arXiv preprint arXiv: 2303.07885, 2023.
[157]	Meier L. A new technique for solving pursuit-evasion differential games. IEEE Transactions on Automatic Control, 1969, 14(4): 352−359 doi: 10.1109/TAC.1969.1099226
[158]	Getz W M, Pachter M. Capturability in a two-target “game of two cars”. Journal of Guidance and Control, 1981, 4(1): 15−21 doi: 10.2514/3.19715
[159]	Scott W, Leonard N E. Dynamics of pursuit and evasion in a heterogeneous herd. In: Proceedings of the 53rd IEEE Conference on Decision and Control (CDC). Los Angeles, USA: IEEE, 2014. 2920−2925
[160]	Garcia E, Fuchs Z E, Milutinovic D, Casbeer D W, Pachter M. A geometric approach for the cooperative two-pursuer one-evader differential game. IFAC-PapersOnLine, 2017, 50(1): 15209−15214 doi: 10.1016/j.ifacol.2017.08.2366
[161]	Zhou Z Y, Zhang W, Ding J, Huang H M, Stipanović D M, Tomlin C J. Cooperative pursuit with Voronoi partitions. Automatica, 2016, 72: 64−72 doi: 10.1016/j.automatica.2016.05.007
[162]	Zhou S B, Li H P, Chen Z Y. Optimal containment strategies on high-speed evader using multiple pursuers with point-capture. In: Proceedings of the 42nd Chinese Control Conference (CCC). Tianjin, China: IEEE, 2023. 1−6
[163]	Zhang Z, Zhang D Y, Zhang Q R, Pan W, Hu T J. DACOOP-A: Decentralized adaptive cooperative pursuit via attention. IEEE Robotics and Automation Letters, 2024, 9(6): 5504−5511 doi: 10.1109/LRA.2023.3331886
[164]	Sun Z Y, Sun H B, Li P, Zou J. Cooperative strategy for pursuit-evasion problem with collision avoidance. Ocean Engineering, 2022, 266: Article No. 112742 doi: 10.1016/j.oceaneng.2022.112742
[165]	Isler V, Sun D F, Sastry S. Roadmap based pursuit-evasion and collision avoidance. Robotics: Science and Systems. Cambridge: MIT Press, 2005. 257−264
[166]	Selvakumar J, Bakolas E. Feedback strategies for a reach-avoid game with a single evader and multiple pursuers. IEEE Transactions on Cybernetics, 2021, 51(2): 696−707 doi: 10.1109/TCYB.2019.2914869
[167]	Shishika D, Paulos J, Kumar V. Cooperative team strategies for multi-player perimeter-defense games. IEEE Robotics and Automation Letters, 2020, 5(2): 2738−2745 doi: 10.1109/LRA.2020.2972818
[168]	Garcia E, Casbeer D W, Pachter M. Active target defense using first order missile models. Automatica, 2017, 78: 139−143 doi: 10.1016/j.automatica.2016.12.032
[169]	Bera R, Makkapati V R, Kothari M. A comprehensive differential game theoretic solution to a game of two cars. Journal of Optimization Theory and Applications, 2017, 174(3): 818−836 doi: 10.1007/s10957-017-1134-z