QI Duo ,HU Junhua ,LIANG Xiaolong ,ZHANG Jiaqiang ,and ZHANG Zhihao

1.Air Traffic Control and Navigation College,Air Force Engineering University,Xi’an 710051,China;2.Shaanxi Province Lab.of Meta-Synthesis for Electronic &Information System,Xi’an 710051,China;3.Aeronautical Engineering College,Air Force Engineering University,Xi’an 710038,China

Abstract:In recent years,with the continuous development of multi-agent technology represented by unmanned aerial vehicle(UAV) swarm,consensus control has become a hot spot in academic research.In this paper,we put forward a discrete-time consensus protocol and obtain the necessary and sufficient conditions for the second-order consensus of the second-order multi-agent system with a fixed structure under the condition of no saturation input.The theoretical derivation verifies that the two eigenvalues of the Laplacian of the communication network matrix and the sampling period have an important effect on achieving consensus.Then we construct and verify sufficient conditions to achieve consensus under the condition of input saturation constraints.The results show that consensus can be achieved if velocity,position gain,and sampling period satisfy a set of inequalities related to the eigenvalues of the Laplacian matrix.Finally,the accuracy and validity of the theoretical results are proved by numerical simulations.

Keywords:multi-agent system,consensus control,input constraint,distributed control.

1.Introduction

Consensus control of multi-agent systems has become an important research topic,which has attracted great attention from researchers in many subjects such as control,mathematics and artificial intelligence,especially in swarm systems,distributed sensor networks,etc [1−8].Due to the limited perception of individuals,it is generally believed that the consensus control would be achieved through systems with large-scale of local information.Various forms of distributed control protocols have been provided by robotics and control research teams.Saber and Murray [9] put forward a general hierarchy to solve the consensus problems of multi-agent systems of a single integrator.Ren and Beard [10] studied the consensus problem with a directed weighted graph,and pointed out that under certain conditions,the system can achieve consensus.Moreau [11] analyzed the network of the discrete system by the Lyapunov method and the convexity theory,which proved that as long as the coupling between agents satisfies certain convexity conditions and the network is connected,the consensus can be achieved.In latest research,researchers have focused on switching directed network time-delays,topologies,and consensus control with disturbance appearing [12−17].

For past years,the consensus control of second-order dynamics has become one of the hottest topics in this field,and it has been affirmed that consensus may not be achieved even the topology is connected and has directed spanning trees.Zhan and Li [18] provided some suffcient conditions for consensus control of second-order multiagent systems with fixed and switching interaction topologies.Ren and Atkins [19] showed clearly that the gain parameters have to satisfy certain conditions related to eigenvalues of the Laplacian matrix in order to guarantee consensus of second-order continuous-time systems.Yu et al20] gave a necessary and sufficient condition to ensure second-order consensus,and they found both the real and imaginary parts of the eigenvalues have important effects.Zhang and Tian [21] indicated that there must exist appropriate gain parameters for discrete-time systems with fixed interaction topology,so that the consensus can be achieved if and only if union of graphs has globally reachable nodes.However,they did not explain how to design the parameters.Although Xie and Wang [22] put forward a mathematic expression and gave a reasonable range of gain parameters under fixed interaction topology,they still did not consider the sampling period of the system.

Another significant fact is that most of the researchers of the existing literature do not pay attention to input constraints which have to be considered in many practical engineering systems due to actuators limitations.To handle this,the so-called parameterized low-gain and high-gain feedback techniques were introduced in [23].With the introduction of the low-gain and high-gain feedback techniques,consensus of multi-agent systems with input saturation was studied in [24−27].Meng et al28] proposed a linear control protocol based on the relative state information.Global leader-following consensus with input saturation was also solved under fixed/time-varying topologies in their article.Yang et al29] further considered the global consensus control for discrete-time systems with input saturation constraints and fixed undirected topologies,and some necessary conditions for achieving global consensus were obtained.In [30,31],model predictive control protocols were used to achieve constrained consensus when the topology had a directed spanning tree and the sampling period was sufficiently small.

Taking a panoramic view of these existing investigations,gain parameters design for achieving consensus with input saturation constraints is a difficult problem.Although some attempts have been made,the problem has not been solved perfectly.For the single-integrator case,Li et al32] indicated that any relative-state-based linear protocol,which solves the linear consensus problem under fixed directed topology without input saturation constraints,can also solve the global consensus problem with input saturation constraints.Though these documents did not explain how to design the parameters,they have presented the affirmation that the desired consensus state may not be reached even the network is connected and has direct spanning trees.When considering the input saturation constraints and sampling period for discretetime situation,things get even more complicated [33,34].This is the motivation of this study.

