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

Authors: Xusheng Gan; Honghong Zhang; Yarong Wu; Jingjuan Sun; Guhao Zhao; Fugen Lin
Journal: International Journal of Aerospace Engineering
 (2021)

---

## 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.


---

## Body

## 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-tupleN,υ, the player set is N=a1,a2,⋯,aP, and υ is the payment value [15, 16]. In the grand coalition structure, S=s1,s2,⋯,sK is the conflict resolution strategies set. For each resolution strategy skk=1,2,⋯,K, the conflict UAV cost is denoted as υsk,aik=1,2,⋯,K,i=1,2,⋯,P. Referring to the excess value definition of cooperative game, the new excess value definition is esk,ai=υsk,ai. 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 esk,ai of all conflicting individuals in the resolution strategy sk is arranged in order from large to small. The sequence is marked as εsk.Definition 1.
There is a unique configurationγ in all the cooperative game grand coalition set N. And it meets the validity configuration, such that
(1)εγ≺lesεx∀x∈N,x≠γ,
whereγ is defined as the minimum “coalition complaint value” in the cooperative game. ≺les is defined as “lexographically less.” If y≺lesz, where y and z are both k-dimensional vectors, then l∈1,⋯,k exists, such that y1=z1,⋯,yl−1=zl−1,yl<zl is true. It should be noted that the cardinality of x and γ 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 UAVsN=P, if there are K conflict resolution strategies, the grand coalition payment matrix V is expressed as
(2)V=υs1,a1⋯υs1,aP⋮⋮υsK,a1⋯υsK,aP.In the formula,υsk,aik=1,2,⋯,K,i=1,2,⋯,P represents the resolution payment value of the ith UAV under the kth resolution strategy.For thekth k=1,2,⋯,K resolution strategy, arrange the resolution payment value in descending order to obtain the sequential payment matrix V′:
(3)V′=maxυs1,ai⋯minυs1,ai⋮⋮maxυsK,ai⋯minυsK,ai,wheremaxυsk,ai is the maximum value of the kth row in matrix V, minυsk,ai is the minimum value of the kth row in matrix V. According to Definition 1, the conflict resolution “coalition complaint value” can be determined.


### 2.2. UAV

In conflict UAV groupA,υ, if there is a high-priority individuali∗performing emergency tasks such as rescue and disaster relief, the UAV i∗ payment cost υsk,ai∗ is regarded as the largest in all conflict resolution solutions, that is, maxυsk,ai=αυsk,ai∗k=1,2,⋯,K,i=1,2,⋯,A, α is the gain coefficient. Its value must satisfy the following conditions.
(4)α>maxmaxυsk,aiminυsk,aik=1,2,⋯,K.The UAV sequential payment matrixV′ is expressed as
(5)V′=maxυs1,ai⋯minυs1,ai⋮⋮maxυsK,ai⋯minυsK,ai=αυs1,ai∗⋯minυs1,ai⋮⋮αυsK,ai∗⋯minυsK,ai.That is to say, the UAV conflict resolution strategy must be produced in the scheme that has the priority UAVi∗ to pay the least cost, so as to ensure that UAV i∗ 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 is5×6 grand coalition payment matrix V, which means there are 5 conflict resolution strategies and 6 conflict individuals.
(6)V=468723167243854514358751456365.Arrange each row of the payment matrix in the order from largest to smallest to obtain the sequential payment matrixV′.
(7)V′=876432764321855441875531665543.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,α is 8, and the sequential payment matrix V′ becomes
(8)V′=32876322476421328554140875314076543.At this point, the optimal solution is the 2nd conflict resolution strategy.


## 2.1. UAV Conflict Resolution Grand Coalition Payment Matrix

For a grand coalition with the number of UAVsN=P, if there are K conflict resolution strategies, the grand coalition payment matrix V is expressed as
(2)V=υs1,a1⋯υs1,aP⋮⋮υsK,a1⋯υsK,aP.In the formula,υsk,aik=1,2,⋯,K,i=1,2,⋯,P represents the resolution payment value of the ith UAV under the kth resolution strategy.For thekth k=1,2,⋯,K resolution strategy, arrange the resolution payment value in descending order to obtain the sequential payment matrix V′:
(3)V′=maxυs1,ai⋯minυs1,ai⋮⋮maxυsK,ai⋯minυsK,ai,wheremaxυsk,ai is the maximum value of the kth row in matrix V, minυsk,ai is the minimum value of the kth row in matrix V. According to Definition 1, the conflict resolution “coalition complaint value” can be determined.


