Two-Layer Optimization Algorithm for Multi-UAV Conflict Resolution considering Individual Fairness

Abstract

In order to solve the unfair individual payment costs problem in the low-altitude unmanned aerial vehicle (UAV) conflict resolution process, a multi-UAV conflict resolution algorithm based on the cooperative game concept “coalition complaint value” is proposed. Firstly, based on the low-altitude multi-UAV conflict scene characteristics, according to the “coalition complaint value” concept, the UAV conflict resolution payment matrix is established. Secondly, combined with the advantages of the artificial potential field (APF) method and the genetic algorithm (GA), a hybrid solution strategy for conflict resolution based on APF-GA is proposed. The final simulation results show that the APF-GA hybrid solution strategy has the best efficiency by combining the three evaluation indicators of calculation time, feasibility, and system efficiency. The reliability of the proposed algorithm is verified based on the Monte Carlo algorithm. The solution strategy based on the cooperative game “coalition complaint value” can improve individual fairness to a certain extent. At the same time, it can achieve the rapid planning goal with priority drones at the expense of a small amount of overall benefits.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

With the development of aviation technology, UAVs have gradually entered the low-altitude fusion airspace due to their strong maneuverability, convenient operation, and low cost. And they have been widely used in many fields such as military, agriculture, logistics, and fire control [1]. Currently, isolated airspace for UAVs and strict approval and control are generally adopted to reduce operational risks. However, as the scale of UAVs continues to increase, it brings huge challenges to UAV air traffic management. Therefore, it is significant to study the low-altitude multi-UAV conflict resolution technology under free flight for the UAV safe operation and the low-altitude airspace resources efficient utilization. At the same time, after entering the low-altitude fusion airspace, the UAV can assist in the management of public safety (PS) by establishing elastic and reliable public safety networks (PSNs), having characteristics such as fast deployment, adaptive operation, coverage guarantees, and low latency [2].

The problem of multi-UAV conflict resolution is a typical complex system, which has the characteristics of large scale, nonlinear, multiconstrained, and high dimensional. It needs to find effective methods to simplify and solve. In recent years, many intelligent optimization algorithms and optimizers have been proposed to solve some practical and complex problems. Currently, the more mature methods for multi-UAV conflict resolution include intelligent algorithms, potential field method, and mathematical optimization methods. Based on the classic ant colony optimization (ACO) algorithm; Tang et al. [3] proposed a multi-UAV conflict resolution based on the speed adjustment strategy and the heading adjustment strategy, and it improved the computational efficiency. Perez-Carabaza et al. [4] optimized the ACO based on the target probability and spatial attributes to improve the convergence speed. Liu et al. [5] combined the APF method with the ACO. Firstly, the APF method was used to quickly search for the initial conflict resolution path, and then, the ACO was used for global optimization; it was both time-effective and feasible. Kim and Yoon [6] proposed a low-altitude unmanned airspace drone cooperative collision avoidance method based on satisfaction game. By combining self-preferences and cooperative preferences to make individual heading decisions, the satisfaction framework provides a strategy to avoid conflicts, and it can increase throughput while reducing unnecessary conflicts. Based on the mathematical optimization algorithm, Yang et al. [7] proposed a two-layer optimization of multi-UAV conflict resolution. First, the stochastic parallel gradient descent method was used to search for the initial solution, and, then the mixed integer linear programming model was used to accurately plan the path. Cai and Zhang [8] proposed a mixed-integer nonlinear programming conflict resolution method. It stipulates that the aircraft is allowed to change the speed and altitude to maintain the interval. Hernández-Romero et al. [9] proposed an aircraft conflict resolution method considering the wind forecast uncertainty influence, and they expressed the problem as a constrained nonlinear programming problem.

The conflict resolution method based on APF has the rapid planning characteristics. However, it often falls into the local optimum and cannot get the global optimum solution. It often generates paths with state mutations, which is not suitable for UAV performance constraints. As a new global optimization search algorithm, the GA algorithm is widely used in nonlinear system optimization problems due to its simple and universal, strong robustness, and suitability for parallel processing. However, due to the complex coding and random search of the initial population, the computational complexity is often high. In this paper, combining the advantages of APF and GA, a hybrid multi-UAV conflict resolution method is proposed. APF is used to search the initial solution quickly. GA is used to search the global optimization, so as to obtain the resolution method, which satisfies the UAV flight constraints.

At the same time, the current research on multi-UAV conflict resolution is limited to the optimal overall efficiency and ignores the fairness issues and priority of individual UAV resolution. In low-altitude airspace, the urgency of UAV missions is different, so it is necessary to consider the factors of different UAV priorities and individual fairness in the resolution process. Based on the cooperative game theory, this paper applies the concept of “coalition complaint value” to the conflict resolution field and studies the individual conflict resolution methods considering priority and fairness.

The contributions of this paper mainly include the following:

(1) A multi-UAV conflict resolution strategy with better comprehensive performance was proposed

(2) A welfare distribution strategy that considers individual fairness to ensure individual fairness in the UAV conflict resolution process was proposed

(3) A strategy that can ensure the rapid arrival of UAVs with high priority was proposed

2. Conflict Resolution Strategy Based on the “Coalition Complaint Value” of Cooperative Game

Cooperative game is an important part of game theory. It is widely used in management, resource allocation, business, and other fields. Cooperative game has many important distribution solutions, such as nucleolus and Shapley value.