The organization logic of this paper is as follows:Section 2 introduces some basic conceptions and problem descriptions;Section 3 considers the consensus problem without constraints.Thereafter,consensus with input saturation constraints is studied in Section 4. Section 5 presents simulation examples which demonstrate the validity of the control protocol and Section 6 is the summarization of this paper.

2.Preliminaries

2.1 Graph theory

G=(W,E,A) is a directed graph,in whichW={w1,w2,···,wN}is the node set of the graph,E⊆{(i,j):i,j∈W} is the edge set,A=[aij]N×Nis the weighted adjacency matrix of the graph.aijindicates the connection weight betweenwiandwj,aij=1 indicates that the nodewican receive information fromwj,otherwiseaij=0.In addition,it is defined here that wheni=j,aij=0.

The Laplacian matrix of the graphGisL,andL=[lij]N×N.It is defined aslii=,i=j.If there is a nodewi,the information can be passed fromwito any other nodes in the graph.The graphGis said to contain a directed spanning tree,andwiis called a root.

Lemma 1[35] The Laplacian matrixLof the graphGhas at least one zero eigenvalue,and otherN−1 nonzero eigenvalues all have positive real parts;ifGhas a directed spanning tree,zero is a single eigenvalue ofL,and 1Nis its corresponding right eigenvector.

2.2 Problem formulations

Consider a multi-agent system withNagents.Each agent is described as

wherei=1,···,N,xi(k)∈Rn,vi(k)∈Rn,ui(k)∈Rn,denote the position,velocity and control input of agentiat timek,respectively.T>0 is the sampling period.It is assumed thatn=1 if not otherwise specified for simplicity of description.However,all the results hereafter remain valid for a higher dimensional case and can be calculated by using the Kronecker product.

Consider the following consensus protocol:

whereα>0,β>0 are position and velocity gain parameters to be designed.

Definition 1System (1) achieves consensus if for any initial conditions,

Denotex(k)=col[x1(k),···,xN(k)],v(k)=col[v1(k),···,vN(k)],u(k)=col[u1(k),···,uN(k)],y(k)=col[x(k),v(k)].Substituting (2) into (1),system (1) can be rewritten in a compact matrix form as follows:

Clearly,then system (1) is equivalent to (3) under the protocol (2).

Let µ be an eigenvalue of matrixΓ.Then by the definition of eigenvalue,we can get

where λiis the eigenvalue of Laplacian matrixL,i=1,···,N.

Lemma 2[22]Lhas a zero eigenvalue with algebraic multiplicitymif and only ifΓhas a one eigenvalue with algebraic multiplicity 2m.

3.Consensus without constraints

Theorem 1[22] The consensus condition can be described as if and only if the matrixΓhas exactly a one eigenvalue of multiplicity two and all the other eigenvalues are in the unit circle.In addition,if the consensus is reached,then,

where ξTis the unique nonnegative left eigenvector with zero eigenvalue satisfying ξT1N=1.

Proof(Sufficiency) It can be verified that if the eigenvalue ofΓis 1,the multiplicity is two and cannot be similar to a diagonal matrix.Suppose there is a matrixP,which is non-singular and satisfiesP−1ΓP=J,in whichJhas the form ofJ=

Note thatΓhas exactly a one eigenvalue of multiplicity two and all the other eigenvalues are in the unit circle,then we get,that is,

From (3),we gety(k)=Γky(0).In combination with Definition 1,one can conclude that the consensus of system (1) is achieved and the consensus state satisfies (5).

(Necessity) SinceLhas at least one zero eigenvalue(Lemma 1),then on the basis of Lemma 2.If the necessity is not satisfied,it indicates thatΓhas at least three eigenvalues which are not in the unit circle,that ishas at least one eigenvalue which is not in the unit circle,thenThis means that there is at least one agent whose consensus conditions cannot be met,which contradicts the assumption that consensus of system (1) is achieved.Thus the necessity is satisfied.

Theorem 2The consensus of multi-agent system (1)can be achieved by protocol (2) if and only if the topology graph has a directed spanning tree,and the gain parameters and sampling period satisfy

where Re(λi) and Im(λi) are the real and imaginary parts ofλirespectively,i=2,···,N.

Proof(Necessity) Suppose that the system (1) is able to get consensus,and then on the basis of Theorem 1 and Lemma 2,Lhas exactly one simple 0 eigenvalue.

Letμ−1=s,hence Re(s)<0 and (4) can be rewritten as

Denotesi,1,si,2are a pair of roots of (8) associated withλ,that issi,1+si,2=−βTλi,then Re(si,1+si,2)=−βTRe(λi)<0.Sinceβ>0,T>0,then we get Re(λi)>0.Then by Lemma 1,there is a directed spanning tree in the topology graph.

