A survey of the pursuit–evasion problem in swarm intelligence?

Zhenxin MU ,Jie PAN ,Ziye ZHOU ,Junzhi YU ,Lu CAO

1State Key Laboratory for Turbulence and Complex Systems,Department of Advanced Manufacturing and Robotics,College of Engineering,Peking University,Beijing 100871,China

2National Innovation Institute of Defense Technology,Beijing 100071,China

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.

Key words: Swarm behavior;Pursuit—evasion;Artificial systems;Biological model;Collective motion

1 Introduction

In recent years,swarm intelligence has advanced significantly as artificial intelligence technology has developed (Gao et al.,2019;Cichos et al.,2020;Rosenberg and Willcox,2020;Beaver and Malikopoulos,2021).One of the primary research directions is based on bio-inspired research,in which biological swarm behavior models are used to reproduce complex behavior observed in groups.The phenomenon,in which individual entities with simple behaviors and intelligence interact to form a swarm,more complex group functions emerge,and more difficult tasks are accomplished,is called “emergence”(Blanchard et al.,1990;Zhou ZY et al.,2022).The complex behaviors that emerge from biological groups have provided valuable decision support for research in the fields of multi-agent system (MAS)and multi-robot system(MRS).Therefore,the study of biological swarm behavior is critical in solving collaboration problem in MAS or MRS.

Swarm intelligence has evolved from the study of biological swarm behavior to the distributed intelligence applied to MAS and MRS,in which the notions of emergence,self-organization,and cooperation are often mentioned.Through simple information interaction,biological groups in nature emerge with their simple behavior,which includes self-organized,cooperative,and adaptive behaviors of the environment.Biological swarm behavior includes mainly the flocking behavior of birds (Sainz-Borgo et al.,2018),the aggregation and dispersion of fish (Neshat et al.,2014),ant colony foraging (van Oudenhove et al.,2011;Durgut,2021),and cooperative transportation(Harras et al.,2012;Takahashi et al.,2015;Barawkar and Kumar,2021).To reproduce these satisfactory behaviors in the artificial system,especially the cooperative behavior in the pursuit—evasion problem in the biological system,a deep understanding of the internal mechanism of these biological group behaviors is important.

The pursuit—evasion problem originated from collective behavior research(Wang JN et al.,2021).Benda et al.(1986) conducted the research on the pursuit—evasion problem,and studied how multiple agents can surround and capture prey in a short time in a two-dimensional lattice network.This is the early origin of the pursuit—evasion problem.Isaacs (1999) proposed the differential game when the mathematical problems in dynamic systems are studied,which extended game theory to the research of pursuit—evasion problems.The goal of pursuit—evasion problems is to model and solve the confrontation between pursuers and evaders,which focuses on the strategies of two groups:pursuers who try to capture evaders and evaders who try to escape from the pursuers.The pursuit—evasion problem as a general framework is widely applied in different scenarios,such as confrontation in the military field,surveillance,and analysis of biological behaviors (Weintraub et al.,2020).

Specifically,in MAS and MRS,the pursuit—evasion problem can be extended and applied to game-theoretic confrontation among multiple agents,which includes both cooperative and antagonistic characteristics.In the future,agents and robots will develop intelligence,and will use the swarm system to make autonomous decisions and autonomously perform tasks.In practice,in the military confrontation field,satellites or drones need to autonomously formulate evasion routes and strategies when facing pursuit by enemy targets.When performing security work,robots need to autonomously pursue and track dangerous criminal targets.These are all pursuit—evasion problems that need to be addressed in real-life scenarios.

The need to address such real-life scenarios makes the pursuit—evasion problem an important research topic.Moreover,the pursuit—evasion problem involves complex interactions such as game theory,cooperation,and confrontation among agents.It deepens our understanding of swarm intelligence systems and provides some new theoretical methods and techniques,which have made important contributions to promoting the development and innovation of future artificial intelligence and swarm intelligence systems.

In researching biological swarm behavior,there are two main guidelines:

1.Biological swarm behavior in nature is an effective swarm model (Kawabayashi and Chen,2008;Zhu and Tang,2010).The designed agent can interact with the environment biologically and perceive similar environmental information to which the biological swarm is sensitive(Zlatev,2001).

2.The design of multi-agent behavior must be convenient to check,evaluate,and improve.Researchers develop swarm models inspired by biological swarm behavior to reveal the mechanisms and principles of emergent behavior.They study biological swarm behavior by hypothesizing that some mechanisms lead to some behaviors and verify those hypotheses through artificial implementation(Nitschke,2005).

The biological swarm behavior model is explained primarily from the perspective of statistical physics.This is based on the observation of biological swarm behaviors in nature.Researchers found that their collective motions are more consistent with the relevant motion models in statistical mechanics or statistical physics,which can be expressed by some specific rule description.Therefore,they regarded the individuals in the group as small molecules and proposed relevant notions and models from the fields of statistical mechanics and statistical physics to precisely define the motion relationship between molecules(Vicsek and Zafeiris,2012).

In addition,the pursuit—evasion behavior between predator and prey reflects the biological group’s intrinsic emergent properties and the external collaborative strategy’s application effects.Swarm intelligence includes studying basic motion models,emergence mechanisms,behavioral cooperation strategies,and so on,among which the pursuit—evasion problem is a specific collective behavior in biological swarm intelligence.As illustrated in Fig.1,self-organization behavior and emergent properties are used to study the biological intelligence behind swarm intelligence,based mainly on the internal mechanisms for studying the motion model and specific mechanism of emergence of the group.Meanwhile,the research on pursuit—evasion behavior focuses mainly on cooperation strategies,which are essentially an external strategy design and application to complete a specific task in a particular scenario.For the design of artificial systems,the pursuit and evasion strategies used by biological groups have significant inspiration.However,there is no review of the pursuit—evasion problem in swarm intelligence.

Fig.1 The taxonomy based on the swarm intelligence research level

Therefore,we propose a novel taxonomy and comprehensive survey of swarm intelligence from the perspective of pursuit—evasion.Groups are divided into strong and weak groups based on individual’s abilities,including speed,maneuverability,and other attributes,although the relationship between pursuers and evaders includes strong vs.weak,weak vs.strong,and equal ability.We establish a link between the pursuit—evasion problem and collective motion.Also,comparison and discussion are presented in relation to the phenomenon of group chase in nature.Therefore,based on a novel taxonomy,a complete framework for the pursuit—evasion problem is illustrated in Fig.2.The motivation is to provide researchers with a new perspective on decision-making in pursuit—evasion.

Fig.2 Framework of the pursuit–evasion problem

2 Overview of the pursuit–evasion problem

Pursuit—evasion problems are divided mainly into three categories according to the solution strategies:game theory,control theory and artificial intelligence,and bio-inspired theory.With research into swarm intelligence,the bio-inspired strategy of swarm intelligence is gradually applied to the pursuit—evasion problem.The traditional strategies for the pursuit—evasion problem are introduced in this section,along with the realization of pursuit and evasion behavior in artificial systems from the perspective of biological inspiration.Additionally,with the advancement of artificial intelligence technology,new research questions and solutions to the pursuit—evasion problem are proposed.

2.1 Game theory