In the process of studying the cooperative game solution, the coalition complaint value is an important concept. It measures the coalition dissatisfaction with the distribution plan. The larger the coalition complaint value, the more dissatisfied the alliance is with the income distribution plan. Scholars have proposed some solutions to cooperative game based on the coalition complaint value. Tae et al. [10] and Baïou and Barahona [11] first based on the coalition complaint value and obtained the prenucleolus and nucleolus of the cooperative game through the lexicographic method. In recent years, scholars have expanded the coalition complaint value and proposed other types of complaint values. Mu and Han [12] put forward the optimistic complaint value and pessimistic complaint value of the coalition. Sakawa and Nishizaki [13] defined the personal complaint value by summing the coalition complaint value where the player belongs. Kong et al. [14] defined the individual jealousy complaint value by considering both the coalition to which the player belongs and its complementary coalition.

When multi-UAVs are engaged in conflict resolution in the low-altitude airspace, individual UAVs tend to choose the strategy beneficial to their own side for conflict resolution. In order to balance UAV individual fairness, based on the characteristics of low-altitude UAV conflict resolution and cooperative game, the “alliance complaint value” idea in cooperative game is introduced. The minimum “alliance complaint value” is used as a negotiation strategy between conflicting parties. The “alliance complaint value” essence in the cooperative game is to minimize the maximum coalition dissatisfaction value. The solution is unique. The following defines the “alliance complaint value” in conflict resolution.

In the cooperative game two-tuple $N,\upsilon$, the player set is $N=a_1,a_2,\cdots ,a_P$, and $\upsilon$ is the payment value [15, 16]. In the grand coalition structure, $S=s_1,s_2,\cdots ,s_K$ is the conflict resolution strategies set. For each resolution strategy $s_{k}k=1,2,\cdots ,K$, the conflict UAV cost is denoted as $\upsilon s_k,a_{i}k=1,2,\cdots ,K,i=1,2,\cdots ,P$. Referring to the excess value definition of cooperative game, the new excess value definition is $e{s}_k,a_i=\upsilon s_k,a_i$. It represents the dissatisfaction level of the individual paying the price in the grand coalition. The closer the excess value is to 0, the smaller the individual dissatisfaction degree. The excess value $e{s}_k,a_i$ of all conflicting individuals in the resolution strategy $s_k$ is arranged in order from large to small. The sequence is marked as $\epsilon s_k$.

Definition 1.

There is a unique configuration $\gamma$ in all the cooperative game grand coalition set $N$. And it meets the validity configuration, such that $$\begin{array}{}\text{(1)}& \epsilon \gamma {\prec }_{les}\epsilon x\hspace{1em}\forall x\in N,x\ne \gamma ,\end{array}$$

where $\gamma$ is defined as the minimum “coalition complaint value” in the cooperative game. ${\prec }_{\text{les}}$ is defined as “lexographically less.” If $y{\prec }_{\text{les}}z$, where $y$ and $z$ are both $k$-dimensional vectors, then $l\in 1,\cdots ,k$ exists, such that $y_1=z_1,\cdots ,y_{l-1}=z_{l-1},y_l<z_l$ is true. It should be noted that the cardinality of $x$ and $\gamma$ are not important. When the cardinality is changed to one dimension, the size of the two can be directly compared. It is easy to see that the nonempty minimum “coalition complaint value” exists in every cooperative game.

2.1. UAV Conflict Resolution Grand Coalition Payment Matrix

For a grand coalition with the number of UAVs $N=P$, if there are $K$ conflict resolution strategies, the grand coalition payment matrix $V$ is expressed as $$\begin{array}{}\text{(2)}& V=\begin{array}{ccc}\upsilon s_1,a_1& \cdots & \upsilon s_1,a_P\\ ⋮& & ⋮\\ \upsilon s_K,a_1& \cdots & \upsilon s_K,a_P\end{array}.\end{array}$$

In the formula, $\upsilon s_k,a_{i}k=1,2,\cdots ,K,i=1,2,\cdots ,P$ represents the resolution payment value of the $i$th UAV under the $k$th resolution strategy.

For the $k$th $k=1,2,\cdots ,K$ resolution strategy, arrange the resolution payment value in descending order to obtain the sequential payment matrix $V^{\prime }$: $$\begin{array}{}\text{(3)}& V^{\prime }=\begin{array}{ccc}\max \upsilon s_1,a_i& \cdots & \min \upsilon s_1,a_i\\ ⋮& & ⋮\\ \max \upsilon s_K,a_i& \cdots & \min \upsilon s_K,a_i\end{array},\end{array}$$

where $\max \upsilon s_k,a_i$ is the maximum value of the $k$th row in matrix $V$, $\min \upsilon s_k,a_i$ is the minimum value of the $k$th row in matrix $V$. According to Definition 1, the conflict resolution “coalition complaint value” can be determined.

2.2. UAV

In conflict UAV group $A,\upsilon$, if there is a high-priority individual$i^{\ast }$performing emergency tasks such as rescue and disaster relief, the UAV $i^{\ast }$ payment cost $\upsilon s_k,a_{i^{\ast }}$ is regarded as the largest in all conflict resolution solutions, that is, $\max \upsilon s_k,a_i=\alpha \upsilon s_k,a_{i^{\ast }}k=1,2,\cdots ,K,i=1,2,\cdots ,A$, $\alpha$ is the gain coefficient. Its value must satisfy the following conditions. $$\begin{array}{}\text{(4)}& \alpha >\max \frac{\max \upsilon s_k,a_i}{\min \upsilon s_k,a_i}k=1,2,\cdots ,K.\end{array}$$