## 2.2. UAV

In conflict UAV groupA,υ, if there is a high-priority individuali∗performing emergency tasks such as rescue and disaster relief, the UAV i∗ payment cost υsk,ai∗ is regarded as the largest in all conflict resolution solutions, that is, maxυsk,ai=αυsk,ai∗k=1,2,⋯,K,i=1,2,⋯,A, α is the gain coefficient. Its value must satisfy the following conditions.
(4)α>maxmaxυsk,aiminυsk,aik=1,2,⋯,K.The UAV sequential payment matrixV′ is expressed as
(5)V′=maxυs1,ai⋯minυs1,ai⋮⋮maxυsK,ai⋯minυsK,ai=αυs1,ai∗⋯minυs1,ai⋮⋮αυsK,ai∗⋯minυsK,ai.That is to say, the UAV conflict resolution strategy must be produced in the scheme that has the priority UAVi∗ to pay the least cost, so as to ensure that UAV i∗ 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 is5×6 grand coalition payment matrix V, which means there are 5 conflict resolution strategies and 6 conflict individuals.
(6)V=468723167243854514358751456365.Arrange each row of the payment matrix in the order from largest to smallest to obtain the sequential payment matrixV′.
(7)V′=876432764321855441875531665543.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,α is 8, and the sequential payment matrix V′ becomes
(8)V′=32876322476421328554140875314076543.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 knownAssuming 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 Figure1. 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 1
Low-altitude UAV conflict resolution mechanism process.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 pi=xi,yii=1,2,3,⋯,N, and N is the UAV number in the area.Figure 2
Schematic diagram of the artificial potential field method.For UAVi, the target position is pgi=xgi,ygi. 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 Uapi and gravity Fapi are expressed as
(9)Uapi=12kaipi−pgi2,Fapi=−∇UaX=‐kaipi−pgi.In the formula,kai 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 fieldUrpi,pj 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 Urpi,pj and the repulsion force Frpi,pj are
(10)Urpi,pj=12kri1pi−pj−1ρ02,pi−pj≤ρ0,0,pi−pj>ρ0,Frpi,pj=−∇Urpi,pj=kri1pi−pj−1ρ01pi−pj2⋅∂pi−pj∂X,pi−pj≤ρ0,0,pi−pj>ρ0.In the formula,kri is the repulsive force constants. Its value is greater than 0. ρ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.(11)Fvpi,pj=±∂Urpi,pj∂y−∂Urpi,pj∂x.Superimpose the gravity, repulsion, and vortex forces experienced by the UAV to obtain the UAV operating equation in the conflict resolution process:(12)pi·=Fap,pgiFapi,pgi+∑jFrpi,pj+Fvpi,pj,j=1,2,⋯,N,i≠j.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 equationpi· to get the speed direction. Assuming the speed is ki, the UAV speed can be expressed as
(13)vi=kipi⋅pi⋅.Using the UAV resolution speedvi, 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 theN 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 C1, C2, and C3. If the UAV current position and heading information matrix is denoted as Akx,y,θ, the next step UAV information matrix is denoted as Ak+1x+vtcosθ′,y+vtsinθ′,θ′. In the formula, θ′ can take θ+π/6,θ and θ−π/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 intoN×L-dimensional vector X=x1,x2,⋯,xN×L, xi∈−1`0`+1. The specific encoding structure is shown in Table 1.Table 1
UAV conflict resolution strategy coding diagram.
UAV 1…UAVNStep 1…StepL…Step 1…StepL001…001


#### 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(14)f=min∑i=1NDelayi.In the formula,Delayi represents the ith 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 kth step as Aik, then, the UAV i delay distance Delayi is expressed as the Euclidean distance between the position AiLxiL,yiL after L steps and the destination position Bixg,yg; it is expressed as
(15)Delayi=AiL−B=xiL−xg2+yiL−yg2.In order to avoid the UAV collision in the conflict resolution process, it is required that the distance between UAVixi,yi andjxj,yj maintains a minimum safety interval at any time:
(16)xi−xj2+yi−yj2>d.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 probabilityPC, 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 Pm.Figure 3
Schematic diagram of one-point crossover.


