Collaborative pursuit-evasion game of multi-UAVs based on Apollonius circle in the environment with obstacle

Abstract

In the game of a two-dimensional plane with a circular obstacle, a strategy of multi-pursuers and a single evader is studied. All the agents are Unmanned Aerial Vehicle and the evader is faster than the pursuers. The collaborative pursuit-evasion mission is divided into two stages: the encirclement stage and pursuit-evasion stage. When pursuers fly to the mission area from a distance, the formation and obstacle avoidance method based on leader-follower mode is designed for the encirclement process. In the pursuit-evasion stage, considering obstacle avoidance and manoeuver constraint, a collaborative strategy combining Apollonius circle algorithm and geometric algorithm is proposed, and the condition for the successful capture of a single superior evader is analysed. In the simulation, the influence of obstacle size and manoeuver constraint is compared and analysed in detail, which indicates that they will increase the capture time even changes the result of the game in the limited map. In addition, the complexity of the algorithm is $\mathit{M}$ times higher than that of the obstacle-free case ($\mathit{M}$ is the number of obstacles in the map).

KEYWORDS:

• Multi-agents collaboration
• pursuit-evasion game
• environment with obstacle
• Apollonius circle
• manoeuver constraint

1. Introduction

Pursuit-evasion game has always been an important branch in the field of artificial intelligence, and it has gradually received a lot of attention in recent years. The traditional pursuit-evasion game adopts a one-to-one capture mode, and in an ideal environment without obstacle (Liang et al., 2019). With the gradual improvement of the one-to-one pursuit-evasion, more and more studies are carried out in the game with obstacle, since it has more practical value (Sani et al., 2020). However, the obstacle makes the pursuer need to have a superior perception or action advantage in order to win (Souidi et al., 2019). So, multi-agents collaboration provides a possible solution to the pursuit-evasion game in an obstacle environment (Liang et al., 2021).

Different from path planning, the pursuit-evasion game contains the information of the two adversarial parties, so that its purpose is to capture the target and not simply the shortest path. Du et al. (2021) proposed a method based on multi-agents reinforcement learning to solve the pursuit-evasion game. By the parameter sharing between multi-UAVs, a higher capture rate can be got in a short time. Liang et al. (2020) studied the pursuit-evasion game of heterogeneous agents in air-ground cooperation mode. The study claims that although the strategy cannot guarantee the pursuer to win, it is optimal in the worst case. Also based on the worst-case analysis, Nath and Ghose (2022) proposed a two-phase evasive strategy for a pursuit-evasion problem which has incomplete information regarding each other’s motion. Due to the complexity of the model, pursuit-evasion game has just been extended to the two-dimensional environments with a simple obstacle in recent years. Zhou et al. (2020) pointed that multi-pursuers can successfully capture an evader with equal speed by using a tracking algorithm in a two-dimensional plane with obstacle. Šćepanović et al. (2019) proposed a random lattice model in an environment with obstacles, and they use numerical methods to study the influence of obstacle density on the pursuit-evasion game. The results show that the larger the density of obstacles is, the faster the pursuer can find the evader. Based on the reachable set in the flow field with an obstacle, Sun et al. (2017) studied the game of multi-pursuers and single evader. When the maximum speed of the evader is less than that of each pursuer, the pursuer can capture the evader. For the “police catching robbers” in the environment with complex obstacles, Zhu et al. (2020) used the rolling horizon optimisation algorithm to solve the bilateral closed-loop optimal control of the pursuit-evasion game. Based on deep reinforcement learning, Zhang et al. (2022) proposed the pursuit-evasion scenario (PES) framework for high-quality simulation of the multiquadcopter and target pursuit-evasion game in the urban environment.

In spite of the multi-agents perform well in the pursuit-evasion game with obstacle, how to capture the evader with speed advantage is the further improvement of multi-agent cooperation ability, especially the agents are UAV that has manoeuver constraint.

In this paper, a strategy for the pursuit-evasion game between multi-pursuers and a single evader in an obstacle environment is proposed. All the agents are UAVs and the evader is faster than pursuers. Based on UAV's model, the scheme of the collaborative pursuit-evasion mission is studied, which is dived into several stages. In the encirclement stage, the leader-follower mode is improved by the dynamic window approach to realise obstacle avoidance and formation. In the pursuit-evasion stage, the geometric algorithm and Apollonius circle algorithm are proposed to analyse the winning conditions while the pursuers cooperate to chase the superior evader in the environment with obstacle. The simulation results show that the proposed method can ensure that the pursuers have a high winning rate even in the presence of UAV constraints and obstacles.

2. Collaborative pursuit-evasion game of multi-UAVs

2.1. Models and assumptions