The pursuit—evasion problem is frequently modeled for game theory based methods as a differential game(Vamvoudakis et al.,2022),with strategies divided typically into two types:quantitative differential strategies and qualitative differential strategies.The differential game is essentially a combination of an optimal control problem and game theory,and because the goals of the pursuer and the evader are contradictory,the strategy design is typically treated as a zero-sum game for both parties.Thus,the saddle point of differential strategies in bilateral confrontation is the Nash equilibrium in a zero-sum game(i.e.,the point at which the strategy for both parties is optimal).

The quantitative differential strategy is the optimal strategy solved in the pursuit game problem with a specific performance index function,boundary conditions,and target set.In the pursuit—evasion problem,most of the quantitative measurements are chosen with respect to distance and time.However,the precise quantitative metrics are decided by the specific application scenario.

The state equation of the given system can be expressed as follows:

wherex(t) denotes the state of the system at timet,andu(t) andv(t) stand for the control strategies of the pursuers and evaders,respectively.Also,the performance index function with respect to particular scenarios is

In the pursuit—evasion problem,the pursuer uses strategyuto try to reduce the performance functionJ,while the evader uses strategyvto increaseJ,if the following inequality holds:

This pair of strategies(u,v)is a saddle point of performance index functionJand a Nash equilibrium strategy for the pursuit—evasion game.Next,dynamic programming or Pontryagin’s minimum principle in the optimal control theory is typically employed to solve the above optimal differential game.The corresponding equations are the Hamilton—Jacobi—Isaacs(HJI) equation (Weintraub et al.,2020) and the Hamilton function (Li ZY et al.,2020,2021),which are solved for the optimal strategies.

The qualitative differential strategy ignores performance index function and concentrates only on the game’s end result.The game’s strategy area is divided into two zones:the capture zone (where the pursuer can always catch the evader by employing the appropriate strategies) and the escape zone(where the evaders can always escape safely by applying the appropriate strategies).The barrier is a semipermeable surface that separates these two zones.Thus,the design of the barrier and the strategies used there will be critical factors in the game results.The capture zone is bounded by the points on the boundary of the target set.The usable part(UP)and the non-usable part(NUP)of the points on the target are separated by the boundary usable part(BUP).Therefore,the intersection of the barrier and the target set boundary is the BUP.

Many classical and attractive problems have been derived from the pursuit—evasion game,with these variations studied from various perspectives.Those variations of pursuit—evasion games have highlighted the insight of the optimal strategy solution and expanded their application scenarios,as shown in Table 1.

Table 1 Variations of the pursuit–evasion game

2.2 Multi-agent system control theory and artificial intelligence

The principles and techniques of the control theory and artificial intelligence approaches are important in solving the pursuit—evasion problem.They are used to design and analyze MAS and MRS.Control theory is a mathematical theory that designs and analyzes MAS,focusing mainly on distributed cooperative control theory,which uses appropriate control algorithms to make the behavior of the swarm system consistent or create specific formations.Artificial intelligence is the use of computers to simulate human thinking processes and intelligent behaviors,mainly by applying bionic algorithms or other machine learning algorithms in swarm systems.

Each method,control theory or artificial intelligence has its own strengths and limitations.Control theory can provide rigorous mathematical analysis and computation but requires more accurate information from dynamic models,which may result in difficulties in dealing with complex environments and uncertainties.Although artificial intelligence can use data-driven approaches to adapt to different scenarios,this requires large amounts of data and resources,and may lack interpretability and robustness (Ma et al.,2022).By combining the advantages of classical control theory and artificial intelligence,researchers have developed methods and techniques such as adaptive control,fuzzy control,artificial neural network control,expert systems,and genetic algorithms.These methods can better handle high-dimensional,nonlinear,and complex swarm systems,which fully consider the interaction,cooperation,and confrontation among the agents in the system(Dong Q et al.,2022).

There has been extensive research with numerous effective algorithms on the challenge of pursuit—evasion in MAS.In contrast to the study of the pursuit—evasion problem from the game theory perspective,which focuses mainly on the design at the strategy level,MAS research primarily focuses on the realization and optimization of control algorithms.

In fact,the progress of designing the optimal control algorithms in distributed cooperative MAS control employs individual local information rather than global information (Liu et al.,2022).The most common MAS application scenario for the pursuit—evasion problem is collective hunting,in which multiple robots collaborate to pursue one or more targets until the hunt is successful and the targets are surrounded in a specific formation.

Because the research on distributed cooperative control uses the local information of individuals,the design of pursuit strategies under the assumption of the local perception range is relatively critical.There is a link between the local information perceived by the individual and the success of the pursuit or evasion.For example,Isler et al.(2006)studied the relationship between the information available to the evader and the conditions of the capture,and then associated the information with its visibility.In this research,the local visibility of evaders was exploited in the pursuit strategy,and an algorithm was provided allowing two pursuers to successfully capture an evader with high probability using a randomized strategy.Katsev et al.(2011)studied types of global information that needs to be learned for simple wallfollowing robots to follow motions on walls,and tasks that can be completed with as little perception and actuation as possible.They also studied relevant strategies for the pursuit—evasion problem by using different sensors that acquire different types of environmental information.

Similarly,one of the methods for researching the pursuit—evasion problem is expanding the global perception range to increase the information obtained.Fregene et al.(2003) proposed the hybrid intelligent control agent (HICA) scheme,in which multiple agents were organized into air and ground teams.Specifically,the air team accurately located the target position through a radar,while the ground team implemented the task of hunting the target.The presence of the air team significantly expanded the perception range,and the ability to share global information was increased by real-time monitoring of teams in the air.Battistini (2020) proposed a method for characterizing the capture zone based on confidence in the estimation of the zero effort miss,which has good performance for the estimation of variables in the guidance formula,especially in scenarios where some sensors are limited.However,it considered only a simplified scenario with a small line-of-sight angle and small flight path angles.

For collective hunting,the collaboration strategies of agents have a crucial impact on the final outcome,and various issues have been covered,including path planning,search strategies,obstacle avoidance,and collision avoidance.Schwarting et al.(2021) proposed a method that combines gametheoretical planning with belief space planning to generate linear feedback policies and predictive feedback policies for robots under perceptual and motion uncertainty.Dong J et al.(2012) proposed a hybrid algorithm based on an improved dynamic artificial potential field and differential game for mobile robots,which can plan the pursuit path and avoid obstacles.For the pursuit—evasion problem of heterogeneous teams,Zhang LM et al.(2021)developed a redundant allocation algorithm to distribute pursuers and minimize the capture time.In addition,with the increase of individuals in the group,the burden of communication between individuals was increased.Therefore,energy-efficient and secure communication within the group is essential for the consistency and robustness of swarm behavior.

The development of artificial intelligence has also created novel approaches to the problem of pursuit—evasion.For the MAS pursuit—evasion problem,Wan et al.(2021) proposed an online decisionmaking and control-oriented framework that developed from a multi-agent deep deterministic policy gradient(MADDPG)framework.In addition,an algorithm termed the adversarial attack trick and adversarial learning MADDPG(A2-MADDPG),which trains the policy to make the decision more robust,was designed.This algorithm introduces the technology of antagonistic learning and improves adaptability to the response induced by other individual changes.In Zhou ZJ and Xu (2020),a novel decentralized intelligent adaptive strategy was proposed for massive MASs,which uses a combination of mean-field game theory and reinforcement learning(RL).This method can obtain a satisfactory pursuit and escape strategy,especially for situations in uncertain environments.