The UAV sequential payment matrix $V^{\prime }$ is expressed as $$\begin{array}{}\text{(5)}& V^{\prime }=\begin{array}{ccc}\max \upsilon s_1,a_i& \cdots & \min \upsilon s_1,a_i\\ ⋮& & ⋮\\ \max \upsilon s_K,a_i& \cdots & \min \upsilon s_K,a_i\end{array}=\begin{array}{ccc}\alpha \upsilon s_1,a_{i^{\ast }}& \cdots & \min \upsilon s_1,a_i\\ ⋮& & ⋮\\ \alpha \upsilon s_K,a_{i^{\ast }}& \cdots & \min \upsilon s_K,a_i\end{array}.\end{array}$$

That is to say, the UAV conflict resolution strategy must be produced in the scheme that has the priority UAV $i^{\ast }$ to pay the least cost, so as to ensure that UAV $i^{\ast }$ task is processed first and the task is completed first.

Here is a toy example to illustrate the selection process of the minimum “coalition complaint value” in the cooperative game.

Suppose there is $5\times 6$ grand coalition payment matrix $V$, which means there are 5 conflict resolution strategies and 6 conflict individuals. $$\begin{array}{}\text{(6)}& V=\begin{array}{cccccc}4& 6& 8& 7& 2& 3\\ 1& 6& 7& 2& 4& 3\\ 8& 5& 4& 5& 1& 4\\ 3& 5& 8& 7& 5& 1\\ 4& 5& 6& 3& 6& 5\end{array}.\end{array}$$

Arrange each row of the payment matrix in the order from largest to smallest to obtain the sequential payment matrix $V^{\prime }$. $$\begin{array}{}\text{(7)}& V^{\prime }=\begin{array}{cccccc}8& 7& 6& 4& 3& 2\\ 7& 6& 4& 3& 2& 1\\ 8& 5& 5& 4& 4& 1\\ 8& 7& 5& 5& 3& 1\\ 6& 6& 5& 5& 4& 3\end{array}.\end{array}$$

According to the minimum “coalition complaint value” concept in the cooperative game, the 5th conflict resolution strategy is the optimal solution, and it can ensure the individuals fairness to the greatest extent.

If the 4th conflicting individual has the allocation priority, $\alpha$ is 8, and the sequential payment matrix $V^{\prime }$ becomes $$\begin{array}{}\text{(8)}& V^{\prime }=\begin{array}{cccccc}32& 8& 7& 6& 3& 2\\ 24& 7& 6& 4& 2& 1\\ 32& 8& 5& 5& 4& 1\\ 40& 8& 7& 5& 3& 1\\ 40& 7& 6& 5& 4& 3\end{array}.\end{array}$$

At this point, the optimal solution is the 2nd conflict resolution strategy.

3. Search Algorithm for Optimal Resolution Strategy Based on APF-GA

According to the ATC (air traffic control) safety regulations and the UAV actual flight situation, the UAV conflict resolution problem has been reasonably simplified.

(1) Considering that the UAV is flying at a fixed altitude during actual flight, except during take-off and landing, and taking into account the UAV fuel consumption, the UAV conflict resolution is simplified into two-dimensional plane

(2) It is assumed that the UAV speed does not change significantly during the actual cruising flight, so it is assumed that the UAV speed remains unchanged. When the UAV executes the release strategy, three maneuvering strategies can be adopted, that is, maintaining the original heading, yawing 30° to the left and yawing 30° to the right

(3) Assuming that UAVs are equipped with ADS-B surveillance equipment, the UAV position, speed, and altitude information at each time point can be obtained. Meanwhile, the UAV target position is known

Assuming that the UAVs in the airspace are all agents, all drones can obtain local and surrounding drone status data through ADS-B. They can communicate with ground station, as shown in Figure 1. The low-altitude UAV system is a distributed multi-intelligence system. The conflict between UAV and other UAVs is a kind of dynamic cooperative task solving problem. The process of proposing a conflict resolution mechanism is as follows.

[figure omitted; refer to PDF]

Step 1: all UAVs with associated conflicts form a conflict group.

Step 2: the UAV in the conflicting group upload their respective status and attribute data to the ground station.

Step 3: the ground station forms a conflict resolution plan based on the negotiation strategy.

Step 4: plans are issued to each UAV and executed.

3.1. Artificial Potential Field Method

The APF method constructs an abstract artificial potential field through simulation to carry out trajectory planning. The APF is composed of a gravitational field, repulsive field, and vortex field. The gravitational field is generated by the target point position and acts on the UAV. The potential field vector direction is from the UAV to the target point, and the potential energy is inversely proportional to the distance to the target point. The repulsive field is generated by obstacles. The potential field vector direction points from the obstacle to the UAV, and the potential energy is inversely proportional to the distance to the obstacle. The vortex field is tangent to the repulsion field [17, 18]. As shown in Figure 2, the position coordinate of UAV $i$ is $p_i=x_i,y_{i}i=1,2,3,\cdots ,N$, and $N$ is the UAV number in the area.

[figure omitted; refer to PDF]

For UAV $i$, the target position is $p_{gi}=x_{gi},y_{gi}$. In order to ensure that the UAV is close to the target point, the gravity is defined as the negative gradient of the gravitational field. Then, the gravitational potential field function $U_a{p}_i$ and gravity $F_a{p}_i$ are expressed as $$\begin{array}{c}\text{(9)}& U_a{p}_i=\frac{1}{2}{k}_{ai}{p_i-p_{gi}}^2,F_a{p}_i=-\nabla U_{a}X=‐k_{ai}{p}_i-p_{gi}.\end{array}$$

In the formula, $k_{ai}$ is the gravitational constant. Its value is greater than 0.