In a pursuit-evasion game with multi-UAVs, $n$ pursuers are randomly distributed around an evader. There is an obstacle in the map, and all the agents know other agents’ position at any time. The initial distance between the pursuers and the evader is greater than the capture radius. When the evader is within the capture radius of the pursuer, the pursuers win. All the agents are UAVs and the model is as follows (De Souza et al., 2021): (1) $\begin{array}{r}\{\begin{array}{l}{\dot{x}}_i=V_{i}cos{\psi }_i\\ {\dot{y}}_i=V_{i}sin{\psi }_i\\ {\dot{\psi }}_i=\frac{V_i}{R}\end{array}\end{array}$(1) In Equation (1), $i\in \{P,e\}$, $P=\{p_{1,\dots ,}{p}_n\}$, $(x_i,y_i)$ represents the position coordinates of the UAV at time $i$. $\psi$ is the heading angle, $R$ is the turning radius of the UAV, $V_p$ is the maximum velocity of the pursuer, and $V_e$ is the maximum velocity of the evader. The velocity ratio between the pursuer and evader is $\lambda =V_p/V_e$. If $\lambda >1$, the pursuer is faster than the evader, and the pursuer will win at any initial position when time is infinite. So this section only considers the condition of $\lambda \le 1$, which means the pursuer is slower than the evader. In actual simulation, the continuous kinematics model of the UAV is usually discretised, and the discrete state equation of the UAV is (2) $\begin{array}{r}\{\begin{array}{c}x(k+1)=x(k)+V_{i}cos\psi (k)\mathrm{\Delta }T\\ y(k+1)=y(k)+V_{i}sin\psi (k)\mathrm{\Delta }T\end{array}\end{array}$(2) Here $\mathrm{\Delta }T$ is the simulation step. The pursuers and evader take turns to move in the game, so the next position of the agent can be calculated by Equation (2). Assuming that all pursuers have the same ability, including the same velocity and manoeuver constraints. When the evader is in the capture area of the pursuer and the distance between the evader and any of the pursuers is less than the capture radius, the evader is captured and pursuers win. So, the following equation is used to calculate the termination condition of the game. (3) $\begin{array}{r}\sqrt{{(x_e-x_{p_i})}^2+{(y_e-y_{p_i})}^2}\le d_i\end{array}$(3) In Equation (3), $i\in \{1\dots n\}$, and $d_i$ is the capture radius of the $i$th pursuer. $(x_{pi},y_{pi})$ and $(x_e,y_e)$ is the position of the $i$th pursuer and the evader, respectively. When the distance $d$ between the evader and any pursuer is less than the capture radius, the evader is captured.

2.2. Collaborative pursuit-evasion mission

In the mission, Multi-UAVs first fly to the combat area in formation from a distance, then play a collaborative pursuit-evasion game with an evader. Therefore, the mission is divided into two stages: formation and pursuit-evasion game. When Multi-UAVs are in formation, they should avoid the obstacles and form a specific encirclement situation for the evader in the combat area. The encirclement situation is a prerequisite for the collaborative pursuit-evasion game, and it can be considered as the preparation for the game. The whole mission is shown in Figure 1.

Figure 1. Description of the mission.

During the encirclement process, Multi-UAVs have found the evader, so they must arrive at the designated position at the same time and finish the transformation of the formation. The designated position is calculated by the collaborative pursuit-evasion algorithm, and is used as the initial condition of the game.

3. Formation and obstacle avoidance in the encirclement process

Based on the theory of consensus control, the input $u_i$ of the system is rewritten into three parts. Assuming that the number of UAVs is $N$, so (4) $\begin{array}{r}{u}_i=u_{ia}+u_{ib}+u_{ir},i=1,2,\dots ,N\end{array}$(4) where $u_{ia}$, $u_{ib}$ and $u_{ir}$ is the input of consensus control, formation control and avoidance control, respectively. During the encirclement process, the model of leader in leader-follower mode is improved as follows. First, the control of the leader is (5) $\begin{array}{r}{u}_L(t)=m+kD(t)+\sum _{i\in N,i\ne L}{a}_{Li}{r}_{Li}(t)+\beta R_L(t)\end{array}$(5) Here $m$, $k$ and $\beta$ are constants. $D(t)$ is the distance between the leader and the target at time $t$. $r_{Li}$ is the distance between the leader and the other followers. Suppose that the location of the leader is $x_i(t)$, then $R_L(t)$ represents the effect of the obstacles and it can be calculated by Equation (6). (6) $\begin{array}{r}{R}_L(t)=\sum _{i\in N,i\ne L}{R}_i(t),R_i(t)=\sum _{l=1}^M\lambda (x_i(t)-{x^l}_{obs}),\end{array}$(6) In Equation (6), $M$ is the number of the obstacles. $\lambda$ is shown as follows: (7) $\begin{array}{r}\lambda =\frac{\frac{1}{d_i(t)}-\frac{1}{d_M}}{\delta \cdot d},d_i(t)=||x_R-x_i(t)||,d=\sum d_i(t)\end{array}$(7) where $\delta$ is the safety coefficient and $d_M$ is the detection distance which is determined by the sensors of the UAV. Suppose that the location of the follower is $x_j(t)$, then the model of the other followers is (8) $\begin{array}{r}{u}_F(t)=\epsilon \sum _{j\in N,j\ne L,F}{a}_{Fj}(x_j(t)-x_L(t)-r_{Fj}(t))+\gamma R_F(t)\end{array}$(8) In addition to ensuring the stability of the formation, the encirclement process also needs to consider the problem of obstacle avoidance. By the dynamic window approach, the obstacle avoidance trajectory can be got based on the model of the UAV, then the following equation is used to select the proper path. (9) $\begin{array}{r}H(V,\omega )={\alpha }_1\cdot \text{heading}(V,\omega )+{\alpha }_2\cdot \text{dist}(V,\omega )+{\alpha }_3\cdot \text{velocity}(V,\omega )\end{array}$(9) where, ${\alpha }_1$, ${\alpha }_2$ and ${\alpha }_3$ is the coefficient. $\text{heading}(V,\omega )$ is the evaluation function of angle, and the smaller the angle, the higher the evaluation score. $\text{dist}(V,\omega )$ is the evaluation function of safety distance, and the larger the angle, the higher the evaluation score. $\text{velocity}(V,\omega )$ is the evaluation function of velocity, and the larger the angle, the higher the evaluation score.

4. Collaborative pursuit-evasion game without obstacle

As the scheme shown in Section 2.2, the process of the task is to make formation and avoid obstacles first, and then play the pursuit-evasion game after the UAV flies to the combat area. However, the combat area is related to the capture condition of pursuit-evasion game, which means the initial positions of the UAVs in the game is the constraint of formation and obstacle avoidance. Therefore, the initial position of multi-UAVs in the pursuit-evasion game should be calculated first according to the state of the evader, and then the position is used as the target point of formation and obstacle avoidance. In this section, the strategy of the UAVs in the pursuit-evasion game is analysed based on Apollonius circle algorithm.

4.1. Pursuit-evasion game based on Apollonius circle algorithm

In the Apollonius circle algorithm, the ratio of the distance from a moving point to two fixed points on the plane is a constant value $\lambda (\lambda \ne 1)$, the trajectory of the moving point $A$ is an Apollonius circle. Isaacs et al. (1999) apply the concept of the Apollonius circle to pursuit-evasion game first, and the game contains a pair of the pursuer $P(x_p,y_p)$ and the evader $E(x_e,y_e)$ with continuous unequal velocity. The velocity of $P$ is $V_P$, and the velocity of $E$ is $V_e$. There is a random point $A(x_A,y_A)$ which makes the ratio of the line $PA$ and $EA$ is $\lambda$. (10) $\begin{array}{r}\lambda =\frac{\overrightarrow{|PA|}}{\overrightarrow{|EA|}}=\frac{V_p}{V_e}\end{array}$(10) Then the trajectory of the point $A$ is the Apollonius circle (as shown in Figure 2), and any point on the circle is considered that when the pursuer and the evader are sailing at maximum velocity, they can reach that point at the same time.

Figure 2. Apollonius circle.

According to the definition of Apollonius circle, there are (11) $\begin{array}{r}\frac{PA}{V_p}=\frac{EA}{V_e}\end{array}$(11) As the definition in Equation (10), $\lambda =V_p/V_e$, so the centre $O$ and the radius $r$ of the Apollonius circle are expressed as follows. (12) $\begin{array}{rl}o& =\left(\frac{x_p-{\lambda }^2{x}_e}{1-{\lambda }^2}\text{, }\frac{y_p-{\lambda }^2{y}_e}{1-{\lambda }^2}\right)\end{array}$(12) (13) $\begin{array}{rl}r& =\frac{\lambda \sqrt{{(x_p-x_e)}^2+{(y_p-y_e)}^2}}{1-{\lambda }^2}\end{array}$(13) From Equation (13), it can be seen that when $\lambda \le 1$, the radius of the Apollonius circle is proportional to the size of $\lambda$. The smaller the radius of the Apollonius circle, the higher the probability that the evader will escape from the pursuer. For a superior evader, the pursuer is inside the Apollonius circle, and the evader is outside the circle. In addition, any evader’s path that passes through the Apollonius circle will result in the evader being captured.

Assuming that the pursuers are evenly distributed around the evader, the number of the minimum pursuers need to surround the evader can be calculated through the angle between them, which is one of the necessary conditions for capture. According to Figure 2, there is (14) $\begin{array}{rl}\frac{v_p}{\text{sin}\beta }& =\frac{v_e}{\text{sin}\alpha }\Rightarrow \text{sin}\beta =\frac{v_p}{v_e}\text{sin}\alpha \le \frac{v_p}{v_e}\end{array}$(14) (15) $\begin{array}{rl}{\beta }_{max}& =arcsin\left(\frac{v_p}{v_e}\right)\end{array}$(15) Therefore, when the velocity of the pursuer is less than that of the evader, the number of the pursuers to achieve a successful capture should meet the lower limit condition of Equation (16). (16) $\begin{array}{rl}n& =\frac{2\pi }{2{\beta }_{max}}=\left[\frac{\pi }{arcsin\left(\frac{v_p}{v_e}\right)}\right]\end{array}$(16) (17) $\begin{array}{rl}& \Rightarrow \frac{v_p}{v_e}\ge sin\left(\frac{\pi }{n}\right)\end{array}$(17) Equation (17) cannot guarantee the victory of the pursuer, unless all adjacent Apollonius circles formed by the pursuer and the evader intersect with each other, or at least they are tangential. If the pursuer wants to completely capture the evader at any time, it needs to meet the conditions of the Equations (3) and (17) at the same time.

In the pursuit-evasion game between two agents, the reward is usually the capture time (Konstantinidis & Kehagias, 2019; Zhang et al., 2021), that is, the pursuer wants to minimise the time, and the evader is the opposite. The optimal strategy of the pursuer is the captured event happens at the point which is the farthest one from the initial position of the evader on the Apollonius circle. In the game of multi-agents, the collaborative advantage will bring some changes to the strategy compared with a single agent. In the collaborative pursuit-evasion game, the process is divided into different states to be discussed. By collaboration, multi-pursuers will form an encirclement of the evader. According to the positional relationship between the pursuers and the evader as shown in Figure 3, the state of the evader will be discussed in different cases.

Figure 3. Position of the pursuer and the evader.

In Figure 3, $E_1$ is in the encirclement, $E_2$ is on the encirclement, $E_3$ is outside the encirclement.

4.2. Strategy of the evader in the case of multi-pursuers

Firstly, according to Figure 3, the evader needs to determine whether it is in the polygon formed by the pursuers or not. Then, the following cases will be used to make specific strategy.

Case 1 is the unenclosed state (as shown in Figure 4). At this time, the evader is outside the encirclement formed by the pursuers.

Figure 4. Unenclosed state.

As shown in Figure 4, the evader is not inside the encirclement formed by the pursuers, and not within the capture radius of each pursuer. Since the velocity of the evader is faster than that of the pursuers, as long as the evader chooses the path away from the encirclement formed by the pursuers, the evader can successfully escape.

Case 2 is the semi-enclosed state (as shown in Figure 5). At this time, although the evader is inside the encirclement formed by the pursuers, there is a clear gap between the Apollonius circles of the two adjacent pursuers.

Figure 5. Semi-enclosed state.

In order to quickly get rid of the encirclement, the evader chooses the direction of the gap to escape. In the process of escaping, the distance between the pursuer and the evader will be reduced. According to Equation (13), the radius of the Apollonius circle will become smaller, and a larger gap will appear, so the evader can finally escape.

Case 3 is the fully enclosed state (as shown in Figure 6). At this time, the evader is inside the encirclement formed by the pursuers, and the Apollonius circles of any two adjacent pursuers all intersect to each other (or they are tangent).

Figure 6. Fully enclosed state.

In Figure 6, the evader is completely surrounded by the pursuers. In order to prolong the time of being captured, the evader will run to the farthest intersection of the Apollonius circle. At this time, according to the principle of the Apollonius circle, the pursuer can capture the evader within the capture radius.

4.3. Collaborative strategy of the multi-pursuers

In the whole pursuit-evasion game, all the pursuers know the direction, velocity and position of the evader at any time. The pursuer dynamically changes the strategy according to the escape state of the evader. By collaboration, the pursuers will be assigned different roles such as some will intercept the evader. Based on the evader’s strategy, this section discusses the strategy of the pursuers when they have the same velocity as the evader, even slower.

During the pursuit-evasion game, the main purpose of the pursuers is each pursuer will cooperate with its two adjacent pursuers to ensure their Apollonius circles intersect to each other, that is, the pursuers want to keep the game in the state of Case 3. If the distance between any two Apollonius circles is greater than the capture radius of the pursuer, it means that the pursuer will be failed because the evader is also intelligent enough to find a gap to escape.

If the game is in the state of Case 1 and 2 (Unenclosed and semi-enclosed states), since the velocity of the pursuer is slower than the evader, the evader will win.

If the game is in the state of Case 3 (Fully enclosed state), the strategy of the evader is to escape to the farthest intersection, and the goal of the pursuer is to catch the evader without destroying the enclosed state of the Apollonius circle. So the strategy of the pursuers is that the two pursuers whose farthest intersection is farther will move to their farthest intersection to intercept the evader, and the remaining two pursuers keep the same direction as the evader to continue pursuit. When the evader changes direction, so do the pursuers, but still execute the strategy until the evader is captured. The whole process is shown in Figure 7.

Figure 7. Strategy of the pursuers.

5. Collaborative pursuit-evasion game of multi-UAVs with a circular obstacle

5.1. Pursuit-evasion game based on geometric obstacle avoidance

Obstacle avoidance is the important basis of the successful capture in the pursuit-evasion game with obstacle. Once UAV finds the obstacle, it needs to ensure its safety first and make obstacle avoidance, then continue pursuit. In this paper, the flight area is divided into two types: obstacle area and obstacle-free area. There are many important obstacle avoidance methods, such as the artificial potential field algorithm (Jiang & Deng, 2021), particle swarm optimisation algorithm (Islam et al., 2021), RRT algorithm (Qi et al., 2020). But these algorithms are difficult to deal with the pursuit-evasion game for the time being. In this section, a geometric obstacle avoidance method is proposed for the pursuit-evasion game. Here, the obstacle is “expanded” (Zheng et al., 2020) to ensure the safety of the UAV.

Step 1. Collision detection

Determine whether there is an obstacle between the evader and the farthest intersection point which it chooses to escape. (18) $\begin{array}{r}\sqrt{{(x_u-x_o)}^2+{(y_u-y_o)}^2}\le R\end{array}$(18) In Equation (18), $O(x_o,y_o)$ is the centre coordinate of the obstacle, $U(x_u,y_u)$ is the current position coordinate point of the UAV, $R$ is the radius of the expanded obstacle. When the distance between the UAV and the obstacle is less than the radius $R$, the obstacle avoidance method will be used.

Step 2. Calculate the collision avoidance point

Calculate the tangents $UC$ and $UD$ from the current position $U$ of the UAV to the expanded circular obstacle, as shown in Figure 8. The centre of the obstacle is $O$ and the radius is $R$, so the circular obstacle can be described as (19) $\begin{array}{r}(x-x_o{)}^2+(y-y_o{)}^2=R^2\end{array}$(19) In Figure 8, $O(x_o,y_o)$ is the centre coordinate of the obstacle, and the coordinate of the UAV is $U(x_u,y_u)$. After calculating the two tangents from the UAV to the obstacle, the slopes of the two tangents are respectively $k_1$ and $k_2$, and the two tangent points on the obstacle are $C(x_1,y_1)$ and $D(x_2,y_2)$. Then, the coordinates of the target point for obstacle avoidance is the furthest intersection point $F(x_f,y_f)$. Since $UC$ is perpendicular to $OC$, so (20) $\begin{array}{r}UC\cdot OC=0\end{array}$(20) Since the vector $\overrightarrow{OC}=(x_o-x_1,y_o-y_1)$ and the vector $\overrightarrow{UC}=(x_u-x_1,y_u-y_1)$, there is (21) $\begin{array}{r}(x_o-x_1)\cdot (x_u-x_1)+(y_o-y_1)\cdot (y_u-y_1)=0\end{array}$(21) On the other hand, because the point $C(x_1,y_1)$ is a point on the circle, it satisfies the equation of the circle, (22) $\begin{array}{r}\Rightarrow (x_1-x_0{)}^2+(y_1-y_0{)}^2=R^2\end{array}$(22)

Figure 8. UAV obstacle avoidance diagram.

By combining Equations (21) and (22), the coordinates of $C(x_1,y_1)$ can be obtained and the calculation of the point $D(x_2,y_2)$ is the same. Furthermore, the equations of the two tangent lines from the point $U(x_u,y_u)$ to the circular obstacle can be obtained as (23) $\begin{array}{r}\{\begin{array}{c}y-y_u=k_1(x-x_u)\\ y-y_u=k_2(x-x_u)\end{array}\end{array}$(23) By combining Equations (22) and (23), the slopes of the tangents $k_1$ and $k_2$ on different sides of the Apollonius circle are calculated then used for the turning angle.

Step 3. Obstacle avoidance of UAV

In Figure 8, the angle between the line $UC$ and the current direction of velocity $v$ is ${\alpha }_c$, and the angle between the line $UD$ and the current direction of velocity $v$ is ${\alpha }_d$. When ${\alpha }_c<{\alpha }_d$, the UAV moves along the line $UC$, otherwise along the line $UD$. However, in addition to agents with omnidirectional steering such as mecanum wheel, many agents are unable to complete the predetermined path due to the limitation of turning radius. Therefore, the following section further introduces the solution.

5.2. Path optimisation based on turning angle of UAV constraints

Since the UAV is constrained by its manoeuverability, the minimum turning radius or the maximum turning angle needs to be considered (Gao et al., 2020). The constraint of turning angle is the maximum turning angle allowed during the flight of the UAV, and its value depends on the performance and physical conditions of the UAV. Therefore, the angle $\theta$ between the current waypoint and the next waypoint should not exceed the maximum turning angle ${\theta }_{max}$. Assuming the waypoint coordinate is $(x_i,y_i)$, the vector of each segment is (24) $\begin{array}{rl}{a}_i& =(x_i-x_{i-1},y_i-y_{i-1})\end{array}$(24) (25) $\begin{array}{rl}{\theta }_{max}& \ge \arccos \left(\frac{{a_i}^T{a}_{i+1}}{|a_i||a_{i+1}|}\right)\end{array}$(25) In Equation (24), $(x_i,y_i)$ is $i$th waypoint coordinate, $(x_{i\text{ - 1}},y_{i-1})$ is $i-1$th waypoint coordinate, and $(x_{i\text{ + 1}},y_{i+1})$ is $i+1$th waypoint coordinate, respectively. In Equation (25), $a_i$ is the $i$th segment of the UAV’s path, $a_{i+1}$ is the $i+1$th segment of the UAV’s path. The turning angle of the UAV is shown in Figure 9.

Figure 9. Turning angle of UAV.

5.3. Whole process of the algorithm

In the process of obstacle avoidance, when the evader uses the method of Sections 5.1 and 5.2 to move to the direction of the obstacle, the pursuers will keep the parallel movement to avoid the gap between adjacent Apollonius circles. After successfully avoiding obstacles, the game adopts the strategy proposed in Section 4. Under the conditions of Equations (3), (17) and (25), the pursuers can catch the evader and win the game. The overall algorithm is shown in Figure 10.

Figure 10. Flow chart of the pursuit-evasion strategy.

6. Simulation analysis and discussion

In this section, the simulation time interval $\mathrm{\Delta }T$ is set to 1s, and the maximum turning angle ${\theta }_{max}$ is set to ${60}^{\circ }$. In the game, there are five UAVs, of which four is pursuer and one is evader. All the UAVs are randomly distributed in a map large enough and they know other UAV’s position at any time. The initial distance between the pursuers and the evader is greater than the capture radius. According to Equation (17), the velocity ratio of the pursuer and the evader should satisfy (26) $\begin{array}{r}\frac{v_p}{v_e}\ge sin\left(\frac{\pi }{4}\right)\approx 0.707\end{array}$(26)

6.1. Simulation of the encirclement process

The initial positions of the four pursuers are $(1,2)$, $(1,0)$, $(0,1)$ and $(2,2)$, respectively. The velocity of the pursuers is $28\text{m/s}$. The evader stays in $(10,12)$ and the encirclement process is shown in Figure 11.

Figure 11. Encirclement process when the evader is stationary.

Here, an encirclement method via deep reinforcement learning is used to compare with the proposed method. By a deep reinforcement learning framework, Ma et al. (2020) studied the problem of capturing formation pattern around a target.

From Figure 11(a), four UAVs bypass the obstacle in a specific formation and surround the evader. The encirclement process first ensures the formation and the obstacle avoidance, and once an obstacle is found, the formation changes. When the formation reaches near the evader, they adjust their positions to satisfy the initial condition of the collaborative pursuit-evasion game described in Section 5.

Although the shapes of Figure 11(a) and (b) are similar, the two places with red circles in Figure 11(b) are worth noting. The effect of the encirclement via deep reinforcement learning depends on enough training which does not have a uniform standard. Therefore, when there are obstacles, the training times used in the paper of Ma et al. (2020) are insufficient and it causes the agent to be too close to the obstacle sometimes. On the other hand, the convergence of the deep reinforcement learning also determines the size of the error. This is particularly evident in the final encirclement result. For example, the evader in Figure 11(b) is not in the centre of the encirclement.

Figure 12 shows the encirclement process if the evader moves. The position and the velocity of the pursuers are the same as the simulation in Figure 11. The result of Ma et al. (2020) is also provided in Figure 12(b). The evader starts from the position of $(10,12)$ and performs linear motion with uniform acceleration. The initial velocity of the evader is $10\text{m/s}$ and the maximum velocity is $50\text{m/s}$. Compared with Figure 12(a), Figure 12(b) has a shorter path but the curvature of the green path is relatively large, it may be due to overtraining. In the other hand, from the final relative positions of the pursuers and evader, Figure 12(a) has a better encirclement effect, that is, evader is in the centre of the encirclement.

Figure 12. Encirclement process when the evader moves.

In Figure 12, the larger red circle indicates the range of motion of the evader. Due to the different velocity of the evader, it can be seen that the final formation of Figure 11 is larger than that of Figure 12, but the pursuers can still complete the encirclement of the evader. In Figure 11(b), the error of the deep reinforcement learning may result in that the evader is not in the centre of the encirclement, which may affect the calculation of the pursuit-evasion game.

6.2. Simulation of the collaborative pursuit-evasion game without obstacle

6.2.1. Obstacle-free and semi-enclosed state with multi-pursuers

The initial coordinate of the agents are $E=[\text{110,100}]$, $P_1=[175,105]$, $P_2=[110,180]$, $P_3=[30,162]$ and $P_4=[105,35]$. The velocity of pursuers and evader is $V_p=3.1\text{m/s}$ and $V_e=4\text{m/s}$, respectively. In the initial state, the evader is in the encirclement formed by the pursuers. During the game, the evader finds a gap between the adjacent Apollonius circles of the pursuers. So the evader moves toward the gap and pursuers use the strategy of semi-enclosed state in Section 4.2. Since the velocity of the pursuers is lower than that of the evader, the evader finally escapes, as shown in Figure 13.

Figure 13. The evader escapes from the gap.

6.2.2. Obstacle-free and fully enclosed state with multi-pursuers

The initial coordinate of the agents are $E=[325.7,305.5]$, $P_1=[203.6,493.5]$, $P_2=[400.6,336.0]$, $P_3=[350.9,250.9]$ and $P_4=[106.9,150.6]$. The velocity of pursuers and evader is $V_p=3.8\text{m/s}$ and $V_e=4\text{m/s}$, respectively. In the initial state, the evader is completely surrounded by the pursuers, and the pursuers and the evader use the strategy of Case 3 (fully enclosed state) to play the game. In Figure 14, although the evader changes the direction of escape, the evader is still completely surrounded by the pursuers. Finally, the evader is captured within the capture radius.

Figure 14. The evader is captured by the pursuers.

According to Figure 14, when there is no obstacle, if the pursuers and evader can satisfy the proposed conditions, the pursuers can successfully capture the evader. In addition, the angle between each segment of the path is less than the maximum turning angle, which satisfies the manoeuver constraints of the UAV. When the initial velocity of the pursuers changes, the results are shown in Table 1.

Table 1. Simulation results of different pursuer’s velocity.

Initial position (m)	$V_e(m/s)$	$V_p(m/s)$	Winner	Capture time(s)
$E$  = [325.7;305.5]	4	2.2	evader	∞
$P_1$ = [203.6;493.5]	4	2.6	evader	∞
$P_2$ = [400.6;336.0]	4	3.0	pursuers	75
$P_3$ = [350.9;250.9]	4	3.4	pursuers	70
$P_4$ = [106.9;150.6]	4	3.8	pursuers	64

From Table 1, it can be seen that in an obstacle-free environment, when the initial position and velocity of the agents are constant, the capture time is related to the velocity of the pursuers. Under the conditions of Equations (3), (11) and (19), the higher the velocity of the pursuers, the shorter the time it takes to capture the evader, which is consistent with the conclusion of the Reference (Yan et al., 2019).

6.3. Simulation of the collaborative pursuit-evasion game with a circular obstacle

6.3.1. Influence of the obstacle and the manoeuver constraints

At this time, there is a circular obstacle in the environment. Three algorithms evolved from the proposed algorithms are used for the analysis and discussion in this section. Especially, a cooperative strategy for pursuit-evasion problem with collision avoidance proposed by Sun et al. (2022) is used for the comparative simulation. The algorithms are as follows.

1. Algorithm I can deal with the turning angle constraints in the obstacle-free environment.

2. Algorithm II cannot deal with the turning angle constraints but it can work in the environment with obstacle.

3. Algorithm III is the proposed method and it can deal with the turning angle constraints in the environment with obstacle.

4. Algorithm IV is proposed by Sun et al. (2022) and it is a flexible self-organising cooperation strategy which can avoid irregular obstacles.

In the figure, the circular obstacle is represented by a black circle whose radius $R$ is 10 and the centre coordinate is $[280,305]$. The maximum turning angle ${\theta }_{max}$ is set to ${60}^{\circ }$. The initial coordinate of the agents are $E=[325.7,305.5]$, $P_1=[203.6,493.5]$, $P_2=[\text{450}\text{.6,376}\text{.0}]$, $P_3=[\text{380}\text{.9,220}\text{.9}]$ and $P_4=[106.9,150.6]$. The velocity of pursuers and evader is $V_p=3.8\text{m/s}$ and $V_e=4\text{m/s}$.

The result of Algorithm I, II, III and IV is respectively shown in Figure 15 and summarised as Table 2 for the analysis of the influence of obstacle and manoeuver constraints.

Figure 15. Simulation results.

Table 2. Comparison of capture time of different algorithms.

Algorithm	Maximum turning angle of pursuers’ path	Capture time	Average path length of pursuers
I	45°	64s	239.56m
II	129°	77s	288.80m
III	56°	83s	316.13m
IV	129°	92s	334.76m

Compared with Figure 15(a) and (c), it can be seen that the Algorithm III will travel longer distances in the game because of the obstacle. The obstacle makes the evader have more opportunity to escape, which causes the pursuers to spend more time to catch the evader.

Compared with Figure 15(b) and (c), there is a larger turning angle in the path of Algorithm II and its value is ${129}^{\circ }$ which is greater than the maximum turning angle ${60}^{\circ }$. Algorithm III can deal with the turning angle constraints, so the maximum angle of its path is ${56}^{\circ }$ which is more reasonable. In addition, the path of Algorithm III needs fewer manoeuvers, but at the cost of path length. However, only the shortest path is meaningless, it must be under the premise of satisfying the turning angle constraint. The simulation results show that the proposed method is more valuable and can deal with the physical constraints of UAV and obstacle constraints.

Compared with Figure 15(d) and (b), the paths in the two figures are similar, but the capture time in Figure 15(d) is longer than that in Figure 15(b). This phenomenon is also confirmed by Table 2. It is because the Algorithm IV treats obstacle avoidance as a priority higher than the pursuit task, which means the Algorithm IV will first consider obstacle avoidance and then capture. However, if obstacle avoidance and pursuit-evasion are not considered at the same time, the result of obstacle avoidance is likely to change the solution space of the pursuit-evasion game, leading to a longer capture time and even changing the outcome of the game. Therefore, the obstacle avoidance should be accompanied by the update of the capture condition to ensure the rationality of the pursuit-evasion results rather than separating them.

In summary, Figure 15 shows that the obstacle constraints and manoeuver constraints have a great impact. Obstacle constraints and manoeuver constraints are strong constraints that are difficult to ignore, so their existence will further compress the solution space of pursuit-evasion game, making the solution more complex. At present, if the information of both pursuer and evader is completely symmetrical (that is, the actions of them are completely known to each other), it is difficult to say which one will benefit more from the constraints. However, if the information is incomplete, for example, the pursuer only has Line-of-Sight (LOS) vision (Zou & Bhattacharya, 2019), the existence of obstacles is likely to be beneficial to the evader.

6.3.2. Influence of the size of the obstacle

Most initial parameters of the experiment are the same as that of Section 6.2.1, and the difference is the radius of obstacle. In this section, the radius of obstacle R=30m. The simulation results are shown in Figure 16. The pursuers take 91s to capture the evader.

Figure 16. Influence when the radius of obstacle is R=30m.

In this theory, the larger the obstacle is, the longer the evader takes to bypass the obstacle (Noori & Isler, 2014). Compared with Figure 16 in Section 6.2.1 and Figure 16, the larger obstacle will prolong the capture time. If the game takes place in a map with infinite size, the proposed method will still ensure the pursuers win. However, if the map is limited, the size of the obstacle is likely to change the result of the game. In addition, Figure 16 shows that the larger obstacle will make the path smoother.

6.3.3. Discussion on the complexity and limitation of the scheme

Based on the overall scheme in Figure 1 of Section 2.2, the whole task consists of the encirclement stage and the pursuit-evasion stage. In the encirclement process, consensus control is improved by obstacle information to achieve formation and obstacle avoidance. Consequently, it is necessary to traverse the number $M$ of obstacles to calculate the control quantity of each UAV and the complexity of $N$ UAVs is $O(N\ast M)$. In the pursuit-evasion process, assuming that the number of obstacles in the combat area is $m<M$ (Here, $m=1$ in Section 5), so the complexity of this stage is $O(N\ast m)$. Therefore, the complexity of the overall scheme is $O(N\ast M)+O(N\ast m)=O(N\ast M)$. It can be seen that due to the existence of obstacles, the complexity of the scheme is $M$ times larger than that of the obstacle free case.

Regarding the limitation of the scheme, the algorithm is still possible to be improved. For example, it can only deal with single obstacle for the time being. Thus, the case of multiple obstacles is one of the most important works in the future. On the other hand, the algorithm is improved from the two-dimensional (2D) Apollonius circle, so the three-dimensional (3D) case is also the current work. Based on our current research, it is not appropriate to use geometric methods directly for the analysis in 3D case, since that the complexity and computation amount will increase explosively. Therefore, it is possible to combine geometric methods with analytical methods, such as the interfered fluid dynamical system (IFDS) (Yao & Qi, 2019) in recent years.

In addition, the minimum number of pursuers is worth discussing. In the paper, the number of pursuers is 4. Although the pursuers may still win after reducing the number of pursuers, but the winning rate will decline according to the simulation results. So, what is the most appropriate number of pursuers? Many researchers put forward their own views. Meir et al. (2020) propose a state feedback capture strategies and an evader strategy that yields a lower bound on his/her time-to-capture are devised using a geometric method. However, these strategies are optimal only in a part of the state space where a strategic saddle point is obtained and the value of the differential game is established. In other words, environment with obstacles means that the solution space is non convex and has holes, which makes it very difficult to discuss Nash equilibrium. It is certain that capture bound is related to the number of obstacles, and the initial position and speed of the agents.

7. Conclusion

In the game of a two-dimensional plane with a circular obstacle, a collaborative pursuit-evasion mission of multi-UAVs is studied. In the encirclement process, the formation and obstacle avoidance method based on leader-follower mode is designed. Then, based on Apollonius circle, the strategy of the pursuers with lower velocity and superior evader in an obstacle-free environment is proposed, respectively. In terms of the physical constraints of UAV and obstacle constraints, a geometric calculation method is used to improve the strategy. The main conclusions are as follows:

1. In the obstacle-free environment, when the pursuers and the evader satisfy Equations (3), (11), and (19), the pursuers can catch the evader.

2. By cooperation, the pursuers can make up for the disadvantages caused by the lower velocity.

3. The obstacle makes the evader have more opportunity to escape, which causes the pursuers have to spend more time to catch the evader. Furthermore, if the map is limited, the size of the obstacle is likely to change the result of the game.

In the future, the influence of multi-obstacles and different shapes of obstacles will be analysed. In addition, the three-dimensional pursuit-evasion game is also one of the important works.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by Foundation of Liaoning Province Education Administration [grant number LJKZ0221]; National Natural Science Foundation of China [grant number 61503255,61973222]; Liaoning Revitalization Talents Program [grant number XLYC1907179].