Deep reinforcement learning (DRL) provides a new scheme for the design of control strategies for swarm systems(Shi et al.,2022).Hüttenrauch et al.(2019) proposed a state representation based on mean feature embeddings,which can handle highdimensional and size-changing information sets in swarm systems.They evaluated the representation method on two typical swarm tasks—rendezvous and the pursuit—evasion problem—and revealed that neural network mean embeddings can capture more evader information with less capture time.However,this study did not compare with other swarm system control methods based on deep multi-agent reinforcement learning (MARL) and did not experimentally verify the effectiveness of the method in practice.de Souza et al.(2021) proposed a DRL approach to decentralized multi-agent pursuit with multiple non-holonomic pursuers with local information and an omnidirectional target evader.The method has been validated in a real unmanned aircraft system,but the presence of obstacles or more complex environments was not considered in this method.

Bio-inspired algorithms combined with swarm intelligence are applied to the pursuit—evasion problem.Hu et al.(2021)imitated the behavior of wolves pursuing prey and proposed a cooperative hunting scheme based on the multi-objectivek-winner-takeall(k-WTA)algorithm and wolf particle model.The method improves the task assignment efficiency for cooperative hunting and has satisfactory adaptability to dynamic environments.However,the effectiveness of this method has not been examined in practice.Heras et al.(2019)used deep attention networks to obtain a collective behavior model that is accurate and insightful,and trained and tested the model with high-quality zebrafish trajectory data,but they did not explain the applicability of deep attention networks to other species or collective behaviors.Considering the homogeneity and locality of biological systems,Yu X et al.(2021) proposed a parameter-sharing adversarial inverse RL method that can reconstruct the reward function from biological collective behavior demonstrations,effectively solving the high-dimensional problem.This study considered only biological systems with strong homogeneity and locality,and did not involve more complex situations such as heterogeneity or global information exchange.

There are some intersections between bioinspired algorithms and artificial intelligence.Bioinspired algorithms can implement learning and optimization functions in artificial intelligence,such as the wolf pack algorithm (Mirjalili et al.,2014),ant colony algorithm (Deng et al.,2020),fish swarm algorithm (Huang ZH and Chen,2015),and particle swarm optimization algorithm (Jain et al.,2022).Bio-inspired algorithms are designed with inspiration obtained from hunting and escaping processes of biological groups in nature.They are just a special method or perspective in the field of artificial intelligence.Artificial intelligence is a broad field that includes other methods and applications besides bio-inspired algorithms,such as the various methods mentioned above.

2.3 Bio-inspired perspectives

The pursuit—evasion problem is essentially a branch of collective behavior research (Wang JN et al.,2021).Studying the pursuit—evasion problem from a bionic perspective means studying the phenomenon of hunting in biological groups.In contrast to the previous two perspectives,the research from a biological perspective focuses more on the emergent mechanisms and modeling processes of collective hunting behavior.Collective hunting is not only an extension of the multi-player problem in the traditional pursuit—evasion problem,but also reveals the results of collective motion with two different motivational groups (Kamimura and Ohira,2019).For determining the pursuit—evasion problem’s optimal strategy and decision-making process,research on the hunting phenomenon in nature is instructive.

2.3.1 Basic model of swarm behavior

The swarm model is used mainly to imitate the collective biological behavior in MAS and MRS.The motivation for studying the swarm model is to understand the intrinsic mechanism of emergence,which is significant for designing artificial systems.Especially for studying the internal mechanisms of collective biological behavior,the swarm model is essential to achieve precise control over MAS and MRS swarm behavior.Therefore,introducing the basic swarm model of collective behavior before analyzing the pursuit—evasion problem is necessary.Next,several basic models of biological swarm behavior will be introduced;a brief comparison of them is tabulated in Table 2.

Table 2 Comparison of various model characteristics

Reynolds(1987)proposed three principles based on the flight of a flock of birds,which can simulate the collective motion of the flock.In the spatial model,the individuals are regarded as “Boid” in the flock,which has a limited field of vision.The spatial model follows three basic principles:

1.Separation.Individuals separate from each other to avoid collision(Fig.3a).

Fig.3 Illustration of Boids model:(a)separation;(b)alignment;(c) cohesion

2.Alignment.The individual direction is adjusted to the average direction of the nearest individual(Fig.3b).

3.Cohesion.Individuals move towards the average position(central position)of neighbors(Fig.3c).

The primary basis for the formation of swarm behavior is the individual’s limited local perception,rather than the global perception.Each “Boid” adjusts its motion in response to the motion state of neighboring individuals,and complex behaviors emerge under the framework of unsophisticated and fixed rules.Although the model can better simulate the collective motion of the flock of birds and the school of fish in three-dimensional space,it has not been realized for foraging,evasion,or other related behaviors.

Vicsek et al.(1995)proposed the Vicsek model,which simulates and explains the models of aggregation,transport,and phase transition in nonequilibrium systems.The model reproduces the statistical characteristics of self-driven collective particle motion and provides a foundational model for the study of complex dynamic networks.

The Vicsek model analyzes the consistency problem in collective motion,which inspires further research on system convergence time and system stability in collective motion(Lin et al.,2004;Ren and Beard,2005;Ren et al.,2005).However,the Vicsek model has its own limitations.In the Vicsek model,each individual has a global vision,which contradicts the fact that the vision of individuals in nature is limited.In addition,the size of the individual is not accounted for in the model,which will affect the actual effect of the collision avoidance rule.Although the Vicsek model has some limitations and considers only the problem of speed synchronization between individuals,the improved model based on the Vicsek model has numerous applications in distributed sensor networks and multi-agent collective motion(Savkin,2004;Tian et al.,2009).

Couzin et al.(2002)divided the space into three regions based on the Boids model:the zone of repulsion (zor),zone of orientation (zoo),and zone of attraction (zoa).The field of the individual’s view was considered in the model.As shown in Fig.4,the range of view isα.Except for the zor sphere area,where there is no individual,there is a perceptual “blind area” in which the center individual reacts to other individuals in zoo and zoa.The model also adds the turning rateθaccording to the actual biological movement,which is the maximum angle that an actual individual can turn per unit of time.The additional rule design is more satisfied with the actual motion conditions.

Fig.4 Illustration of the Couzin model (zor:zone of repulsion;zoo:zone of orientation;zoa:zone of attraction)

The Couzin model uses accurate mathematical formulas to reveal how the changes in individuals’behavior affect swarm behavior.By using unsophisticated local rules for individuals,individuals can accurately change their position in the flock,which can well simulate the motion rules of biological groups.The collective motion emerging in the simulated groups can be well verified in actual swarms,particularly schools of fish.This model reveals that individuals may change their position relative to other individuals in schools according to their internal state or the risk of predation(Krause,1993;Bumann et al.,1997;Gazi and Passino,2003),which is of enlightening significance to the study of the pursuit—evasion problem in subsequent biological groups.