In order to realize the collision problem when multi-UAVs are gathered and run, the repulsion field $U_r{p}_i,p_j$ will be excited between the UAV $i$ and UAV $j$. Define the repulsion force as the negative gradient of the repulsion field. Then, the repulsion potential field function $U_r{p}_i,p_j$ and the repulsion force $F_r{p}_i,p_j$ are $$\begin{array}{c}\text{(10)}& U_r{p}_i,p_j=\begin{array}{cc}\frac{1}{2}{k}_{ri}{\frac{1}{p_i-p_j}-\frac{1}{{\rho }_0}}^2,\hfill & p_i-p_j\le {\rho }_0,\hfill \\ 0,\hfill & p_i-p_j>{\rho }_0,\hfill \end{array}{F}_r{p}_i,p_j=-\nabla U_r{p}_i,p_j=\begin{array}{cc}{k}_{ri}\frac{1}{p_i-p_j}-\frac{1}{{\rho }_0}\frac{1}{{p_i-p_j}^2}\cdot \frac{\partial p_i-p_j}{\partial X},\hfill & p_i-p_j\le {\rho }_0,\hfill \\ 0,\hfill & p_i-p_j>{\rho }_0.\hfill \end{array}\end{array}$$

In the formula, $k_{ri}$ is the repulsive force constants. Its value is greater than 0. ${\rho }_0$ represents the range of the UAV’s repulsive force field. When the UAV $i$ is in the range of the UAV F’s repulsive force field, it will be subjected to a repulsive force.

In order to prevent UAVs from randomly turning to generate a large number of redundant paths in the conflict resolution process, it is necessary to introduce rules to ensure that UAVs turn in unison, so a vortex field is introduced, and it is tangent to the repulsion field. $$\begin{array}{}\text{(11)}& F_v{p}_i,p_j=\pm \frac{\partial U_r{p}_i,p_j}{\partial y}-\frac{\partial U_r{p}_i,p_j}{\partial x}.\end{array}$$

Superimpose the gravity, repulsion, and vortex forces experienced by the UAV to obtain the UAV operating equation in the conflict resolution process: $$\begin{array}{}\text{(12)}& \stackrel{·}{p_i}=\frac{F_{a}p,p_{gi}}{F_a{p}_i,p_{gi}}+\sum _j{F}_r{p}_i,p_j+F_v{p}_i,p_j,j=1,2,\cdots ,N,i\ne j.\end{array}$$

Both the repulsive force and the vortex force are taken between 0 and 1 to control the UAV to avoid collisions. The gravity is normalized so that the force received by the UAV is kept at the same order of magnitude; so as to avoid the large difference between the forces, it may lead to the conflict resolution failure or the generation of redundant paths.

Normalize the UAV motion equation $\stackrel{·}{p_i}$ to get the speed direction. Assuming the speed is $k_i$, the UAV speed can be expressed as $$\begin{array}{}\text{(13)}& v_i=k_i\frac{\stackrel{\cdot }{p_i}}{\stackrel{\cdot }{p_i}}.\end{array}$$

Using the UAV resolution speed $v_i$, iterate gradually according to the time step, and obtain the multi-UAV conflict resolution trajectory.

3.2. Genetic Algorithm

GA is a global optimization probability search algorithm formed by simulating the genetic and evolution process of living beings in the natural environment. It repeatedly acts on the entire evolutionary group through operation operators such as selection, crossover, and mutation. Finally, the optimal solution or approximate optimal solution of the problem is obtained [19–21].

3.2.1. Coding Method

Divide the path from the initial position to the target position of the $N$ UAVs into $L$ steps, respectively. Through analysis, the UAV has three steering strategies. If the UAV reaches point $B$ from point $A$ at time $t$, then, the reachable positions at time $t+1$ are $C_1$, $C_2$, and $C_3$. If the UAV current position and heading information matrix is denoted as $A_{k}x,y,\theta$, the next step UAV information matrix is denoted as $A_{k+1}x+vt\cos {\theta }^{\prime },y+vt\sin {\theta }^{\prime },{\theta }^{\prime }$. In the formula, ${\theta }^{\prime }$ can take $\theta +\pi /6$,$\theta$ and $\theta -\pi /6$ three kinds of adjustment strategies.

If the three UAV maneuvering strategies are coded as -1 (representing a 30° left turn), 0 (representing a heading maintenance), and +1 (representing a right turn 30°), the UAV system conflict resolution strategy can be encoded into $N\times L$-dimensional vector $X=x_1,x_2,\cdots ,x_{N\times L}$, $x_i\in -1`0`+1$. The specific encoding structure is shown in Table 1.

Table 1

UAV conflict resolution strategy coding diagram.

UAV 1			…	UAV $N$
Step 1	…	Step L	…	Step 1	…	Step $L$
0	0	1	…	0	0	1

3.2.2. Objective Function and Constraints

The UAV uses appropriate maneuvers to resolve conflicts in accordance with the prescribed coding strategy. At the end of the resolution process, the UAV reaches the shortest distance from the destination. Therefore, the fitness function for conflict resolution is set as $$\begin{array}{}\text{(14)}& f=\min \sum _{i=1}^N{\text{Delay}}_i.\end{array}$$

In the formula, ${\text{Delay}}_i$ represents the $i$th UAV delay distance from the destination at the end of conflict resolution. The smaller the delay distance is, the better the conflict resolution effect. Denote the position of UAV $i$ at the $k$th step as $A_i^k$, then, the UAV $i$ delay distance ${\text{Delay}}_i$ is expressed as the Euclidean distance between the position $A_i^L{x}_i^L,y_i^L$ after $L$ steps and the destination position $B_i{x}_g,y_g$; it is expressed as $$\begin{array}{}\text{(15)}& {\text{Delay}}_i=A_i^L-B=\sqrt{{x_i^L-x_g}^2+{y_i^L-y_g}^2}.\end{array}$$