Defineg(µ)=(µ−1)2+[αT2+(µ−1)βT]λi,i=2,···,N.ThenΓhas exactly a one eigenvalue of multiplicity two and all the other eigenvalues are in the unit circle,which is equivalent to thatΓhas exactly a one eigenvalue of multiplicity two andg(µ) is Schur stable,that is,all the roots ofg(µ) satisfy |µ|<1.By the technique of bilinear transformation µ=we get

Define

Then the polynomialg(µ) is Schur stable if and only if γ(σ) is Hurwitz stable.

Denote σ=iω and substitute it in (10),it follows that

Then,by the Hermite-Biehler theorem,γ(σ) is Hurwitz stable if and only if the following conditions hold:

(i)m(ω)=0 has two different roots,denoted asm1

(ii) The single root ofn(ω)=0 satisfiesm1

(iii)m(0)n′(0)−m′(0)n(0)>0.

Simple calculation gives

where

By solving the inequality (13),conditions in (7) can be established.

(Sufficiency) By Lemma 1,we get that ifGhas a spanning tree,thenLhas exactly one simple 0 eigenvalue.Hence,Γhas exactly a one eigenvalue of multiplicity two by Lemma 2.From the above proof in necessity,we obtain that parametersα,β,T,which meet the conditions of(8),also guarantee the roots ofg(µ) satisfy |µ|<1.ThereforeΓhas exactly a one eigenvalue of multiplicity two and all the other eigenvalues are in the unit circle.Hence,Theorem 2 is established.□

Corollary 1If the topology graph is an undirected one,then the consensus of system (1) can be achieved by protocol (2) if and only if the graph is connected and

where λNis the maximum eigenvalue of the Laplacian matrixL.In addition,if the consensus of system (1) is achieved,then

Since ξTsatisfies ξT1N=1 and is a left eigenvector ofLassociated with eigenvalue 0,that is ξTL=0.If the graph is undirected,it follows thatthen Corollary 1 can be easily verified.

Remark 1Theorem 1 and Theorem 2 are extensions of existing literature and this is considerable because the sampling period is a critical parameter for practical applications.For example,Dong et al36] applied a consensus-based time-varying formation tracking protocol to quadrotor formation flying test.Its controller update frequency is up to 10 Hz so as to be on the safe side.However,this is not only a vast waste of energy,but also extremely challenging for mobile communication network when the number of vehicles in the swarm is getting more.

4.Consensus with input saturation constraints

Suppose there is a multi-agent system with the members ofN,and the constrained input is described asc(ui(k))=[cs(ui,1(k)),···,cs(ui,n(k))],wherecs(·) is the standard sat uration function,and the definition is as follows:

whereu0is the maximum control input.

Theorem 3Assume that the topology is undirected and fixed.The consensus of multi-agent system (1) with input constraints described in (16) can be achieved by protocol (2) if the topology graph is connected and the gain parameters and sampling period satisfy

where λNis the maximum eigenvalue ofL.

ProofWhen considering the input constraints,system (1) can be rewritten as the following form:

For simplicity,x(k),v(k),u(k),andy(k),whose definitions have been given in Section 2,are denoted asx,v,u,andy,respectively.

Consider the equation below:

SincecT(u)u≥cT(u)c(u) for any column vectoru,we get that

Suppose θ −(αT)2>0 and αL−θLTLis semi-positive definite,then it follows thatV(k)≥0 andV(k)=0 if and only ifx1=···=xN,v1=···=vN,that is,the consensus is achieved.Thus (18) is an appropriate Lyapunov candidate function.Next,the proof is given to show that there exists suchθmeeting the conditions.

Since the graph is undirected,it follows thatLT=Land the eigenvalues of αL−θLTLcan be obtained by(i=1,···,N).The graph is undirected and connected,also indicating that 0＝λ1<λ2≤···≤λN.αL−θLTLis semi-positive definite if and only if αλi−≥0,then we can get α−θλi≥0,thus θ ≤α/λN.Further consider that θ −(αT)2>0,it follows (αT)2<θ ≤α/λN.If there exists such θ meeting the conditions,then (αT)2<α/λN,that is,

Now,it is time to show that ∆V(k+1)=V(k+1)−V(k)≤0.By (18),it can be obtained that

wheret=c(u(k+1)).

Hence,the condition ∆V(k+1)≤0 is satisfied if there existsα,β,Tsatisfying (24).

We then show that ∆V(k+1)=0 if and only if the consensus is achieved,that isx1=···=xN,v1=···=vN.Note that if there exists |ui|>u0,∆V(k+1)=0 cannot be established since at least one of the first two lines of (23)is negative.Hence,|ui|≤u0is satisfied for all agents.Then we can get that