#### 3.2.4. Optimal Retention

In order to retain the excellent individuals that have been obtained, the optimal retention is added to the selection operation. That is, the good individuals that have appeared in the previous generation are directly inherited to the next generation without any crossover and mutation.


#### 3.2.5. Conditions for Genetic Termination

When the number of inherited generations exceeds a predetermined value, the inheritance is terminated, and the individual with the greatest fitness in the final chromosome is output.


## 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 pi=xi,yii=1,2,3,⋯,N, and N is the UAV number in the area.Figure 2
Schematic diagram of the artificial potential field method.For UAVi, the target position is pgi=xgi,ygi. 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 Uapi and gravity Fapi are expressed as
(9)Uapi=12kaipi−pgi2,Fapi=−∇UaX=‐kaipi−pgi.In the formula,kai 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 fieldUrpi,pj 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 Urpi,pj and the repulsion force Frpi,pj are
(10)Urpi,pj=12kri1pi−pj−1ρ02,pi−pj≤ρ0,0,pi−pj>ρ0,Frpi,pj=−∇Urpi,pj=kri1pi−pj−1ρ01pi−pj2⋅∂pi−pj∂X,pi−pj≤ρ0,0,pi−pj>ρ0.In the formula,kri is the repulsive force constants. Its value is greater than 0. ρ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.(11)Fvpi,pj=±∂Urpi,pj∂y−∂Urpi,pj∂x.Superimpose the gravity, repulsion, and vortex forces experienced by the UAV to obtain the UAV operating equation in the conflict resolution process:(12)pi·=Fap,pgiFapi,pgi+∑jFrpi,pj+Fvpi,pj,j=1,2,⋯,N,i≠j.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 equationpi· to get the speed direction. Assuming the speed is ki, the UAV speed can be expressed as
(13)vi=kipi⋅pi⋅.Using the UAV resolution speedvi, 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 theN 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 C1, C2, and C3. If the UAV current position and heading information matrix is denoted as Akx,y,θ, the next step UAV information matrix is denoted as Ak+1x+vtcosθ′,y+vtsinθ′,θ′. In the formula, θ′ can take θ+π/6,θ and θ−π/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 intoN×L-dimensional vector X=x1,x2,⋯,xN×L, xi∈−1`0`+1. The specific encoding structure is shown in Table 1.Table 1
UAV conflict resolution strategy coding diagram.
UAV 1…UAVNStep 1…StepL…Step 1…StepL001…001


### 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(14)f=min∑i=1NDelayi.In the formula,Delayi represents the ith 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 kth step as Aik, then, the UAV i delay distance Delayi is expressed as the Euclidean distance between the position AiLxiL,yiL after L steps and the destination position Bixg,yg; it is expressed as
(15)Delayi=AiL−B=xiL−xg2+yiL−yg2.In order to avoid the UAV collision in the conflict resolution process, it is required that the distance between UAVixi,yi andjxj,yj maintains a minimum safety interval at any time:
(16)xi−xj2+yi−yj2>d.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 probabilityPC, 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 Pm.Figure 3
Schematic diagram of one-point crossover.


### 3.2.4. Optimal Retention

In order to retain the excellent individuals that have been obtained, the optimal retention is added to the selection operation. That is, the good individuals that have appeared in the previous generation are directly inherited to the next generation without any crossover and mutation.


### 3.2.5. Conditions for Genetic Termination

When the number of inherited generations exceeds a predetermined value, the inheritance is terminated, and the individual with the greatest fitness in the final chromosome is output.


## 3.2.1. Coding Method

Divide the path from the initial position to the target position of theN 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 C1, C2, and C3. If the UAV current position and heading information matrix is denoted as Akx,y,θ, the next step UAV information matrix is denoted as Ak+1x+vtcosθ′,y+vtsinθ′,θ′. In the formula, θ′ can take θ+π/6,θ and θ−π/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 intoN×L-dimensional vector X=x1,x2,⋯,xN×L, xi∈−1`0`+1. The specific encoding structure is shown in Table 1.Table 1
UAV conflict resolution strategy coding diagram.
UAV 1…UAVNStep 1…StepL…Step 1…StepL001…001