Jadbabaie et al.(2003) proposed a modified leader—follower model based on the Vicsek model.The concept of a leader is introduced into the model,which makes the followers move at the same speed as the leader and have a fixed heading.Finally,with the evolution of the system,the movement of all individuals in the system will converge to the leader.This is of great significance in consistency research.Couzin et al.(2005)studied the impact of the proportion of leaders on the behavior of biological systems.Despite the fact that other individuals in the system do not know which individuals are leaders,the leaders’ information can still be transmitted within the group.

For the practical application of the leader—follower model in an MAS,a theoretical framework for a distributed flocking algorithm for multi-agent network systems was proposed (Olfati-Saber and Murray,2004;Olfati-Saber,2006;Olfati-Saber et al.,2007),which laid the foundation for most of the theoretical frameworks of MAS consistency problems.In this algorithm,it was assumed that all individuals in the group know the leader’s information even though the leader is virtual,which contradicts the reality.However,Su et al.(2009)and Song et al.(2010)simplified this condition by assuming that only some individuals knew the leader’s information and adopted the method of implicated control to prove system consistency,which makes the method more realistic and general.

2.3.2 Model of pursuit—evasion

From a biological perspective,the majority of studies on collective hunting behavior describe the mathematical model in terms of statistical physics.In this subsection,we focus on the rules and mathematical models involved in pursuit—evasion behavior,whereas the related biologically specific swarm behaviors and biological effects are discussed in Section 3.

The current research aims to derive universal statistical features from collective hunting(a mathematical,highly nonlinear,dynamic model of pursuit—evasion behavior).The strategy of collective hunting behavior is applied to those models based on the classical models mentioned above to reproduce biological collective hunting.A lattice model was proposed by Kamimura and Ohira (2010) to examine the problem of how one group chases another.The group was divided into predators and evaders.Each predator chased the nearest evader,while the evader avoided the closest predator.Based on the Vicsek model,Angelani (2012) proposed a simple pursuit—evasion model which serves as a foundation model for subsequent studies.Additionally,the predation phenomenon and escape strategy were examined in the context of various escape strategies and various group speeds.Its mathematical model provides an explanation of the escape strategy mechanism in improving the probability of prey survival.

Collective motion and the traditional pursuit—evasion problem are linked in this subsection.The motivation is to develop mathematical models and rules that can represent collective hunting from a swarm intelligence standpoint.In Dutta (2014),the inherited rules and mathematical models of biological collective hunting behavior were introduced.To make the model more realistic,these discrete statistical models need to be extended with animal behaviors and sophisticated strategies.When extending the classical model to a biological vision based pursuit—evasion model,Qi et al.(2020)took perception into account and proposed the visual perceptiondecision-propulsion model with the self-propulsion and alignment term,repulsion term,and escape termas

The predatory behavior of natural biological groups is instructive for the extension of the pursuit model,in addition to the physical model for studying pursuit—evasion behavior from the perspective of collective motion.Cooperation between individuals is necessary for biological groups to engage in collective hunting and escape,whether it is for a group of predators to capture prey or a group of preys to avoid capture or even repel predators.There are two main research directions for the study of pursuit—evasion from the perspective of cooperation:establishing a cooperative hunting model for predators and establishing a cooperative escape model for prey.Chakraborty et al.(2020)investigated the escape dynamics and survival probability of groups by varying the range of interactions between prey groups based on a simple prey—predator model.They did not consider other factors that may affect the outcome,such as environmental noise or heterogeneity among individuals.After finding that prey had the maximum chance of survival over an intermediate range of interactions,the theoretical framework can be extended to study cooperative hunting by multiple predators.When a prey group is being pursued,it might choose anti-attack behavior rather than escape,although this choice puts it at greater risk of being captured.Zhang S et al.(2019a) considered the prey’s anti-attack behavior by abstracting the anti-attack game simply as a game of energy confrontation.Although they did not compare their model with other existing models,this is a novel research perspective.The update functions of energy for prey and predators are as follows:

where Δe(ξ,v)=ξa(·)?(1?ξ)b(v)denotes the energy update function within the prey’s energy Δetarand the predator’s energy Δecha.ξis a switch function with a value range [0,1].For the prey,.Udenotes the rate of energy acquisition,andnpis the number of preys.echadenotes the residual energy,andnais the number of antiattacking preys.For the predators,,whereetardenotes the energy of the captured prey.b(v)=kv?is an energy loss function.

In contrast to the typical pursuit—evasion game,there are two types of prey:evading prey and antiattacking prey.The group with an energy advantage will win the game.In addition,the above-mentioned model extends the group chase and escape model,and investigates the effect of prey aggregation preferences.Most research on group chase and escape does not consider individual energy,which is contrary to the reality of pursuit—evasion scenarios.A model for analyzing how energy management affects predation behavior was provided by Zhang S et al.(2019b).Also,in the two behaviors of staying to eat and continually escaping in the pursuit—evasion process,Zhang S et al.(2019b) analyzed how the prey weighs these two options based on its energy levels.This research has great reference value for long-term chase-and-escape scenarios or scenarios that require multi-round games.

2.4 Comparison of pursuit–evasion methods from different perspectives

There are some intersections between the research methodologies for solving pursuit—evasion problems from different perspectives,but they are not completely independent from one another.As mentioned above,the bio-inspired perspective and the artificial intelligence perspective intersect each other.Bio-inspired algorithms can be used for learning and optimization in the field of artificial intelligence,and game theory methods can be combined with artificial intelligence methods to form a new scheme.These different research perspectives on pursuit—evasion games have some common characteristics:

1.Same goal.The pursuer’s goal is to find and capture the evader,while the evader’s goal is to avoid being caught.

2.Constraints.Both sides of the pursuit—evasion game have certain constraints in real situations,such as different speeds,turning radii,perception ranges,and other maneuverability constraints.

3.Equilibrium assumption.The abilities of the pursuer and the evader are studied under the premise of trade-offs.The pursuer and the evader usually do not have all “strong” abilities at the same time,but if they have “strong” abilities,they have relative weakness.For example,lions have high speed and attack ability;however,due to their large size,they have a larger turning radius compared to rabbits and antelopes.Therefore,if a pursuer’s speed is higher than that of an evader,there may be other limiting conditions,such as a large turning radius,fast energy consumption,limited pursuit time,or a small perception range.Otherwise,regardless of the evader’s escape strategies,the evader will definitely be caught if the pursuer is stronger than the evader in all aspects.

In addition to the common characteristics of the above-mentioned pursuit—evasion problems,there are differences in the methods from different perspectives.

1.Game theory.The game theory method that is suited to the situation is small-scale (few players) and involves relatively simple mathematical game models.From this perspective,research focuses mainly on differential games,using game theory methods and models to analyze the optimal strategies,equilibrium solutions,and other information on both sides of the pursuit—evasion problem.It can effectively describe the relationship between pursuers and evaders and depict their rational behavior and expected effects.However,for complex practical situations,it is difficult to establish accurate and reasonable models,and when uncertain factors interfere,it will lead to unpredictable and uncontrollable results.For complex and nonlinear models,there is significant computation,and it may be difficult to solve and derive subsequent results from the given state using only a mathematical method.

2.Control theory and artificial intelligence.The methods of control theory and artificial intelligence are more suitable for large-scale,more complex nonlinear pursuit—evasion processes.By analyzing the nonlinear factors in the pursuit process,a reasonable dynamic model is established,the cost function is determined,and the optimal strategy is analyzed and solved by solving the HJI equation.The development of artificial intelligence technology makes the pursuit problem independent of the dynamic model,and can complete the solution and optimization of complex cost functions through corresponding learning algorithms that can adapt to a wider range of application scenarios.

