Key Technology in Multi-UAV Conflict Detection and Resolution Strategy

，，

College of Civil Aviation，Nanjing University of Aeronautics and Astronautics，Nanjing 211106，P.R.China

Abstract:Based on ADS-B surveillance data，this paper proposes a multi-unmanned aerial vehicle（multi-UAV）collision detection method based on linear extrapolation for ground-based UAV collision detection and resolution，thus to provide early warning of possible conflicts.To address the problem of multi-UAV conflict，the basic ant colony algorithm is introduced.The conflict simplification model of the traditional basic ant colony algorithm is optimized by adding a speed regulation strategy.A multi-UAV conflict resolution scheme is presented based on speed regulation and heading strategies.The ant colony algorithm is improved by adding angle information and a queuing system.The results show that the improved ant colony algorithm can provide multi-UAV joint escape routes for a multi-UAV conflict situation in airspace.Unlike the traditional ant colony algorithm，our approach converges to the optimization target.The time required for the calculation is reduced by 43.9%，and the total delay distance caused by conflict resolution is reduced by 58.4%.

Key words:unmanned aerial vehicle（UAV）；ground station；ant colony algorithm；conflict resolution

0 Introduction

Thanks to the progressing drone technologies targeting lower cost，simpler operation，and stronger maneuverability，drones have been widely used in many fields such as agricultural plant protection，public security policing，and forest fire protection［1］.And research in techniques that use multiple unmanned aerial vehicles（UAVs）has experienced a significant increase in recent decades［2］.The expansion of the drone market has created severe challenges for airspace management［3］.Up to now，the prevalent operation and control strategy for UAVs has been mainly using fixed airspace regulation methods to reduce security risks by avoiding or strictly controlling the entry of other types of aircraft into the designated airspace.However，because airspace resources are limited and the number of drones is steadily increasing，it is necessary to study ground station-based drone collision-detection technology and to develop a multi-UAV conflict resolution strategy to ensure safe operation of drones.

Researchers all around the world have divided the multi-UAV conflict path planning problem into two parts:Conflict detection and escape route planning.In terms of conflict detection，the major problem of conflict detection and resolution lies in the accurate collision prediction and efficient adjustment of the flight status among conflicting UAVs［4-5］.Conflict detection and resolution（CDR）algorithms for UAV swarms often merge with formation control algorithms.Control algorithms with CDR can be sorted into two general types:Rule-based approaches and optimization-based approaches［6］.CDR methods that can solve possible collisions between UAVs based on the CDR method.Ho et al.introduced an adaptation of ORCA，called adapted ORCA，which can minimize the ORCA generated deviations from the nominal flight path and a value for separation distance between UAVs that use the airspace efficiently can be determined by simulating realistic UAV traffic for delivery［7］.Farlik et al.analyzed the possibility of detecting flying aircraft based on calculations and simulations，and experiments in laboratories and measurements of the exterior were subsequently performed［8］.Cheng et al.proposed a learning based framework where the conflict and avoidance problem can be formulated as a Markov decision process and the maneuver policies for the UAV were learned［9］.Navarro et al.developed a sense and avoid strategy based on a deep learning approach［10］.Hu et al.proposed distributed velocityaware algorithm to serve motion planning of multiple UAVs［11］.During motion，a decentralized consensus algorithm was adopted for agents to converge to their positions for the desired formation and to maintain a stable geometric configuration.A temporal and spatially integrated conflict-detection model was improved，especially for UAV swarms.A token-allocation strategy was especially improved for distributed coordination to resolve the partial knowledge of the airspace condition.Damping of the coordination was proposed to address data dropouts and transmission delays［12］.Reich et al.carried out research on establishing flight safety intervals and quantifying conflict probabilities［13-15］. To address the inconsistency problem caused by the state information of multi-UAV communication under a dynamic environment，a state estimation method was proposed based on the Kalman algorithm［16］.A realtime conflict resolution algorithm based on model predictive control（MPC）was introduced to address the flight conflict resolution problem in multi-UAV scenarios by Chen et al.And the controller structure of the distributed nonlinear model predictive control（DNMPC）was designed to predict potential conflicts and calculate control variables for each UAV.Numerical simulations of multi-UAV coordination were performed to verify the performance of the proposed algorithm［17］.An advanced flocking strategy was developed to address the autonomous multi-UAVs'cooperative flight［18］.In Ref.［19］，trackinglearning-detection（TLD）was used for target tracking from a UAV and achieved a good result in a short term.Fu et al.introduced a novel robust visual tracking algorithm for UAVs in the midair to track an arbitrary aircraft at real-time frame rates，together with a unique evaluation system［20］.Tang et al.and Xu et al.considered drone performance constraints，established an airborne conflict detection model，and classified conflict alert levels.According to these，a corresponding escape strategy was developed［21-22］.These studies have outlined multi-UAV collision detection approaches.