## 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(14)f=min∑i=1NDelayi.In the formula,Delayi represents the ith 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 kth step as Aik, then, the UAV i delay distance Delayi is expressed as the Euclidean distance between the position AiLxiL,yiL after L steps and the destination position Bixg,yg; it is expressed as
(15)Delayi=AiL−B=xiL−xg2+yiL−yg2.In order to avoid the UAV collision in the conflict resolution process, it is required that the distance between UAVixi,yi andjxj,yj maintains a minimum safety interval at any time:
(16)xi−xj2+yi−yj2>d.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 probabilityPC, 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 Pm.Figure 3
Schematic diagram of one-point crossover.


## 3.2.4. Optimal Retention

In order to retain the excellent individuals that have been obtained, the optimal retention is added to the selection operation. That is, the good individuals that have appeared in the previous generation are directly inherited to the next generation without any crossover and mutation.


## 3.2.5. Conditions for Genetic Termination

When the number of inherited generations exceeds a predetermined value, the inheritance is terminated, and the individual with the greatest fitness in the final chromosome is output.


## 4. Multi-UAV Conflict Resolution Process Based on APF-GA Algorithm

Firstly, based on the APF method principle, a preliminary search is made for the initial path of multi-UAV conflict resolution. After the iteration is terminated, the initial path is used to initialize the population information. Finally, the global optimum is searched through constant iteration. The whole calculation process is shown in Figure4. The specific implementation steps are described as follows:Figure 4
Multi-UAV conflict resolution process based on the APF-GA algorithm.Step 1: initialize the parameters. Set the initial conflict positionpi0=xi0,yi0 and target point pgi=xgi,ygi for the UAVs in the area.Step 2: force analysis of the potential field. Calculate the gravitational forceFapi,pgi, repulsion force Frpi,pj, and vortex force Fvpi,pj 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 theUAVi has reached its destination pgi=xgi,ygi, 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 Figure5. 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×N−1/2 distance curves in the conflict resolution process.Figure 5
Classic 6 aircraft-to-flight conflict scenario.


#### 5.1.2. Scenario 2: UAV Flow Conflict Scene

As shown in Figure6, the UAVs maintain a certain minimum safety interval during the operation, and they converge at the intersection point at a certain moment, and the initial path is a straight line. The entire system conflict resolution is completed by adjusting the direction.Figure 6
Conflict scene of UAV flow.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 Figure7, the conflict area is a block area of 200m×200m, 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 7
Conflict scene in the square airspace.The parameters required for simulation in the three conflict scenarios are shown in Table2.Table 2
Simulation parameter setting.
ParameterValueParameterValued20 mα100kri1L200kvi1PC0.02ki1Pm0.7ρ050 mNmax100


### 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 Figures8 and 9.Figure 8
Conflict resolution strategies based on APF: (a) 2 UAVs’ conflict, (b) 6 UAVs’ conflict, and (c) 10 UAVs’ conflict.
(a)(b)(c)Figure 9
Conflict resolution strategies based on APF-GA: (a) 2 UAVs’ conflict, (b) 6 UAVs’ conflict, and (c) 10 UAVs conflict.
(a)(b)(c)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 Figure10. 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×1/2=1 distance curve during the 2 UAVs’ conflict resolution process, 6×5/2=15 distance curve exists during 6 UAVs’ conflict resolution process, and 10×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.Figure 10
The conflict resolution strategies simulation result about the convergence of the APF-GA algorithm: (a) 2 UAVs’ conflict, (b) 6 UAVs’ conflict, and (c) 10 UAVs’ conflict.
(a)(b)(c)Figure 11
Conflict resolution strategies based on APF-GA: (a) 2 UAVs’ conflict, (b) 6 UAVs’ conflict, and (c) 10 UAVs’ conflict.
(a)(b)(c)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(17)CT=1m∑j=1mTj.In the formula,m represents the simulations number for conflict resolution, and Tj represents the time required for the jth 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(18)F=∑j=1Nfj.In the formula,fj 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(19)SE=1N∑j=1NSgjSj+Sgj.In the formula,Sgj and Sj, respectively, represent the preset step length and delay of the jth 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 Figure12, 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.Figure 12
Performance comparison of conflict resolution solution strategies: (a) computing time, (b) feasibility, and (c) conflict resolution efficiency comparisons.
(a)(b)(c)


