Similar articles

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.