# Formation Control for Unmanned Aerial Vehicles with Directed and Switching Topologies

Authors: Yahui Qi; Shaolei Zhou; Yuhang Kang; Shi Yan
Journal: International Journal of Aerospace Engineering
 (2016)

---

## Abstract

Formation control problems for unmanned aerial vehicle (UAV) swarm systems with directed and switching topologies are investigated. A general formation control protocol is proposed firstly. Then, by variable transformation, the formation problem is transformed into a consensus problem, which can be solved by a novel matrix decomposition method. Sufficient conditions to achieve formation with directed and switching topologies are provided and an explicit expression of the formation reference function is given. Furthermore, an algorithm to design the gain matrices of the protocol is presented. Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results.


---

## Body

## 1. Introduction

In the past decades, unmanned aerial vehicles (UAVs) have been widely used in civilian and military areas, such as surveillance and reconnaissance [1, 2] and target search and localization [3]. Since the performance of a team of UAVs working cooperatively exceeds the performance of individual UAVs, formation control of UAVs is of importance and has received a lot of attention.The formation control of UAVs has been studied with many different methods, such as leader–follower [4], behavior [5], and virtual structure-based [6] approaches. Recently, with the development of consensus theory [7–15], some related methods are also used to deal with the formation control problems of UAVs. Consensus means that all agents reach a common state. The results in [16] show that consensus approaches can be used to deal with formation control problems, and leader–follower, behavior, and virtual structure-based formation control approaches are special cases of consensus-based approaches.Based on consensus method, Abdessameud and Tayebi [17] proposed controllers for UAV swarm systems to achieve formation in the presence of communication delays. A consensus protocol together with an output feedback linearization method is presented in [18] such that the UAV swarm systems can achieve partially time-varying formation. Besides, indoor and outdoor flight experiments for quadrotor swarm systems to achieve formation by consensus approaches are carried out in [19] and [20], respectively. Based on consensus theory, we know that the achievement of formation depends on not only the individual UAV dynamics but also the structure of the networks between UAVs which can be modeled by directed and undirected graphs. However, the interaction topologies between UAVs in [19, 20] are assumed to be fixed. In practical applications, the interaction topologies of UAV swarm systems may be switching due to the fact that the communication channel may fail and new channels may be created during flight. Time-varying formation control for UAV swarm systems and high-order LTI systems with switching interaction topologies are studied by Dong [20, 21], but the topologies are assumed to be undirected. To the best of our knowledge, there is still work to do on formation control of UAV swarm systems with directed and switching topologies.In this paper, we aim to solve the formation problem of UAV swarm systems with directed and switching topologies. Compared with the existing results, the assumptions of the communication topology are quite general. The remainder of this paper is organized as follows. In Section2, some necessary concepts and useful results on graph theory are summarized and the problem formulation is given. Main theoretical results are proposed in Section 3. In Section 4, a numerical simulation is presented. Section 5 is the conclusion.


## 2. Preliminaries and Problem Description

### 2.1. Notations and Graph Theory

In this paper, the following notations will be used.Rn×n and Cn×n denote the set of n×n real and complex matrices, respectively. For μ∈C, the real part is Reμ. ⊗ denotes the Kronecker product. In is the identity matrix of order n. For a square matrix A, λA denotes the eigenvalues of matrix A. A>0 (A≥0) means that A is positive definite (positive semidefinite). max⁡λA (min⁡λA) denotes the largest (smallest) eigenvalue of the matrix A.A directed graphG=(V,E,A) contains the vertex set V={1,2,…,N}, the directed edges set E⊆V×V, and the adjacency matrix A=[aij]N×N with nonnegative elements aij. aij=1 if there is a directed edge from vertex j to i; aij=0, otherwise. The Laplacian matrix of the graph G is defined as L=LijN×N, where Lii=∑j≠iaij and Lij=-aij (i≠j). Zero is an eigenvalue of L with the eigenvector 1N. A directed graph is said to have a spanning tree if there is a vertex such that there is a directed path from this vertex to every other vertex.Lemma 1 (see [8]).
Zero is a simple eigenvalue ofL and all the other nonzero eigenvalues have positive real parts if and only if the graph has a directed spanning tree.


### 2.2. Problem Description