### 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 probabilityPct.
(20)Pct=Nt−NcNt×100%.In the formula,Nt is the number of UAV distance intervals in the area, which is N×N−1/2, and Nc 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 of200m×200m. The random situation of the four UAVs is shown in Figure 13. The initial position pixi,yi and the target position pgixgi,ygi of the UAV are randomly distributed in the square area Asqu, and the range of the horizontal and vertical coordinates is −200m,200m. Other simulation conditions are consistent with Section 5.1.Figure 13
Random situation of four UAVs.Taking the number of UAVs of 2-50 as the object, through the Monte Carlo simulation experiment, the trend of conflict probabilityPct 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 14
Trend of conflict probability.


### 5.4. The Impact of Cooperative Game “Coalition Complaint Value” and Traditional Cooperative Solution Strategy on Individual Fairness

Taking the UAV flow conflict scenario in scenario 2 as an example, APF-GA can quickly solve the resolution strategy. Based on the two solution strategies of cooperative game “coalition complaint value” and traditional cooperation (take the total costs paid by the individual as an indicator), two solution strategies are obtained. The individual UAV payment costs under the two solution strategies are shown in Table3.Table 3
Performance comparison of the two resolution strategies.
StrategiesConflict resolution UAVs individual pay costsυ (m)UAV1UAV2UAV3UAV4UAV5UAV6UAV7UAV8Cooperative game “coalition complaint value”30.4838.4843.5816.5442.1536.4730.5824.15Traditional cooperation20.5863.5624.5918.444.2566.4816.146.8In order to more intuitively compare the two solution strategies impact of cooperative game “coalition complaint value” and traditional cooperation on individual fairness, draw the Lorentz curve, as shown in Figure15.Figure 15
Comparison of individual fairness between the two solutions under scenario 2.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 Figure16.Figure 16
Comparison of individual fairness between the two solutions under scenario 3.According to Figures15 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 (α takes 100), and the resolution effect is shown in Figure 17.Figure 17
Priority allocation strategy of UAV: (a) strategy without considering priority and (b) priority allocation based on “coalition complaint value.”
(a)(b)The individual payment costs under the two deployment strategies are shown in Table4. 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 strategiesIndividual costυ/mUAV1UAV2UAV3UAV4TotalDeployment strategy without considering priority28.289428.289428.289428.2894141.45Priority allocation based on “coalition complaint value”14.070553.362747.011238.0139182.55


## 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 Figure5. 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×N−1/2 distance curves in the conflict resolution process.Figure 5
Classic 6 aircraft-to-flight conflict scenario.


### 5.1.2. Scenario 2: UAV Flow Conflict Scene

As shown in Figure6, the UAVs maintain a certain minimum safety interval during the operation, and they converge at the intersection point at a certain moment, and the initial path is a straight line. The entire system conflict resolution is completed by adjusting the direction.Figure 6
Conflict scene of UAV flow.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 Figure7, the conflict area is a block area of 200m×200m, 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 7
Conflict scene in the square airspace.The parameters required for simulation in the three conflict scenarios are shown in Table2.Table 2
Simulation parameter setting.
ParameterValueParameterValued20 mα100kri1L200kvi1PC0.02ki1Pm0.7ρ050 mNmax100


## 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 Figure5. 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×N−1/2 distance curves in the conflict resolution process.Figure 5
Classic 6 aircraft-to-flight conflict scenario.


## 5.1.2. Scenario 2: UAV Flow Conflict Scene

As shown in Figure6, the UAVs maintain a certain minimum safety interval during the operation, and they converge at the intersection point at a certain moment, and the initial path is a straight line. The entire system conflict resolution is completed by adjusting the direction.Figure 6
Conflict scene of UAV flow.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 Figure7, the conflict area is a block area of 200m×200m, 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 7
Conflict scene in the square airspace.The parameters required for simulation in the three conflict scenarios are shown in Table2.Table 2
Simulation parameter setting.
ParameterValueParameterValued20 mα100kri1L200kvi1PC0.02ki1Pm0.7ρ050 mNmax100


