Abstract: For complex functions to emerge in artificial systems, it is important to understand the intrinsic mechanisms of biological swarm behaviors in nature. In this paper, we present a comprehensive survey of pursuit–evasion, which is a critical problem in biological groups. First, we review the problem of pursuit–evasion from three different perspectives: game theory, control theory and artificial intelligence, and bio-inspired perspectives. Then we provide an overview of the research on pursuit–evasion problems in biological systems and artificial systems. We summarize predator pursuit behavior and prey evasion behavior as predator–prey behavior. Next, we analyze the application of pursuit–evasion in artificial systems from three perspectives, i.e., strong pursuer group vs. weak evader group, weak pursuer group vs. strong evader group, and equal-ability group. Finally, relevant prospects for future pursuit–evasion challenges are discussed. This survey provides new insights into the design of multi-agent and multi-robot systems to complete complex hunting tasks in uncertain dynamic scenarios.

群体智能中的追逃围捕问题综述

[1]Analikwu CV, Schwartz HM, 2017. Multi-agent learning in the game of guarding a territory. Int J Innov Comput Inform Contr, 13(6):1855-1872.

[2]Angelani L, 2012. Collective predation and escape strategies. Phys Rev Lett, 109(11):118104.

[3]Barawkar S, Kumar M, 2021. Ant-inspired strategies for multi-robot collaborative transportation—an Ockham’s razor. IFAC-PapersOnLine, 54(20):789-794.

[4]Battistini S, 2020. A stochastic characterization of the capture zone in pursuit-evasion games. Games, 11(4):54.

[5]Beaver LE, Malikopoulos AA, 2021. An overview on optimal flocking. Ann Rev Contr, 51:88-99.

[6]Bedoya-Pérez MA, Le A, McGregor IS, et al., 2021. Anti-predator responses toward cat fur in wild brown rats tested in a semi-natural environment. Behav Ecol, 32(5):835-844.

[7]Benda M, Jagannathan V, Dodhiawala R, 1986. On Optimal Cooperation of Knowledge Sources: an Empirical Investigation. Technical Report BCS-G2010-28, Boeing Advanced Technology Center, Washington, USA.

[8]Blanchard BS, Fabrycky WJ, Fabrycky WJ, 1990. Systems Engineering and Analysis. Prentice Hall Upper Saddle River, USA.

[9]Bravo L, Ruiz U, Murrieta-Cid R, 2020. A pursuit–evasion game between two identical differential drive robots. J Frankl Inst, 357(10):5773-5808.

[10]Bumann D, Krause J, Rubenstein D, 1997. Mortality risk of spatial positions in animal groups: the danger of being in the front. Behaviour, 134(13-14):1063-1076.

[11]Chakraborty D, Bhunia S, De RM, 2020. Survival chances of a prey swarm: how the cooperative interaction range affects the outcome. Sci Rep, 10(1):8362.

[12]Chen J, Zha WZ, Peng ZH, et al., 2016. Multi-player pursuit–evasion games with one superior evader. Automatica, 71:24-32.

[13]Chiu C, Reddy PV, Xian W, et al., 2010. Effects of competitive prey capture on flight behavior and sonar beam pattern in paired big brown bats, Eptesicus fuscus. J Exp Biol, 213(19):3348-3356.

[14]Cichos F, Gustavsson K, Mehlig B, et al., 2020. Machine learning for active matter. Nat Mach Intell, 2(2):94-103.

[15]Civitello DJ, Cohen J, Fatima H, et al., 2015. Biodiversity inhibits parasites: broad evidence for the dilution effect. Proc Nat Acad Sci USA, 112(28):8667-8671.

[16]Couzin ID, Krause J, James R, et al., 2002. Collective memory and spatial sorting in animal groups. J Theor Biol, 218(1):1-11.

[17]Couzin ID, Krause J, Franks NR, et al., 2005. Effective leadership and decision-making in animal groups on the move. Nature, 433(7025):513-516.