Consider UAV swarm systems withN UAVs. The interaction topology of the UAV swarm systems can be described by a directed graph G, in which UAV i can be denoted by a vertex and the interaction channel from UAV i to UAV j can be denoted by an edge. Compared with the attitude dynamics, the trajectory dynamics of each UAV have much larger time constants, which means the attitude controller and trajectory controller can be designed separately. On the formation level, only trajectory control needs to be considered. Therefore, in this brief, the dynamics of each UAV can be described by the following double integrator [18, 21, 22]: (1)x˙it=vit,v˙it=uit,where i=1,2,…,N, xit∈Rn and vit∈Rn denote the position and velocity vectors of UAV i, respectively, and uit∈Rn are the control inputs. In the following, for simplicity of description, it is assumed that n=1, if not otherwise specified.Therefore, UAV swarm systems (1) can be rewritten as(2)ξ˙it=Aξit+Buit,where ξit=xit,vitT, A=0100, B=01.A formation is specified by a vectorht=h1Tt,h2Tt,…,hNTtT∈R2N with hit=hixt,hivtT (i=1,2,…,N) continuously differentiable and hivt being the derivative of hixt. Let hxt=hx1Tt,hx2Tt,…,hxNTtT and let hvt=hv1Tt,hv2Tt,…,hvNTtT; then one has that if hvt are not equal to zeros, the formation is time-varying.Definition 2 (see [21]).
UAV swarm systems (2) are said to achieve formation ht if there exists a function rt=rxt,rvt∈R2 with rvt being the derivative of rxt such that (3)limt→∞⁡ξit-hit-rt=0,i=1,2,…,N,where rt is called a formation center function.In this paper, the communication topology is molded by a directed graph and we assume that the communication topology is time-varying. LetG^=G1,G2,…,Gp, p≥1, be the set of all possible directed topologies. We define the switching signal σt, where σt:0,+∞→P=1,2,…,p. 0=t0<t1<t2<⋯ denote the switching instants of σt. Let Gσt∈G^ be the communication topology at time t. Lσt stands for the corresponding Laplacian matrix of Gσt.Assumption 3.
Each possible graphGσt∈G^ is fixed and contains a directed spanning tree.Letλiσt (i=1,2,…,N) be the eigenvalues of the Laplacian matrix Lσt. Without loss of generality, it is assumed that Reλ1σt≤Reλ2σt≤⋯≤ReλNσt. Furthermore, from Lemma 1, one can obtain that λ1σt=0 and 0≤Reλ2σt≤⋯≤ReλNσt. Let λmin=min⁡λim∀m∈P;i=2,3,…,N.Consider the following formation protocol:(4)uit=K1ξit-hit+K2∑j=1Naijξjt-hjt-ξit-hit+h˙ivt,i=1,2,…,N,where i=1,2,…,N, K1∈R1×2 and K2∈R1×2 are constant gain matrices, and aij is defined as in Section 2.1. Let ξt=ξ1Tt,ξ2Tt,…,ξNTtT, let hxt=h1xTt,h2xTt,…,hNxTtT, and let hvt=h1vTt,h2vTt,…,hNvTtT. Under protocol (4), the UAV swarm systems (2) can be written in a compact closed-loop form as follows:(5)ξ˙t=IN⊗A+BK1-Lσt⊗BK2ξt-IN⊗BK1-Lσt⊗BK2ht+IN⊗Bh˙vt.This brief mainly investigates how to design the gain matrices in protocol (4) for the UAV swarm systems (5) to achieve the formation ht.


## 2.1. Notations and Graph Theory

In this paper, the following notations will be used.Rn×n and Cn×n denote the set of n×n real and complex matrices, respectively. For μ∈C, the real part is Reμ. ⊗ denotes the Kronecker product. In is the identity matrix of order n. For a square matrix A, λA denotes the eigenvalues of matrix A. A>0 (A≥0) means that A is positive definite (positive semidefinite). max⁡λA (min⁡λA) denotes the largest (smallest) eigenvalue of the matrix A.A directed graphG=(V,E,A) contains the vertex set V={1,2,…,N}, the directed edges set E⊆V×V, and the adjacency matrix A=[aij]N×N with nonnegative elements aij. aij=1 if there is a directed edge from vertex j to i; aij=0, otherwise. The Laplacian matrix of the graph G is defined as L=LijN×N, where Lii=∑j≠iaij and Lij=-aij (i≠j). Zero is an eigenvalue of L with the eigenvector 1N. A directed graph is said to have a spanning tree if there is a vertex such that there is a directed path from this vertex to every other vertex.Lemma 1 (see [8]).
Zero is a simple eigenvalue ofL and all the other nonzero eigenvalues have positive real parts if and only if the graph has a directed spanning tree.


## 2.2. Problem Description