In order to avoid the UAV collision in the conflict resolution process, it is required that the distance between UAV $i{x}_i,y_i$ and$j{x}_j,y_j$ maintains a minimum safety interval at any time: $$\begin{array}{}\text{(16)}& \sqrt{{x_i-x_j}^2+{y_i-y_j}^2}>d.\end{array}$$

In the formula, $d$ represents the minimum safe interval among UAVs.

3.2.3. Selection, Crossover, and Mutation

According to the fitness of each individual in the group, the roulette method is used to select the fittest survival among the individuals in the group. According to the crossover probability $P_C$, two parent individuals are randomly selected from the group for single-point crossover to generate new individuals. Taking into account that the one-point crossover operator is less likely to destroy individuals with higher fitness values, this method is adopted to ensure the superiority of increasing the population. As shown in Figure 3. In the meantime perform gene flip mutation with probability $P_{\text{m}}$.

[figure omitted; refer to PDF]

Step 1: initialize the parameters. Set the initial conflict position $p_i^0=x_i^0,y_i^0$ and target point $p_{gi}=x_{gi},y_{gi}$ for the UAVs in the area.

Step 2: force analysis of the potential field. Calculate the gravitational force $F_a{p}_i,p_{gi}$, repulsion force $F_r{p}_i,p_j$, and vortex force $F_v{p}_i,p_j$ of each UAV and calculate the motion equation of each UAV according to formula (12).

Step 3: update location. According to the calculated UAV speed direction and given speed size, step length, and other information, iteratively update the position step by step.

Step 4: judge the result. To monitor in real time whether the ${\text{UAV}}_i$ has reached its destination $p_{gi}=x_{gi},y_{gi}$, if it has reached the destination, the conflict resolution process is completed; if it has not been reached, it turns to Step 3 to update the position.

Step 5: the initial path generated by the APF method is approximated and encoded and set as the initial value of the GA search.

Step 6: apply the concept of “coalition complaint value” in cooperative game to the conflict resolution process, calculate the fitness value of each body in the group, and iterate the population information through the selection, crossover, mutation, and other operations in the GA algorithm, so as to obtain the optimal calculation result of the global area and corresponding conflict resolution path.

Step 7: if the specified termination condition is reached, the final conflict resolution path will be output; if not, turn to Step 6 to iterate until the requirements are met.

5. The Simulation Analysis

5.1. Setting of Simulation Scene

5.1.1. Scenario 1: Multi-UAV Opponent Conflict Scene

In a classic conflict scenario, UAVs are uniformly distributed on the boundary of the circular conflict zone with their velocities pointing to the circle center. Assuming that the conflict circle radius is 100 m, the initial paths are linear, as shown in Figure 5. By changing course, UAVs can reach their respective destinations while ensuring a safe interval between them. As an extreme case, classical conflict scenario can better test the merits and demerits of conflict resolution algorithm. For $N$ conflict individuals, there are $N\times N-1/2$ distance curves in the conflict resolution process.

[figure omitted; refer to PDF]

In this calculation example, it is assumed that each cluster contains 4 individual UAVs. The start position and end position are, respectively, UAV1: (0-60), (0 100); UAV2: (0-90), (0 70); UAV3: (0 -120), (0 40); UAV4: (0-150), (0 10); UAV5: (-150 0), (10 0); UAV6: (-120 0), (40 0); UAV7: (-90 0), (70 0); and UAV8: (-60 0), (100 0), unit: m.

5.1.3. Scenario 3: UAV Conflict Scene in the Square Airspace

As shown in Figure 7, the conflict area is a block area of $200\text{m}\times 200\text{m}$, the headings of the conflicting UAVs all point to the center of the block area, and the initial routes are straight lines. The UAVs complete the obstacle avoidance process through the conflict resolution strategy.

[figure omitted; refer to PDF]

The parameters required for simulation in the three conflict scenarios are shown in Table 2.

Table 2

Simulation parameter setting.

Parameter	Value	Parameter	Value
$$d$$	20 m	$$\alpha$$	100
$$k_{ri}$$	1	$$L$$	200
$$k_{vi}$$	1	$$P_C$$	0.02
$$k_i$$	1	$$P_{\text{m}}$$	0.7
$${\rho }_0$$	50 m	$$N_{\max }$$	100

5.2. Algorithm Validation

Taking the 2, 6, and 10 aircraft-to-flight conflict scenario in scenario 1 as an example, two algorithms, APF and APF-GA, are used to solve the solution strategy. The results are shown in Figures 8 and 9.

[figures omitted; refer to PDF]

[figures omitted; refer to PDF]

In order to visually demonstrate the effectiveness of the algorithm proposed in this paper, the convergence curves of 2 UAVs, 6 UAVs, and 10 UAVs are shown in Figure 10. After analyzing the simulation phenomenon, it can be seen that the algorithms can converge quickly without oscillation. Figure 11 shows the running distance of the convergence curve of 2, 6, and 10 UAVs, respectively. There is $2\times 1/2=1$ distance curve during the 2 UAVs’ conflict resolution process, $6\times 5/2=15$ distance curve exists during 6 UAVs’ conflict resolution process, and $10\times 9/2=45$ distance curve exists during 10 UAVs’ conflict resolution process. According to the simulation data, it can be seen that the distance during the UAV operation is greater than the safety interval $d=20$ m, indicating that the solved conflict resolution path meets the safety constraints. It should be noted that due to the symmetry of conflict scenes, curves in Figure 11 overlap and the number of lines remains unchanged.