[18]Dai H, Lu W, Li X, et al. 2022. Cooperative planning of multi-agent systems based on task-oriented knowledge fusion with graph neural networks. Front Inform Technol Electron Eng, 23(7):1069-1076.

[19]Deng W, Xu JJ, Song YJ, et al., 2020. An effective improved co-evolution ant colony optimisation algorithm with multi-strategies and its application. Int J Bio-Inspired Comput, 16(3):158-170.

[20]de Souza C, Newbury R, Cosgun A, et al., 2021. Decentralized multi-agent pursuit using deep reinforcement learning. IEEE Robot Autom Lett, 6(3):4552-4559.

[21]Dong J, Zhang X, Jia XM, 2012. Strategies of pursuit-evasion game based on improved potential field and differential game theory for mobile robots. Proc 2^nd Int Conf on Instrumentation, Measurement, Computer, Communication and Control, p.1452-1456.

[22]Dong Q, Wu ZY, Lu J, et al., 2022. Existence and practice of gaming: thoughts on the development of multi-agent system gaming. Front Inform Technol Electron Eng, 23(7):995-1001.

[23]Duffield C, Ioannou CC, 2017. Marginal predation: do encounter or confusion effects explain the targeting of prey group edges? Behav Ecol, 28(5):1283-1292.

[24]Durgut R, 2021. Improved binary artificial bee colony algorithm. Front Inform Technol Electron Eng, 22(8):1080-1091.

[25]Dutta K, 2014. Hunting in groups. Resonance, 19(10):936-957.

[26]Emmons M, Maciejewski AA, Chong EKP, 2018. Modelling emergent swarm behavior using continuum limits for environmental mapping. Proc IEEE 14^th Int Conf on Control and Automation, p.86-93.

[27]Emmons M, Maciejewski AA, Anderson C, et al., 2020. Classifying environmental features from local observations of emergent swarm behavior. IEEE/CAA J Autom Sin, 7(3):674-682.

[28]Estes RD, 2012. The Behavior Guide to African Mammals: Including Hoofed Mammals, Carnivores, Primates. University of California Press, Berkeley, USA.

[29]Fang X, Wang C, Xie LH, et al., 2022. Cooperative pursuit with multi-pursuer and one faster free-moving evader. IEEE Trans Cybern, 52(3):1405-1414.

[30]Fregene K, Kennedy D, Wang D, 2003. Multi-vehicle pursuit–evasion: an agent-based framework. Proc IEEE Int Conf on Robotics and Automation, p.2707-2713.

[31]Gao KZ, Cao ZG, Zhang L, et al., 2019. A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems. IEEE/CAA J Autom Sin, 6(4):904-916.

[32]Garcia E, 2021. Cooperative target protection from a superior attacker. Automatica, 131:109696.

[33]Garcia E, Fuchs ZE, Milutinovic D, et al., 2017. A geometric approach for the cooperative two-pursuer one-evader differential game. IFAC-PapersOnLine, 50(1):15209-15214.

[34]Garcia E, Casbeer DW, Fuchs ZE, et al., 2018. Cooperative missile guidance for active defense of air vehicles. IEEE Trans Aerosp Electron Syst, 54(2):706-721.

[35]Gazi V, Passino KM, 2003. Stability analysis of swarms. IEEE Trans Autom Contr, 48(4):692-697.

[36]Haque M, Rahmani A, Egerstedt M, 2010. Geometric foraging strategies in multi-agent systems based on biological models. Proc 49^th IEEE Conf on Decision and Control, p.6040-6045.

[37]Harras G, Tessone CJ, Sornette D, 2012. Noise-induced volatility of collective dynamics. Phys Rev E, 85(1):011150.

[38]Hayoun SY, Shima T, 2017. A two-on-one linear pursuit–evasion game with bounded controls. J Optim Theory Appl, 174(3):837-857.