The mathematical analysis of control theory can provide theoretical guarantees and guidance,and can use artificial intelligence structures,such as neural networks,to calculate optimal solutions of more complex systems.This ability makes this method capable of handling multiple participants and have better solutions to uncertainty in the real world.However,this also requires a lot of computing resources and time,and accurate knowledge of model parameters and initial conditions.These methods may also have problems such as falling into local optimal solutions and overfitting.

3.Bio-inspired.Bio-inspired methods are suitable for large-scale,high-dimensional,dynamic,nonlinear,and complex pursuit processes.The main research focuses on the local rules of individuals,and by imitating the tasks and roles of biological swarm individuals in the group,complex global behaviors emerge.From a bio-inspired perspective,it can handle more complex dynamic pursuit processes and is closer to real-world pursuit—evasion scenarios and strategies.However,the individual modeling rules of this imitation design lack theoretical analysis and proof and have not revealed the specific mechanism of emergence.In addition,the simulation and test require a lot of computing resources and time.

3 Pursuit–evasion in biological systems

Self-organizing behavior in biological groups emerges with more functions at the swarm level,and the actual biological inspiration is more concentrated in decision-making strategies and cooperative collaboration.Pursuit—evasion behavior in biological systems is reflected mainly in predator—prey behavior.The objective of predators is to pursue and capture prey,while the prey’s objective is the opposite.Both predator and prey have their animal strategies,with predator and prey guiding movements based on them.They also adjust their motion according to their perception of relative position.These animal strategies provide enlightening ideas for strategy design in artificial systems.Therefore,investigating predator and prey behavior and modeling animal strategies as algorithms for artificial systems are critical to understanding the relationship between pursuers and evaders.

3.1 Predator pursuit behavior

For predators,a successful capture phase includes the processes of discovery,search,pursuit,strike,and capture (Peterson et al.,2021).Samespecies predators always engage in cooperative collective hunting,which also needs collaboration and perception among individuals.The biological collective hunting strategy provides a reference design for the problem of multiple pursuers in pursuit—evasion.In this subsection,we overview the collective hunting behavior of fish schooling and bird flocking,along with the animal strategies applied to increase the success rate of capturing.

3.1.1 Intermittent pursuit

Fish predators pursue prey usually with intermittent burst-and-coast swimming (Soto and McHenry,2020).During the burst phase,the predator accelerates and changes the heading rapidly.The coast phase is the duration between consecutive bursts.Fish predators enter the coast phase after burst swimming and adjust the direction of the tail beat to relocate the prey.

3.1.2 Pursuit formation

Mammal groups usually capture their prey by gathering prey,and predators form a certain formation to surround the prey to prevent escape (Haque et al.,2010).Tursiops truncatus dolphins arrange themselves into a horizontal “l(fā)ine abreast” array when hunting their prey to form a predator front,move uniformly to the collection of prey,and attack by gathering prey (Pryor and Norris,1991).The lion forms a “catcher’s mitt” shape,and its prey is encircled for capture and attack(Estes,2012).

3.1.3 Classic pursuit and CATD pursuit

For flying predators(Chiu et al.,2010),the pursuit strategy of flying predators is different from the pursuit strategy of fish.For stationary prey targets,classical pursuit(CP)strategy is often applied,in which the predator directly pursues the instantaneous position of the prey,and the speed vector of the predator is always pointed to the prey (Nahin,2012).However,when the prey moves,CP is inefficient.In this situation,flying predators often use a constant absolute target direction (CATD) strategy.During the evasion of the prey,the predators adjust their speed and heading as the prey changes.In CATD,the sight line of the predator and the prey is constant at each stage.In addition,there is a deviated tracking strategy that is more general for the prey’s constant viewing angle(Kane et al.,2015).

3.2 Prey evasion behavior

For prey,antipredator strategies are often used to respond to the predator’s pursuit behavior (Bedoya-Pérez et al.,2021).The purpose of an anti-predation strategy is to make the prey escape successfully.The escape distance is a critical factor affecting the survival of prey (Peterson et al.,2021).In addition,sensitive perception and excellent escape speed can increase the success rate of evasion.Through the observation of anti-predation responses in biological systems,the intrinsic mechanism of prey escape behavior can be generalized,which provides an excellent solution to the evasion problem in pursuit—evasion.

3.2.1 Evasion formation

When a school of fish encounters predators,the formations may be as follows(Parrish et al.,2002):

1.Ball.All individuals come together to form a closed sphere.This is the defensive formation of the fish,and the formation of dense,large groups contributes to the predator confusion effect.

2.Flash expansion.The school of fish quickly spreads from the center point in all directions,escaping to all directions.

3.Split.The school of fish is split into two groups that move in two directions.

4.Vacuole.Schools of fish swim in circles around predators,forming a circular formation centered on the predator.

3.2.2 Evasion group effect

In addition to the evasion and escape of formation change,the group effect created by self-schooling will reduce the probability that the fish become prey:

1.Dilution effect.This is a concept in the field of behavioral ecology.The probability of a roaming individual being preyed on will be reduced by joining the group,with the probability of being preyed on reduced to 1/Nof the original probability,whereNrepresents the number of individuals in the group(Civitello et al.,2015).

2.Confusion effect.Many fish move rapidly in the predator’s field of vision,making it difficult for the predator to focus on a single individual.The predation targets are continually changing,thereby effectively reducing the predation success rate(Ioannou et al.,2012).

3.Marginal predation.Predators preferentially capture individuals that are located on the periphery of the formation in the prey group(Duffield and Ioannou,2017).

3.2.3 Evasion orientation

When the prey is pursued by the predator,it favors sideways evasion,which has proved to be more effective than other evasion tactics(Ilany and Eilam,2008) because sideways evasion interferes with the visual guidance of predators(Shifferman and Eilam,2004).In addition,the rapid degree of prey evasion response and the short burst speed will greatly affect the success rate of the sideways evasion strategy.

4 Pursuit–evasion in artificial systems

In artificial systems,collective behavior is applied mainly in MAS and MRS.Thus,the essence of the research on the pursuit—evasion problem in artificial systems is to study the strategy designed to realize the actions of pursuit and evasion in MAS and MRS.We have a clear understanding of the pursuit—evasion strategy in biology as reviewed in the previous section.In this section,the pursuit and escape behaviors in artificial systems will be specifically classified according to the biological predation process,and the different stages of their behaviors will be discussed separately.The motivation is to establish a connection with each link of the predatorprey process of biological groups and provide an integrated framework in the field of swarm intelligence for the study of pursuit and evasion strategy.

4.1 Relationship between predator–prey and pursuit–evasion

Inspired by the cooperative behavior of biological groups in nature,the research aims to reproduce and imitate the behavior of biological groups.The researchers tried to achieve group-level functionality through the formulation of interaction rules between individuals and the design of an overall control strategy.The pursuit—evasion problem in biological groups includes two roles,predator and prey,in which the predator wants to catch the prey,while the prey tries to escape to avoid being caught.Based on the biological predator—prey behavior,the pursuit—evasion process is divided into the following four stages (Mirjalili et al.,2014;Zhang XQ and Ming,2017;Zhang XQ et al.,2021):