Consider UAV swarm systems withN UAVs. The interaction topology of the UAV swarm systems can be described by a directed graph G, in which UAV i can be denoted by a vertex and the interaction channel from UAV i to UAV j can be denoted by an edge. Compared with the attitude dynamics, the trajectory dynamics of each UAV have much larger time constants, which means the attitude controller and trajectory controller can be designed separately. On the formation level, only trajectory control needs to be considered. Therefore, in this brief, the dynamics of each UAV can be described by the following double integrator [18, 21, 22]: (1)x˙it=vit,v˙it=uit,where i=1,2,…,N, xit∈Rn and vit∈Rn denote the position and velocity vectors of UAV i, respectively, and uit∈Rn are the control inputs. In the following, for simplicity of description, it is assumed that n=1, if not otherwise specified.Therefore, UAV swarm systems (1) can be rewritten as(2)ξ˙it=Aξit+Buit,where ξit=xit,vitT, A=0100, B=01.A formation is specified by a vectorht=h1Tt,h2Tt,…,hNTtT∈R2N with hit=hixt,hivtT (i=1,2,…,N) continuously differentiable and hivt being the derivative of hixt. Let hxt=hx1Tt,hx2Tt,…,hxNTtT and let hvt=hv1Tt,hv2Tt,…,hvNTtT; then one has that if hvt are not equal to zeros, the formation is time-varying.Definition 2 (see [21]).
UAV swarm systems (2) are said to achieve formation ht if there exists a function rt=rxt,rvt∈R2 with rvt being the derivative of rxt such that (3)limt→∞⁡ξit-hit-rt=0,i=1,2,…,N,where rt is called a formation center function.In this paper, the communication topology is molded by a directed graph and we assume that the communication topology is time-varying. LetG^=G1,G2,…,Gp, p≥1, be the set of all possible directed topologies. We define the switching signal σt, where σt:0,+∞→P=1,2,…,p. 0=t0<t1<t2<⋯ denote the switching instants of σt. Let Gσt∈G^ be the communication topology at time t. Lσt stands for the corresponding Laplacian matrix of Gσt.Assumption 3.
Each possible graphGσt∈G^ is fixed and contains a directed spanning tree.Letλiσt (i=1,2,…,N) be the eigenvalues of the Laplacian matrix Lσt. Without loss of generality, it is assumed that Reλ1σt≤Reλ2σt≤⋯≤ReλNσt. Furthermore, from Lemma 1, one can obtain that λ1σt=0 and 0≤Reλ2σt≤⋯≤ReλNσt. Let λmin=min⁡λim∀m∈P;i=2,3,…,N.Consider the following formation protocol:(4)uit=K1ξit-hit+K2∑j=1Naijξjt-hjt-ξit-hit+h˙ivt,i=1,2,…,N,where i=1,2,…,N, K1∈R1×2 and K2∈R1×2 are constant gain matrices, and aij is defined as in Section 2.1. Let ξt=ξ1Tt,ξ2Tt,…,ξNTtT, let hxt=h1xTt,h2xTt,…,hNxTtT, and let hvt=h1vTt,h2vTt,…,hNvTtT. Under protocol (4), the UAV swarm systems (2) can be written in a compact closed-loop form as follows:(5)ξ˙t=IN⊗A+BK1-Lσt⊗BK2ξt-IN⊗BK1-Lσt⊗BK2ht+IN⊗Bh˙vt.This brief mainly investigates how to design the gain matrices in protocol (4) for the UAV swarm systems (5) to achieve the formation ht.


## 3. Main Results