[39]Heras FJH, Romero-Ferrero F, Hinz RC, et al., 2019. Deep attention networks reveal the rules of collective motion in zebrafish. PLoS Comput Biol, 15(9):e1007354.

[40]Hou ML, Ren J, Zhang D, et al., 2020. Network embedding: taxonomies, frameworks and applications. Comput Sci Rev, 38:100296.

[41]Hu RK, Tan N, Ni FL, 2021. A new scheme for cooperative hunting tasks with multiple targets in dynamic environments. Proc IEEE Int Conf on Robotics and Biomimetics, p.1816-1822.

[42]Huang LN, Zhu QY, 2022. A dynamic game framework for rational and persistent robot deception with an application to deceptive pursuit-evasion. IEEE Trans Autom Sci Eng, 19(4):2918-2932.

[43]Huang ZH, Chen YD, 2015. Log-linear model based behavior selection method for artificial fish swarm algorithm. Comput Intell Neurosci, 2015:685404.

[44]Hüttenrauch M, Šošić A, Neumann G, 2019. Deep reinforcement learning for swarm systems. J Mach Learn Res, 20(1):1966-1996.

[45]Ilany A, Eilam D, 2008. Wait before running for your life: defensive tactics of spiny mice (Acomys cahirinus) in evading barn owl (Tyto alba) attack. Behav Ecol Sociobiol, 62(6):923-933.

[46]Ioannou CC, Guttal V, Couzin ID, 2012. Predatory fish select for coordinated collective motion in virtual prey. Science, 337(6099):1212-1215.

[47]Isaacs R, 1999. Differential Games: a Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. Dover Publications, New York, USA.

[48]Ishii H, Wang Y, Feng S, 2022. An overview on multi-agent consensus under adversarial attacks. Ann Rev Contr, 53:252-272.

[49]Isler V, Kannan S, Khanna S, 2006. Randomized pursuit-evasion with local visibility. SIAM J Discr Math, 20(1):26-41.

[50]Jadbabaie A, Lin J, Morse AS, 2003. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans Autom Contr, 48(6):988-1001.

[51]Jain M, Saihjpal V, Singh N, et al., 2022. An overview of variants and advancements of PSO algorithm. Appl Sci, 12(17):8392.

[52]Janosov M, Virágh C, Vásárhelyi G, et al., 2017. Group chasing tactics: how to catch a faster prey. New J Phys, 19(5):053003.

[53]Jiang YX, Wu Q, Zhu SK, et al., 2022. Orca predation algorithm: a novel bio-inspired algorithm for global optimization problems. Expert Syst Appl, 188:116026.

[54]Kamimura A, Ohira T, 2010. Group chase and escape. New J Phys, 12(5):053013.

[55]Kamimura A, Ohira T, 2019. Group Chase and Escape: Fusion of Pursuits-Escapes and Collective Motions. Springer, Singapore.

[56]Kane SA, Fulton AH, Rosenthal LJ, 2015. When hawks attack: animal-borne video studies of goshawk pursuit and prey-evasion strategies. J Exp Biol, 218(2):212-222.

[57]Katsev M, Yershova A, Tovar B, et al., 2011. Mapping and pursuit-evasion strategies for a simple wall-following robot. IEEE Trans Robot, 27(1):113-128.

[58]Kawabayashi H, Chen YW, 2008. Interactive system of artificial fish school based on the extended boid model. Proc Int Conf on Intelligent Information Hiding and Multimedia Signal Processing, p.721-724.

[59]Kothari M, Manathara JG, Postlethwaite I, 2017. Cooperative multiple pursuers against a single evader. J Intell Robot Syst, 86(3-4):551-567.

[60]Krause J, 1993. The relationship between foraging and shoal position in a mixed shoal of roach (Rutilus rutilus) and chub (Leuciscus cephalus): a field study. Oecologia, 93(3):356-359.