[figures omitted; refer to PDF]

[figures omitted; refer to PDF]

In order to evaluate the effectiveness of the multi-UAV conflict resolution algorithm, three indicators of calculation time, feasibility, and system efficiency are now proposed to measure the resolution effectiveness.

In calculation time, the conflict resolution process needs to meet real-time requirements, so the shorter the calculation time is, the stronger the real-time performance is, and the better the resolution efficiency is. The calculation time expressed as $$\begin{array}{}\text{(17)}& \text{CT}=\frac{1}{m}\sum _{j=1}^m{T}_j.\end{array}$$

In the formula, $m$ represents the simulations number for conflict resolution, and $T_j$ represents the time required for the $j$th UAV to resolve.

For feasibility, it is used to measure whether the conflict resolution path satisfies the UAV flight. Generally speaking, if the single heading change is too large, the path point is regarded as nonflyable. The greater the feasibility value is, the safer the conflict resolution process is. The feasibility is expressed as $$\begin{array}{}\text{(18)}& F=\sum _{j=1}^N{f}_j.\end{array}$$

In the formula, $f_j$ represents the number of nonflyable UAV in the UAV $j$ conflict resolution path.

For system efficiency, it is used to measure the delay degree in the conflict resolution process. If all UAVs run along the original path, the system efficiency is 100%. When the UAVs have conflicts, the system efficiency is reduced accordingly; it is expressed as $$\begin{array}{}\text{(19)}& \text{SE}=\frac{1}{N}\sum _{j=1}^N\frac{S_{gj}}{S_j+S_{gj}}.\end{array}$$

In the formula, $S_{gj}$ and $S_j$, respectively, represent the preset step length and delay of the $j$th UAV.

The UAV number is selected from 2 to 28. In the antiflight conflict scene, the solution strategy performance is verified by comparing calculation time, feasibility, and system efficiency. The reference algorithm includes APF, GA method, stochastic parallel gradient descent (SPGD), and a typical nonlinear optimization solver Snopt. As shown in Figure 12, in terms of computing time indicators CT, the APF-GA algorithm can maintain a calculation speed similar to APF, which is far lower than the GA algorithm, SPGD, and Snopt. In terms of feasibility indicators $F$, APF generates more path points with state mutations, which is not conducive to UAV flight. But APF-GA can absorb the GA advantages and can restrict the path points in a targeted manner to generate a flyable path. In terms of conflict resolution efficiency SE, with the increase of conflicting individuals, the efficiency of APF-GA lies between APF, GA. SPGD, and Snopt, and the efficiency declines slowly. Therefore, APF-GA can quickly generate a flyable path and can maintain a high conflict resolution efficiency. On the whole, the performance is better.

[figures omitted; refer to PDF]

5.3. Reliability Analysis of Conflict Resolution Strategy Based on Monte Carlo Algorithm

In the above simulation analysis, the conflicts of multi-UAVs are all successfully resolved. However, due to the complicated environment during the actual operation of the UAV, the above simulation is only based on the conflict situation where the position, speed, and heading are all fixed, and the universality of the algorithm cannot be guaranteed. Therefore, a large number of random UAV conflicts are generated by the Monte Carlo method to obtain the conflict probability of multi-UAVs. Similar to the above, this paper is still based on the simulation of small UAVs.

In order to evaluate the performance of the algorithm in this paper, some Monte Carlo simulation parameters need to be set. The performance of the algorithm can be evaluated by the collision probability $P_{ct}$. $$\begin{array}{}\text{(20)}& P_{ct}=\frac{N_t-N_c}{N_t}\times 100\%.\end{array}$$

In the formula, $N_t$ is the number of UAV distance intervals in the area, which is $N\times N-1/2$, and $N_c$ is the number of intervals that do not meet the safety interval during the conflict resolution process.

In order to simplify the simulation conditions, the UAVs in the Monte Carlo simulation are kept flying in a fixed square area of$200\text{m}\times 200\text{m}$. The random situation of the four UAVs is shown in Figure 13. The initial position $p_i{x}_i,y_i$ and the target position $p_{gi}{x}_{gi},y_{gi}$ of the UAV are randomly distributed in the square area $A_{\text{squ}}$, and the range of the horizontal and vertical coordinates is $-200\text{m},200\text{m}$. Other simulation conditions are consistent with Section 5.1.

[figure omitted; refer to PDF]

Taking the number of UAVs of 2-50 as the object, through the Monte Carlo simulation experiment, the trend of conflict probability $P_{ct}$ under different numbers of individuals is obtained. As shown in Figure 14, the conflict probability decreases with the increase of conflicting individuals. But the overall level is at a relatively high level, meeting the reliability index.

[figure omitted; refer to PDF]

Taking the UAV conflict scenario in the square area in scenario 3 as an example, APF-GA can quickly solve the resolution strategy. In the same way, the individual UAV payment costs under the two solution strategies are obtained, and the Lorentz curve is drawn, as shown in Figure 16.

[figure omitted; refer to PDF]

According to Figures 15 and 16, the solution strategy based on the cooperative game “coalition complaint value” is fair. The curve is closer to the fairness baseline, and it indicates that the solution strategy of the cooperative game “coalition complaint value” can improve individual fairness to a certain extent.

5.5. UAV Priority Allocation

