Received May 31, 2019, accepted June 25, 2019, date of publication June 28, 2019, date of current version July 15, 2019. Digital Object Identifier 10.1109/ACCESS.2019.2925633 Collision Avoidance Method for Self-Organizing Unmanned Aerial Vehicle Flights YANG HUANG 1, JUN TANG 2, AND SONGYANG LAO1 1 Collegeof Systems Engineering, National University of Defense Technology, Changsha 410072, China 2 Technical Innovation Cluster on Aeronautical Management, Universitat Autònoma de Barcelona, 08201 Sabadell, Spain Corresponding author: Jun Tang (jun.tang@e-campus.uab.cat) This work was supported in part by the National Natural Science Foundation of China, China, under Grant 71601181, in part by the Young Talents Lifting Project, China, under Grant 17JCJQQT048, in part by the Huxiang Young Talents, China, under Grant 2018RS3079, and in part by the Complex Situational Cognitive Technology under Grant 315050202. ABSTRACT Autonomous unmanned aerial vehicle (UAV) swarm flights have been investigated widely. In the presence of a high airspace density and increasingly complex flight conditions, collision avoidance between UAV swarms is very important; however, this problem has not been fully addressed, particularly among self-organizing flight clusters. In this paper, we developed a method for avoiding collisions between different types of self-organized UAV clusters in various flight situations. The Reynolds rules were applied to self-organized flights of UAVs and a parameter optimization framework was used to optimize their organization, before developing a collision avoidance solution for UAV swarms. The proposed method can self-organize the flight of each UAV swarm during the overall process and the UAV swarm can continue to fly according to the self-organizing rules in the collision avoidance process. The UAVs in the airspace all make decisions according to their individual type. The UAVs in different UAV swarms can merge in the same space while avoiding collisions, where the UAV’s self-organized flight process and collision avoidance process are very closely linked, and the trajectory is smooth to satisfy the actual operational needs. The numerical and experimental tests were conducted to demonstrate the effectiveness of the proposed algorithm. The results confirmed the effectiveness of this approach where self-organized flight cluster collision avoidance was successfully achieved by the UAV swarms. INDEX TERMS Collision avoidance, parameter optimization, Reynolds rules, self-organized, unmanned aerial vehicle cluster. I. INTRODUCTION might merge from different directions during a self-organized Owing to scientific and technological development, the roles UAV flight. Therefore, a collision avoidance method is of unmanned aerial vehicles (UAVs) have become increas- required to prevent collisions assuming self-organized flight ingly important in both military and civilian fields. The conditions. inherently small and flexible nature of UAVs allows them Improvements and optimization are required for the UAV to perform well in many areas, and they are particularly self-organizing flight model, and a collision avoidance useful in environments and situations that are not suitable method is needed for UAV swarms comprising multiple for humans. UAV swarm collaboration will become com- UAVs in the self-organized flight mode. Many methods are monplace to meet the increasingly complex requirements currently employed for self-organizing UAV flights, such of future missions. Communication and control become as the Reynolds rules [1], pigeon flock algorithm, and increasing difficult as the number of UAVs increases; thus, goose swarm algorithm. In the field of UAV collision it is important to achieve self-organization behavior dur- avoidance, the approaches employed include the artificial ing UAV flights. In self-organizing cluster flights, com- potential field method [2], [3], ant colony algorithm [4], [5], munication and messaging can occur between the UAVs; genetic algorithm [6], [7], particle swarm optimization however, external instructions cannot be sent. Thus, indi- algorithm [8], [9], Markov decision method [10], and vidual UAVs must analyze the available information and dynamic programming method [11], [12]. make their own decisions. However, a swarm of UAVs UAV collision avoidance methods have been studied for decades and various strategies have been proposed for col- The associate editor coordinating the review of this manuscript and lision avoidance by self-organized drones, but each method approving it for publication was Haluk Eren. This work is licensed under a Creative Commons Attribution 3.0 License. For more information, see http://creativecommons.org/licenses/by/3.0/ 85536 VOLUME 7, 2019 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights TABLE 1. Self-organizing uav flight anti-collision methods. has practical difficulties. Thus, to facilitate collision avoid- cluster control algorithm based on the dove cluster and ance in self-organizing UAV flights in practical applications, a coordinated obstacle avoidance model for managing a we developed a method by optimizing the parameters of the situation where a UAV swarm flies through an environ- force formula used in the Reynolds rules. In the following, ment containing obstacles without additional information. we review relevant research into the UAV self-organized Hauert et al. [22] studied the trade-off between the commu- flight collision avoidance problem. nication range and flight dynamics in a simulation within the Table 1 lists 14 previous studies that proposed models Reynolds cluster. Hildenbrandt et al. [23] combined conven- for UAV self-organized flight collision avoidance, where the tional coordination rules based on separation, attraction, and key characteristics of these studies are indicated as: physical alignment with the details of ostrich behavior to provide new experiment, target parameter optimization, UAV type, and insights into the complex clustering mechanisms employed leader agent based. In particular, ‘‘physical experiment’’ indi- by ostriches and other birds. Han et al. [24] proposed a new cates whether a physical experiment was conducted, ‘‘target concept called ‘‘soft control’’ for regulating the collective parameter optimization’’ indicates whether parameter opti- behavior of self-organizing, multi-agent systems and demon- mization was performed based on the flight target, ‘‘UAV strated a natural method for intervening in distributed sys- type’’ denotes the type of UAV, i.e., fixed-wing UAV(F) or tems. Vásárhelyi et al. [25] solved the problem of seamless quadrotor UAV(Q), while ‘‘/’’ indicates that the type of UAV navigation by a UAV swarm in a narrow space by addressing was not specified, and ‘‘leader agent based’’ shows whether and resolving issues in terms of constrained motion and com- there was a leader in the UAV swarm. munication capabilities, delays, disturbances, or obstacles. Qiu and Duan [14] proposed a distributed optimization They proposed carefully selected sequence parameters and an control framework for UAV clusters, which transformed the evolutionary optimization framework for a fitness function, multi-objective optimization problem into a problem that can and they used 30 self-organizing UAVs in field experiments. be solved using a single UAV. A distributed cluster control This was the largest airborne outdoor system without central algorithm for UAVs based on an improved multipath I/O was control reported in previous studies, and they demonstrated proposed, which allows a UAV swarm to exhibit stable flight successful avoidance by clusters of collective UAVs with in a complex environment. Di et al. [15] proposed a two-layer effective avoidance control. control framework to address the collaborative surveillance In the present study, we developed an optimized, self- problems using multiple UAVs, and distributed back horizon organizing flight method to ensure stable flight and colli- optimization for planning UAV movements in cluster flight sion avoidance by UAV clusters. Our approach does not situations. Braga et al. [16] used the Reynolds cluster rules require a leader to self-organize the flight and it achieves to drive a swarm of UAVs, and then conducted physical self-organized flight collision avoidance for multiple UAV experiments to demonstrate the feasibility of the method. swarms by optimizing the resulting trajectory for fixed-wing Kownacki et al. applied the two basic Reynolds rules and UAVs and quadrotor UAVs, which is difficult for other meth- combined them with leadership features to achieve the col- ods. Our method does not require a leader, which means lective flight of fixed-wing UAVs. Clark and Jacquesva [18] that there is no mutual control between the drones and a conducted a UAV cluster flight test at NASA’s Dryden Flight flight decision is made by assessing the airspace situation. Research Center as an important step in the development The core idea of this method involves optimizing UAV flight of a deployable distributed boid system. Sajwan et al. [19] parameters by defining a fitness function for optimizing clustered the UAVs in a leader–follower manner and solved UAV flight. We studied the collision avoidance method in each follower’s control problem in the context of stochastic a self-organized UAV swarm flight and designed a new optimal control, where the problem was solved offline by collision avoidance algorithm for self-organized flight col- dynamic programming to minimize the expectations within lision avoidance. The method was validated in simulations a limited range. Qiu and Duan [14] designed a distributed using MATLAB. VOLUME 7, 2019 85537 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights The remainder of this paper is organized as follows. The clustering algorithm based on the bird flight rules pro- In Section II, we present the traditional Reynolds flocking posed by Reynolds can be summarized as follows. model. In Section III, we describe the optimization method R1 - Alignment: individuals attempt to align their velocity based on the Reynolds rules and a collision avoidance method to the average velocity of nearby flock mates. for self-organizing flight. In Section IV, we present the simu- R2 - Cohesion: individuals attempt to match the average lation results and their analysis. We give our conclusions and position of nearby flock mates. discuss future research in Section V. R3 - Separation: individuals attempt to avoid collisions with nearby flock mates. II. TRADITIONAL REYNOLDS FLOCKING MODEL However, the Reynolds rules are simply a simulation of It should be noted that we do not consider the specific flight flock behavior and model details need to be optimized further control problem for the UAV and our method only plans the for application to a real UAV system. trajectory of the UAV. Thus, we address the collision avoid- ance problem for UAV clusters with normal communication III. OPTIMIZED FLOCKING MODEL WITH between UAVs regardless of the time delay for communica- COLLISION AVOIDANCE tion between UAVs. The proposed flocking model is based on the Reynolds rules We write U =< P, V , A > to represent the UAV clus- and the optimized model is based on a previously described * * * * * ter system. P = ( p 1 , p 2 , · · · , p i , · · · , p N ), p i ∈ Rn are model [25]. As shown in Figure 1, self-organized UAV flight * * defined as the position vector of UAVi ; V = ( v 1 , v 2 , · · · , cluster collision avoidance is based on the Reynolds rules, * * v i , · · · , v N ) are defined as the speed vector of UAVi ; A = where the first advance involves providing an update by * * * * * ( a 1 , a 2 , · · · , a i , · · · , a N ), a i ∈ Rn indicate the acceleration calculating the combined effect of different forces. None of vector of UAVi . The formula for the motion of a UAV is as the different UAV swarms in the simulation are controlled by follows. ground control stations, but instead they rely solely on infor- ( * mation sent by other UAVs for analysis and decision making. ṗi (t) = v i (t) * (1) In Section A, we introduce the basic Reynolds cluster rules v̇i (t) = a i (t) and some added buffer functions to make the cluster rules According to this formula, the control of the motion by more suitable for actual flight. In Section B, we introduce a UAV cluster may depend on the acceleration control. The the parameter optimization method for the cluster flight rules speed and acceleration of the UAV are constrained by the as well as the design of the corresponding objective function following formulae: and iterative search of a random simulation scene to find the * various force parameters that best match the objective func- *  v i (t),  v i (t) ≤ vmax tion. In Section C, we describe the self-organizing collision *  * avoidance method for UAV swarms. v i (t) = v i (t) * (2) v · , v i (t) > vmax  max *   v (t) i A. OPTIMIZED FLOCKING MODEL 1) REPULSION * * a (t), a i (t) ≤ amax  i  To keep the focal UAV, UAVs , separate from the other UAVs,  * * a i (t) = a i (t) * (3) each UAV receives a collision avoidance force known as the a · , a i (t) > amax ,  max *  separation force, which is defined as follows:  a i (t) n n * where vmax is the limited maximum speed value and amax is * 1 X* 1X p s (t) − pi (t) f sep (t) = f s,i (t) = k · ψi (t) · n n * the limited maximum acceleration value. i=1 i=1 p s (t) − pi (t) During the actual flight of an UAV, the change in flight (5) angle needs to be limited owing to the flight performance limitations of the UAV. where ψi (t) is defined as: The amount of change in the angle of an UAV is also  1 1 limited, as shown in Eq. (4), where θmax is the maximum   r −p , d  * * sep  change in the angle of the UAV.    p s (t) − p i (t) * ψi (t) = * * (6) vi (t) · v i (t − 1) if p s (t) − p i (t) ≤ dsep > cos θmax  * * (4)    k v i (t)k · k v i (t − 1)k  0, if *  * p (t) − p (t) > dsep ,  s i Reynolds first introduced a distributed flock behavior model in 1987 [1]. This model is based on the phenomenon and n indicates the serial number of each remaining UAV of cluster flights according to the behavior of bird flocks. other than the focal UAV (UAVs ). In Eq. (6), ψi (t) is the non- * * Subsequent research into flock modeling led to the defi- linear gain of pairwise repulsion and p s (t) − p i (t) is the nition of three simple rules for simulating flight decisions distance between UAVs and UAVi . The symbol dsep defines and state updates for a single individual in a flock of birds. the maximum interaction range at which UAVs start to repel 85538 VOLUME 7, 2019 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights FIGURE 1. Self-organized flight concept diagram based on Reynolds rules. each other and k is a coefficient that affects the magnitude of Thus, the velocity alignment term calculated for UAVi with the repellent force. respect to UAVj is:    max 2) VELOCITY ALIGNMENT    Qtor vij − vtorij UAV clusters are collectively managed by individuals match- * *   *tor  v i (t) − v j (t) ing their average cluster velocity according to Eq. (7): v ij (t) = · , if vij > vtor ij max (10) * * n n n    v i (t) − v j (t) * 1 X* 1 X* 1X * *    0, f ali (t) = f a,i (t) = v a,i (t) = ( v i (t)− v a (t)) otherwise n n n i=1 i=1 i=1 (7) where vtor represents the amount of velocity slack required * to allow for a certain amount of speed difference, which where v a,i (t) represents the speed of UAVi relative to UAVa is independent of the relative distance, ptor 0 indicates the and n represents the number of UAVs other than UAVa . distance of UAVi relative to the stop point in front of UAVj , The flocking algorithm needs to handle possibly large and k tor and ator represent the linear gain and acceleration velocity differentials at the same time, so a braking curve parameters for a pair of consistent speed changes, respec- known as a velocity decay function (denoted by D(.)) is tively. In Eq. (10), Qtor represents the linear coefficient of applied to the flocking algorithm. The decay function aims to the speed fault reduction and vij represents the absolute value provide constant acceleration at high speed and exponential of the speed difference between UAVi and UAVi . acceleration at low speed, as shown in Eq. (8):  3) FLOCK CENTERING  0, if r ≤ 0   The UAV cluster needs to be as close to the center of nearby D(r, a, p) = q rp, if o < rp < a/p (8)  UAVs as possible, and thus the cohesion force is given by  2ar − a2 /p2 , otherwise  Eq. (11): where r is the distance between a UAV and a desired stopping * n 1 X* n 1 X *  * point, a denotes the expected acceleration, and p represents f cen (t) = f c,i (t) = p i (t) − p c (t) (11) n n the maximum speed difference allowed at a certain separation i=1 i=1 distance. where n represents the number of UAVs other than UAVc . To construct the velocity alignment pattern, the speed dif- ference that can be tolerated at a certain relative distance is 4) FLIGHT TARGET POSITION given by Eq. (9). To reach the desired position, the UAV cluster should know vtor max = max vtor , D pij − ptor 0 ,a ,k tor tor  ij (9) the general direction of the flight. We define the general VOLUME 7, 2019 85539 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights direction as: where S(ξ, ξ0 , d) is a sigmoid function: * * * 1, if x < x0 − d  f tar (t) = p des − p i (t) (12)   1 π  * (x − x0 ) ,  where p des represents the target end point vector of the UAV. 1 − cos  S (x, x0 , d) = 2 d (21)   if x0 − d < x < x0 5) FINAL COMBINED FORCE FORMULAE    0, otherwise Thus, the final combined force formulae are: * * * The second transfer function is a sharp peak transfer func- v i (t) = f steer + v i (t − 1) (13) tion, as follows. * * p i (t) = p i (t − 1) + vi (t) (14) z2 where: F2 (ξ, z) = (22) (ξ − z)2 * * * f steer (t) = ω1 · f sep (t) + ω2 · f ali (t) + ω3 Finally, we construct the following single objective fitness * * * function, which includes all of the related flocking behaviors. · f cen (t) + ω4 · f tar (t) − v i (t − 1) (15) F = Fcor · Fcol · Fspeed (23) In Eq. (15), ω1 , ω2 , ω3 , and ω4 represent the weight coef-  ficients of each force.  Fcor = 2 (ξcor ) · ξcor  Fcol = F2 ξcol , aup  (24) B. FLOCKING OPTIMIZATION ALGORITHM Fspeed = F1 ξvel , vflock , vup    1) FLIGHT EFFECT EVALUATION FUNCTION A statistic is employed to measure the anti-collision effect C. COLLISION AVOIDANCE BETWEEN SWARMS OF UAVs during the self-organizing flight of a UAV swarm, which When different UAV swarms merge together, the probabil- is then organized according to the statistic for parameter ity of collisions will increase significantly. The separation optimization. Let T be the entire simulation duration, dij (t) force defined above is no longer effective because its direc- is the distance between UAVi and UAVj at time t, and dcol tion is almost opposite to the direction of speed. Therefore, refers to the danger zone around a UAV. In this situation, new rules are necessary to achieve the anti-collision targets the collision risk is defined as shown in Eq. (16), where 2(·) between different UAV swarms. is the Heaviside step function. In the presence of other UAV swarms, the force responsible T X N X for preventing collisions is a force that overlaps with other 1 1 X forces as little as possible; otherwise, the force used for ξcol = · 2 dij (t) − dcol  (16) T N (N − 1) collision prevention would be diluted. To meet this require- t=1 i=1 i=j  ment, we employ a three-dimensional (3D) geometry-based  0,  x<0 approach where we calculate the closest proximity position of 2(x) = 1, x>0 (17) the two opposing flying UAVs, and the corresponding applied  1/2, x = 0 force is then obtained according to the speed and position  information for the UAVs. The magnitude of the force is the The next key element for self-organizing flight is the veloc- same as the previous separation force but its direction differs. ity alignment motion. The UAV cluster velocity correlation is measured as shown by Eq. (17). T N X X X vi (t) · vj (t) 1 1 ξcor = · (18) T N (N − 1) * * t=1 i=1 i=j v i (t) · v j (t) Finally, we require that the UAV cluster move at a des- * ignated speed. Let v flock be the designated speed and it is measured according to Eq. (18). T N 1 1 X X *  ξvel = · v i (t) − vflock (19) T N t=1 i=1 FIGURE 2. Method for calculating the nearest relative distance between two UAVs. The global function can be defined using the following three types of transfer functions. The first type is a monotonically growing function repre- As shown in Figure 2, the key step involves calculating the sented as: time taken to arrive at the closest point of approach (CPA). CPA occurs at the moment when the two UAVs arrive at their F1 (ξ, ξ0 , d) = 1 − S (ξ, ξ0 , d) (20) closest point. 85540 VOLUME 7, 2019 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights Algorithm 1 Self-Organizing UAV Flight Cluster Collision Avoidance Algorithm Input: initial position, target position, initial velocity of UAVs, number of UAVs N , simulation step length S, labels of the UAVs Output: trajectories of all the UAVs while flock do if label is the same &&Dij < Dsafe1 Steering_force = Repulsion_force + Alignment_force + Cohesion_force + Target_force – Current_velocity; elseif label is different &&Dij < Dsafe2 Steering_force = Repulsion_force; end Updated_velocity = Current_velocity + Steering_force; Updated_position = Current_position + Updated_velocity; end First, we calculate the CPA between UAVi and UAVj . The Similarly, the anti-collision force for UAVj can be written distance between UAVi and UAVj is defined according to as follows. Eqs (25)–(27):  * * * h ji dCPA,ij * * , if h ji · p ji < 0  h ij · p ij    C · * * · * dCPA,ij = (25) * | v i| · | v j| | p ij |  * h ij fj= *  h ji dCPA,ij * * , if h ji · p ji ≥ 0,  C · * ·  * * *  * * h ij = v i × v j (26) | v i| · | v j| | p ij | * * * * * * p ij = p j − p i (27) h ji = v j × v i (33) * * where p i = (xi , yi , zi ) and p j = (xj , yj , zj ) are the positions * The basic idea of this method is that the direction of of UAVi and UAVj , respectively, and v i = (vi,x , vi,y , vi,z ) and * the force is perpendicular to the relative position vector v j = (vj,x , vj,y , vj,z ) are their velocities. of the UAV when it reaches CPA. This approach gives the We then determine the time required to reach CPA, which * * UAV the most effective control over the relative distance is defined as 1t. The formula p ij,t+1t · v ij = 0 holds when beyond the safe distance to the CPA. the UAVs arrive at the CPA. Assuming that the locations of Algorithm 1 is the collision avoidance algorithm for a the UAVs at time t + 1t are as given by Eqs (28) and (29): * cluster of self-organizing UAVs, where the core step involves p i,t+1t = xi + vi,x · 1t, yi + vi,y · 1t, zi + vi,z · 1t (28)  distinguishing the UAV repulsive force from different UAV * p j,t+1t = xj + vj,x · 1t, yj + vj,y · 1t, zj + vj,z · 1t , (29) swarms.  where t is the current moment, then we can calculate the IV. SIMULATION AND RESULTS relative position vectors for the UAVs at time t + 1t. Scripts were written in Matlab to generate four different pij,t+1t = (xj − xi + (vj,x − vi,x ) · 1t, yj simulation scenarios. Each UAV swarm was assumed to be − yi + (vj,y −vi,y ) · 1t, zj − zi + (vj,z − vi,z ) · 1t) heading toward its own target position along a straight line (30) at 5 m/s. The minimum safe separation distance, d0, was defined as 15 m. The interval time, t0, for discrete points Therefore, the time interval 1t can be calculated as was set as 0.1 s. The corresponding weight coefficients follows. w1, w2, w3, and w4 were calculated as 427, 0.225, 0.452, 1t and 548, respectively. The maximum variation range for (xj −xi )(vj,x −vi,x )+(yj −yi )(vj,y −vi,y )+(zj −zi )(vj,z −vi,z ) the pitch angle, A, was 0.74, and the minimum value, B, = was −0.74. We assumed that each UAV could receive infor- (vi,x −vj,x )2 +(vi,y −vj,y )2 +(vi,z −vj,z )2 (31) mation from the other UAVs and that the simulation calcula- tion times could be ignored. The simulations were performed Based on the information described above, we propose using an HP EliteBook laptop, with an Intel i5 processor at a formula for calculating the anti-collision force for UAVi , 2.6 GHz and 4 GB of RAM. as follows.  * h ij dCPA,ij * * A. UAVs IN A SWARM FLYING TOWARD EACH OTHER · * , if h ij · p ij < 0   C · |*   * We assumed that two swarms of UAVs approached each other  * v i | · | · | v j | | p ij | fi= * (32) from opposite directions, and thus collisions were imminent.  h ij dCPA,ij * * · * , In the simulations, each UAV swarm contained three UAVs  C · *   * if h ij · p ij ≥ 0 | v ij | · | v j | | p ij | and each UAV swarm was self-organized to form its own team VOLUME 7, 2019 85541 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights TABLE 2. Initial UAV states for the first flight scenario. FIGURE 3. Simulation results for scenario one. at the target location. The initial state and target status for each area, where the distributions of their positions in space UAV are shown in Table 2. were uniform and their trajectories satisfied the actual flight In Figure 3a, each UAV trajectory is displayed in the form demands. of a 3D curve. The green tracks represent the trajectories Figure 3b shows the relative distance between each of the first UAV swarm and the red tracks represent the UAV pair. The minimum distance between any two UAVs trajectories of the second swarm. Figure 3a shows that the was 15.03 m, which was above the lower limit of the safe trajectories of the two swarms changed continually during separation distance. the collision avoidance process. The UAVs in the two swarms flew from the scheduled starting position in a self-organized B. UAV SWARM FLIGHT SCENARIO THAT manner until the end of the flight. During the entire col- MIGHT CAUSE A DOMINO EFFECT lision avoidance process, the two UAV swarms adaptively A second scenario was generated to detect whether collision generated collision avoidance movements within the collision avoidance could be achieved in a high traffic density situation 85542 VOLUME 7, 2019 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights FIGURE 4. Simulation results for scenario two. TABLE 3. Initial UAV states for the second flight scenario. where the airspace was limited and the UAV vertical sepa- trajectory of the first UAV swarm and the red track repre- ration distances were very small. Figure 4 shows that two sents that of the second swarm. In this simulation scenario, swarms of approaching UAVs were present and their colli- the UAVs generally adopted horizontal strategies for collision sions were imminent. Unlike scenario 1, the UAV formations avoidance because vertical collision avoidance movements in each swarm were arranged in a vertical manner and this could have resulted in a domino effect. This scenario verified formation could lead to a collision domino effect when the the anti-collision effect of self-organizing UAV clusters in a UAV swarms met. Table 3 shows the initial state and the target vertically stacked situation. Figure 4b shows the relative dis- status of each UAV. tances between each UAV pair, where the minimum distance The trajectory of each UAV is presented in the form of between any two UAVs was 15.02 m, which was higher than a 3D curve in Figure 4a. The green track represents the the minimum safe separation distance. VOLUME 7, 2019 85543 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights FIGURE 5. Simulation results for scenario three. TABLE 4. Initial UAV states for the third flight scenario. C. UAV SWARM VERTICAL CROSS FLIGHT the second swarm. Figure 5b shows the relative distance This scenario was designed to test whether UAV swarm col- between each pair of UAVs, where the minimum distance lisions could be avoided effectively in the vertical direction. between any two UAVs was 15.04 m, which was above the Figure 5 shows that two UAV swarms approached each other minimum safe separation distance. at a vertical angle and collisions were imminent. The simu- lation showed that the method could readily ensure collision D. THREE DIFFERENT DIRECTIONS OF UAV avoidance in this scenario and the anti-collision trajectories SWARM GATHERING SCENE were very smooth, thereby meeting the realistic flight require- This scenario tested the effect of the anti-collision method ments. This scenario supported the effectiveness of the anti- when several UAVs arrived in the same airspace from dif- collision method when UAV swarms meet at a vertical angle. ferent directions. Figure 5 shows that three swarms of UAVs The initial state and target status for each UAV are shown were flying from three different directions and collisions were in Table 4. imminent. This scenario tested whether the algorithm was The trajectory of each UAV is represented by a 3D curve still effective at avoiding collisions when the UAV swarms in Figure 5a. The green track represents the trajectory of merged from three different directions. The simulation results the first UAV swarm and the red track is the trajectory of showed that although the airspace density was high, the 85544 VOLUME 7, 2019 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights TABLE 5. Initial UAV states for the fourth flight scenario. FIGURE 6. Simulation results for scenario four. anti-collision effect was very good and the flight paths did that collisions were successfully avoided in the drone swarm. not require excessive deviations, thereby meeting the realistic The relative distance maps indicated that the collision avoid- flight requirements. The initial state and target status of each ance effect was very good for the UAVs, and each UAV swarm UAV is shown in Table 5. continued to move toward the target position after completing The trajectory of each UAV is represented by a 3D curve the collision avoidance process. The relative distances of the in Figure 6a. The green track represents the trajectory of the UAVs in the same swarm or in different swarms were also first UAV swarm, the red track is that for the second swarm, maintained in a smooth manner during the entire collision and the blue track is that for the third swarm. Figure 6b avoidance process. However, in the fourth scenario, the rel- shows the relative distance between each pair of UAVs, where ative distances of the UAVs at the CPA varied more than the minimum distance between any two UAVs was 15.03 m, those in the first three scenarios because the airspace traffic which was higher than the minimum safe separation distance. density was very high in the same airspace at the moment corresponding to the CPA, and each UAV swarm was at risk E. SIMULATION ANALYSIS AND COMPARISON of colliding with the UAV swarm in both directions. OF VARIOUS SCENARIOS The mixed state of the UAV swarm was observed using the Each simulation scenario showed that all of the UAVs were relative distance curves for the UAVs and by assessing the located greater than the safe distance, thereby demonstrating topology of the UAV swarm from the side. For each scene, VOLUME 7, 2019 85545 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights two types of relative distance curves were obtained, where [3] Y. C. Chang and Y. Yamamoto, ‘‘On-line path planning strategy inte- one tended to form a straight line and other tended to form grated with collision and dead-lock avoidance schemes for wheeled mobile robot in indoor environments,’’ Ind. Robot, vol. 35, no. 5, pp. 421–434, a curve. The former represents the relative distances of the Aug. 2008. doi: 10.1108/01439910810893590. UAVs inside the swarm and the latter within the different [4] S. Perez-Carabaza, E. Besada-Portas, J. A. Lopez-Orozco, and J. M. de la swarms. The relative distance curve inside the swarm was Cruz, ‘‘Ant colony optimization for multi-UAV minimum time search in uncertain domains,’’ Appl. Soft Comput., vol. 62, pp. 789–806, Jan. 2017. smooth and it varies little, and thus the UAVs inside the doi: 10.1016/j.asoc.2017.09.009. swarm had a smooth and compact topology throughout the [5] H.-B. Duan, X.-Y. Zhang, J. Wu, and G.-J. Ma, ‘‘Max-min adaptive simulation. ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments,’’ J. Bionic Eng., vol. 6, no. 2, pp. 161–173, Jun. 2009. doi: 10.1016/S1672-6529(08)60113-4. V. CONCLUSION AND FUTURE WORK [6] V. Y. Pehlivanoglu, ‘‘A new vibrational genetic algorithm enhanced In this study, the self-organized flight of UAV swarms was with a Voronoi diagram for path planning of autonomous UAV,’’ Aerosp. Sci. Technol., vol. 16, no. 1, pp. 47–55, Jan./Feb. 2012. optimized based on the Reynolds rules. A new fitness func- doi: 10.1016/j.ast.2011.02.006. tion was proposed and the parameters were optimized using [7] O. K. Sahingoz, ‘‘Generation of bezier curve-based flyable trajectories a CMA-ES optimization algorithm. A new cluster anti- for multi-UAV systems with parallel genetic algorithm,’’ J. Intell. Robotic Syst., vol. 74, nos. 1–2, pp. 499–511, Apr. 2014. doi: 10.1007/s10846-013- collision algorithm was also proposed. The simulation results 9968-6. proved that the proposed self-organized UAV swarm flight [8] Y. Liu, X. J. Zhang, X. M. Guan, and D. Delahaye, ‘‘Adaptive sensitivity collision avoidance method performed in a safe and effective decision based path planning algorithm for unmanned aerial vehicle with improved particle swarm optimization,’’ Aerosp. Sci. Technol., vol. 58., manner with smooth avoidance trajectories, thereby meeting pp. 92–102, Nov. 2016. doi: 10.1016/j.ast.2016.08.017. the realistic flight requirements. The main contributions of [9] J. L. Foo, J. Knutzon, and V. Kalivarapu, ‘‘Path planning of unmanned our study are summarized as follows. aerial vehicles using b-splines and particle swarm optimization,’’ J. Aerosp. Comput., Inf., Commun., vol. 58, pp. 271–290, Nov. 2009. doi: 1) Self-organizing flight rules were modeled for a UAV 10.2514/1.36917. swarm based on the traditional Reynolds rules and [10] S. Ragi and E. K. P. Chong, ‘‘UAV path planning in a dynamic envi- suitable constraints were added. A fitness function was ronment via partially observable Markov decision process,’’ IEEE Trans. Aerosp. Electron. Syst., vol. 49, no. 4, pp. 2397–2412, Oct. 2013. constructed to optimize the rules in the model to ensure doi: 10.1109/TAES.2013.6621824. that the self-organizing UAV swarm flight collision [11] M. Li, R. Z. Chen, W. L. Zhang, and D. Li, ‘‘A stereo dual-channel dynamic avoidance behavior was aligned with the actual flight programming algorithm for UAV image stitching,’’ Sensors, vol. 17, no. 9, p. 2060, Sep. 2017. doi: 10.3390/s17092060. requirements. [12] M. Radmanesh and M. Kumar, ‘‘Flight formation of UAVs in pres- 2) The traditional self-organizing flight rules are not ence of moving obstacles using fast-dynamic mixed integer linear pro- effective for addressing the collision avoidance prob- gramming,’’ Aerosp. Sci. Technol., vol. 50, pp. 149–160, Mar. 2016. doi: 10.1016/j.ast.2015.12.021. lem between UAV clusters, so we derived new anti- [13] M. De Benedetti and F. D’Urso, G. Fortino, F. Messina, G. Pappalardo, and collision rules between UAVs to improve the collision C. Santoro, ‘‘A fault-tolerant self-organizing flocking approach for UAV avoidance efficiency and obtain smooth avoidance aerial survey,’’ J. Netw. Comput. Appl., vol. 96, pp. 14–30, Oct. 2017. doi: 10.1016/j.jnca.2017.08.004. trajectories. In the simulations, the UAVs com- [14] H. Qiu and H. Duan, ‘‘Pigeon interaction mode switch-based UAV dis- pleted their anti-collision maneuvers without changing tributed flocking control under obstacle environments,’’ ISA Trans., vol. 71, speed, which is suitable for meeting the actual flight pp. 93–102, Nov. 2017. doi: 10.1016/j.isatra.2017.06.016. [15] B. Di, R. Zhou, and H. Duan, ‘‘Potential field based receding horizon requirements. motion planning for centrality-aware multiple UAV cooperative surveil- 3) Our proposed method was verified in four simulation lance,’’ Aerosp. Sci. Technol., vol. 46, pp. 386–397, Oct./Nov. 2015. experiments, where UAV swarms approached face- doi: 10.1016/j.ast.2015.08.006. [16] R. G. Braga, R. C. da Silva, A. C. B. Ramos, and F. Mora-Camino, to-face as well as extreme collision avoidance by ‘‘Collision avoidance based on reynolds rules: A case study using quadro- UAV swarms in the vertical direction, vertical angle tors,’’ in Proc. Inf. Technol.—New Generations, 2018, pp. 773–780. convergence to allow anti-collision by UAV swarms doi: 10.1007/978-3-319-54978-1_96. [17] C. Kownacki and D. Ołdziej, ‘‘Flocking algorithm for fixed-wing approaching in the horizontal direction, and colli- unmanned aerial vehicles,’’ in Proc. Adv. Aerosp. Guid., Navigat. Control, sion avoidance by UAV swarms approaching the same 2015, pp. 415–431. doi: 10.1007/978-3-319-17518-8_24. airspace from three different directions. [18] J. B. Clark and D. R. Jacques, ‘‘Flight test results for UAVs using boid guid- ance algorithms,’’ Procedia Comput. Sci., vol. 8, pp. 232–238, Dec. 2012. In future research, we will consider factors such as commu- doi: 10.1016/j.procs.2012.01.048. nication delays to further optimize the rules model as well as [19] M. Sajwan, D. Gosain, and S. Surani, ‘‘Flocking behaviour simulation: the drone speed to make the model more flexible. In addition, Explanation and enhancements in boid algorithm,’’ Int. J. Comput. Sci. Inf. Technol., vol. 5, no. 4, p. 5539, Jul. 2014. actual flight experiments will be conducted using fixed-wing [20] S. A. P. Quintero, G. E. Collins, and J. P. Hespanha, ‘‘Flocking with UAVs to validate our proposed method. fixed-wing UAVs for distributed sensing: A stochastic optimal control approach,’’ in Proc. Amer. Control Conf., Jun. 2013, pp. 2025–2031. [21] J. Espelosín, L. Acosta, and D. Alonso, ‘‘Path planning approach based on REFERENCES flock dynamics of moving particles,’’ Appl. Soft Comput., vol. 13, no. 4, [1] C. W. Reynolds, ‘‘Flocks, herds, and schools: A distributed behavioral pp. 2159–2170, Apr. 2013. doi: 10.1016/j.asoc.2012.12.015. model,’’ in Proc. ACM, Aug. 1987, pp. 25–34. [22] S. Hauert, S. Leven, M. Varga, F. Ruini, A. Cangelosi, J.-C. Zufferey, [2] A. K. Pamosoaji and K.-S. Hong, ‘‘A path-planning algorithm and D. Floreano, ‘‘Reynolds flocking in reality with fixed-wing robots: using vector potential functions in triangular regions,’’ IEEE Trans. Communication range vs. maximum turning rate,’’ in Proc. IEEE/RSJ Int. Syst., Man, Cybern. Syst., vol. 43, no. 4, pp. 832–842, Jul. 2013. Conf. Intell. Robots Syst. (IROS), San Francisco, CA, USA, Sep. 2011, doi: 10.1109/TSMCA.2012.2221457. pp. 25–30. 85546 VOLUME 7, 2019 Y. Huang et al.: Collision Avoidance Method for Self-Organizing UAV Flights [23] H. Hildenbrandt, C. Carere, and C. K. Hemelrijk, ‘‘Self-organized aerial JUN TANG is currently an Assistant Professor displays of thousands of starlings: A model,’’ Behav. Ecology, vol. 21, with the Science and Technology on Informa- no. 6, pp. 1349–1359, Nov./Dec. 2009. doi: 10.1093/beheco/arq149. tion Systems Engineering Laboratory, National [24] J. Han, M. Li, and L. Guo, ‘‘Soft control on collective behavior of a group University of Defense Technology. He was dedi- of autonomous agents by a shill agent,’’ J. Syst. Sci. Complex., vol. 19, cated to the Ph.D. researches with the Technical no. 1, pp. 54–62, Mar. 200. doi: 10.1007/s11424-006-0054-z. Innovation Cluster on Aeronautical Management, [25] G. Vásárhelyi, C. Virágh, G. Somorjai, T. Nepusz, A. E. Eiben, and Universitat Autònoma de Barcelona. His research T. Vicsek, ‘‘Optimized flocking of autonomous drones in confined envi- interests include logistic systems, causal model- ronments,’’ Sci. Robot., vol. 3, no. 20, Jul. 2018, Art. no. eaat3536. ing, state space, air traffic management, and dis- doi: 10.1126/scirobotics.aat3536. crete event simulation. He is the winner of William Sweet Smith Prize, in 2015. He has been very active in the simulation community, organizing as the General Co-Chair for several international con- ferences. He acted as one of the main participants playing an important role in the FP7 European Project INnovative TEchnologies and Researches for a new Airport Concept toward Turnaround coordinatION (INTERACTION) with collaboration of Airbus. YANG HUANG received the B.S. and M.S. degrees in information and communication engi- SONGYANG LAO received the B.S. degree in neering from the National University of Defense information system engineering and the Ph.D. Technology, Changsha, China, in 2013 and 2017, degree in system engineering from the National respectively, where he is currently pursuing the University of Defense Technology, Changsha, Ph.D. degree with the Science and Technology China, in 1990 and 1996, respectively. He joined on Information Systems Engineering Laboratory. as a Faculty Member with the National Univer- During the B.S. degree, he studied the system sity of Defense Technology, in 1996, where he is engineering and the operation research. After fin- currently a Professor with the School of Informa- ishing the B.S. degree, he began to study the self- tion System and Management. He was a Visiting organizing flight theory of UAVs and the collision avoidance problem of Scholar with Dublin City University, Ireland, from UAV clusters. His research interests include the air traffic management and 2004 to 2005. His current research interests include image processing and unmanned aerial vehicle systems, such as collision avoidance of multi-UAV video analysis, and human–computer interaction. systems, especially the self-organized UAV collision avoidance problem. VOLUME 7, 2019 85547