[61]Li W, 2017. A dynamics perspective of pursuit-evasion: capturing and escaping when the pursuer runs faster than the agile evader. IEEE Trans Autom Contr, 62(1):451-457.

[62]Li ZY, Zhu H, Yang Z, et al., 2020. Saddle point of orbital pursuit-evasion game unde J₂-perturbed dynamics. J Guid Contr Dyn, 43(9):1733-1739.

[63]Li ZY, Zhu H, Luo YZ, 2021. An escape strategy in orbital pursuit-evasion games with incomplete information. Sci China Technol Sci, 64(3):559-570.

[64]Lin ZY, Broucke M, Francis B, 2004. Local control strategies for groups of mobile autonomous agents. IEEE Trans Autom Contr, 49(4):622-629.

[65]Liu Y, Li Z, Jiang Z, et al., 2022. Prospects for multi-agent collaboration and gaming: challenge, technology, and application. Front Inform Technol Electron Eng, 23(7):1002-1009.

[66]Ma Y, Tsao D, Shum HY, 2022. On the principles of Parsimony and Self-consistency for the emergence of intelligence. Front Inform Technol Electron Eng, 23(9):1298-1323.

[67]Makkapati VR, Sun W, Tsiotras P, 2018. Optimal evading strategies for two-pursuer/one-evader problems. J Guid Contr Dyn, 41(4):851-862.

[68]Merz AW, 1972. The game of two identical cars. J Optim Theory Appl, 9(5):324-343.

[69]Mirjalili S, Mirjalili SM, Lewis A, 2014. Grey wolf optimizer. Adv Eng Softw, 69:46-61.

[70]Muro C, Escobedo R, Spector L, et al., 2011. Wolf-pack (Canis lupus) hunting strategies emerge from simple rules in computational simulations. Behav Proc, 88(3):192-197.

[71]Nahin PJ, 2012. Chases and Escapes: the Mathematics of Pursuit and Evasion. Princeton University Press, Princeton, USA.

[72]Neshat M, Sepidnam G, Sargolzaei M, et al., 2014. Artificial fish swarm algorithm: a survey of the state-of-the-art, hybridization, combinatorial and indicative applications. Artif Intell Rev, 42(4):965-997.

[73]Nitschke G, 2005. Emergence of cooperation: state of the art. Artif Life, 11(3):367-396.

[74]Olfati-Saber R, 2006. Flocking for multi-agent dynamic systems: algorithms and theory. IEEE Trans Autom Contr, 51(3):401-420.

[75]Olfati-Saber R, Murray RM, 2004. Consensus problems in networks of agents with switching topology and time-delays. IEEE Trans Autom Contr, 49(9):1520-1533.

[76]Olfati-Saber R, Fax JA, Murray RM, 2007. Consensus and cooperation in networked multi-agent systems. Proc IEEE, 95(1):215-233.

[77]Parker LE, 1994. Heterogeneous Multi-robot Cooperation. AITR-1465, Massachusetts Institute of Technology, Cambridge, USA.

[78]Parrish JK, Viscido SV, Grünbaum D, 2002. Self-organized fish schools: an examination of emergent properties. Biol Bull, 202(3):296-305.

[79]Peterson AN, Soto AP, McHenry MJ, 2021. Pursuit and evasion strategies in the predator–prey interactions of fishes. Integr Comp Biol, 61(2):668-680.

[80]Pierson A, Wang ZJ, Schwager M, 2017. Intercepting rogue robots: an algorithm for capturing multiple evaders with multiple pursuers. IEEE Robot Autom Lett, 2(2):530-537.

[81]Pryor K, Norris KS, 1991. Dolphin Societies: Discoveries and Puzzles. University of California Press, Berkeley, USA.

[82]Qi JT, Bai L, Xiao YD, et al., 2020. Group chase and escape of biological groups based on a visual perception-decision-propulsion model. IEEE Access, 8:160490-160499.

[83]Ramana MV, Kothari M, 2017. Pursuit-evasion games of high speed evader. J Intell Robot Syst, 85(2):293-306.

