SS symmetry Article UAV Group Formation Collision Avoidance Method Based on Second-Order Consensus Algorithm and Improved Artificial Potential Field Yang Huang, Jun Tang * and Songyang Lao College of systems engineering, National University of Defense Technology, Changsha 410073, China; huangyang13@nudt.edu.cn (Y.H.); laosongyang@nudt.edu.cn (S.L.) * Correspondence: jun.tang@e-campus.uab.cat  Received: 29 August 2019; Accepted: 11 September 2019; Published: 13 September 2019  Abstract: The problem of collision avoidance of an unmanned aerial vehicle (UAV) group is studied in this paper. A collision avoidance method of UAV group formation based on second-order consensus algorithm and improved artificial potential field is proposed. Based on the method, the UAV group can form a predetermined formation from any initial state and fly to the target position in normal flight, and can avoid collision according to the improved smooth artificial potential field method when encountering an obstacle. The UAV group adopts the “leader–follower” strategy, that is, the leader UAV is the controller and flies independently according to the mission requirements, while the follower UAV follows the leader UAV based on the second-order consensus algorithm and formations gradually form during the flight. Based on the second-order consensus algorithm, the UAV group can achieve formation maintenance easily and the Laplacian matrix used in the algorithm is symmetric for an undirected graph. In the process of obstacle avoidance, the improved artificial potential field method can solve the jitter problem that the traditional artificial potential field method causes for the UAV and avoids violent jitter. Finally, simulation experiments of two scenarios were designed to verify the collision avoidance effect and formation retention effect of static obstacles and dynamic obstacles while the two UAV groups fly in opposite symmetry in the dynamic obstacle scenario. The experimental results demonstrate the effectiveness of the proposed method. Keywords: second-order consensus algorithm; improve artificial potential field; leader-follower; collision avoidance; formation retention 1. Introduction Group control issues have long been recognized as a very important part of a multi-agent system. Because in the near future, it will become more and more common for unmanned robots to replace people in a cluster to perform difficult tasks. Cluster phenomena are common in nature, such as flocks, ant colonies, bee colonies and so on. These phenomena have inspired us to study the behavior of these biological groups to control unmanned clusters [1–4]. The way unmanned aerial vehicles (UAVs) perform tasks are becoming more and more clustered. Formation maintenance is one of the key technologies of UAV cluster technology. At the same time, collision avoidance technology is also the basic problem to be considered in cluster control [5,6]. In response to those problems, this paper studies and analyzes the collision avoidance technology in the case of formation maintenance. Cluster avoidance is studied via cluster formation control, mainly through the graph theory method and the Laplace function method. Among them, the degree matrix, the adjacency matrix and the Laplacian matrix are very commonly used in the graph theory control method [7]. The eigenvalues of the Laplacian matrix can reflect much of the information of the network. Literature [8] clearly Symmetry 2019, 11, 1162; doi:10.3390/sym11091162 www.mdpi.com/journal/symmetry Symmetry 2019, 11, 1162 2 of 15 discusses the stability of formation topology represented by undirected graphs, and points out that the study of graphs plays a key role in formation control. The minimum positive eigenvalue of the Laplacian matrix determines the time it takes for the agent to reach the formation position. However, the complex analysis of the switching network topology makes the applicability of these attributes very difficult [9]. The Laplace function method is the most advantageous method for the stability analysis of complex dynamic systems and control theory, because, for the analysis of nonlinear systems, it is easier to use Laplacian functions rather than matrix theory methods [9]. A very important aspect of cluster control is consensus. Consensus means that each individual in the cluster reaches a common indicator according to an algorithm to maintain a stable state [10]. In the actual scenario, the consensus of cluster control is mainly reflected in the control of the formation under the consensus strategy. The formation control mainly hopes that all the agents in the formation can maintain a stable formation. Therefore, the strategy based on distance maintenance is more suitable for practical use because it does not require harsh sensitivity. This idea is representative of the self-organizing agent consensus algorithm [11]. A necessary and sufficient condition for reaching a consensus is that the communication directed graph allows for a directed spanning tree [10,11]. The literature [12,13] only proves sufficiency and assumes that the graph is undirected or strongly connected. Collision avoidance is an indispensable part while maintaining the formation of the UAV cluster. Collision avoidance includes collision avoidance against stationary obstacles and dynamic collision avoidance between UAV clusters. Traditional methods of collision avoidance include methods at the tactical level and methods at the strategic level [14]. The method at the tactical level is a collision avoidance algorithm based on geometric relations, mainly by analyzing geometric relations in space and provide conflict resolution [15–18]. The strategic level approach refers to proactively planning collision-free flight paths from the current location to the destination based on the perceptual detection of obstacles under the constraints of the minimum safe separation distance. Among them, the performance of systems using radar to actively detect obstacles is discussed in [19]. The collision avoidance algorithm based on geometric relationship has the characteristics of simple and efficient calculation, but most of the collision avoidance systems based on geometric relationship only support the collision avoidance between a pair of UAVs. At the same time, the method has strong requirements on the accuracy and real-time response of the sensor in actual use [20]. The main aspects of the trajectory planning algorithm at the strategic level include the potential field method [21–23], linear programming [24], and intelligent optimization algorithm [25]. The linear programming algorithm will significantly reduce computational efficiency with the increase of the number of UAVs. The intelligent optimization algorithm can quickly calculate the path, but the accuracy of its inherent properties is relatively low. The artificial potential field method has the characteristics of high computational efficiency and good real-time performance. It is widely used under real-time control conditions. The artificial potential field method was first proposed by Khatib, and its principle is very simple for real-time control [26,27]. However, the traditional artificial potential field method will have certain problems in practical application. The literature [22] combines the Lyapunov theorem with the artificial potential field method to solve the local minimum problem. [28] proposes a two-way concept and provides spacing information between UAVs so that they can avoid conflict in order to reach the target point. In [29], a new control force is proposed to transform the constrained UAV trajectory planning problem into an unconstrained UAV trajectory planning problem. The method proposed in this paper is based on the collision avoidance strategy of consensus strategy and artificial potential field method. Based on this method, the UAV cluster can quickly restore the formation while avoiding collision. 2. Consensus Algorithm 2.1. Graph Theory This section introduces the basic concepts of graph theory and paves the way for subsequent formation consensus algorithms. The relationship between individuals in formation is represented by Symmetry 2019, 11, x FOR PEER REVIEW 3 of 15 2. Consensus Algorithm 2.1. Graph Theory Symmetry 2019, 11, 1162 3 of 15 This section introduces the basic concepts of graph theory and paves the way for subsequent formation consensus algorithms. The relationship between individuals in formation is represented a byweighted adjacency a weighted adjacencymatrix. matrix. Suppose Suppose thethenodes nodes ofof the thegraph graphareareV V= ={v{1v1, ,vv22, ,. . . ,, vvNN}},, the the directed directed edge are grouped e = ( E ) edge are grouped e = (ijEijN×N , and the weighted adjacency matrix is d ) N × N , and the weighted adjacency matrix is d ij= (N×N = ( D ) . The directed Dij ) N × N . The directed edge eij in the graph refers to the directed connection from node vi to node v j . edge eij in the graph refers to the directed connection from node vi to node v j . The degree matrix is a diagonal matrix that represents the number of links each node connects to each The degree node, matrix by represented is athe diagonal followingmatrix that represents the number of links each node connects equation: to each node, represented by the following equation: ( deg(v ), if i = j Di,j = deg(vii ), if i = j (1) Di , j =  0, otherwise (1)  0, otherwise The adjacency matrix represents the relationship between nodes and the relationship of information The adjacency matrix represents the relationship between nodes and the relationship of flow, which is represented by the following formula: information flow, which is represented by the following formula: ( 1, if j is neighbor of i Ai,jA= = 1, if j is neighbor of i (2) i, j  0, otherwise (2)  0, otherwise The The Laplacian Laplacian matrix is: LL= matrix is: =DD−−AA.. The The eigenvalues eigenvalues of of the the Laplacian Laplacian matrix matrix are are useful useful in in many many ways. The Laplacian matrix is also symmetric for an undirected graph and it is positive-semidefinite. ways. The Laplacian matrix is also symmetric for an undirected graph and it is positive-semidefinite. For For instance, instance, aa graph graphwith withdegree degreematrix, matrix,adjacency adjacencymatrix matrixand the and Laplacian the Laplacianmatrix is shown matrix in is shown Figure 1. 1. in Figure Figure 1. Example of a simple graph. The degree matrix is written as:  1 00   1 00 00 00  00 00     11 00 00 == 0 00   DD 4 0  0  0 0 0 2     00  00 00 00 00 22  Adjacency Adjacency matrix matrix is: is:    0 0 1 0  0  0 00 00  11 00  0   A =  10 01 01  10 01  A = 01 11   10 01 10    0 0 10 1 01 0 0 1 1 0  Laplacian matrix should be: Symmetry 2019, 11, 1162 4 of 15 Laplacian matrix should be:    1 0 −1 0 0      0 1 −1 0 0   L =  −1 −1 4 −1 −1    0 0 −1 2 −1     0 0 −1 −1 2  The dynamic equation of the UAV is [7]: . x(t) = v(t) . (3) v(t) = a(t) T T where x(0) = x0 , v(0) = v0 , x = [xT1 , xT2 , . . . , xTn ] , v = [vT1 , vT2 , . . . , vTn ] . x, v and a are the position, velocity and acceleration of the UAV respectively. The consensus clause is that the UAV needs to converge to the same state as the surrounding UAVs. In this paper, the formation maintenance is based on the second-order consensus. The second-order consensus is satisfied if the following formula can be satisfied [7]: kxi (t) − x j (t)kt→∞ = 0 (4) kvi (t) − v j (t)kt→∞ = 0 From Formulas (3) and (4), we can know that the second-order consensus can also be written as . . xi (t) = vi (t) . N N vi (t) = −ω Lij x j (t) − ϕ Lij v j (t) P P (5) j=1 j=1 i = 1, 2, . . . , N where ω and ϕ are constant. T Let m = (xT , vT ) , the above formula be written in a compact form [7]: . m ( t ) = ( L ⊗ IN ) m (6) Among them L is the Laplacian matrix, ⊗ is Kronecker multiplication. 2.2. Artificial Potential Field Method The paper adopts the adaptive artificial potential field method in the collision avoidance method of the UAV. The basic method is that the UAV moves in the direction in which the potential field drops at the fastest velocity [1]. The combined force of the attraction of the target and the repulsive force of the obstacle controls the next movement of the UAV. Assuming that the position of the UAV is PUAV , and the target position is P goal , then the gravitational potential field function is [28]: Ua = ζa (P goal − PUAV )2 (7) The repulsion potential field function is [28]: 1 1 1 2 Urep = ψ( − ) (8) 2 λ λ0 Symmetry 2019, 11, 1162 5 of 15 where ζa and ψ are constants, λ is the distance between the UAV and the obstacle. λ0 is the maximum working distance between the UAV and the obstacle. When the relative distance is greater than the maximum working distance, the obstacle has no force on the UAV. P So the whole potential field is: Ut = Ua + Urep . The algorithm has certain limitations. When the UAV approaches the obstacle, the repulsive force is significantly increased. 3. Second-Order Consensus Formation Control Model and Improved UAV Collision Avoidance Method 3.1. Formation Control Continuous Time Domain Model Assume that each UAV meets the same dynamic equation: . si = Ksi + Zai , i = 1, 2, . . . , N (9) where si represents the amount of state that should be stored, ai represents the amount of control input. In order to control the position and velocity, sp = ((sp )1 , . . . , (sp )N ) and sv = ((sv )1 , . . . , (sv )N ) ! ! 1 0 represent the position and velocity variables, so s = sp ⊗ + sv ⊗ . In this paper, in order to 0 1 ! 0 1 simplify the problem, we hypothesize K = . This means that in this UAV dynamic system, the 0 1 position of the UAV is determined only by the velocity, and the velocity is determined only by the amount of control input. ! 1 The formation is represented by the following vector F = Fp ⊗ ∈ R2nN , the UAV maintains 0 a formation F if and only if there is a vector m, n ∈ Rn that satisfies (sp )i (t) − (Fp )i = m, (sp )i (t) = n, i = , 2, . . . , N at the moment t. In the dynamic formation, the UAVs need to establish contact with each other to control the next movement of the UAV. This paper uses the Laplacian matrix to realize the formation control. Assume that Mi is the neighbor of UAV i. The output function can be defined as [13]: X zi = ((si − Fi ) − (s j − F j )), i = 1, . . . , N (10) j=M j The corresponding output vector can be written as z = L(s − F), where L is the Laplace matrix. After the formula is merged we can get [13]: . s = Kcs + Zca (11) a = L(s − F) where Kc = IN ⊗ K, Zc = IN ⊗ Z. The dynamic equation of the formation system in the continuous time domain is [7]: . s = Kcs + ZcL(s − F) (12) 3.2. Discretized Data Processing The corresponding output vector can be written as z = L(s − F), where L is the Laplace matrix. After the formula is merged, you can get [7]: . s(t) = Ks(t) + Za(t) (13) m(t) = K1 s(t) + Z1 a(t) Symmetry 2019, 11, 1162 6 of 15 According to Formula (13), the state s at the moment (k + 1)T can be obtained: Z (k +1)T K (k +1)T K (k +1)T s((k + 1)T ) = e x(0) + e e−Kϕ Za(ϕ)dϕ (14) 0 Set Kd to the matrix K in the discrete model, Kd = eKt . Available from Taylor’s expansion: ∞ 1 2 2 1 X1 eKt = I + tK + t K + t3 K3 . . . = ti K i (15) 2! 3! i! i=0 Rt Remove the high-order items, we can get Kd = I + tK, Zd = 0 e y Zdy. Then the discretization model of the continuous time domain is: s((k + 1)T ) = Kds(kT ) + Zda(kT ) (16) 3.3. Path Optimization Based on Improved Artificial Potential Field Method The equation of motion of the UAV during collision avoidance is: Pu (1, t + 1) = Pu (1, t) + l cos η ( (17) Pu (2, t + 1) = Pu (2, t) + l sin η Pu (1, t + 1) and Pu (1, t) represents the position of the x axis coordinates of the UAV at the moment t + 1 and time t. Pu (2, t + 1) and Pu (2, t) represent the y axis coordinate position of the UAV at time t + 1 and time t. l is the step size of the UAV every moment, η is the direction angle of the next moment of the UAV. The gravitational potential field function is the same as the traditional artificial potential field method, and the potential field is expressed as Ua = ζa (P goal − PUAV )2 . The repulsion potential field function uses a repulsion function of a Gaussian-like function [1]: 1 Urep,i = ζrep exp(− [(xu − xob,i )2 + ( yu − yob,i )2 − r2u − r2ob ]) (18) σ2 where xu and yu represents the coordinate position of the current UAV, xob,i and yob,i represents the coordinate position of the obstacle i, σ represents the standard deviation of the obstacle potential field, ζrep represents the range coefficient of the obstacle potential field, ru indicating the size of the UAV, rob indicates the size of the obstacle. P It can be concluded that the entire potential field is: Ut = Ua + Urep,i . Assume that the total potential field in each direction at a certain point is Ut,1 , Ut,2 , . . . , Ut,n . Take the direction of the smallest potential field as the direction of motion of UAV in the next times’ step. In order to make the UAV not shake in the collision avoidance process, the paper adopts a smooth strategy, that is, the potential field under the previous simulation step and the currently calculated potential field are summed according to a certain ratio, so that the direction will not become too fast and cause jitter. The potential field method concept map is shown in Figure 2 while the collision avoidance direction selection algorithm is shown in Figure 3. Symmetry 2019, 11, 1162 7 of 15 Symmetry 2019, 11, x FOR PEER REVIEW 7 of 15 Fu Frep Fa Figure 2. Figure 2. Artificial potential field method concept map. η l U ob, A = min[U ob, A,1 ,U ob, A,2 , ,U ob, A, n ] Figure 3. Collision Collision avoidance direction selection algorithm based on artificial potential field field method. method. 3.4. UAV Formation 3.4. UAV Formation Keeps Keeps Cluster Cluster Collision Collision Avoidance Avoidance Method Method In In this this paper, paper, two two aspects aspects are are considered considered for for the the collision collision avoidance avoidance ofof the the UAV UAV cluster. cluster. One One is is that the UAV keeps the formation through the static obstacles, and the other is the collision that the UAV keeps the formation through the static obstacles, and the other is the collision avoidance between avoidancethe two UAV between the groups two UAV that maintain groups that the formation. maintain The UAVThe the formation. formation flying collision UAV formation flying avoidance method based collision avoidance methodon based consensus algorithmalgorithm on consensus are shownare inshown Figure in 4. Figure 4. Symmetry 2019, 11, 1162 8 of 15 Symmetry 2019, 11, x FOR PEER REVIEW 8 of 15 Figure 4. 4. Figure Unmanned Unmanned aerial vehicle aerial (UAV) vehicle formation (UAV) flying formation collision flying avoidance collision method avoidance based method onon based consensus consensusalgorithm. algorithm. 4. 4. Simulation Simulation Case Case For For UAVformation UAV formation collision collision avoidance, avoidance, twotwo practical practical scenarios scenarios should should bebe considered considered when when verifying the collision avoidance effect. The first is that when the obstacle is stationary, verifying the collision avoidance effect. The first is that when the obstacle is stationary, the UAV the UAV group can avoid group the obstacle can avoid while while the obstacle maintaining the formation; maintaining the second the formation; case is that the second casewhen thewhen is that obstacle the is obstacle is also dynamic, the UAV group keeps the formation flight while avoiding the collision. these also dynamic, the UAV group keeps the formation flight while avoiding the collision. To verify To two scenarios, verify these two we designed scenarios, wetwo classictwo designed scenes. Onescenes. classic is a static Oneobstacle scene, is a static and the obstacle other scene, andscene the is twoscene other UAV is formations two UAV flying opposite formations with flying each other. opposite with These two scenarios each other. These two are the mostare scenarios common the mostand common and relatively difficult to solve. If the UAVs in the two scenarios successfully avoidthe relatively difficult to solve. If the UAVs in the two scenarios successfully avoid collision, then methodthen collision, is proved to be effective. the method is proved to be effective. 4.1. Static Obstacle Scene 4.1. Static Obstacle Scene In the experiment, each group of UAV consists of four UAVs, one of which is the leader UAV, In the experiment, each group of UAV consists of four UAVs, one of which is the leader UAV, whose target position, initial position and initial velocity were set in advance, followed by follower whose target position, initial position and initial velocity were set in advance, followed by follower UAVs. The target position was set to (200, 200). The initial position and initial velocity of the follower UAVs. The target position was set to (200, 200). The initial position and initial velocity of the UAVs were also set in advance. The initial positions of the four UAVs are shown in Table 1: follower UAVs were also set in advance. The initial positions of the four UAVs are shown in Table 1: Table 1. Static obstacle scene UAV initial position. Table 1. Static obstacle scene UAV initial position. UAV Initial Position (m, m) Initial Velocity (m/s, m/s) UAV Initial Position (m, m) Initial Velocity (m/s, m/s) Follower Follower1 1 (0, 0) (0, 0) (5, 0) (5, 0) Follower 2 (60, 5) (0, 3) Follower 2 Follower 3 (60, 5)(30, 50) (0, 3) (2, 2) Follower Leader 3 (30, 50) (20, 20) (2, 2) (1, 1) Leader (20, 20) (1, 1) 2019, 11, 1162 Symmetry 2019, x FOR PEER REVIEW 99 of of 15 15 Figure 5 records the actual motion trajectories of the four UAVs, each of which took Figure 5 records maneuvering measuresthe to actual avoidmotion trajectories collisions of the four UAVs, when encountering each ofInwhich obstacles. took maneuvering the initial formation of measures the formation, the UAV group formed a formation according to the consensus algorithm.formation, to avoid collisions when encountering obstacles. In the initial formation of the When the the UAV group obstacles were formed a formation encountered, according the UAVs in theto UAV the consensus algorithm.the group performed When the obstacles movement were operation encountered, according to the improved artificial potential field method, then re-formed the formation. After the the UAVs in the UAV group performed the movement operation according to the improved leader UAV artificial reached potential field the target method,the position, then re-formedfollower remaining the formation. After the UAVs slowed leader down andUAV reached hovered in the target position, the remaining follower UAVs slowed down and hovered in formation. formation. UAV formation flight collision avoidance diagram in static obstacle scene. Figure 5. UAV Figure Figure 6. 6. shows shows thethe relative relative distance distance between betweeneach eachpair pairof ofUAVs UAVs inin the the UAV UAV group group over over time. time. From From the thecurve curveininthe figure, the it can figure, be seen it can that that be seen therethere is no collision between is no collision the UAVs, between the and the distance UAVs, and the between the UAVs gradually stabilizes with the passage of time after passing distance between the UAVs gradually stabilizes with the passage of time after passing through thethrough the obstacles, indicating that the UAV obstacles, indicating thathas theformed UAV has a stable formedformation a stablewithout formation thewithout leader. After the UAV the leader. reached After the UAVthe target reachedpoint, the follower the target UAVs point, the shookUAVs follower back shook and forth backnearby andnearby and forth slowly and stabilized slowlyinto a formation. stabilized into a When formation. When the leader UAV arrived at the target position, the follower UAVs continued todue the leader UAV arrived at the target position, the follower UAVs continued to fly forward fly to inertia,due forward whileto the leader inertia, UAV while slowed the leaderdown, UAV so the relative slowed down,position betweenposition so the relative the leader UAV and between the follower leader UAVUAVs andsuddenly followerbecame smaller, as UAVs suddenly shownsmaller, became in Figure as6.shown in Figure 6. Symmetry 2019, 11, 1162 x FOR PEER REVIEW 10 of 15 Symmetry 2019, 11, x FOR PEER REVIEW 10 of 15 Figure Figure 6. 6. Relative Relative position position map map between between UAV UAV formation formation crews under the crews under the static static obstacle obstacle scene. scene. Figure 6. Relative position map between UAV formation crews under the static obstacle scene. Figure 77 shows showsthe theposition positionofofthe theUAV UAV relative relative to the to the obstacle obstacle as aas a function function of time. of time. It canItbe can be seen Figure 7 shows the position of the UAV relative to the obstacle as a function of time. It can be seen fromfrom the enlarged the enlarged partial partial viewview of figure of the the figure thatthat the UAV’s the UAV’s closest closest distance distance to the to the obstacle obstacle waswas 5 5 m, seen from the enlarged partial view of the figure that the UAV’s closest distance to the obstacle was 5 m, which proves that the obstacle was avoided and free of collision during which proves that the obstacle was avoided and free of collision during the flight. the flight. m, which proves that the obstacle was avoided and free of collision during the flight. Figure Figure 7. 7. Relative Relative distance distance diagram diagram of of drone drone and and obstacle obstacle in in the the static static obstacle scene. obstacle scene. Figure 7. Relative distance diagram of drone and obstacle in the static obstacle scene. Figure 88 records recordsthe thevelocity velocityversus versus time time curve curve of each of each UAV UAV during during flight. flight. It also It can can bealso be from seen seen Figure 8 records the velocity versus time curve of each UAV during flight. It can also be seen from the velocity the velocity curvecurve that that the the group UAV UAV group is divided is divided intophases into three three phases duringduring the flight. the flight. The The first first phase from the velocity curve that the UAV group is divided into three phases during the flight. The first phase is gradually is gradually changed changed from the from the irregular irregular initialForming initial state. state. Forming a formation, a formation, so in theso in the early early follower phase is gradually changed from the irregular initial state. Forming a formation, so in the early follower UAVs, they UAVs, firstthey first accelerated accelerated and thenand then decelerated decelerated to achieveto achieve formation. formation. When When the obstacles the obstacles were follower UAVs, they first accelerated and then decelerated to achieve formation. When the obstacles were encountered, encountered, each UAV each UAV moved moved according according to theto the trajectory trajectory generated generated by thebyartificial the artificial potential potential field. were encountered, each UAV moved according to the trajectory generated by the artificial potential field. After After the successful the successful collision collision avoidance, avoidance, the UAV the UAV groupgroup decelerated decelerated to atostable a stable velocity velocity to to form form a field. After the successful collision avoidance, the UAV group decelerated to a stable velocity to form aformation. formation.Finally Finallythe theUAV UAVgroupgroupreached reachedthethetarget targetpoint pointand andthen then gradually gradually slowed slowed to a velocity a formation. Finally the UAV group reached the target point and then gradually slowed to a velocity close to 0, indicating that the UAV was in a hovering state. The The three three curves curves gradually gradually return return toto zero, zero, close to 0, indicating that the UAV was in a hovering state. The three curves gradually return to zero, and one maintained maintained thethe original original velocity. velocity. Therefore, Therefore, this this means means that that the velocity velocity ofof the the three UAVs and one maintained the original velocity. Therefore, this means that the velocity of the three UAVs gradually decreased to near zero, and only one UAV maintained the original velocity. This is gradually decreased to near zero, and only one UAV maintained the original velocity. This is Symmetry 2019, 11, 1162 11 of 15 Symmetry 2019, 11, x FOR PEER REVIEW 11 of 15 gradually decreased to near zero, and only one UAV maintained the original velocity. This is because because the UAV the UAV cluster cluster flight flightonisthe is based based on the leader–follower leader–follower model, and model, andUAV’s the leader the leader targetUAV’s target velocity was velocity was set, so the performance in the simulation was that the leader UAV will set, so the performance in the simulation was that the leader UAV will shake at the original velocityshake at the original when velocity arrived at thewhen targetarrived position, at while the target position, the other while followers UAV thegradually other followers reduced UAV gradually the velocity and reducedathe formed velocity In formation. and formed athree summary, formation. In summary, UAV gradually threeand stopped, UAVthegradually leader UAV stopped, swayedandat the leader UAV original swayed at the original velocity. velocity. UAV velocity change diagram in the static obstacle scene. Figure 8. UAV 4.2. Dynamic Obstacle Scene 4.2. Dynamic Obstacle Scene In this experiment, there were two groups of UAVs. Each group of UAV consists of four UAVs. In this experiment, there were two groups of UAVs. Each group of UAV consists of four UAVs. One of the UAVs is the lead UAV. The target position, initial position and initial velocity were set One of the UAVs is the lead UAV. The target position, initial position and initial velocity were set in in advance. The initial position and initial velocity of the follower UAVs were also set in advance. advance. The initial position and initial velocity of the follower UAVs were also set in advance. The The initial positions of the eight UAVs of the two groups of UAVs are shown in Table 2. initial positions of the eight UAVs of the two groups of UAVs are shown in Table 2. Table 2. Dynamic obstacle scene UAV initial position. Table 2. Dynamic obstacle scene UAV initial position. Group UAV Group UAV InitialInitial PositionPosition (m, m) (m, m) InitialInitial Velocity (m/s, m/s) Velocity (m/s, m/s) Follower Follower 1 1 (0, 0) (0, 0) (5, 0) (5, 0) Follower 2 (10, 25) (0, 3) Group 1 Follower 2 3 (10, 25) (0, 3) (2, 2) Group 1 Follower (0, 50) Follower 3 Leader (0, 50)(20, 20) (2, 2) (1, 1) Leader Follower 1 (20, 20) (190, 180) (1, 1) (−5, −5) Follower 1 Follower 2 (190, 180) (210, 155) (−5, −5) (−3, −3) Group 2 Follower Follower 2 3 (180, 200) (210, 155) (−2, −2) (−3, −3) Group 2 Leader (170, 170) (−1, −1) Follower 3 (180, 200) (−2, −2) Leader (170, 170) (−1, −1) Figure 9 records the actual motion trajectories of eight UAVs. Each UAV takes maneuvering measures Figureto 9avoid collisions records when the actual encountering motion the of trajectories other UAV eight group. UAVs. Similar Each UAVtotakes the static obstacle maneuvering scene, the to measures UAV group avoid formed collisions a formation when according encountering the otherto theUAVconsensus group. algorithm Similar to the during staticthe initial obstacle formation scene, the process. UAV group When the other formed UAV group a formation was encountered, according each UAV to the consensus performed algorithm duringthethemotion initial operation according to the improved artificial potential field method. After formation process. When the other UAV group was encountered, each UAV performed the motion passing the other UAV group, the according operation UAV group tore-formed the formation. the improved After thefield artificial potential leader UAV reached method. the target After passing theposition, other UAV the other group,followers the UAVslowed group down and hovered re-formed according the formation. After to the formation. leader UAV reached the target position, the other followers slowed down and hovered according to the formation. Symmetry 2019, 11, 1162 12 of 15 Symmetry Symmetry 2019, 2019, 11, 11, xx FOR FOR PEER PEER REVIEW REVIEW 12 12 of of 15 15 Figure Figure 9. 9. UAV UAV formation formation flight anti-collision flight anti-collision flight diagram anti-collision diagram in diagram in dynamic in dynamic obstacle dynamic obstacle scene. obstacle scene. scene. Figure Figure 10 shows the 10 shows the position position ofof the the UAV UAV relative relative toto the the other UAV other UAV group UAV group over group over time. over time. time. As As can can be be seen from the enlarged partial view, the closest distance between the two UAVs is 5 m. The seen from from the the enlarged enlarged partial partial view, view, the the closest closest distance distance between between the two the two UAVs is UAVs 5 m. Theis 5 m. successful The successful collision collision collision avoidance successfulavoidance of the UAVof avoidance the the UAV ofgroup UAVwasgroup was realized group was realized during theduring realized flight. the during flight. In the the In In the figure, flight. thefigure, the the solid line figure, the solid line indicates indicates the relative the relative distance distance between between different different groups of groups UAVs, andof UAVs, the solid line indicates the relative distance between different groups of UAVs, and the dashed line dashed and the line dashed indicates line the indicates relative indicates the the relative distance between relative distance the UAVs distance between in thethe between same the UAVs group. UAVs in the in The same same group. the initial group. The relative initial distance The relative was initial less than relative distance 50 m, distance was was less which less than was thanthe5050 m, m, which relative was distance which the the relative was between thedistance relative unmanned distance between aerial the between unmanned vehicles the in the aerial unmanned same vehicles aerial group, vehicles in andin the the same group, relative and distance the relative between thedistance unmanned between the aerial unmanned vehicles in aerial different vehicles groups same group, and the relative distance between the unmanned aerial vehicles in different groups was in wasdifferent greater groups than was 50 m. greater It than can bethan greater 50 seen50from m. It m. Itthecan can be seen dotted from linefrom be seen the thatthe dotted thedotted line closestline that relative the closest distance that the closest relative between relativethe distance between UAVs between distance in the samethe the UAVs group in wasthe same also group greater was than 5 also m. greater UAVs in the same group was also greater than 5 m. than 5 m. Figure 10. Relative distance diagram of UAV and obstacle in dynamic obstacle scene. Figure Figure 10. 10. Relative Relative distance distance diagram diagram of of UAV UAV and and obstacle obstacle in in dynamic dynamic obstacle obstacle scene. scene. Figure 11 records the velocity versus time curve of each UAV during flight. It can also be seen Figure 11 11 records the velocity versus time curve of of each UAV during flight. It It can also be be seen from Figure records the velocity curve the thatvelocity the UAVversus grouptime was curve divided eachthree into UAVphases duringduring flight. the can alsoThe flight. seen first from from the the velocity velocity curve curve that that the the UAV UAV group group was was divided divided into into three three phases phases during during thethe flight. flight. The The first first phase was the UAV group gradually changing from the irregular initial state. The phase was the UAV group gradually changing from the irregular initial state. The follower UAVs follower UAVs Symmetry 2019, 11, 1162 13 of 15 Symmetry 2019, 11, x FOR PEER REVIEW 13 of 15 phase was the UAV group gradually changing from the irregular initial state. The follower UAVs first accelerated and then slowed down to achieve a formation. The The second second stage stage waswas that that each each UAV UAV moved ininaccordance accordance withwith the trajectory the trajectory generated generated by the potential by the artificial artificialfield potential field when when encountering encountering the obstacles. The the obstacles. third stageThewas third stage that after thewas that after successful the successful collision avoidance, collision the UAVavoidance, group hadthean UAV group process acceleration had an and acceleration decelerated process and decelerated to a stable to aastable velocity to form velocity formation. After to finally form areaching formation. the After target finally point, thereaching the target slowed UAV gradually point, the downUAV to agradually slowed velocity close down to 0, to a velocity indicating that theclose UAV towas0, indicating hovering. We thatcan the find UAVthat wasthere hovering. We can were three UAVsfindwith that non-zero there were butthree UAVs velocity near-zero with non-zero but at the end near-zero velocity of the flight, the rootat the endwas cause of the flight, that the root the leader UAVcause was was that theback swinging leader UAV and forthwas swinging with back the original and forth velocity at with the end theposition, original asvelocity the leaderat the willend still position, have had as thethe leader will still pre-programmed have had original the velocity. pre-programmed The follower UAVsoriginal velocity. still followed theThe follower consensus UAVs still algorithm followed to follow the the consensus leader UAV to algorithm maintain theto follow formationthe leader when the UAV to maintain leader the formation UAV arrives whenposition, at the target the leaderand UAVthe arrives at thestill leader UAV target position, maintained and the leader the original UAVatstill velocity themaintained target position the due original to thevelocity pre-set at the target velocity, so theposition follower due to the UAVs pre-set were also velocity, slowed down so the butfollower UAVs at still oscillating were the also targetslowed down position. Thesebutthree still UAVs oscillating at the obtained target position. a non-zero velocity These threeofUAVs at the end obtained the flight becausea non-zero the followervelocity UAVs at will the end swingof back the flight because and forth with the followervelocity a certain UAVs will swing by calculated backtheand forth with consensus a certain velocity calculated by the consensus algorithm. algorithm. Figure 11. UAV UAV velocity change graph in dynamic obstacle scene. 5. Conclusions 5. Conclusions This paper This paperstudied studiedthe theformation formation of of collision avoidance collision avoidance methods methodsfor UAV for UAVgroups. The UAV groups. The group UAV needs to group formtoformations needs and fly and form formations to theflytarget to thepoint when target pointit is whensafe,itand can effectively is safe, avoid obstacles and can effectively avoid when encountering obstacles them. Thethem. when encountering collision The avoidance of static obstacle collision avoidance of static scene obstacleandscene the dynamic obstacle and the dynamic obstacle avoidance scene are simulated respectively in this paper, and the simulation results Itare avoidance scene are simulated respectively in this paper, and the simulation results are analyzed. is worth analyzed.noting It isthat worththenoting method thatis essentially the methodaiscentralized essentiallycontrol method, a centralized that is, control the calculation method, is that is, the performed by the same calculation unit and then the control instruction is calculation is performed by the same calculation unit and then the control instruction is sent to the sent to the lower unit. But if the computational lower unit. But if the processor is efficient computational enough is processor and there isenough efficient little delay and in the information there is little delaytransfer in the process, the method can be a distributed algorithm. In this case, each UAV information transfer process, the method can be a distributed algorithm. In this case, each UAV acts acts as a computing unit and performs computational processing on the received information as a computing unit and performs computational processing on the received information toto generate its own decisions. In order to achieveits generate a real ownflight test, we decisions. In will order design a control to achieve framework. a real flight test,The weoverall control will design framework a control consists framework. of two aspects: The first aspect is about decision calculate, the other aspect The overall control framework consists of two aspects: The first aspect is about decision calculate, is information sharing. For other the the first aspect, aspect we would use is information the computing sharing. unitaspect, For the first of the leader we would UAVuse to calculate the computing the next moment unit of the trajectory of follower UAVs, then the leader UAV will send the control leader UAV to calculate the next moment trajectory of follower UAVs, then the leader UAV will signal to the follower UAVs. For the send thesecond controlaspect, signal wetoset the allfollower followerUAVs.UAVs to send For thetheir secondownaspect, velocity weandsetlocation information all follower UAVs to to the leader send their UAV. own This framework velocity and locationwill enable information information to thesharing leader and UAV. realThis flight. framework will enable information sharing and real flight. The conclusions are as follows: (1) The contribution of this research is to study the formation maintenance method of the UAV group based on the second-order consensus algorithm, which can Symmetry 2019, 11, 1162 14 of 15 The conclusions are as follows: (1) The contribution of this research is to study the formation maintenance method of the UAV group based on the second-order consensus algorithm, which can control each UAV in the formation and has a significant effect in forming a stable formation. (2) The application of the improved artificial potential field method in the collision avoidance problem of UAV is studied. The smoothing strategy is adopted to make the collision avoidance trajectory smooth and suitable for practical engineering use. (3) The collision avoidance between the UAV groups was studied. The UAV groups completed the formation while avoiding collisions and quickly formed a stable formation after the collision avoidance operation. The recommendations and future work are as follows: (1) Propose a collision-avoidance solution in more complicated situations while maintaining the formation of the UAV formation; (2) Study the method while considering the communication delay between the UAVs; (3) Consider the formation change of the UAV group. Author Contributions: Conceptualization, Y.H. and J.T.; methodology, Y.H.; software, Y.H.; validation, Y.H.; formal analysis, Y.H.; investigation, Y.H.; resources, Y.H., J.T. and S.L.; data curation, Y.H.; writing—original draft preparation, Y.H.; writing—review and editing, Y.H. and J.T.; visualization, Y.H.; supervision, J.T. and S.L.; project administration, J.T. and S.L.; funding acquisition, J.T. and S.L. Funding: This work has been financially supported by the National Natural Science Foundation of China, China 71601181, the Young Talents Lifting Project, China 17JCJQQT048 and the Huxiang Young Talents, China 2018RS3079. Acknowledgments: In this section you can acknowledge any support given which is not covered by the author contribution or funding sections. This may include administrative and technical support, or donations in kind (e.g., materials used for experiments). Conflicts of Interest: The authors declare no conflict of interest. References 1. Fax, J.A.; Murray, R.M. Information flow and cooperative control of vehicle formations. IEEE Trans. Autom. Control. 2003, 49, 1465–1476. [CrossRef] 2. Jadbabaie, A.; Lin, J.; Morse, A.S. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Autom. Control. 2003, 48, 998–1001. 3. Lawton, J.; Beard, R.; Young, B. A decentralized approach to formation maneuvers. IEEE Trans. Robot. Autom. 2003, 19, 933–941. [CrossRef] 4. Leonard, N.E.; Ogren, P. Obstacle avoidance in formation. IEE Icra 2003, 2, 2492–2497. 5. Tang, J.; Piera, M.A.; Guasch, T. Coloured Petri net-based traffic collision avoidance system encounter model for the analysis of potential induced collision. Transp. Res. Part. C: Emerg. Technol. 2016, 67, 357–377. [CrossRef] 6. Tang, J.; Zhu, F.; Piera, M.A. A causal encounter model of traffic collision avoidance system operations for safety assessment and advisory optimization in high-density airspace. Transp. Res. Part. C: Emerg. Technol. 2018, 96, 347–365. [CrossRef] 7. Olfati-Saber, R.; Fax, J.A.; Murray, R.M. Consensus and cooperation in networked multi-agent systems. Proc. IEEE 2007, 95, 215–233. [CrossRef] 8. Chen, Y.Q.; Wang, Z. Formation control: A review and a new consideration. Intelligent Robots and Systems. In Proceedings of the 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, Edmonton, AB, Canada, 2–6 August 2005. 9. Cao, Y.; Yu, W.; Ren, W.; Chen, G. An overview of recent progress in the study of distributed multi- agent coordination. IEEE Trans. Ind. Inform. 2013, 9, 427–438. [CrossRef] 10. Ren, W.; Beard, R. Consensus seeking in multi-agent systems using dynamically changing interaction topologies. IEEE Trans. Autom. Control. 2005, 50, 655–661. [CrossRef] 11. Ren, W.; Beard, R. Consensus of information under dynamically changing interaction topologies. In Proceedings of the American Control Conference, Boston, MA, USA, 30 June–2 July 2004; pp. 4939–4944. 12. Olfati-Saber, R.; Murray, R. Agreement problems in networks with directed graphs and switching topology. In Proceedings of the IEEE Conference on Decision and Control, Maui, HI, USA, 9–12 December 2003; pp. 4126–4132. Symmetry 2019, 11, 1162 15 of 15 13. Olfati-Saber, R.; Murray, R. Consensus protocols for networks of dynamic agents. In Proceedings of the American Control Conference, Denver, CO, USA, 4–6 June 2003; pp. 951–956. 14. Jun, T.; Yang, W. A causal model for safety assessment purposes in opening the low-altitude urban airspace of chinese pilot cities. J. Adv. Transp. 2018, 2018, 1–18. 15. Luongo, S.; Corraro, F.; Ciniglio, U.; Di Vito, V.; Moccia, A. A novel 3d analytical algorithm for autonomous collision avoidance considering cylindrical safety bubble. In Proceedings of the 2010 IEEE Aerospace Conference, Big Sky, MT, USA, 6–13 March 2010; pp. 1–13. 16. Park, J.W.; Oh, H.D.; Tahk, M.J. Uav collision avoidance based on geometric approach. In Proceedings of the 2008 SICE Annual Conference, Tokyo, Japan, 20–22 August 2008. 17. Chakravarthy, A.; Ghose, D. Obstacle avoidance in a dynamic environment: A collision cone approach. IEEE Trans. Syst. Man Cybern. Part A Syst. Hum. 1998, 28, 562–574. [CrossRef] 18. Carbone, C.; Ciniglio, U.; Corraro, F.; Luongo, S. A novel 3d geometric algorithm for aircraft autonomous collision avoidance. In Proceedings of the 45th IEEE Conference on Decision and Control, San Diego, CA, USA, 13–15 December 2006; pp. 1580–1585. 19. Fasano, G.; Accardo, D.; Moccia, A.; Luongo, S.; Di Vito, V. In-flight performance analysis of a non-cooperative radar-based sense and avoid system. J. Proc. Inst. Mech. Eng. Part. G J. Aerosp. Eng. 2016, 230, 1592–1604. [CrossRef] 20. Orefice, M.; Vito, V.D.; Torrano, G. Sense and avoid: Systems and methods. In Encyclopedia of Aerospace Engineering; Wiley: New York, NY, USA, 2015. 21. Sigurd, K.; How, J. Uav trajectory design using total field collision avoidance. In Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit, Austin, TX, USA, 11–13 August 2003; p. 5728. 22. Liu, J.Y.; Guo, Z.Q.; Liu, S.Y. The simulation of the uav collision avoidance based on the artificial potential field method. Adv. Mater. Res. 2012, 591, 1400–1404. [CrossRef] 23. Ruchti, J.; Senkbeil, R.; Carroll, J.; Dickinson, J.; Holt, J.; Biaz, S. Unmanned aerial system collision avoidance using artificial potential fields. J. Aerosp. Inf. Syst. 2014, 11, 140–144. [CrossRef] 24. Yoshiaki, K. Real-Time Trajectory Design for Unmanned Aerial Vehicles Using Receding Horizontal Control; Massachusetts Institute of Technology: Cambridge, MA, USA, 2003. 25. Mavrovouniotis, M.; Yang, S.; Yao, X. Multi-colony ant algorithms for the dynamic travelling salesman problem. In Proceedings of the 2014 IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environments (CIDUE), Singapore, 16–19 April 2014; pp. 9–16. 26. Kim, D.H.; Shin, S. Local path planning using a new artificial potential function composition and its analytical design guidelines. Adv. Robot. 2005, 20, 115–135. [CrossRef] 27. Vascak, J. Navigation of Mobile Robots Using Potential Fields and Computational Intelligence Means. Acta Polytech. Hung. 2007, 4, 63–74. 28. McIntyre, D.; Naeem, W.; Xu, X.D. Cooperative Obstacle Avoidance using Bidirectional Artificial Potential Fields. In Proceedings of the 11th UKACC Control, Belfast, UK, 31 August–2 September 2016; pp. 1–6. 29. Chen, Y.B.; Luo, G.C.; Mei, Y.S.; Yu, J.Q.; Su, X.L. UAV trajectory planning using artificial potential field method updated by optimized control theory. Int. J. Syst. Sci. 2014, 45, 1407–1420. © 2019 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).