As for multi-UAV escape route planning，current mature and popular algorithms include the A*algorithm，the artificial potential field method，genetic algorithm［23］and the ant colony algorithm.The A*algorithm is applied to traverse a graph to plan conflict-free flight routes［24］.Granger et al.improved the A*algorithm to generate a coordinated and decentralized embarked conflict solver［25］.Tang et al.assumed the destination of a known drone，introduced the A*algorithm to improve the open table and to reduce computational complexity，and considered the performance of the drone.They finally proposed a plan for determining an escape route［26］.Researchers introduced artificial potentials［27］for obstacle avoidance as well as leader-follower schemes for goal searching［28］.Zhu et al.［29］studied how to use the artificial potential field method to plan a conflict resolution path for UAVs in a dynamic environment.Wu et al.proposed an artificial potential fieldguided evolutionary algorithm to track single targets［30］.The advantage of the artificial potential field method is that it can plan a smooth route，but easily fall into local optima simultaneously.In 1991，Dorigo first proposed the ant colony algorithm［31］.By releasing different quantities of pheromones for different feasible paths，the pheromone concentration of different paths was controlled，and the concentration was increased in the optimal line to guide a gradual search for the optimal path.This algorithm has expertise at solving function optimization and path planning problems.Sara et al.studied an optimized ant colony algorithm based on the probability and space attributes of the target，which effectively reduced the time required to reach the search target［32］.Li et al.combined the UAV performance index with the ant colony algorithm and used the artificial potential field method to obtain the prior value，which shortened the flight distance of the multi-UAV mission［33］.Zhuang et al.improved the ant colony algorithm based on angle information and an elite strategy and obtained better conflict resolution strategies for multiple aircraft［34］.These studies laid the foundation for research on ground-based unmanned aircraft conflict resolution.

In summary，at present，for multi-UAV path planning problems，the ant colony algorithm can provide a path planning solution.However，most current studies consider a single condition，usually adopting only a steering strategy，and fail to take advantage of the drone's flexibility.In addition，due to the large amount of searching in the initial stage of the algorithm，it takes a long time for the optimal path to converge to the result.Therefore，in this study，based on UAV performance，a UAV flight protection zone is established，and the ground station is used to detect and predict flight conflicts in the airspace.Further，based on the basic ant colony algorithm，an improved ant colony algorithm with angle information and a sorting system is proposed.The multi-UAV algorithm is introduced to the conflicting multi-UAV airspace and a coordinated speed regulation and direction adjustment strategy is developed for collision-free paths with the objective of minimizing total delay distance.The function provides the optimally linked escape strategy under multi-UAV conflict scenarios.

1 Collision Detection for UAVs

Ground station-based drone collision detection requires three steps.

Step 1Set up a flight protection zone for the drones and convert the acquired surveillance data into spatial coordinates with the ground station as the origin.

Step 2Stratify the drones in the airspace according to their respect heights，analyze the target trajectories of the drones at the same level，and initially screen target pairs for potential conflicts.

Step 3Carry out specific analysis using a linear extrapolation method and calculate the UAVs that have been screened to determine the conflict situation more precisely.

1.1 Safety interval of UAVs