1.Locking.Predators in the biological group search for the hunting target.

2.Driving &chasing.The prey is driven to favorable terrain and positions.

3.Encircling.The predators surround the prey and form a circle that keeps shrinking.

4.Besieging.The predators develop a hunting strategy and attack the hunting target,and finally capture it.

Whether it is a predator or prey,it needs to go through the stages mentioned above.The four stages establish a link between the two problems of predator—prey behavior and pursuit—evasion.The biological system’s pursuit—evasion strategies provide an inspired idea for the design of artificial systems.Thus,the pursuer can improve the success rate of the pursuit by imitating the predator’s pursuit behavior and employing comparable strategies or formations,whereas if the evasion group effect was properly employed in the artificial system,the success rate of escape may be increased.Jiang et al.(2022)proposed a novel bio-inspired algorithm called the orca predation algorithm (OPA) that simulates the hunting behavior of orcas.The predation process is divided into three steps:driving,encircling,and attacking prey.The algorithm balances the development and exploration phases by parametertuning to assign different weights to the drive and besiege phases.After testing and comparative analysis,the predation algorithm is able to maintain superior performance compared to other tested algorithms.Based on the improved Boids model,Yu ZJ et al.(2022)simulated the predator’hunting behavior,which includes searching,approaching,chasing groups,chasing individuals,attacking,and other steps.According to these steps,the predatory behavior of wolf packs was simulated in the experiments,which is similar to the realistic observation results.Muro et al.(2011) proposed two simple distributed rules to control intelligent agents that can emerge the main characteristics of wolf pack hunting behavior:tracking the prey,pursuit,and encircling the prey.This provides an explanation for the cooperative behavior of wolves when hunting.

In contrast,unlike artificial systems,biological groups have fully autonomous movement and decision-making capabilities,the working mechanism specifics of which have not yet been fully revealed.This presents a significant challenge to the design of artificial systems.The current research on the problem of pursuit—evasion in artificial systems is focused mainly on the design of strategies for collective behavior,i.e.,establishing a series of equations through the mathematical description of the problem and finally solving the optimal decision strategy.Moreover,the performance of the strategy designed determines the quality of the individual’s autonomy,which is a critical requirement of the pursuit—evasion problem.

Next,some recent results are introduced by a novel taxonomy based on the degree of each individual’s ability:strong-pursuer-weak-evader,weakpursuer-strong-evader,and strong (weak)-pursuer-strong (weak)-evader.The terms “strong” and “weak” refer to different levels of ability,and there is a threshold that can be used to make this distinction.The specific definition is as follows:

Definition 1The ability of agentiis defined asgi,which involves a variety of performance indices,such as maneuverability and attack capability.There is a uniform standard thresholdcthat denotes the boundary between strong and weak.Ifgi ≥c,agentiis considered “strong;” otherwise,agentiis considered “weak.”

However,extending to all scenarios of the pursuit—evasion problem,it is hard to find a standard threshold.In this paper,to make it easier to describe the literature,“strong” and “weak” are considered as a pair of relative concepts.For example,if the pursuer’s speed is higher than the evader’s,given the same other performance indices,then the type is strong-pursuer-weak-evader.Based on this,the concepts of “strong” and “weak” are defined here:Definition 2 Consider in scenarioA.A pursuer groupPnis composed ofnpursuers,the ability of theith(i=1,2,···,n) pursuer is defined asgi,and the ability ofPnis denoted asGn.giinvolves various performance indices,such as maneuverability and attack capability.Similarly,an evader groupEmis composed ofmevaders,the ability of thejth(j=1,2,···,m) evader is defined asfi,and the ability ofEmis denoted asFm.Ifgi >fj,theithpursuer is considered as “strong” and thejthevader is considered as “weak” in scenarioA.IfGn >Fm,the pursuer groupPnis considered as “strong,” and the evader groupEmis considered as “weak.” The ability of theithpursuergican be expressed as follows:

whereW=[w1,w2] denotes the weight matrix,Miis the maneuverability ofgi,andAiis the attack capability ofgi.w1andw2satisfyw1+w2=1,and usuallyw1

If the system is homogeneous,the strength of a single member determines whether the group is “strong” or “weak,” whereas for the heterogenous system,the group’s strength depends on the sum strength of all members.

With the definition of “strong” and “weak,” the pursuit—evasion problem can be classified into three types:strong pursuer group vs.weak evader group,weak pursuer group vs.strong evader group,and equal-ability pursuit—evasion.

4.2 Strong pursuer group vs.weak evader group

For the strong pursuer group pursuing the weak evader group,because the stronger group is faster,the research on the pursuit—evasion problem focuses on two issues:the escape strategy of the weak evader and the optimal number of pursuers for the strong pursuer.Kamimura and Ohira(2010)evaluated the effectiveness of the optimal number of chasers in a population,i.e.,whether there is an optimal number of chasers that minimizes the cost of capturing all targets.In the scenario of two faster pursuers pursuing one evader,because inMi=‖vi+Δt·al‖2,Δtwas a very small constant,the maneuverability was determined mainly by the speed.The attack capability was not considered in this literature;according to Eq.(6),we havegi >fi.Therefore,this is two “strong” pursuers chasing a “weak” evader.Makkapati et al.(2018) discussed the escape strategy under the maximum capture time.The escape strategies for two specific situations were analyzed in detail,and the optimal evasion strategy for relay-pursuit was investigated.This research provides a framework for multi-player pursuit games in different information structures.

It is hoped that the strong pursuer will use an optimal number of pursuers or an effective pursuit strategy to ensure that the evader will be caught regardless of the escape strategies applied.Hayoun and Shima(2017)provided a solution to the pursuit—evasion game about missile interception based on a linear bounded control.Also,the optimal control strategy for the scenario in which two strong pursuers are pursuing one weak evader was discussed.They found that the overall performance of strong pursuers was not caused by cooperation or coordinated maneuvers,but by their own presence.The central capture zone(CZ)and two additional no-escape zones(NEZs)were the three regions into which they divided the game space in their construction and analysis,while in CZ or NEZs,the outcome of the pursuers was guaranteed.Pierson et al.(2017) proposed a distributed algorithm that guarantees capturing multiple evaders by multiple pursuers in finite time,which extends an “area minimization” based on Voronoi tessellation of the environment.However,its success in capturing all evaders assumes that all pursuers and evaders are in a bounded convex environment.

Although the pursuer is faster than the evader in this assumption,the evader generally has more agile maneuvers and a smaller turning radius,which guarantees that they can apply some maneuvering strategies to avoid capture by the pursuers.Li W (2017)proposed a dynamic framework and effective escape strategies from a bio-inspired perspective,which are accomplished by evaders’ sudden maneuvers and by controlling the scale of agile maneuvers.The escape strategyfe(t)is described as follows:

wheredenotes the unitary relative-positional vector from the positionx1(t) of the pursuer to the evader positionxe(t),andcis a threshold for the evader beginning to make an agile maneuver.Ris one of the constant matrices ofRlandRr.

Rld(t) denotes the sudden left turn maneuver,andRrd(t) represents the right turn maneuver.This is distinct from the other modeling of escape strategies as differential game problems.This study has an enlightening significance for revealing the natural laws of biological groups.