Therefore,∆V=0 if and only ift=[(αT2−βT)+I]uandLu=0 are satisfied,that ist=u.By the definition ofuand with some algebra,we obtaint=u(k+1)=u(k)−αLv(k).

Since α>0,we haveLv(k)=0,that isvi(k)=vj(k),∀i,j=1,···,N.Furthermore,Lu=0 is satisfied if and only ifui(k)=uj(k),∀i,j=1,···,N.Now,we shall provexi(k)=xj(k).Note thatLv(k)=0 also indicatesu(k)=−αLx(k),in other words,we have

The graph is connected,indicating thatLhas exactly one simple 0 eigenvalue,that is,Rank(L)=N−1.Hence,one can obtain that all eigenvalues ofL˜ are strictly positive and Rank(L˜)=N−1,thus (27) only has all-zero solution,which is equivalent tox1=···=xN.Hence,we have shown that ∆V≤0 and ∆V=0 if and only ifx1=···=xN,v1=···=vN,that is,the consensus is achieved.

Note that (17) can be obtained by (20) and (24).Hence,Theorem 3 is proved in conclusion.□

Remark 2The sampling period is taken into account and the result can be regarded as a special case of Theorem 3 withT=1.Furthermore,the results in Theorem 3 is less conservative by substituting inT=1.

5.Simulation experiment

5.1 Consensus without input constraints

Suppose there is a multi-agent system with the members ofN,hereN=15,and its topologyG1is given inFig.1.The initial settings arex(0)=[100,110,120,130,140,150,60,70,80,90,40,30,50,20,10],v(0)=[10,11,12,13,14,15,6,7,8,9,5,4,3,2,1].Clearly,G1has a directed spanning tree and the eigenvalues of the Laplacian matrix are λ1=0,λ2=0.186,λ3=0.509,λ4=1,λ5,6=2,λ7=2.710,λ8,9=1.411±0.585i,λ10,11=1.461±0.439i,λ12,13=1.980±1.171i,λ14,15=2.446±0.970i.i is the imaginary unit.Letα=0.20,β=0.35 and plot change curves offj(α,β,T,λi) (i=1,···,15,j=1,2) vsT,it is known that the system can attain consensus if and only ifT<0.8 s based on the results of Theorem 2.

Fig.1 Graph topology of G1

For comparison,simulations are conducted continuously under the condition thatT=0.7 s andT=0.8 s,respectively.The change curves of accelerations,velocities and positions of each member of the system are shown inFig.2andFig.3respectively.The results presented here show that the control protocol (2) makes them meet the consensus whenT=0.7 s inFig.2.While inFig.3,one can see that whenT=0.8 s,the system cannot meet the consensus conditions.Thus the result of Theorem 2 is verified.

Fig.2 Evolution of positions and velocities of all agents (α=0.20,β=0.35,T=0.7 s)

Fig.3 Evolution of positions and velocities of all agents (α=0.20,β=0.35,T=0.8 s)

5.2 Consensus with input constraints

Suppose there is a multi-agent system with the members ofN,hereN=15 and input constraints |ui|≤u0=2.The topologyG2is given inFig.3 (a),here we need to pay attention to that the graph here is undirected and simply connected.The initial settings,including positions and velocities,are the same as Section 5.1.After some calculation,we know the maximum eigenvalues of the Laplacian matrix λN=5.06.Let α=0.20,β=0.35 and substituting them into (17),one can obtain that the consensus condition isT<0.90 s.Hence,we takeT=0.85 s in the simulation.

The change curves of accelerations,velocities and positions of each member of the system are shown inFig.4 (b),Fig.4 (c)andFig.4 (d)respectively.The results indicate that the control protocol (2) makes them meet the consensus and the control input satisfies the constraints,which demonstrates the effectiveness and feasibility of Theorem 3.

Fig.4 Evolution of positions and velocities of all agents (α=0.20,β=0.35,T=0.85 s)

6.Conclusions

Consensus control of the multi-agent system is of significant importance.In this paper,the consensus problem of the second-order discrete-time multi-agent system is considered.Firstly,some necessary and sufficient conditions are given in order to ensure the second-order consensus,which shows the importance of eigenvalues of the Laplacian matrix of the topology and the sampling period in achieving consensus.Then,the case with input saturation constraints is mainly studied and the deduction of the sufficient condition for consensus is completed.What has been found in this paper is that consensus will be realized of the constrained multi-agent systems if velocity and position gains and sampling period satisfy some appropriate ranges.Finally,numerical simulations are carried out and the feasibility of the theoretical results is illustrated.

Extensions of directing and switching topologies are currently under investigation.Velocity and acceleration constraints should be taken into account simultaneously in future studies.