A safety interval for UAVs involves establishing a corresponding flight protection zone for each drone to ensure that the drone has reasonable space to perform its mission while avoiding the risk of collision.The construction of each UAV's flight protection zone depends on the flight performance of the UAV，including its maximum operating speed and the time it takes to respond to commands.Based on these factors，the flight protection zone is larger than the size of the drone itself.The protected area contains two elements:The vertical safety intervalDverand the horizontal safety intervalDhor［17］.Fig.1 shows a model of the protected area centered the drone.

Fig.1 UAV flight protection area

1.2 Conflict pre-judgment algorithm based on linear extrapolation

A local cartesian coordinate system with the ground base station as the origin is established by transforming the WGS84 coordinate system into a local rectangular spatial coordinate system. The UAV's latitude and longitude and its velocity in the airspace are converted into position and velocity vectors relative to the ground station by a coordinate conversion method.UAVs at different heights correspond to different two-dimensional planes.

（1）Conflict screening

For any drone among theNUAVs in a two-dimensional plane，it is necessary to makeN-1 conflict judgments.For all drones，it is theoretically necessary to makeN(N-1)/2 judgments.In reality，many targets are far apart and will not generate conflicts any time soon.Therefore，setting a distance threshold can reduce the number of detections and improve collision detection efficiency.

In the two-dimensional plane，set the horizontal distance thresholdR TA.When the horizontal interval is greater than the threshold，the target is filtered.R TAis set as

whereTAis the set warning time，vmhthe maximum horizontal flight speed of the target，andDhorthe horizontal interval of the target protection zone.

Linear extrapolation is applied to objects that move linearly.The algorithm is based on the current position and velocity vectors of the two machines and calculates whether a distance less than the safety level interval is possible and the whether safety height interval between the two objects during the warning time[0，TA]，is a possibile.

（2）Horizontal warning detection

In the horizontal direction，it is assumed that the two objects to be evaluated area，b.According to the established local coordinate system，the horizontal coordinate ofais(vax，vay)，the horizontal velocity ofais(vax，vay)，the horizontal coordinate ofbis (xb，yb)，and the horizontal velocity ofbis(vbx，vby).A few definitions are needed for the relative states ofa，bflying in a horizontal plane.

Definition 1The true distance betweenaandbis

Definition 2Speed of intruderbrelative to thex-axis of dronea

Definition 3Speed of intruderbrelative to they-axis of dronea

The steps for detecting collisions in the horizontal direction are as follows.

Step 1According to the drone speed information，find the relative speed Δv.If|Δv|=0，go to Step 2；if|Δv|≠0，go to Step 3.

Step 2Compare the horizontal intervalD ab(0)with the safety intervalDhor.WhenD ab(0)＜Dhor，there is a conflict in the horizontal direction，and the conflict period[T h1，T h2]=[0，TA]；otherwise，[T h1，T h2]=?，and the evaluation ends.

Step 3Calculate the horizontal interval as

The time range whenD ab(t)＜Dhoris determined，that is，in the time range[T h1，T h2]the conflict occurs.

2 Multi-UAV Conflict Resolution Modeling

2.1 Basic ant colony algorithm application modeling

A simplified model of multi-UAV ground station-based conflict resolution planning can be formulated as follows.

（1）The drone has good maneuverability and can even hover in the air.However，because the power consumption during hovering is far greater than the working power consumption，it is assumed that the drone does not use the hovering strategy when a collision is imminent，but one of three speed-regulation strategies has to be chosen:Low，medium，or high speed.

（2）Assume that the drone can use any of three steering maneuvering strategies when implementing an escape strategy:Maintaining the original heading，yawing 30°to the left，or yawing 30°to the right.

（3）Assume that the drones are equipped with ADS-B surveillance equipment，thus the position，speed，and altitude of the drone at each point in time can be obtained，and the target position of the drone is known.

ThenUAVs are divided intolsteps along the line joining their current positions to their target position.During the forward propulsion process，there are three heading strategies and three speed strategies available to the UAVs.It is assumed that when a drone moves from positionAat timet-1 to positionBat timet，there are nine possibilities for positionCthat the drone may reach at timet+1.As shown in Fig.2，C1，C2，andC3are positions that represent high-speed，medium-speed，and lowspeed left yaw at 30°；C4，C5，andC6are positions that represent high-，medium-，and low-speed propulsion along the original heading；C7，C8，andC9are positions that represent high，medium，and low speed with a right yaw at 30°；the nine possible paths areBC1，BC2，…，BC9.The current UAV position and velocity vector matrix is represented asA k=[x，y，θ，v]，and the next UAV matrix can be expressed as