[84]Ren W, Beard RW, 2005. Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Trans Autom Contr, 50(5):655-661.

[85]Ren W, Beard RW, Atkins EM, 2005. A survey of consensus problems in multi-agent coordination. Proc American Control Conf, p.1859-1864.

[86]Reynolds CW, 1987. Flocks, herds and schools: a distributed behavioral model. Proc 14^th Annual Conf on Computer Graphics and Interactive Techniques, p.25-34.

[87]Rosenberg L, Willcox G, 2020. Artificial swarm intelligence. In: Bi YX, Bhatia R, Kapoor S (Eds.), Intelligent Systems and Applications. Springer, Cham, p.1054-1070.

[88]Rubenstein M, Cornejo A, Nagpal R, 2014. Programmable self-assembly in a thousand-robot swarm. Science, 345(6198):795-799.

[89]Sainz-Borgo C, Kofler S, Jaffe K, 2018. On the adaptive characteristics of bird flocks: small birds form mixed flocks. Ornitol Neotrop, 29(1):289-296.

[90]Savkin AV, 2004. Coordinated collective motion of groups of autonomous mobile robots: analysis of Vicsek’s model. IEEE Trans Autom Contr, 49(6):981-982.

[91]Schwarting W, Pierson A, Karaman S, et al., 2021. Stochastic dynamic games in belief space. IEEE Trans Robot, 37(6):2157-2172.

[92]Selvakumar J, Bakolas E, 2022. Min–max Q-learning for multi-player pursuit-evasion games. Neurocomputing, 475:1-14.

[93]Shi Y, Hua Y, Yu J, et al., 2022. Multi-agent differential game based cooperative synchronization control using a data-driven method. Front Inform Technol Electron Eng, 23(7):1043-1056.

[94]Shifferman E, Eilam D, 2004. Movement and direction of movement of a simulated prey affect the success rate in barn owl Tyto alba attack. J Avian Biol, 35(2):111-116.

[95]Singh A, Sharma S, Singh J, 2021. Nature-inspired algorithms for wireless sensor networks: a comprehensive survey. Comput Sci Rev, 39:100342.

[96]Song Q, Cao JD, Yu WW, 2010. Second-order leader-following consensus of nonlinear multi-agent systems via pinning control. Syst Contr Lett, 59(9):553-562.

[97]Soto AP, McHenry MJ, 2020. Pursuit predation with intermittent locomotion in zebrafish. J Exp Biol, 223(24):jeb230623.

[98]Sturdivant RL, Chong EKP, 2018. The necessary and sufficient conditions for emergence in systems applied to symbol emergence in robots. IEEE Trans Cogn Dev Syst, 10(4):1035-1042.

[99]Su HS, Wang XF, Lin ZL, 2009. Flocking of multi-agents with a virtual leader. IEEE Trans Autom Contr, 54(2):293-307.

[100]Takahashi R, Takimoto M, Kambayashi Y, 2015. Cooperative transportation using pheromone agents. Proc 6^th Int Conf on Agents and Artificial Intelligence, p.46-62.

[101]Tang J, Liu G, Pan QT, 2021. A review on representative swarm intelligence algorithms for solving optimization problems: applications and trends. IEEE/CAA J Autom Sin, 8(10):1627-1643.

[102]Tian BM, Yang HX, Li W, et al., 2009. Optimal view angle in collective dynamics of self-propelled agents. Phys Rev E, 79(5):052102.

[103]Vamvoudakis KG, Fotiadis F, Kanellopoulos A, et al., 2022. Nonequilibrium dynamical games: a control systems perspective. Ann Rev Contr, 53:6-18.

[104]van Oudenhove L, Billoir E, Boulay R, et al., 2011. Temperature limits trail following behaviour through pheromone decay in ants. Naturwissenschaften, 98(12):1009-1017.