In order to more clearly compare the different priority allocation strategies impact on the cost of individual resolution payment, 4 aircrafts in scenario 1 are selected to simulate the flight conflict scene. The UAV priority deployment rule based on cooperative game “coalition complaint value” proposed in this paper is compared with the deployment method without considering priority. If UAV1 is performing emergency tasks such as rescue and disaster resolution, the priority is the highest ($\alpha$ takes 100), and the resolution effect is shown in Figure 17.

[figures omitted; refer to PDF]

The individual payment costs under the two deployment strategies are shown in Table 4. Under the deployment strategy without considering priority, each UAV individual conflict status is symmetrical and equal, and the payment cost is basically the same. The priority deployment based on the cooperative game gain coefficient can reduce the UAV1 payment cost and promote the high-priority UAV to reach the destination quickly, but it will sacrifice the conflict system overall interests. Compared with the nonpriority deployment, the priority deployment increases 29.06%, but the payment cost of UAV1 decreases 50.26%. Therefore, it can be analyzed that priority deployment based on “coalition complaint value” can realize the UAV rapid planning with priority to reach the target at the premise of sacrificing a small amount of overall benefits.

Table 4

Individual payment costs of the two UAV priority allocation strategies.

Deployment strategies	Individual cost $\upsilon$/m
	UAV1	UAV2	UAV3	UAV4	Total
Deployment strategy without considering priority	28.2894	28.2894	28.2894	28.2894	141.45
Priority allocation based on “coalition complaint value”	14.0705	53.3627	47.0112	38.0139	182.55

6. Conclusion

Based on the cooperative game “coalition complaint value” concept, this paper proposes a low-altitude multi-UAV conflict resolution algorithm, and it realizes the conflict resolution under the premise of ensuring the individual resolution payment costs fairness.

(1) Considering the three conflict resolution evaluation indexes of calculation time, feasibility, and system efficiency, the multi-UAV conflict resolution algorithm based on APF-GA has better performance and can quickly generate a resolution path. And, it satisfies UAV performance constraints

(2) The reliability of the proposed algorithm is verified based on the Monte Carlo algorithm. The conflict probability decreases with the increase of conflicting individuals, but the overall level is at a relatively high level, which meets the reliability index

(3) The conflict resolution strategy based on the cooperative game “coalition complaint value” can improve individual fairness to a certain extent

(4) Priority deployment based on “coalition complaint value” can achieve the rapid planning goal with priority UAV at a small amount of overall benefit expense

Glossary

Abbreviations

$N=a_1,a_2,\cdots ,a_P$:Player set

$\upsilon s_k,a_{i}k=1,2,\cdots ,K,i=1,2,\cdots ,P$:Payment value

$S=s_1,s_2,\cdots ,s_K$:Conflict resolution strategies set

$s_{k}k=1,2,\cdots ,K$:Resolution strategy

$e{s}_k,a_i$:New excess value

$\epsilon s_k$:The sequence when the resolution strategy $s_k$ is arranged in order from large to small

$\gamma$:The minimum “coalition complaint value” in the cooperative game

${\prec }_{\text{les}}$:Lexographically less

$V$:The grand coalition payment matrix

$\alpha$:Gain coefficient

$V^{\prime }$:The sequential payment matrix

$i^{\ast }$:High priority individuals

$p_i=x_i,y_{i}i=1,2,3,\cdots ,N$:Position coordinate of UAV $i$

$p_{gi}=x_{gi},y_{gi}$:Target position of UAV $i$

$k_{ai}$:Gravitational constant

$U_a{p}_i$:Gravitational potential field function

$F_a{p}_i$:Gravity

$U_r{p}_i,p_j$:Repulsion potential field function

$F_r{p}_i,p_j$:Repulsion force

$k_{ri}$:Repulsive force constants

${\rho }_0$:The range of the UAV’s repulsive force field

$F_v{p}_i,p_j$:Vortex force

$\stackrel{·}{p_i}$:UAV operating equation

$k_i$:UAV speed size

$v_i$:UAV resolution speed

$L$:Step number

$t$:Time

$A_{k}x,y,\theta$:UAV position and heading information matrix at time k

$A_{k+1}x+vt\cos {\theta }^{\prime },y+vt\sin {\theta }^{\prime },{\theta }^{\prime }$:UAV position and heading information matrix at time $k+1$

$X=x_1,x_2,\cdots ,x_{N\times L}$:Conflict resolution path coding vector

$\theta$:Angle

${\text{Delay}}_i$:The $i$th UAV delay distance from the destination at the end of conflict resolution

$f$:Fitness function for conflict resolution

$A_i^k$:The position of UAV $i$ at the $k$th step

$d$:The minimum safe interval

$P_C$:Crossover probability

$P_{\text{m}}$:Mutation probability

$N_{\max }$:Iterations

$\text{CL}$:Calculation time

$m$:The simulations number for conflict resolution

$T_j$:The time required for the $j$th UAV to resolve.

$F$:Feasibility

$f_j$:The number of nonflyable UAV in the UAV $j$ resolution path.

$\text{SE}$:System efficiency

$S_{gj}$:The preset step length of the j-th UAV.

$S_j$:The delayof the $j$th UAV.

$P_{ct}$:Collision probability

$N_t$:The number of UAV distance intervals in the area

$N_c$:The number of intervals that do not meet the safety interval.

References

[1] H. Shakhatreh, A. Sawalmeh, A. Al-Fuqaha, Z. Dou, E. Almaita, I. Khalil, N. S. Othman, A. Khreishah, M. Guizani, "Unmanned aerial vehicles: a survey on civil apications and key research chalinges," IEEE Access, vol. 7, pp. 48572-48634, 2019.