Fig.2 UAV path selection

Based on the above three conditions，collision detection is performed on all the UAVs in the airspace.When the conflict conditions are met，the trajectory can be changed by adjusting the heading and speed of the drone，and the distance of the deviation is guaranteed to be the shortest under the premise of escaping the conflict.

The three-dimensional coordinates of droneiafter operating forksteps are denoted asThe objective function of the algorithm is

where the objective functionfis required to be the minimum value，that is，the shortest distance of the drone from the original target in the conflict resolution situation；D irepresents the delay distance caused by droneiin this heading change.The delay distance generated by the drone can be expressed as the distance between positionand the destination coordinatesafterlsteps.The expression is

The expression can be expanded as follows

To make the conflict escape process reasonable，during maneuvering，a minimum horizontal interval constraint is added.This means that，at each moment，a minimum horizontal interval must be maintained between any two drones in the airspace.Assume that dronesi(x i，yi)andj(xj，yj)must satisfy the following expression

whereδindicates the minimum security interval when the drone is operating.

According to the previous assumptions and definitions，the ant colony algorithm is used to calculate the fundamental conflicts forndrones in the airspace.

First，the probabilityP k(t)of the drone passing through a certain pathkto another spatial position at timetis calculated as

whereτk(t)is the pheromone value of pathkat timet.The value is updated after each iteration is completed，and the updated expression is

whereτk(t+1)is the pheromone value on thek-segment trajectory att+1；ρthe attenuation coefficient of the pheromone value；1-ρthe pheromone retention coefficient；and Δτk(t)the total amount of pheromone obtained by pathkin this iteration.

Regarding the problem of pheromone distribution during execution of the ant colony algorithm，there are usually three models，and their calculation expressions are as follows.

（1）Ant cycle system model

whereQis a constant that represents the sum of pheromones that an ant can produce in each cycle andL ithe total distance that antihas traveled.

（2）Ant density system model

（3）Ant quantity system model

whered iis the distance that antipasses through the section.

It can be seen from Eqs.（13）—（15）that each model considers a different range.The ant density system model considers the ants passing through the path，whereas the ant quantity system model and the ant cycle system model separately consider the distance traveled by the ants from local and overall perspectives and then assign the pheromone concentrations.This study uses the path with the least delay from the perspective of global optimization.Therefore，using the ant cycle system pheromone release model，the shorter the path，the greater the pheromone increments that are obtained during each iteration.

According to Eq.（13）for the ant cycle system model，the expression for the pheromone release amount Δτk(t)is

whereQis the total amount of pheromone left after a drone has gone completely andfthe sum of the final delay distances of all drones.

After the objective function，constraints，path selection method，and pheromone release method have been determined，the operation of the ant colony algorithm can be divided into five steps.

Step 1Assign initial values to the variables and parameters that need to be used during the operation of the ant colony algorithm，including the number of dronesM=N×m，the starting pheromone at each nodeφ，the volatilization factorρ，the maximum number of loop iterationsCmax，and the sum of the pheromones released by the drone at each cycleQ，and the starting value of the iterative computationk.

Step 2Divide theMUAVs intoNgroups andmbatches and place them atNdifferent starting points.For each drone，the probability of passing to the next target is obtained according to Eq.（11），and a random selection is conducted according to probabilities to guide the drone to complete the step node selection.

Step 3Constrain the selection of each batch of drone nodes according to Eq.（10），which should meet the minimum safety interval of the drone.If the selected path does not satisfy the constraint，the batch of drones is re-selected，and the path combination is no longer selected at the same time to ensure that no drone at any time has conflict with other drones.

Step 4Calculate the distance between each drone and the target point after completing the path.Calculate the target function value of each batch of drones using Eqs.（7）—（9）.The minimum objective function value is obtained by comparing the objective function values in one cycle，and then each node pheromone value is updated according to the pheromone release expression.