Letzit=ξit-hit, zt=z1Tt,z2Tt,…,zNTtT. Then the UAV swarm systems can be rewritten as follows:(6)z˙t=IN⊗A+BK1-Lσt⊗BK2zt+IN⊗Aht-IN⊗Inh˙t+IN⊗Bh˙vt.As forh˙ixt=hivt, one can obtain that(7)IN⊗Aht-IN⊗Inh˙t+IN⊗Bh˙vt=0.Thus (6) can be further rewritten as (8)z˙t=IN⊗A+BK1-Lσt⊗BK2zt.It holds directly that UAV swarm systems (2) with directed and switching topologies achieve formation ht if and only if system (8) achieves consensus.Before the consensus analysis of system (8), the following lemmas and definition are introduced.Lemma 4 (see [23]).
For a Laplacian matrixL of graph G and a full row rank matrix E defined as(9)E=1-10⋯001-1⋯0⋮⋮⋱⋮⋮0001-1,there exists a matrix M such that L=ME. Further, if the graph has a directed spanning tree, M is of full column rank and the eigenvalues of EM are equal to the nonzero eigenvalues of L.Lemma 5 (see [24]).
Suppose that the eigenvalues ofA∈RN×N have positive real parts; then there exists a positive definite matrix Q>0 such that(10)ATQ+QA>0.Definition 6.
For a switching signalσt over time interval 0,t, the average dwell time of the switching signal is defined as τa=t/(Nσ(t)+1), where Nσt denotes the number of the switches.Remark 7.
In [11, 25], the definition of the average dwell time of a switching signal σt over time interval 0,t can be described as follows. If there exist two positive numbers N0 and τa such that Nσt≤N0+t/τa, where Nσt denotes the number of the switches, τa is called the average dwell time. It is inaccurate to give the definition by an inequality, but, according to Definition 6, it can be seen that Nσt≤t/τa.From Lemma4, one can obtain that, for each Li, i∈P, there exists a matrix Mi such that Li=MiE. Given Assumption 3 and Lemma 1, it can be known that the eigenvalues of each EMi (i∈P) have positive real parts. Based on Lemma 5, one can obtain that there exist positive definite matrices Qi such that (11)EMi-αITQi+QiEMi-αI>0,where α<λmin. Further, one can obtain that (12)EMiTQi+QiEMi>2αQi,i∈P.Letθit=zi+1t-zit, i=1,2,…,N, and let θt=θ1Tt,θ2Tt,…,θNTtT. One can obtain that θt=E⊗Inzt, where E is defined as in Lemma 4.Premultiplying both sides of (8) by E⊗In leads to (13)θ˙t=IN-1⊗A+BK1-EMσt⊗BK2θt,where Mσt=LσtETEET-1.According to the definition ofθt, it is obvious that z1t=z2t=⋯=zNt if and only if θt=0. So if system (13) converges to zero, system (8) achieves consensus and UAV swarm systems (2) with directed and switching topologies achieve formation ht.Theorem 8.
Suppose that Assumption3 holds. The formation problem of UAV swarm systems (2) with directed and switching topologies can be solved by controller (4) if there exists a positive definite matrix P such that (14)A+BK1TP+PA+BK1-2αPBBTP+βP≤0,where α<λmin, β>ln⁡h/τa, h=φ1/φ2, φ1=maxi∈P⁡λQi, φ2=mini∈P⁡λQi, and Qi satisfies (12). The feedback matrix is designed as K2=BTP.Proof.
Consider the following piecewise Lyapunov candidate of system (13):(15)Vt=θtTQσt⊗Pθt,where P is a solution of inequality (14) and Qσt are feasible solutions of (12).Note that the communication topology is fixed fort∈ti,ti+1, i=0,1,…. Then, the derivation of this Lyapunov candidate along the trajectory of system (13) within the interval is(16)V˙t=θtTIN-1⊗A+BK1-EMσt⊗BK2TQσt⊗Pθt+θtTQσt⊗PIN-1⊗A+BK1-EMσt⊗BK2θt.SubstitutingK2=BTP into (16) yields(17)V˙t=θtTQσt⊗A+BK1TP+PA+BK1-EMσtTQσt+QσtEMσt⊗PBBTPθt.It then follows from (12) that (18)V˙t≤θtTQσt⊗A+BK1TP+PA+BK1-2αPBBTPθt.Based on (14), one has(19)V˙t<-βθtTQσt⊗Pθt.Thus, from (15), one can obtain that (20)Vt<e-βt-tiVti.Note that the communication topology switches att=ti; then one can get(21)Vti≤hVti-,where h=φ1/φ2, φ1=maxi∈P⁡λQi, and φ2=mini∈P⁡λQi.Thus, whent∈ti,ti+1, from (20) and (21), one has(22)Vt<e-βt-tihVti-<e-βt-tihe-βti-ti-1Vti-1<e-βthiV0.Sincei≤Nσt≤t/τa,(23)Vt<e-β-ln⁡h/τatV0.From (15), one can obtain that (24)V0≤ϕ1θ02,ϕ2θt2≤Vt,where ϕ1=φ1max⁡λP and ϕ2=φ2min⁡λP.According to (23) and (24), one has(25)θt2≤ϕ1ϕ2e-β-ln⁡h/τatθ02.Note thatβ>ln⁡h/τa; one has θt→0 as t→∞. This means that the consensus problem of system (8) is solved. Furthermore, formation for UAV swarm systems (2) with directed and switching topologies is achieved.Corollary 9.
If UAV swarm systems (2) achieve formation ht, the formation center function rt can be determined as follows:(26)rt=eA+BK1t-tipσtT⊗Ixti-hti,t∈ti,ti+1,where pσt is the left eigenvector of Lσt associated with eigenvalue 0 and pσtT1N=1.Proof.
From [7], there exists a left eigenvector pσt of Lσt associated with eigenvalue 0 and pσtT1N=1. For t∈ti,ti+1, Lσt is fixed and so is pσt.Premultiplying both sides of (8) by pσtT⊗I results in(27)pσtT⊗Iz˙t=A+BK1pσtT⊗Izt.Based on Definition2, one can obtain that (28)limt→∞⁡zt-1N⊗Irt=0.Premultiplying both sides bypσtT⊗I, one has(29)limt→∞⁡pσtT⊗Izt-rt=0.Therefore, a formation center function can be(30)rt=pσtT⊗Izt.It follows from (27) and (30) that (31)r˙t=A+BK1rt.Thus, (26) can be obtained.Remark 10.
As can be seen, the formation center is discontinuous due to the switching of the communication topology. In addition,K1 can be used to design the motion modes of the formation center function. If K1=0, protocol (4) becomes a totally distributed controller. K2 has no effect on the formation center function.Remark 11.
Compared with [21, 22], the interaction topologies are more common. Formation for UAV swarm systems with directed and switching topologies is solved. Furthermore, the gain matrix was designed by solving an LMI, which is simpler than solving an algebraic Riccati equation in [22]. In fact, undirected topologies are just special cases of directed topologies. So the algorithms presented in this paper are applicable to those cases in [21, 22].Based on the above results, a design procedure of protocol (4) can be summarized as follows. First, choose K1 to design the motion modes of the formation center by assigning the eigenvalues of A+BK1. Then design K2 using the conclusion of Theorem 8.