The evader wants to extend the time before being captured as much as possible.If the evader’s goal is to reach a specified destination,the escape strategy needs only to ensure that the evader is not caught before reaching the destination,rather than being pursued for an indefinite period of time.On the basis of the previously mentioned concepts,Selvakumar and Bakolas(2022)proposed a method based on min—max Q-learning in RL to compute the escape strategy of an evader such that the slower evader reached the specified destination,while avoiding being captured by multiple pursuers.To characterize the salient features of the pursuit—evasion game,its state space is represented using capture time parameters rather than position and velocity.This approach has its own limitations.It assumes that the pursuer uses a relay pursuit strategy,which may not be optimal for the entire pursuit process.

There are also some special situations,i.e.,one strong pursuer pursuing multiple weak evaders or homogeneous systems wheregi >fj,but the number of pursuers is smaller than the number of evaders(n

4.3 Weak pursuer group vs.strong evader group

Overcoming strength with weakness is a very topical problem of practical importance and research value.In contrast to a strong pursuer group pursuing a weak evader group,there is no pursuer speed advantage,which eliminates the guarantee that an evader can be captured in a pure pursuit and sustained pursuit strategy.For weak pursuers pursuing strong evaders,an efficient cooperative mechanism is necessary to capture the evader.The drawback of slow movement is offset by a cooperative strategy that takes advantage of the number of the pursuers.To describe the natural group chasing in a closed boundary area,Janosov et al.(2017) proposed an agent-based,bio-inspired approach.They analyzed the characteristics of a pursuit strategy for scenarios in which the pursuers pursued faster evaders.They did not consider the attack capability of the pursuer and evader,with the pursuer’s maneuverabilityMpsmaller than the evader’s maneuverabilityMe.According to Eq.(6),we havegi

To increase the chances of successfully capturing the evader,the pursuers must not only approach the evader quickly using maneuvering strategies,but also rely on the advantages of numbers to encircle the evader.A distributed pursuit algorithm for a faster free-moving evader was proposed in Fang et al.(2022),which consists of two parts:the encirclement algorithm and the trade-off algorithm,where the encirclement algorithm enables the pursuers to quickly form an encirclement as follows:

whereαidenotes the polar angle,?i,i+1is the coverage angle of adjacent pursuers,ki >0 is a surrounding coefficient,and ˙αrepresents the pursuer surrounding the evader counterclockwise.

The trade-off algorithm finds a balance between forming an encirclement of evaders and rapidly approaching them for capture.The surrounding coefficientkiand hunting coefficienthiare represented in the trade-off algorithm by designing trade-off coefficientβi,as shown in the following:

whereδi ∈[0,1]denotes the surrounding factor,andγi ∈[0,1]is the hunting factor.

However,the research(Fang et al.,2022)needs to satisfy the assumption that the pursuers should be distributed based on equal angles around the evader before the game starts.This implies that in addition to an effective cooperative strategy to overcome strength with weakness,the initial spatial distribution of the pursuers has a critical impact on the success of the capture.When the evaders are initially distributed in this way,the pursuit—evasion problem becomes a fishing game;i.e.,the superior evader attempts to pass the gap between the two pursuers to avoid capture.Chen et al.(2016) proposed a besieged state and a capturing state under encirclement and provided an expression for the minimum number of pursuers required to guarantee capture.The besieged status inequality (12)and capturing status inequality(13)are described as follows:

whereri,i+1denotes the distance between two adjacent pursuers,andkis the time step.represents the speed ratio of the pursuer to the evader.diis the distance between the evader and theithpursuer.Δtrepresents the length of one time step.

In addition,they found that the minimum number of pursuersnminwas related to the speed ratioa:

where [·] is the least integer operator.Based on the above expressions,they designed a cooperative pursuit scheme for the pursuers:besiege-shrink-capture.This provides an excellent research idea for the design of capture strategies in multi-player collective hunting.

In fact,most of the current studies have been carried out under the premise that there is a closed boundary environment or that the initial space of the pursuer is evenly distributed around the evader.Wang CY et al.(2022)developed a cooperative hunting strategy based on the idea of the Apollonius circle for multiple pursuers pursuing a superior evader,in which the pursuers capture the evader while maintaining formation.Some necessary requirements for the successful capture of a “strong” evader are clarified,but they did not account for the effects of limited observation and measurement noise,whereas in Ramana and Kothari (2017),an escape strategy for high-speed evaders was proposed based on the same idea.On the basis of this work,Vechalapu (2020)proposed a trapping pursuit strategy to capture a high-speed evader.Based on the Apollonius circle principle,trapping pursuers were used to mislead the evader into the trap.This approach is more effective than the cooperative pursuit strategy because it adjusts the critical speed ratios and the capture time.

4.4 Equal-ability pursuit–evasion

The equal-ability pursuit—evasion problem is similar to the game of two cars because both the pursuers and the evaders have the same speed and other properties.The situation is probably the “fairest” pursuit—evasion game.With identical dynamics and external constraints,the ultimate success of capture or escape depends entirely on the corresponding strategy.

There are few current studies on the equalability pursuit—evasion problem,and the research on these situations has concentrated on differential game methods to find the capture zone and escape zone in strategy space.Kothari et al.(2017) presented a cooperative strategy for multiple pursuers to pursue an evader in a bounded connected domain,where all pursuers and the evader had the same speed and turning radius.By discussing the capture strategy based on minimizing the safe-reachable areas for holonomic systems and the pursuit guidance law,an extension of non-holonomic system tracking algorithms was developed.Bravo et al.(2020)discussed the pursuit—evasion problem for two identical differentially driven robots,which was the same case as the game of two cars.Similarly,the strategy design considered in this work is under non-holonomic constraints that both robots have motion constraints and are not able to change orientation instantaneously.They exhibited cases where the evader can always avoid capture when the barrier is closed.The above studies are both based on qualitative differential strategies in differential games,where the corresponding barriers are constructed to find the capture and escape zones.

5 Future studies

Although great progress has been made in the research of pursuit—evasion in group behavior,there are still some problems to be solved.

5.1 Emergence mechanism and quantitative metrics

Although some biological swarm behaviors have been reproduced in artificial systems,there is still no accurate explanation for the specific internal mechanism of emergent behavior.Individuals with simple intelligence and behavior in nature have complex behavioral functions after forming a group.If the specific internal mechanism is studied clearly,it can better realize similar behavior in the design of artificial systems.

For emergent behaviors,corresponding quantitative metrics need to be proposed,to not only better describe behaviors in biological systems,but also quantitatively measure emergent mechanisms in artificial systems.Whether it is the corresponding emergence model or the corresponding quantitative parameter,the basic mechanisms behind emergence should be revealed.Emphasis can be placed on the analysis of weak emergent,non-emergent,and strong emergent phenomena,as well as discussion of necessary and sufficient conditions for the emergence of emergent behaviors(Sturdivant and Chong,2018).In this sense,seeking the intrinsic mechanism of emergence and corresponding measurement methods is a critical issue.There is still a lack of interpretability and measurability of the emergent mechanism when designing feasible artificial systems,so any progress will have a strong promotional effect on the group cooperation behavior of artificial systems.

5.2 Heterogeneous system design

Swarm behavior in nature often involves the interaction of many independent individuals to produce complex functions (Rubenstein et al.,2014).In artificial systems,for the purpose of achieving more complex functions,an increase in the number of agents is required.However,if homogeneous individuals with the same functional attributes are used,it will lead to redundancy in task coverage (Parker,1994).Agents with different attributes and functions can make the assignment of tasks more dynamically adaptable.Therefore,heterogeneous systems will play an important role in MAS and MRS in the future,and the increase of heterogeneous individuals in the system will enhance the robustness of the entire swarm system.Moreover,considering the consistency of the communication structure of the swarm system network,the expansion algorithm of the communication network is one of the challenges(Hou et al.,2020).

5.3 Generalization of strategy

Most current pursuit—evasion strategies are predicated on specific premises and necessitate the satisfaction of specific initial conditions.The extension of pursuit—evasion strategies to general situations,not limited to a specific scenario,is a great challenge for future research.Additionally,in an actual environment,there are many uncertainties and multi-source disturbances.Therefore,it is of great importance to improve the stability and robustness of group decision-making for the reproduction of artificial group behaviors.The biologically heuristic swarm intelligence algorithm has demonstrated superior performance in solving optimization problems,especially the swarm intelligence algorithms of fish schools,bird flocks,and wolves,which provide a significant reference for the formulation of MAS pursuit and evasion strategies.With the development of artificial intelligence technology,the future expansion of these swarm intelligence algorithms will require exploration of more general characteristics and mechanisms,and the combination of other advanced and effective algorithms (Tang et al.,2021).Such endeavors will promote the development of relevant areas such as cooperative games and non-cooperative games.Furthermore,interdisciplinary research in multi-disciplinary fields such as control,gaming,biology,and communication may shed new light on the cooperative control of swarm systems.

5.4 Uncertain pursuit speed

Many studies of the circumstances involving pursuit and evasion make the assumption that the pursuers move at a certain speed,which is not the case in practice.Given the complexity of the actual environment,the pursuers’ speeds are uncertain as a result of environmental factors such as terrain,weather,and energy (Yan FH et al.,2019).Therefore,it is crucial to research cooperative strategies that account for the uncertain speed of the pursuer.Meanwhile,we need to explore the bias introduced in the pursuit strategy under speed uncertainty and ensure that the success of the capture strategy is not affected by speed uncertainty.Especially when the speed of some of the pursuers is greatly reduced by a lack of energy,designing effective strategies that can coordinate pursuers with different energies to accomplish the task of capture is a challenging research direction for the future.

5.5 Environmental feature prediction

The shape of the environment affects the distribution of individuals in the swarm,and different environmental characteristics make individuals form a discriminative distribution in the environment (Emmons et al.,2018).In the same way,the distribution of individuals in a group can reflect the characteristics of the environment.The environmental features are inferred by analyzing the formation and density of the swarm system,and their distribution is of great significance for the prediction of surrounding environmental features.Compared with obtaining global information to model environmental scenes,it is more convenient and efficient to obtain unknown environmental information through local perception among individuals and autonomous distributed observations.

The key questions of this study are divided mainly into the following three aspects:

1.Determine the relationship between individuals’behavior,environmental characteristics,and the distribution of observable quantities.

2.Develop the appropriate prediction distribution algorithm based on the determined relationship.The challenge is to quickly and accurately predict the environmental characteristics based on the known individuals’ behavior and the observed local distribution (Dai et al.,2022).To improve system robustness,the already developed aspects must not be disturbed by individual faults and damages(Emmons et al.,2020).

3.The design of optimal network sensor coverage in swarm systems is critical for reducing the scope of local perception and the occupation and consumption of computing resources (Singh et al.,2021).There is a great correlation between the sensor networks and the number of individuals in the swarm systems.In addition,we need to explore the application in large-scale swarm systems.

Analysis of the local autonomous behavior and distribution of the group has a significant effect on the judgment of obstacles and exits in the process of individual movement.For random motion,the denser area in the group may be more crowded,which can predict the position of the exit through the distribution observation of this position.The relationships between the environmental features and the distribution of individuals may have better guiding significance for expanding the type of application environment scene in the MAS.By predicting environmental characteristics,the exit and the location of obstacles can be found only through local autonomous behavior analysis without global communication.Therefore,the designed control strategy can adapt to more random environments,especially the environment where communication is lost and the positioning sensor is damaged.This has important application significance and makes the swarm system more robust in adapting to complex environments,thus expanding the types of swarm intelligence application scenarios in the future.

5.6 Cyber security

In pursuit—evasion problems,predators rely primarily on vision to pursue their prey.The advancement of artificial intelligence technology not only enables predators to accurately identify prey,but also makes prey deceptive.The prey uses the adversarial sample to attack the predator’s pursuit algorithm,resulting in misidentification by pursuers and camouflage creation.Similarly,the deliberate deception of information by internal cheaters can affect the behavior of the entire system (Huang LN and Zhu,2022).In the MRS and MAS,the impact of deceptive behavior of multiple individuals on the overall system behavior needs in-depth research.In addition to deception and camouflage,there are attacks against multi-agent and multi-robot cyber systems(Ishii et al.,2022).These attacks may result in leakage of system information or system failure,increasing the risk to the entire system.The research on cyber security is related to information security and capture success rate in the pursuit—evasion system.In the future,combining artificial intelligence technology to study individual camouflage and deception strategies may be one of the solutions to optimizing pursuit—evasion strategies.In addition,cyber security for communication and control systems is a crucial study topic to ensure dependability of pursuit and evasion strategies.

6 Concluding remarks

Pursuit—evasion is a critical issue in swarm behavior,and it is also a multidisciplinary research hotspot.In this paper,we reviewed the classical pursuit—evasion models and then discussed the pursuit—evasion problem from the perspectives of biological systems and artificial systems.We proposed a taxonomy of swarm behavior according to the characteristics of the swarm system and introduced swarm behavior in biological systems and artificial systems.In artificial systems,we discussed the application of relevant pursuing strategies from three perspectives:strong pursuer group vs.weak evader group,weak pursuer group vs.strong evader group,and equal-ability group.Finally,we discussed some key problems and future studies to promote the development and improvement of pursuit—evasion in swarm intelligence.

Exploring the pursuit—evasion problem is a generalization of swarm intelligence in the MAS and MRS.To realize the goal of intelligent hunting in artificial systems in the future,a breakthrough in design is still indispensable for studying the emergent mechanism of swarm behavior and control theory methods,especially the design of heterogeneous swarm systems,which will be a major potential direction of future development.It is also essential to expand the application scenarios for swarm systems and improve the effectiveness of pursuit—evasion strategies in practical situations because swarm systems require more reliability and security.Additionally,encouraging the fusion of artificial intelligence and swarm intelligence technology will result in novel solutions to the pursuit-evasion problem.

Contributors

Zhenxin MU designed the survey and drafted the paper.Junzhi YU guided the survey and edited the paper.Jie PAN and Junzhi YU helped organize the paper.Ziye ZHOU provided his experience on collective motion and made suggestions to improve the presentation of the paper.Lu CAO and Junzhi YU revised and finalized the paper.

Compliance with ethics guidelines

Zhenxin MU,Jie PAN,Ziye ZHOU,Junzhi YU,and Lu CAO declare that they have no conflict of interest.