Step 5If the number of cycles is less than the set maximum number of iterations，return to Step 2 and continue the iterations.Otherwise，stop iterating and output the escape path.

Fig.3 shows the operation of the basic ant colony algorithm.

2.2 Improved ant colony algorithm application model

2.2.1 Introduction of angle information

In the selection process of the UAV at timetto the next time target，the basic ant colony algorithm is based solely on the ratio of the pheromone at the next node to the total pheromone at all feasible nodes，and this ratio is proportional to the probability of selecting the node.On this basis，the UAV is constrained to the angle between nodet+1 and the starting point，which means increasing the probability of selecting a node with a smaller angle between the end point and the starting line，as shown in Fig.4.

Fig.3 Ant colony execution process

Fig.4 Preferred angle diagram

In Fig.4，the two pointsSandDare the starting point and the destination of the drone. The drone has nine nodes to choose from at timet.The available nodes are connected to the starting point，and then the starting point is connected to the target point. The smaller the angle formed by the two lines，the more likely it is to be selected.In this example，the angleαformed by the selection of nodeFis the smallest，and therefore the probability that nodeFwill be selected is increased when the next node is selected.

2.2.2 Introduction of ant system based on sorting

A sorting-based ant colony system is introduced in this study.After each iteration，the objective function valuesfcalculated by all batches are sorted.The smaller the value，the higher the ranking.Only the topγunmanned drones will release pheromone through the path without missing the optimal solution，which ensurs that the best path has more pheromone superposition，speeds up algorithm convergence，and obtains the optimal solution faster.

The pheromone update formula is

wherefis the sum of the final delay distances of a group of drones；pkthe set of paths in the topk；andthe sum of the pheromone released by the drone on pathkin one iteration after the sort is introduced.

After introducing the angle information and sorting the ant system，the operation of the ant colony algorithm can be divided into five steps.

Step 1Assign initial values to the variables and parameters that need to be used during operation of the ant colony algorithm，including the number of dronesM=N×m，the starting pheromone concentration at each nodeφ，the volatilization factorρ，the maximum number of loop iterationsCmax，the sum of the pheromones released by the drone at each cycleQ，and the starting value of the iterative computationk.

Step 2Divide theMUAVs intoNgroups andmbatches and place them atNdifferent starting points.Add the factors of angle selection by weight and combine the pheromone concentrations to find the probabilities of going to the next target.According to the probabilities，a random selection is made to guide the drones to complete thel-step node selection.

Step 3Constrain the selection of each batch of drone nodes according to Eq.（10），which should meet the minimum safety interval of the drone.If the selected path does not satisfy the constraint，the batch of drones reselects the path and does not select the path combination at the same time，which ensures that there is no conflict between any drone and other drones at any time.

Step 4Calculate the distance between each drone and the target point after completing the path，and calculate the objective function valuefof each batch of drones by Eq.（7）.The objective function values in a loop are compared to obtain the minimum objective function value.The minimum objective function values are sorted from small to large，and the firstγvalues are recorded.At the same time，the pheromone concentration at each node is updated according to the improved pheromone release expression.

Step 5If the number of cycles is less than the set maximum number of iterations，return to Step 2 and continue the iterations；otherwise，stop iterating and output the escape path.

3 Multi-UAV Conflict Resolution Simulation

3.1 Basic ant colony algorithm simulation

Based on the above theory，a model was built，and a simulation scenario was designed.In the airspace range of 18 km×18 km，there were four drones，U1，U2，U3，andU4.The initial state of the four drones is shown in Table 1.

Table 1 Drone start state

The process of getting the drone from the starting point close to the target point was decomposed into 20 steps using a distance value.Each drone could adopt one of three flight speeds:5 m/s，10 m/s，or 15 m/s.As shown by the path of the UAVs simulated in Fig.5，the path running in the current state shows that a multi-UAV conflict condition will occur during the flight.Therefore，the basic ant colony algorithm，the improved ant colony algorithm added to the sorting system，and the improved ant colony algorithm with the ordering system and angle information were used to perform the conflict escape simulation.During the simulation，the total number of drones was set toM=80（divided into four groups），ρ=0.3，Q=100，and the maximum number of iterationsCmax=200.