[105]Vechalapu TR, 2020. A trapping pursuit strategy for capturing a high speed evader. AIAA SciTech Forum, p.2069.

[106]Vicsek T, Zafeiris A, 2012. Collective motion. Phys Rep, 517(3-4):71-140.

[107]Vicsek T, Czirók A, Ben-Jacob E, et al., 1995. Novel type of phase transition in a system of self-driven particles. Phys Rev Lett, 75(6):1226-1229.

[108]Wan KF, Wu DW, Zhai YW, et al., 2021. An improved approach towards multi-agent pursuit–evasion game decision-making using deep reinforcement learning. Entropy, 23(11):1433.

[109]Wang CY, Shi WX, Liang L, 2022. Cooperative hunting strategy with a superior evader based on differential game. Complexity, 2022:2239182.

[110]Wang JN, Li GL, Liang L, et al., 2021. A pursuit-evasion problem of multiple pursuers from the biological-inspired perspective. Proc 40^th Chinese Control Conf, p.1596-1601.

[111]Wang YD, Dong L, Sun CY, 2020. Cooperative control for multi-player pursuit-evasion games with reinforcement learning. Neurocomputing, 412:101-114.

[112]Weintraub IE, Pachter M, Garcia E, 2020. An introduction to pursuit-evasion differential games. Proc American Control Conf, p.1049-1066.

[113]Yan FH, Jiang JC, Di K, et al., 2019. Multiagent pursuit-evasion problem with the pursuers moving at uncertain speeds. J Intell Robot Syst, 95(1):119-135.

[114]Yan R, Shi ZY, Zhong YS, 2019. Reach-avoid games with two defenders and one attacker: an analytical approach. IEEE Trans Cybern, 49(3):1035-1046.

[115]Yu X, Wu WJ, Feng P, et al., 2021. Swarm inverse reinforcement learning for biological systems. Proc IEEE Int Conf on Bioinformatics and Biomedicine, p.274-279.

[116]Yu ZJ, Tan JY, Li S, 2022. Simulation of collective pursuit-evasion behavior with runtime situational awareness. Comput Animat Virt World, 33(5):e2124.

[117]Zha WZ, Chen J, Peng ZH, et al., 2017. Construction of barrier in a fishing game with point capture. IEEE Trans Cybern, 47(6):1409-1422.

[118]Zhang LM, Prorok A, Bhattacharya S, 2021. Pursuer assignment and control strategies in multi-agent pursuit-evasion under uncertainties. Front Robot AI, 8:691637.

[119]Zhang S, Liu MY, Lei XK, et al., 2019a. Stay-eat or run-away: two alternative escape behaviors. Phys Lett A, 383(7):593-599.

[120]Zhang S, Liu MY, Lei XK, et al., 2019b. Group chase and escape with prey’s anti-attack behavior. Phys Lett A, 383(30):125871.

[121]Zhang XQ, Ming ZF, 2017. An optimized grey wolf optimizer based on a mutation operator and eliminating-reconstructing mechanism and its application. Front Inform Technol Electron Eng, 18(11):1705-1719.

[122]Zhang XQ, Zhang YY, Ming ZF, 2021. Improved dynamic grey wolf optimizer. Front Inform Technol Electron Eng, 22(6):877-890.

[123]Zhou ZJ, Xu H, 2020. Mean field game and decentralized intelligent adaptive pursuit evasion strategy for massive multi-agent system under uncertain environment. Proc American Control Conf, p.5382-5387.

[124]Zhou ZY, Liu JC, Yu JZ, 2022. A survey of underwater multi-robot systems. IEEE/CAA J Autom Sin, 9(1):1-18.

[125]Zhu YF, Tang XM, 2010. Overview of swarm intelligence. Proc Int Conf on Computer Application and System Modeling, p.V9-400-V9-403.

[126]Zlatev J, 2001. The epigenesis of meaning in human beings, and possibly in robots. Minds Mach, 11(2):155-195.