## 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 Figures8 and 9.Figure 8
Conflict resolution strategies based on APF: (a) 2 UAVs’ conflict, (b) 6 UAVs’ conflict, and (c) 10 UAVs’ conflict.
(a)(b)(c)Figure 9
Conflict resolution strategies based on APF-GA: (a) 2 UAVs’ conflict, (b) 6 UAVs’ conflict, and (c) 10 UAVs conflict.
(a)(b)(c)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 Figure10. 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×1/2=1 distance curve during the 2 UAVs’ conflict resolution process, 6×5/2=15 distance curve exists during 6 UAVs’ conflict resolution process, and 10×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.Figure 10
The conflict resolution strategies simulation result about the convergence of the APF-GA algorithm: (a) 2 UAVs’ conflict, (b) 6 UAVs’ conflict, and (c) 10 UAVs’ conflict.
(a)(b)(c)Figure 11
Conflict resolution strategies based on APF-GA: (a) 2 UAVs’ conflict, (b) 6 UAVs’ conflict, and (c) 10 UAVs’ conflict.
(a)(b)(c)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(17)CT=1m∑j=1mTj.In the formula,m represents the simulations number for conflict resolution, and Tj represents the time required for the jth 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(18)F=∑j=1Nfj.In the formula,fj 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(19)SE=1N∑j=1NSgjSj+Sgj.In the formula,Sgj and Sj, respectively, represent the preset step length and delay of the jth 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 Figure12, 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.Figure 12
Performance comparison of conflict resolution solution strategies: (a) computing time, (b) feasibility, and (c) conflict resolution efficiency comparisons.
(a)(b)(c)


## 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 probabilityPct.
(20)Pct=Nt−NcNt×100%.In the formula,Nt is the number of UAV distance intervals in the area, which is N×N−1/2, and Nc 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 of200m×200m. The random situation of the four UAVs is shown in Figure 13. The initial position pixi,yi and the target position pgixgi,ygi of the UAV are randomly distributed in the square area Asqu, and the range of the horizontal and vertical coordinates is −200m,200m. Other simulation conditions are consistent with Section 5.1.Figure 13
Random situation of four UAVs.Taking the number of UAVs of 2-50 as the object, through the Monte Carlo simulation experiment, the trend of conflict probabilityPct 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 14
Trend of conflict probability.


## 5.4. The Impact of Cooperative Game “Coalition Complaint Value” and Traditional Cooperative Solution Strategy on Individual Fairness

Taking the UAV flow conflict scenario in scenario 2 as an example, APF-GA can quickly solve the resolution strategy. Based on the two solution strategies of cooperative game “coalition complaint value” and traditional cooperation (take the total costs paid by the individual as an indicator), two solution strategies are obtained. The individual UAV payment costs under the two solution strategies are shown in Table3.Table 3
Performance comparison of the two resolution strategies.
StrategiesConflict resolution UAVs individual pay costsυ (m)UAV1UAV2UAV3UAV4UAV5UAV6UAV7UAV8Cooperative game “coalition complaint value”30.4838.4843.5816.5442.1536.4730.5824.15Traditional cooperation20.5863.5624.5918.444.2566.4816.146.8In order to more intuitively compare the two solution strategies impact of cooperative game “coalition complaint value” and traditional cooperation on individual fairness, draw the Lorentz curve, as shown in Figure15.Figure 15
Comparison of individual fairness between the two solutions under scenario 2.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 Figure16.Figure 16
Comparison of individual fairness between the two solutions under scenario 3.According to Figures15 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 (α takes 100), and the resolution effect is shown in Figure 17.Figure 17
Priority allocation strategy of UAV: (a) strategy without considering priority and (b) priority allocation based on “coalition complaint value.”
(a)(b)The individual payment costs under the two deployment strategies are shown in Table4. 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 strategiesIndividual costυ/mUAV1UAV2UAV3UAV4TotalDeployment strategy without considering priority28.289428.289428.289428.2894141.45Priority allocation based on “coalition complaint value”14.070553.362747.011238.0139182.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



---

*Source: 9975538-2021-10-18.xml*