For the multi-UAV ground station-based collision resolution problem，the conflict resolution path planned by the basic ant colony algorithm is shown in Fig.6.

Fig.5 Simulation plan design

Fig.6 Escape path plan by basic ant colony algorithm

According to the escape path obtained by the basic ant colony method，although the conflict situation between the multiple machines can be understood，the UAVs are far away from the target position，and the quality of the escape path plan is not good.The reason is not only that the initial conflict path selection is computationally intensive，but also that the low-quality a priori path causes the basic ant colony algorithm to converge finally to a local optimal solution instead of the global optimal solution.Therefore，the algorithm is improved by adding angle information and a sorting system to reduce the deviation of the azimuth，reduce the amount of calculation，shorten the calculation time，and verify the effect of the improved algorithm.

3.2 Improved ant colony algorithm simulation

The algorithm was revised to ensure that the best path has more pheromone superposition，speeding up algorithm convergence，and faster speed of obtaining the optimal solution.

The results of the escape path plan，shown in Fig.7，show that the improved algorithm objective function value is better than that obtained from the basic ant colony algorithm，and that the delay generated by the improved algorithm by introducing the sorting system and angle information is significantly reduced.

Fig.7 Improved ant colony algorithm conflict resolution results

In the face of multiple unmanned aircraft conflicts，the drone needs to maintain a minimum interval between itself and other drones.Fig.8 shows the real-time distances between the drones during the unmanned aircraft unblocking process.At this time，the distance between UAV2and UAV3in the operation to Step 14 is a minimum of 1.58 km，which is greater than the minimum interval and meets the minimum interval requirement in the conflict resolution process.

Fig.8 Distances between two drones

The two algorithms were simulated 30 times each，and thef-values obtained by both algorithms were recorded.The length of the minimum delay was calculated every three times，as shown in Fig.9.It can be seen that the improved ant colony algorithm reduces the final total delay distance.

Fig.9 Final delay distance based on the conflict resolution algorithm

In the simulation，each algorithm was simulated 30 times.The time taken by the various algorithms was recorded（Table 2），and the shortest time was selected 10 times. Obviously，the improved ant colony algorithm reduces computation time.

Table 2 Calculation time of the optimization algorithm s

3.3 UAV priority allocation

Depending on the length of time that each drone is waiting in the air and the priority of each drone's operation，it is determined whether the drone needs to be prioritized.By increasing the proportion of priority drones in the optimal target，the system ensures that UAVs that need to be prioritized consistently obtain a better solution.

During the simulation，the priority levels of UAV1and UAV2were increased to ensure their priorities in reaching their destination，and the escape routes were simulated. The simulation results（Fig.10）showed that the UAV conflict can be solved and that the priority-guaranteed UAVs can obtain a better path plan in the simulation process，that is，it will be closer to its target point after completing the operation according to the planned route，whereas the other unmanned machines will sacrifice distances from their target points.After performing multiple simulations，the average calculation time was 28.4 s，which was not much different from the optimization algorithm in this paper.However，average delay distance was 13.3 km，which was 13% longer than the no-priority situation.Therefore，this method can effectively realize priority drone path planning at the expense of a small amount of overall optimization.

Fig.10 UAV priority allocation release results

4 Conclusions

With the objective of resolving the multi-UAV conflict situation that may occur when operating UAVs in airspace，this paper proposes an interplane linear extrapolation method for collision detection to determine possible multi-UAV conflicts.Based on the basic ant colony algorithm，the ordering system and angle information are combined，and speed and heading adjustment strategies for the drones are also considered.The minimum delay distance is the optimization target to plan the path of the drone under imminent collision.Case analysis demons trates the basic ant colony algorithm can provide solutions for multiple unmanned aircraft conflicts，but the total delay distance is large，and the calculation time is long.With the improved ant colony algorithm proposed in this paper，computational efficiency is improved，the time required for the algorithm to converge to the optimal target path is reduced by 43.9%，and the final total delay distance is reduced by 58.4%.