Formation control of unmanned aerial vehicles (UAVs) can accomplish a task better than a single UAV and has been studied using various methods. UAVs are widely adopted in various situations^{[12]}. However, the requirements nowadays have already overtaken the current abilities of a single UAV. In order to satisfy the requirements, different plans for the cooperation of many UAVs have been proposed by Chaumette^{[3]} and Rasche^{[4]}, and the design of a method for multiUAV formation is important^{[5]}. Different methods have been proposed such as the leaderfollower approach^{[6]}, artificial potential field^{[7]}, and sliding mode control^{[8]}.
Among these approaches, consensus is an effective and easy method for distributed control^{[9]}. Using several simple consensus equations, UAVs can fly along complex trajectories. Consensus originates from the natural behavior of animals such as fish and birds. A single bird or fish is small and weak, but a population can hold a complicated formation. It is consensus that plays an essential role in this phenomenon. Vicsek^{[10]} and Ren^{[9, 1112]} have achieved many results in this field. This paper adopts this method to design a controller for a multiUAV formation.
There are two main parts of the consensus algorithm^{[1314]}. First, the formation is treated as a virtual rigid body, every UAV has a desired position and this acts as a point on the body. Using consensus, the UAVs' desired positions concentrate together and create the desired formation. However, a distance error always exists between the desired position and the real position for each UAV, and the second part of the algorithm deals with this problem by considering this error as a variable in consensus. By devising a useful algorithm, the error closes to zero as time tends to infinity. The real position for each UAV is the sum of the desired position and the error. In this way, UAVs with random initial locations always concentrate and fly along their predesigned routes. These two parts of the algorithm added to the communication networks of the individual vehicles comprise the whole UAV system^{[1314]}. However, consensus can only ensure that all the variables are close to the given state and does not know whether the values of variables at each moment are optimal. It is a good idea to improve consensus with optimal algorithms.
Pigeoninspired optimization (PIO) is a novel swarm intelligence optimizer proposed by Duan and Qiao in 2014^{[15]}. The method imitates pigeons' behavior when seeking a way back to their loft. It is believed that pigeons adopt different tools at different stages when returning home. In the beginning, compass and map factors are adopted^{[16]}, each pigeon's velocity is updated by the linear combination of its neighbors' (including itself) best locations and its former velocity. When pigeons approach home, some smart ones with good memories can recognize familiar landmarks which guide them^{[17]}, the others just need to follow these leaders. The second part of PIO is designed to concentrate the average location of all the pigeons. It is widely known that each optimizer fits one or several problems, and PIO was first proposed for air robot path planning^{[15, 18]}, image processing^{[17, 19]}, and orbit formations^{[20]}. When it comes to the optimization of consensus mentioned above, disadvantages appear such as the trajectory closes to the desired trace with oscillation to an unsatisfactory degree^{[21]}. This means that PIO needs to be modified and a pigeoninspired optimization with slow diving strategy (SDPIO) is proposed.
The remainder of this paper is organized as follows. In Section 2, details of the application of consensus in a multiUAV formation are given. The construction of SDPIO and the convergence analysis is considered in Section 3. In Section 4, the SDPIObased consensus algorithm is proposed for a multiUAV formation, followed by numerical simulation and results analysis in Section 5. Finally, several conclusions concerning the use of optimal algorithms in consensus theory are drawn.
1 Controller design based on consensus 1.1 MultiUAV formation controller designIt is supposed that each UAV possesses a moving coordinate system with three axes (x, y, and z). The shape of the UAV is ignored and a mass point model is used instead. This is because the time delay of an aircraft control loop is much shorter than that of the navigation and guidance loops. Therefore, when dealing with formation control, the UAV model can be simplified as a point, which means there is no need to consider each UAV's attitude. Under this assumption, all the UAV's x, y, and z axes are parallel.
Consensus means that multiple UAVs reach an agreement on a common state, e.g., the UAV's position. In detail, every UAV has its initial 3dimensional position (x, y, z) in an inertial coordinate system, namely the ground coordinate system. The velocity of the original UAV_{i}'s moving coordinate system converges to the standard state of the virtual leader UAV_{10} by consensus. The UAV_{10}'s state consists of a timevarying position and predesigned velocity. In this way, all the UAVs' coordinates become one common moving coordinate system. After adding the relative position of each UAV in the moving coordinate system, the desired timevarying position is achieved for each UAV. When viewed as a mass of moving points, all these UAVs constitute a virtual body.
The formation method consists of both singleand doubleintegrator consensus algorithms. The latter aims to concentrate the UAVs with random initial positions and ensure that the desired positions of all the UAVs converge to points on the predesigned trajectory. The former ensures the distance error between the desired and the real position converges to 0 ^{[14]}. The real position of each UAV can be easily acquired and the UAV's trajectory is drawn.
For the formation problem in a multiUAV system, the UAVs' states should include both position and velocity, and the control inputs are the accelerations ^{[14]}. This model is always described by secondorder differentiation equations, and as a result, a consensus algorithm for doubleintegrator dynamics is required. The dynamic math model of the multiUAV system is given below,
$ \left\{ \begin{array}{l} {{\mathit{\boldsymbol{\dot \xi }}}_i} = {\mathit{\boldsymbol{\zeta }}_i}\\ {{\mathit{\boldsymbol{\dot \zeta }}}_i} = {\mu _i}\\ {\mathit{\boldsymbol{\xi }}_i} = {\left[ {{x_i}{y_i}{z_i}} \right]^{\rm{T}}} \end{array} \right. $  (1) 
where ξ_{i}, ζ_{i}, μ_{i}∈R^{3} represent the position, the velocity and the acceleration of UAV_{i}, respectively and x_{i}, y_{i}, z_{i} are the 3dimensional positions, i∈{1, 2, …, 10}. The consensus algorithm can be described as in Ref ^{[14]}.
$ \begin{array}{*{20}{c}} {{\mu _i} = \frac{1}{{{k_i}}}\sum\limits_{j = 1}^9 {{a_{ij}}\left[ {{{\dot \zeta }_j}  {\mathit{\boldsymbol{K}}_{ri}}\left( {{\xi _i}  {\xi _j}} \right)  {\mathit{\boldsymbol{K}}_{vi}}\left( {{\zeta _i}  {\zeta _j}} \right)} \right]} + }\\ {\frac{1}{{{k_i}}}{a_{i10}}\left[ {{{\dot \zeta }^r}  {\mathit{\boldsymbol{K}}_{ri}}\left( {{\xi _i}  {\xi ^r}} \right)  {\mathit{\boldsymbol{K}}_{vi}}\left( {{\zeta _i}  {\zeta ^r}} \right)} \right]} \end{array} $  (2) 
Where a_{ij} is element (i, j)in the adjacency matrix
To attain the desired position for one single UAV in the moving coordinate system, the error between the desired and the real position should be treated as an extra variable, this can be described by singleintegrator dynamics for simplicity. The math model can be described as
$ {\rm{\dot e}}{{\rm{r}}_i} = {u_i} $  (3) 
and the consensus algorithm is in Ref [9].
$ {u_i} =  \sum\limits_{j = 1}^9 {{a_{ij}}\left( {{\rm{e}}{{\rm{r}}_i}  {\rm{e}}{{\rm{r}}_j}} \right)} $  (4) 
$ {{\tilde r}_i} = r{p_i} + {\rm{e}}{{\rm{r}}_i} $  (5) 
Where
$ \left\{ \begin{array}{l} \left( {\mathit{\boldsymbol{L}} \otimes {\mathit{\boldsymbol{I}}_3}} \right)\ddot \xi + \left( {b \otimes {\mathit{\boldsymbol{I}}_3}} \right){{\ddot \xi }^r} =  {\mathit{\boldsymbol{K}}_r}\left[ {\left( {\mathit{\boldsymbol{L}} \otimes {\mathit{\boldsymbol{I}}_3}} \right)\xi + \left( {b \otimes {\mathit{\boldsymbol{I}}_3}} \right){\xi ^r}} \right]  \\ {\mathit{\boldsymbol{K}}_v}\left[ {\left( {\mathit{\boldsymbol{L}} \otimes {\mathit{\boldsymbol{I}}_3}} \right)\xi + \left( {b \otimes {\mathit{\boldsymbol{I}}_3}} \right){\xi ^r}} \right]\\ \dot e =  \left( {\mathit{\boldsymbol{L}} \otimes {\mathit{\boldsymbol{I}}_3}} \right)e\\ r = \tilde r + \xi = {\rm{rp}} + {\rm{er}} + \xi \end{array} \right. $  (6) 
where L_{9×9} is the Laplace matrix of the communication topology graph,
Equation (6) is the core of the multiUAV controller, and r provides the necessary positional information for all the UAVs for use in the next step. After acquiring the target instructions, the UAVs fly toward their destinations.
1.2 MultiUAV formation taskThe desired formation shape is designed as follows:
There are nine UAVs flying at two different heights, they are divided into three groups, each group containing three UAVs. In every small group, the UAVs form a triangle and these are the same size, so the UAVs fly symmetrically. The side length of the triangle and the distance between different triangles is much larger than the size of an UAV, so they can fly safely without danger of collision. The desired heights in Table 1 are relative values and the height of the origin of the moving coordinate system is their reference height, so when a UAV flies at zero or even a negative height, it is still acceptable. The blue star in Fig. 2 represents the center of the formation. x/m means distance along the xaxis in meters.
When designing the communication plan, the UAVs were numbered from 1 to 9. To clarify the plan, some background knowledge on topology and graph theory is required.
A graph with only vertices and arrows can be adopted to show the communication relationship among all the UAVs. Each UAV acts as a vertex, and an arrow from UAV_{1} to UAV_{2} means that UAV_{2} can receive information from UAV_{1}. There is also a virtual leader named UAV_{10}, which can emit an arrow to another UAV so that the latter knows the predesigned trajectory.
The communication topology among UAVs is described as a directed graph in Fig. 3. A graph with n vertices can be denoted by
For consensus, the adjacency matrix and the Laplace matrix were acquired. The Laplace matrix
According to the sufficient and necessary condition of multiUAV consensus, there is a directed spanning tree with its root UAV_{10}, in the communication topology graph, and all the state variables converge to the state of the root as time tends to infinity^{[11]}.
2 Pigeoninspired optimization with slow diving strategy 2.1 Basic pigeoninspired optimization algorithmQiao ^{[15]} studied pigeon behavior when seeking their way home and proposed the twostage algorithm. The first stage of PIO is the map and compass part.
$ \begin{array}{*{20}{c}} {\left\{ \begin{array}{l} {v_i}\left( {t + 1} \right) = {v_i}\left( t \right) \cdot \exp \left( {  Rt} \right) + {\rm{rand}} \cdot \left( {{x_{{\rm{lbest}}}}  {x_i}} \right)\\ {x_i}\left( {t + 1} \right) = {x_i}\left( t \right) + {v_i}\left( {t + 1} \right) \end{array} \right.}\\ {{\rm{if}}\;t < {T_{{\rm{label}}}}} \end{array} $  (7) 
In the formula above, the best local position
$ {\rm{fitness}}\left( {{x_i}\left( t \right)} \right) = \left {{x_i}\left( t \right)  {x_{i{\rm{standard}}}}\left( t \right)} \right $  (8) 
After calculating the distance between the desired and the present positions of all the pigeons, only half of the pigeons with lower fitness are selected for the iteration. This ensures that the positions of these pigeons converge to the desired position as fast as possible.
In the second part, the landmark operator is employed. Its update formula is:
$ \begin{array}{*{20}{c}} {\left\{ \begin{array}{l} {N_p}\left( {t + 1} \right) = \frac{{{N_p}\left( t \right)}}{2}\\ {x_{iC}}\left( {t + 1} \right) = \frac{{\sum {{x_i}\left( t \right) \cdot f\left( {{x_i}\left( t \right)} \right)} }}{{\sum {f\left( {{x_i}\left( t \right)} \right)} }}\\ {x_i}\left( {t + 1} \right) = {x_i}\left( t \right) + {\rm{rand}} \cdot \left( {{x_{iC}}\left( {t + 1} \right)  {x_i}\left( t \right)} \right) \end{array} \right.}\\ {{\rm{if}}\;t \ge {T_{{\rm{label}}}}} \end{array} $  (9) 
Apparently,
The problem in the former algorithm occurs mainly in the altitude part, the height of the UAV decreases too fast and it dives sharply. To slow the process, the update formula should be changed, not only to consider the best local position but also the slowest diving velocity. In the first part of PIO, the formula is not changed, but the method of acquiring the best local position is modified. The criterion is a linear combination of the distance error between the desired and the real positions and the diving speed. An UAV that dives very slowly is imitated by the others. This is the socalled "slow diving strategy". The update formula is:
$ \begin{array}{*{20}{c}} {\left\{ \begin{array}{l} {v_i}\left( {t + 1} \right) = {v_i}t \cdot \exp \left( {  Rt} \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;r \cdot \left[ {\varphi \cdot \left( {{x_{{\rm{lbest}}}}  {x_i}} \right) + \left( {1  \varphi } \right) \cdot {v_{{\rm{slow}}}}} \right]\\ {x_i}\left( {t + 1} \right) = {x_i}\left( t \right) + {v_i}\left( {t + 1} \right) \end{array} \right.}\\ {{\rm{if}}\;t < {T_{{\rm{label}}}}} \end{array} $  (10) 
where
The second part of PIO should be modified in the following way: all the UAVs converge to the center of the flock, which is calculated by a combination of the UAV positions and the slowest diving speed. The update equation can be described as:
$ \begin{array}{*{20}{c}} {\left\{ \begin{array}{l} {N_p}\left( {t + 1} \right) = \frac{{{N_p}\left( t \right)}}{2}\\ {x_{iC}}\left( {t + 1} \right) = \frac{{\sum {{x_i}\left( t \right) \cdot f\left( {{x_i}\left( t \right)} \right)} + 10 \cdot {x_{{\rm{slow}}}} \cdot f\left( {{x_{{\rm{slow}}}}} \right)}}{{\sum {f\left( {{x_i}\left( t \right)} \right) + 10 \cdot {x_{{\rm{slow}}}} \cdot f\left( {{x_{{\rm{slow}}}}} \right)} }}\\ {x_i}\left( {t + 1} \right) = {x_i}\left( t \right) + {\rm{rand}} \cdot \left( {{x_{iC}}\left( {t + 1} \right)  {x_i}\left( t \right)} \right) \end{array} \right.}\\ {{\rm{if}}\;t \ge {T_{{\rm{label}}}}} \end{array} $  (11) 
where
Fitness function Eq. (10) remains. Each UAV has its own fitness value.
2.3 Convergence analysis of SDPIO based on Banach fixedpoint theoremIn this section, convergence analysis of SDPIO is performed and a sufficient condition is proposed for the first part of SDPIO (SDPIOI). The main method adopted to prove the stability of iteration is the Banach fixedpoint theorem, as stated below:
A map T from a normed space
In the first part of SDPIO, each pigeon updates its speed and location according to Eq. (10), which can be transformed as
$ \begin{array}{*{20}{c}} {\left[ {\begin{array}{*{20}{c}} {{x_i}\left( {t + 1} \right)}\\ {{v_i}\left( {t + 1} \right)} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {1  r\varphi }&{\exp \left( {  Rt} \right)}\\ {  r\varphi }&{\exp \left( {  Rt} \right)} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{x_i}\left( t \right)}\\ {{v_i}\left( t \right)} \end{array}} \right] + }\\ {r\left[ {\begin{array}{*{20}{c}} \varphi &{1  \varphi }\\ \varphi &{1  \varphi } \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{x_{{\rm{lbest}}}}}\\ {{v_{{\rm{slow}}}}} \end{array}} \right]} \end{array} $  (12) 
when it considers all the pigeons,
where
$ \begin{array}{*{20}{c}} {\mathit{\boldsymbol{F = }}\left[ {\begin{array}{*{20}{c}} {1  r\varphi }&{}&{}&{\exp \left( {  Rt} \right)}&{}&{}\\ {}& \ddots &{}&{}& \ddots &{}\\ {}&{}&{1  r\varphi }&{}&{}&{\exp \left( {  Rt} \right)}\\ {1  r\varphi }&{}&{}&{\exp \left( {  Rt} \right)}&{}&{}\\ {}& \ddots &{}&{}& \ddots &{}\\ {}&{}&{  r\varphi }&{}&{}&{\exp \left( {  Rt} \right)} \end{array}} \right]}\\ {\mathit{\boldsymbol{B}} = r\left[ {\begin{array}{*{20}{c}} \varphi &{}&{}&{1  \varphi }&{}&{}\\ {}& \ddots &{}&{}& \ddots &{}\\ {}&{}&\varphi &{}&{}&{1  \varphi }\\ \varphi &{}&{}&{1  \varphi }&{}&{}\\ {}& \ddots &{}&{}& \ddots &{}\\ {}&{}&\varphi &{}&{}&{1  \varphi } \end{array}} \right]}\\ {\mathit{\boldsymbol{u}}\left( {\mathit{\boldsymbol{z}}\left( t \right)} \right) = {{\left[ {{x_{{\rm{lbest1}}}}\left( t \right) \cdots {x_{{\rm{lbest}}n}}\left( t \right)\;\;{v_{{\rm{slow1}}}}\left( t \right) \cdots {x_{{\rm{slow}}n}}\left( t \right)} \right]}^{\rm{T}}}.} \end{array} $ 
If iteration
Denoting
Because the best local location and the slowest speed are among all the pigeons' locations and velocities,
$ \begin{array}{*{20}{c}} {d\left( {T\left( {{z_1}} \right),T\left( {{z_2}} \right)} \right) = \mathop {\max }\limits_{1 \le i \le 2n} \left {T\left( {{z_1}} \right),T\left( {{z_2}} \right)} \right = }\\ {\mathop {\max }\limits_{1 \le i \le 2n} \left {\mathit{\boldsymbol{F}}{z_1} + \mathit{\boldsymbol{B}}u\left( {{z_1}} \right)  \mathit{\boldsymbol{F}}{z_2}  \mathit{\boldsymbol{B}}u\left( {{z_2}} \right)} \right = }\\ {{{\left\ {\mathit{\boldsymbol{F}}{z_1} + \mathit{\boldsymbol{B}}{K_1}{z_1}  \mathit{\boldsymbol{F}}{z_2}  \mathit{\boldsymbol{B}}{K_2}{z_2}} \right\}_\infty }} \end{array} $  (13) 
There is
$ {L_j} = {F_{j \cdot }}\left( {{z_1}  {z_2}} \right) + {B_{j \cdot }}{\left[ {0 \cdots {x_{1a}}  {x_{2b}}\;0 \cdots {v_{1a}}  {v_{2b}}\;0 \cdots 0} \right]^{\rm{T}}} $  (14) 
s.t.
$ \begin{array}{*{20}{c}} {\left {{L_j}} \right = \left {{F_{j \cdot }}\left( {{z_1}  {z_2}} \right) + {B_{j \cdot }}{{\left[ {0 \cdots {k_1}\Delta z\;0 \cdots {k_2}\Delta z\;0 \cdots 0} \right]}^{\rm{T}}}} \right = }\\ {\left {{F_{j \cdot }}\left( {{z_1}  {z_2}} \right) + {B_{j \cdot }}{{\left[ {0 \cdots {k_1} \cdots {k_2} \cdots 0} \right]}^{\rm{T}}}\Delta z} \right \le }\\ {{{\left\ {\mathit{\boldsymbol{F}}\left( {{z_1}  {z_2}} \right) + \mathit{\boldsymbol{BK}}\left( {{z_1}  {z_2}} \right)} \right\}_\infty } \le }\\ {{{\left\ {\mathit{\boldsymbol{F}} + \mathit{\boldsymbol{BK}}} \right\}_\infty }{{\left\ {{z_1}  {z_2}} \right\}_\infty } = {{\left\ {\mathit{\boldsymbol{F}} + \mathit{\boldsymbol{BK}}} \right\}_\infty }d\left( {{z_1},{z_2}} \right)} \end{array} $  (15) 
Where
The equation holds if and only if
The Banach fixedpoint theorem requires
$ \begin{array}{l} \Leftrightarrow \max \left\{ {\left {1  \varphi r + \exp \left( {  Rt} \right) + r{k_1}\varphi + r{k_2}\left( {1  \varphi } \right)} \right,} \right.\\ \;\;\;\;\;\left. {\left {  \varphi r + \exp \left( {  Rt} \right) + r{k_1}\varphi + r{k_2}\left( {1  \varphi } \right)} \right} \right\} < 1\\ \Leftrightarrow \left\{ \begin{array}{l}  1 <  \varphi r + \exp \left( {  Rt} \right) + r{k_1}\varphi + r{k_2}\left( {1  \varphi } \right) < 0\\ 1  \le {k_1},{k_2} \le 1,{k_1}{k_2} \ne 0 \end{array} \right. \end{array} $  (16) 
Equation (16) is a sufficient condition for the convergence of SDPIOI, once it is satisfied, we have
$ \left\{ \begin{array}{l} {x^ * } = {v^ * } + {x^ * }\\ {x^ * } = {x^ * } + \exp \left( {  Rt} \right){v^ * } + r\left[ {\varphi \left( {x_{{\rm{lbest}}}^ *  {x^c}} \right) + \left( {1  \varphi } \right)v_{{\rm{slow}}}^ * } \right] \end{array} \right. $  (17) 
Equation (17)
For the second part of SDPIO, all the pigeons converge to the flock's center. Their trajectories can only contract and approach each other. In formation processes this part serves only as a transition, and as the traces do not diverge this second part satisfies the demands.
3 MultiUAV formations with a SDPIObased consensus algorithmThe first three sections introduced consensus and SDPIO, now this section uses them to optimize the trajectory of an UAV. When consensus is only applied to the planned routes of all the UAVs, there is unavoidable overshoot because of the distributed control plan itself. Every UAV has its own limited communication relationship, which means it cannot always receive the desired trajectory. For example,
UAV_{1} can never acquire the planned trajectory directly, it relies on UAV_{3} to pass on the information. If UAV_{3}'s initial altitude is much too high, it must dive to meet the desired trajectory. Because of inertia and a lack of forecasting, UAV_{3} can only produce positive additions to its height when it goes below the desired trajectory and this is the reason for overshoot. However, as for UAV_{1}, only when its leader UAV_{3} flies below the proposed height does it begin to recognize that it should fly a bit higher, then its velocity is changed by Eq. (7), followed by its position. This process is much slower than a change in the desired route. As a result, the UAVs' trajectories dive sharply and appear to overshoot, then they converge to the desired trajectory. SDPIO provides a gentle and slowly changing trajectory for each UAV at the start, then, as soon as the UAVs fly down and meet the desired trajectory, consensus starts to operate.
The formula of the combination of these two algorithms can be described as:
$ \left\{ \begin{array}{l} x\left( {t + 1} \right) = x\left( t \right) + T \cdot \left( {v\left( {t + 1} \right) + {v_2}\left( {t + 1} \right)} \right)\\ v\left( {t + 1} \right) = v\left( t \right) + T \cdot a\left( {t + 1} \right)\\ a\left( {t + 1} \right) =  \left( {\left( {\mathit{\boldsymbol{L}} \otimes {\mathit{\boldsymbol{I}}_3}} \right) \cdot x\left( {t + 1} \right) + } \right.\\ \left. {\gamma \cdot \left( {\mathit{\boldsymbol{L}} \otimes {\mathit{\boldsymbol{I}}_3}} \right) \cdot v\left( {t + 1} \right)} \right) \cdot \\ \left( {\frac{1}{{\rm{ \mathsf{ π} }}} \times \arctan \left( {R \times \left( {t  {T_{{\rm{chg}}}}} \right)} \right) + 0.5} \right)\\ {v_2}\left( {t + 1} \right) = f\left( {x\left( t \right),v\left( t \right)} \right) \cdot \\ \left( {  \frac{1}{{\rm{ \mathsf{ π} }}} \times \arctan \left( {R \times \left( {t  {T_{{\rm{chg}}}}} \right)} \right) + 0.5} \right) \end{array} \right. $  (18) 
where
1) Input the number of UAVs in the formation task, give the expectation formation and consider the communication restriction.
2) Design a suitable communication network topology and acquire its adjacency matrix and the Laplace matrix.
3) Randomly initialize the positions and velocities of all the UAVs along with the parameters involved in the equations used in Eq. (18).
4) Calculate the acceleration input, consensus, and the velocity input using Eq. (18)
5) Update each UAV's position and velocity using Eq. (18)
6) Draw the UAV's trajectory according to its position in each iteration.
The process is summarized in the following process flow chart:
To validate the SDPIObased consensus, numerical simulations were conducted using MATLAB 2012a on a PC with an i5480 m, 2.67 GHz CPU and Windows 10 operating system. SDPIO was compared with consensus itself and consensus with two other optimizations, particle swarm optimization (PSO) and PIO. The results prove the effectiveness of SDPIO.
The main parameters in Eqs. (7), (9), and (18) are listed in Table 2 below. The time step for the simulation is T=0.05 s.
Nine UAVs were initialized with random positions in a 3dimensional environment as shown in Table 3.
These heights, the numbers on the zaxis, are relative positions corresponding to the height of origin of the common moving coordinate system in Fig. 2. Each UAV had the same initial position in the four simulations, i.e., consensus, PSObased consensus, PIObased consensus, and SDPIObased consensus.
As known from Sections 2 and 3, the performance of consensus cannot satisfy the requirements, which is clearly displayed in Fig. 5. Because of communication restrictions and lack of forecasting, all the UAVs tend to dive sharply and climb quickly. This causes great overload at the turning point, which may damage the UAV's structure and result in difficulties for flight control. Their routes seem to tie a knot when viewed from this perspective, however, it is important to clarify the fact that the trajectories do not cross and the UAVs do not crash in the sky.
To demonstrate the advantage of SDPIObased consensus, PSOand PIObased consensus algorithms were adopted to compare their performances with that of the modified algorithm. In Fig. 6, most trajectories are apparently better than those in Fig. 5, as the trajectories are gentle at the beginning and turn without diving sharply. UAV_{3}, UAV_{5}, andUAV_{9} serve as a set of convincing simulations that support the conclusions above. In Figs. 7 and 8, PIO and SDPIO work and further improve the performance. In Fig. 7, the overshoot almost disappears, but there is still fluctuation in the trajectories from this perspective, especially for UAV_{3}, UAV_{4}, and UAV_{5}. In Fig. 8, the trajectories become much smoother and the overshoot can be ignored compared with Figs. 5 to 7. This is reflected in the lowest parts of the trajectories of UAV_{3}, UAV_{4}, and UAV_{5}.
The effect of the SDPIObased consensus can be analyzed according to the x and z trajectories, but the y trajectory by consensus is smooth enough and does not need improvement. In Figs. 9 and 10, oscillation is more obvious than the counterparts in Figs. 11 and 12. The undesirable trajectories in Fig. 11 partly explain the shortcomings of PIO.
The performance of the x trajectories can be evaluated using change of direction as the criterion. After starting, if a UAV flies along a smooth trajectory towards the desired one without turning, it must have chosen the best and straightest trajectory. An undesirable trajectory leads the UAV into making frequent turns, which costs too much energy and increases the probability of collision.
The X trajectories in Figs. 9 and 10 belong to the undesirable type. In Fig. 9, the trajectories of UAV_{2}, UAV_{4}, and UAV_{7} curve during flight and each of them turns twice or even three times. UAV_{2} flies in the direction in which x becomes larger, however at nearly t=1 s, x begins to decrease, then at nearly t=3.5 s, x increases again and meets the desired value at t=5 s. This conflict process can be explained by its topology. In Fig. 3, UAV_{2} is deeply influenced by UAV_{1} and UAV_{3}. Unfortunately, all its neighbors start at positions further along the xaxis, which means that UAV_{2} has to catch up with its neighbor by consensus without reaching its desired positions. Only when its leader realizes they have deviated from the right position, do they begin to correct it. This is a result of a lack of forecasting. However, if UAV_{2} can directly receive information from UAV_{10}, perhaps it can perform better. This is the limit of communication. These two shortcomings illustrate the necessity for improvement.
In Fig. 10, the situation is not any better. UAV_{3}, UAV_{4}, UAV_{5}, and UAV_{8} have the same problem. For example, UAV_{8} starts at x=24.806 m at t=0, then x=21.5 m at nearly t=2 s, then x=25.1 m at nearly t=6 s and decreases to x=18.3 m at t=8 s; the real trajectory goes up and down frequently. This implies PSO cannot satisfy the demand of performance improvement.
In Figs. 11 and 12, fluctuation weakens and the trajectories become much smoother. Most UAVs can fly directly towards their destinations at t=7 s. In Fig. 11, the x position of UAV_{5} decreases quickly from the beginning to t=5 s, this fast slide slip spoils the performance as it causes a sliding movement of a flying UAV and makes it harder to control.
In Fig. 12, most trajectories are pleasant and suitable as commands for multiUAV formations.
Performance of the z trajectories can be evaluated by the following criterion: diving slowly and never flying up and down. In Fig. 13, all the trajectories quickly go down before t=4 s, this means that the UAVs dive sharply in the beginning, as shown in Fig. 5. The aim of this work is to overcome this shortcoming.
The trajectories in Fig. 14 clarify the advantage of PSObased consensus because the modified algorithm can effectively reduce oscillation. UAV_{2} and UAV_{8} clarify UAV_{8} this view as they both slowly decrease their height following the desired trajectory instead of diving down swiftly.
However, reduplicative climb and dive still exist, which may induce oscillation. The dangerous trajectories of UAV_{3} and UAV_{5} at UAV_{5} t∈[0, 10]s in Fig. 14 reveal that they are not the desired ones that descend slowly at the beginning, then converge to the desired trajectory. This is why there is great demand for another optimizer.
In Fig. 15, PIO is used to apply a gliding procedure. Before 4s, the map and compass operator takes effect and all the UAVs fly towards the best local position. In the time range, 4 to 6 s, the landmark operator drives the UAVs nearby to the same height. When all of them fly to the standard height, the PIO part stops working and consensus continues concentrating the UAVs and guiding them to fly along the designed trajectory.
The SDPIObased consensus algorithm also follows the steps above, but the difference occurs in the first 8 s as the UAVs descend more slowly and smoothly. UAV_{1}, UAV_{2} and UAV_{3} can support this opinion, as they at the same respective height, but at t=5 s, UAV_{2} and UAV_{3} by SDPIO are above 20 m while their counterparts are clearly lower. At t=7 s, the height of UAV_{1} by SDPIO is 16.04 m and the outcome by PIO is only 15.47 m.
From the fitness function Eq. (8), the closer the UAV_{i}approaches its desired location, the smaller the fitness value. In Fig. 17, as iteration Nc increases, average fitness values decrease and finally approach zero, and different optimizers possess different convergence rates. In Fig. 17(a), PIO shows the fastest speed in the beginning, SDPIO is a bit slower and PSO shows the weakest performance of the three. However, after Nc= 80, PIO becomes slow and is finally overtaken by SDPIO at Nc= 93. The poor efficiency of PIO is due to the inadequate local optimum.
In Fig. 17(b), all the fitness values show a tendency to decrease and SDPIO is the slowest at the beginning. This problem is attributed to the effect of the slow diving strategy itself.
In order to avoid diving sharply, each UAV learns from its neighbor with the smallest velocity on the zaxis in Eq. (11), so the distance error between the desired position and the real one decreases at a slower rate. The UAVs performance and the efficiency of the algorithm have to be a compromise. But SDPIO successfully eliminates the wrong local optimum and reaches a small value at Nc=167. This clearly reflects the advantage of our improvement as PSO and PIO are trapped at Nc=118. The two platforms in Fig. 17(b) demonstrate the local optimum and the algorithms temporarily stop evolution. However, all three optimizers manage to find the global minimum after Nc=270.
5 Conclusions and future worksIn this paper, consensus for multiUAV formations is improved with a modified SDPIO formula. PIO and PSO are adopted to optimize consensus for better performance of the initial flight trajectory. The method effectively reduces oscillation and smooths the curves. Consensus takes into effect subsequent responses and ensures that all the UAVs converge to the standard path. The combination of the two algorithms is proved to be useful for the multiUAV formation problem.
Our future work will focus on the optimization of consensus. The method introduced is perhaps not the best choice and there is still room to explore better optimizations. However, the outstanding advantage of consensus is its distributed features, as most optimization methods demand global information. How to combine them while retaining their individual advantages remains a challenge.
[1] 
RYAN A, ZENNARO M, HOWELL A, et al. An overview of emerging results in cooperative UAV control[C]//The proceedings of 43rd IEEE Conference on Decision and Control. atlantis, Paradise Island, Bahamas, 2004: 602607
(0)

[2] 
ZHA W, CHEN J, PENG Z. Dynamic multiteam antagonistic games model with incomplete information and its application to multiUAV[J]. IEEE/CAA Journal of automatica sinica, 2015, 2(1): 7484. DOI:10.1109/JAS.2015.7032908 (0)

[3] 
CHAUMETTE S, LAPLACE R, MAZEL C. CARUS, an operational retasking application for a swarm of autonomous UAVs: first return on experience[C]//The proceedings of 2011 Military Communications Conference Track 5 Communications and Network Systems. Baltimore, Maryland, USA, 2011: 20032010.
(0)

[4] 
RASCHE C, STERN C, KLEINJOHANN L, et al. A distributed multiUAV path planning approach for 3D environments[C]//The proceedings of the 5th International Conference on Automation, Robotics and Applications. Wellington, New Zealand, 2011: 712.
(0)

[5] 
GIULIETTI F, INNOCENTI M, NAPOLITANO M, et al. Dynamic and control issues of formation flight[J]. Aerospace science and technology, 2005, 9(1): 6571. DOI:10.1016/j.ast.2004.06.011 (0)

[6] 
CRUZ J. Leaderfollower strategies for multilevel systems[J]. IEEE transactions on automatic control, 1978, 23(2): 244255. DOI:10.1109/TAC.1978.1101716 (0)

[7] 
PAUL T, KROGSTAD T, GRAVDAHL J. Modelling of UAV formation flight using 3D potential fields[J]. Simulation modelling practice and theory, 2008, 16(9): 12401254. (0)

[8] 
RAO V, SINHA N. A sliding mode controller for aircraft simulated entry into spin[J]. Aerospace science and technology, 2013, 8(1): 154163. (0)

[9] 
REN W, BEARD R, ATKINS E. Information consensus in multivehicle cooperative control:collective group behavior through local interaction[J]. IEEE control systems, 2007, 27(2): 7182. DOI:10.1109/MCS.2007.338264 (0)

[10] 
VICSEK T. Universal patterns of collective motion from minimal models of flocking[C]//The proceedings of the 2nd IEEE International Conference on SelfAdaptive and SelfOrganizing Systems. Venice, Italy, 2008: 311.
(0)

[11] 
REN W, BEARD R W, MCLAIN T W. Coordination variables and consensus building in multiple vehicle systems[J]. Lecture notes in control and information sciences, 2005, 309: 439442. (0)

[12] 
REN W, BEARD R W. Consensus seeking in multiagent systems under dynamically changing interaction topologies[J]. IEEE transactions on automatic control, 2005, 50(5): 655661. DOI:10.1109/TAC.2005.846556 (0)

[13] 
SORENSEN N, REN W. A unified formation control scheme with a single or multiple leaders[C]//The proceedings of American Control Conference. New York City, USA, 2007: 54125418.
(0)

[14] 
REN W, SORENSEN N. Distributed coordination architecture fo r multirobot formation control[J]. Robotics and autonomous systems, 2008, 56(4): 324333. DOI:10.1016/j.robot.2007.08.005 (0)

[15] 
DUAN H, QIAO P. Pigeoninspired optimization:a new swarm intelligence optimizer for air robot path planning[J]. International journal of intelligence computation and cybernetics, 2014, 7(1): 2437. DOI:10.1108/IJICC0220140005 (0)

[16] 
GUILFORD T, ROBERTS S, BIRO D, et al. Positional entropy during pigeon homing Ⅱ:navigational interpretation of Bayesian latent state models[J]. Journal of theoretical biology, 2004, 227(1): 2538. DOI:10.1016/j.jtbi.2003.07.003 (0)

[17] 
LI C, DUAN H. Target detection approach for UAVs via improved pigeoninspired optimization and edge potential function[J]. Aerospace science and technology, 2014, 39: 352360. DOI:10.1016/j.ast.2014.10.007 (0)

[18] 
ZHANG B, DUAN H. Threedimensional path planning for uninhabited combat aerial vehicle based on predatorprey pigeoninspired optimization in dynamic environment[J]. IEEE/ACM transactions on computation and biology bioinformaion, 2017, 14(1): 97107. DOI:10.1109/TCBB.2015.2443789 (0)

[19] 
DUAN H, WANG X. Echo state networks with orthogonal pigeoninspired optimization for image restoration[J]. IEEE transactions on neural networks and learning Systems, 2016, 27(11): 24132425. DOI:10.1109/TNNLS.2015.2479117 (0)

[20] 
ZHANG S, DUAN H. Gaussian Pigeoninspired optimization approach to orbital spacecraft formation reconfiguration[J]. Chinese journal of aeronautics, 2015, 28(1): 200205. DOI:10.1016/j.cja.2014.12.008 (0)

[21] 
ZHAO J, ZHOU R. Pigeoninspired optimization applied to constrained gliding trajectories[J]. Nonlinear dynamics, 2015, 82(4): 17811795. DOI:10.1007/s1107101522779 (0)