[2] D. Sikeridis, E. E. Tsiropoulou, M. Devetsikiotis, S. Papavassiliou, "Wireless powered public safety IoT: a UAV-assisted adaptive-learning approach towards energy efficiency," Journal of Network and Computer Applications, vol. 123, pp. 69-79, DOI: 10.1016/j.jnca.2018.09.003, 2018.

[3] X. M. Tang, X. Q. Ji, T. Li, "Key technology in multi-UAV conflict detection and resolution strategy," Transactions of Nanjing University of Aeronautics and Astronautics, vol. 37, pp. 175-186, 2020.

[4] S. Perez-Carabaza, E. Besada-Portas, J. A. Lopez-Orozco, J. M. de la Cruz, "Ant colony optimization for multi-UAV minimum time search in uncertain domains," Applied Soft Computing, vol. 62, pp. 789-806, DOI: 10.1016/j.asoc.2017.09.009, 2018.

[5] H. Liu, F. Liu, X. Zhang, X. Guan, J. Chen, P. Savinaud, "Aircraft conflict resolution method based on hybrid ant colony optimization and artificial potential field," Science China (Information Sciences), vol. 61 no. 12, pp. 190-192, DOI: 10.1007/s11432-017-9310-5, 2018.

[6] N. Kim, Y. Yoon, "Cooperative sUAV collision avoidance based on satisficing theory," International Journal of Aeronautical and Space Sciences, vol. 20 no. 4, pp. 978-986, DOI: 10.1007/s42405-019-00183-4, 2019.

[7] J. Yang, D. Yin, Q. Cheng, L. Shen, "Two-layered mechanism of online unmanned aerial vehicles conflict detection and resolution," IEEE Transactions on Intelligent Transportation Systems, vol. 19 no. 10, pp. 3230-3244, DOI: 10.1109/TITS.2017.2771465, 2018.

[8] J. Cai, N. Zhang, "Mixed integer nonlinear programming for aircraft conflict avoidance by applying velocity and altitude changes," Arabian Journal for Science and Engineering, vol. 44 no. 10, pp. 8893-8903, DOI: 10.1007/s13369-019-03911-w, 2019.

[9] E. Hernández-Romero, A. Valenzuela, D. Rivas, "Probabilistic multi-aircraft conflict detection and resolution considering wind forecast uncertainty," Aerospace Science and Technology, vol. 105,DOI: 10.1016/j.ast.2020.105973, 2020.

[10] H. Tae, B.-I. Kim, J. Park, "Finding the nucleolus of the vehicle routing game with time windows," Applied Mathematical Modelling, vol. 80, pp. 334-344, DOI: 10.1016/j.apm.2019.11.026, 2020.

[11] M. Baïou, F. Barahona, "Network strength games: the core and the nucleolus," Mathematical Programming, vol. 180 no. 1-2, pp. 117-136, DOI: 10.1007/s10107-018-1348-3, 2020.

[12] L. Mu, S. Han, "Satisficing game approach to conflict resolution for cooperative aircraft sharing airspace," Big Data, vol. 9 no. 1, pp. 53-62, DOI: 10.1089/big.2020.0155, 2021.

[13] M. Sakawa, I. Nishizaki, "A lexicographical solution concept in an n -person cooperative fuzzy game," Fuzzy Sets and Systems, vol. 61 no. 3, pp. 265-275, DOI: 10.1016/0165-0114(94)90169-4, 1994.

[14] Q. Kong, H. Sun, G. Xu, D. Hou, "The general prenucleolus of n-person cooperative fuzzy games," Fuzzy Sets and Systems, vol. 349, pp. 23-41, DOI: 10.1016/j.fss.2017.08.005, 2018.

[15] S. Airiau, "Cooperative games and multiagent systems," Knowledge Engineering Review, vol. 28 no. 4, pp. 381-424, 2013.

[16] K. Bergstresser, P. L. Yu, "Domination structures and multicriteria problems in n-person games," Theory and Decision, vol. 8 no. 1,DOI: 10.1007/BF00133085, 1977.

[17] Z. Yi, L. Li, X. Qu, Y. Hong, P. Mao, B. Ran, "Using artificial potential field theory for a cooperative control model in a connected and automated vehicles environment," Transportation Research Record, vol. 2674 no. 9, pp. 1005-1018, DOI: 10.1177/0361198120933271, 2020.

[18] D. Li, Z. Pan, H. Deng, "Two-dimensional obstacle avoidance control algorithm for snake-like robot in water based on immersed boundary-lattice Boltzmann method and improved artificial potential field method," Transactions of the Institute of Measurement and Control, vol. 42 no. 10, pp. 1840-1857, DOI: 10.1177/0142331219897992, 2020.

[19] R. I. Dancila, R. M. Botez, "New flight trajectory optimisation method using genetic algorithms," The Aeronautical Journal, vol. 125 no. 1286, pp. 618-671, DOI: 10.1017/aer.2020.138, 2021.

[20] X. Guan, X. Zhang, R. Lv, J. Chen, W. Michal, "A large-scale multi-objective flights conflict avoidance approach supporting 4D trajectory operation," Science China (Information Sciences), vol. 60 no. 11, pp. 198-210, DOI: 10.1007/s11432-016-9024-y, 2017.

[21] T. R. Schäfle, M. Mitschke, N. Uchiyama, "Generation of optimal coverage paths for mobile robots using hybrid genetic algorithm," Journal of Robotics and Mechatronics, vol. 33 no. 1, pp. 11-23, DOI: 10.20965/jrm.2021.p0011, 2021.