## 4. Examples

In this section, we provide an example to illustrate the effectiveness of the above theoretical results. UAV swarm systems consisting of four agents are considered. The system matrices are defined as(32)xi=xi1xi2xi3xi4,A=0100000000010000,B=00100001,where xi1, xi2, xi3, and xi4 stand for east position, east velocity, north position, and north velocity. The directed communication topologies are given in Figure 1. Clearly, each topology contains a directed spanning tree. The switching signal is shown in Figure 2.Figure 1
Communication topologies.Figure 2
Switching signalσt.Thus, we can obtainλmin=1 and then choose α=0.9. Further, we can get that φ1=3.4175, φ2=0.2009, and h=17.0075. From Figure 2, we can get that the average dwell time is 1.25 s and then choose β=5.Assign the eigenvalues ofA+BK1 at ±i,±i; we get (33)K1=-100000-10.Solve LMI (14) with α=0.9 and β=5; a feasible solution can be obtained. Accordingly, we can get (34)K2=0.65651.343100000.65651.3431.Choose the following time-varying formation:(35)
h
i
t
=
3
sin
⁡
0.2
t
+
i
-
1
π
2
0.6
cos
⁡
0.2
t
+
i
-
1
π
2
8
cos
⁡
0.5
t
+
i
-
1
π
2
-
4
sin
⁡
0.5
t
+
i
-
1
π
2
i
=
1,2
,
3,4
.Ifht is achieved, both the positions and velocities of the four UAVs locate at the vertexes of a rotating parallelogram, respectively. Choose initial states of four UAVs as x10=3040T, x20=-20-50T, x30=00-10T, and x40=50-50T.Figure3 shows the trajectories of the difference of UAV states and time-varying formation, which are denoted by solid line, dotted line, dash-dotted line, and dashed line. And the bold dotted line denotes the formation center trajectory. It is obvious that the differences achieve consensus after about t=7 s and converge to the formation center. From Definition 2, one can obtain that the time-varying formation problem is solved. Figure 4 shows the snapshots of four UAV positions at different time. It can be seen that, after t=6 s, the UAV swarm systems achieve a time-varying parallelogram formation. Therefore, the time-varying formation is achieved under the directed and switching topologies.Figure 3
Difference of UAV state and time-varying formation.
(a)
East position (b)
East velocity (c)
North position (d)
North velocityFigure 4
Snapshots of UAV positions.
(a)
t = 4 s (b)
t = 6 s (c)
t = 8 s (d)
t = 10 s


## 5. Conclusions

Formation problems for UAV swarm systems with directed and switching topologies are studied. The average dwell time of the switching topologies is introduced, based on which an LMI-based method to design the protocol is proposed. Though the UAV swarm systems can achieve the specified formation with the presented method, there are still problems in real application. As mentioned in Assumption3, each of the switching topologies is supposed to have a spanning tree, which may not be applicable, so there is still work to do in our future work.



---

*Source: 7657452-2016-09-06.xml*