Improved Consensus Speed for Discrete-Time Multi-agent Systems

LI Min ( ),LI Qi-qiang(歧強(qiáng)),GAO Huan-li ()

1 School of Control Science and Engineering,Shandong University,Jinan 250061,China

2 School of Electrical Engineering and Automation,Qilu University of Technology,Jinan 250061,China

3 College of Automation,South China University of Technology,Guangzhou 510641,China

Introduction

The study of the interactions between communication and control for multi-agent systems (MASs) is considered,due to its broad applications in formation of mobile robots and scheduling of automated highway systems and alignment of clusters of satellites.If all agents converge to a common constant vector or common trajectories,we say that the MASs reach consensus.In recent years,a large number of interesting results for continuous-time MASs have been obtained[1-4].The effect of communication delays on consensus properties was investigated[1].A general consensus protocol was considered for the static and the dynamic consensus problem of high-order integrators[2].Chengetal.[3]solved the modified consensus problem.Yanetal.[4]considered the problems of formation and obstacle avoidance for MASs.Besides,a great many of results for discrete-time MASs have been given[5-10].The consensus condition for low-order MASs was presented[5].Two consensus problems can be solved,provided that the dynamic graph is jointly connected[6].Guetal.[7]added a suitably designed dynamic filter into the protocol.An observer-type protocol based on the relative outputs was proposed[8].Tuna presented the synchronization of discrete-time systems[9].

The convergence time to consensus is an important design consideration.For example,the time is too long to achieve the prescribed relative states for all agents within the allowed time in the formation problem and it is necessary to design a protocol to improve the consensus speed.At present,Refs.[3-4,8-10] dealt with the consensus problem without regarding the convergence speed.Some references[2,11-16]analyzed the convergence rate or the finite-time consensus problem.The protocol could not improve the consensus rate[11].Kuangetal.[2]got the desired consensus speed for continuous-time integrators.Similar problem was studied for general continuous-time MASs[12].Youetal.[13]derived the lower bound of optimal asymptotic convergence factor for the single-input discrete-time MAS and undirected graphs,but left an open question for finding an optimal protocol gain.References[14-15] dealt with the finite-time consensus of continuous multi-agent systems.Sundarametal.[16]considered the finite-time distributed consensus of first-order discrete-time MASs.However,few references have improved the consensus rate for general discrete-time MASs with directed graphs.

In this study,for a general discrete-time MAS with directed graphs,a protocol whose gains are to be determined is designed to enhance the consensus speed.The convergence speed may be predetermined.The protocol is based on the absolute state of each agent and the relative states between neighboring agents[2- 3,17].Determining how to get a constant consensus function has been studied for continuous-time MASs[3],and we put more types of the consensus function,which is divided by different protocol gains into four types: zero,non-zero constant vector,bounded trajectories,and ramp trajectories.An algorithm of constructing the protocol gains is provided to fulfill the joint design of an expected type of consensus function and a prescribed consensus speed.

1 Notation and Preliminaries

A matrix is said to be Schur stable if all the eigenvalues are less than unity in magnitude.A matrix is said to be neutrally stable if all the eigenvalues are not larger than unity in magnitude and the Jordan block corresponding to the eigenvalues with unit magnitudes has order 1.

(1)

wherexi=xi(k)∈n，k=0,1,…,is the state at the current time instant,=xi(k+1) is the state at the next time instant,andui=ui(k)∈ris the control input at the current time instant;A∈n×nandB∈n×rare constant matrices and represent the state and input matrices,respectively.The following assumptions are used throughout the paper.

Assumption1The pair (A,B) is controllable.

Assumption2The directed graph G has a spanning tree.

A modified distributed protocol for agentiis proposed as follows:

(2)

wherei=1,2,…,N,andK1,K2∈r×nare the gain matrices to be determined.

Definition1The multi-agent system Eq.(1) reaches consensus if there exists a protocol Eq.(2) such that for any initial value

(3)

wherec(·) is called a consensus function.

2 Improved Consensus Speed

(4)

In this paper the following two problems are focused: (1) how to designK1such that MAS Eq.(4) reaches an expected type of consensus function; (2) how to designK2such that MAS Eq.(4) reaches consensus with an improved convergence speed.

Introduce a new variable

ξ=((IN-1γT)?In)X,

(5)

By the idea of Theorem 3.3 in Ref.[12],underAssumption2,the closed-loop MAS Eq.(4) is consensusable if and only if system Eq.(5) is asymptotically stable.

In the sequel,we will give a sufficient and necessary condition such that MAS Eq.(4) is consensusable.

(6)

wherek→+∞,γ∈Nis a nonnegative vector and satisfiesTTandT1=1.

ProofIt is not difficult to prove the results above.The method of the proof may refer to Refs.[8,12].So the proof is omitted. □

Definition2MAS (Eqs.(1) and (2)) is said to be consensusable with the consensus speed indexσif the spectral radii ofA+BK1+(1-λi)BK2，i=2,3,…,Nare less thanσwithσ∈(0,1].

Lemma3The spectral radius ofAin systemx+=Axis less thanσ(0<σ≤1)，if and only if there exists a matrixQ>0such that[20]

ATQA-σ2Q<0.

Next,we will make a theorem and give a sufficient condition such that the multi-agent system Eq.(1) via protocol Eq.(2) reaches consensus with a consensus speed indexσfor any linear agent (A,B) controllable.First,we propose a lemma.

Lemma4For 0≤δ<1 and 0<σ≤1，the following modified algebraic Riccati equation (MARE):

σ2P=ATPA+Q-

(1-δ2)ATPB(BTPB+I)-1BTPA

(7)

(8)

ProofFrom Eq.(7),we have

(9)

Forδ=0，MARE Eq.(9) is reduced to the commonly-used discrete-time Riccati equation studied[21].So according to the conditions of the lemma,MARE Eq.(9) withδ=0 has a unique solutionP>0.

For 0<δ<1，since (A,B) is stabilizable,σ>δ，Q>0andAhas no eigenvalues with magnitude larger than 1,jointly with Lemma 3.2[10],MARE Eq.(9) has a unique solutionP>0.

According to the proof above,MARE Eq.(9) has a unique solutionP>0.Thus by Hewer[21]and Sinopolietal.[22],MARE Eq.(8) holds. □

Next,inspired by the idea of Theorem 3.1 in Ref.[10],we get the following theorem.

Theorem1Supposing thatAssumptions1and2hold.ChooseK1such that all the eigenvalues ofAK1are in the closed unit circle.σ(0<σ≤1) is a given scalar.If there exists aw∈such that

(10)

the gain matrixK2=-w(BTPB+I)-1BTPAK1solves the consensus problem of MAS Eq.(1) with the consensus speed indexσ，wherePis the unique solution of the following MARE

(11)

with any matrixQ>0.

ProofIn accordance with the conditions of the theorem,together withLemma4,MARE Eq.(11) has a solutionP>0.ByLemmas2and3,it suffices to verify that there exists a matrixP>0such that

(AK1+(1-λj)BK2)HP(AK1+(1-λj)BK2)-σ2P<0,

j∈{2,3,…,N}.

(AK1+(1-λj)BK2)HP(AK1+(1-λj)BK2)-σ2P=

(BTPB(BTPB+I)-1-I)BTPAK1=

i=2,3,…,N.

(12)

The Formula (12) implies that the consensus problem of system Eq.(1) under protocol Eq.(2) is solved with the consensus speed indexσ. □

Remark2References[8,10] addressed the consensus problem of discrete-time MASs,but to improve the consensus speed was not considered in their results.Youetal.[13]gave an algorithm to compute a suboptimal consensus speed only for the single-input MASs and undirected graphs.However,in this study,the convergence speed of the general discrete-time MASs with directed graphs may be greatly improved by designing proper protocol gains in light ofTheorem1and in addition the consensus function may be prescribed.

Corollary1presents that the parameterw=1 inK2ofTheorem1may be selected for the special case.Next,we give a lemma to analyze what condition inequality (10) holds and how to choosewin general.

(13)

{w∈

(14)

is not empty.

ProofIt follows from Formula (13) that

Sogj(w)=0 has two unequal real rootswj 1andwj 2,j∈{2,3,…,N}.Thus one can easily verify that the assertion remains true. □

Finally,we propose an algorithm to construct protocol Eq.(2) to reach the prescribed consensus function with an improved consensus speed.

Algorithm1Assuming thatAssumptions1and2hold.Given consensus speed indexσ(0<σ≤1) and an expected type of consensus function,the gain matrices in protocol Eq.(2) can be constructed as follows.

Step1Verify whetherσandλj,j=2,3,…,Nsatisfy Formula (13).If Formula (13) holds,turn to the next step.Otherwise,quit.

Step3According to the expected type of consensus function,choosenscalars in light ofRemark1as all the eigenvalues ofA+BK1.Obtain the gain matrixK1by using classical pole placement algorithms,such as the Ackermann’s formula[20]and the algorithm based on a Sylvester equation[20].

Step4SubstituteK1intoAK1.LetQ=I，and further chooseK2=-w(BTPB+I)-1BTPAK1whereP>0 is the unique solution of MARE (11).

Remark3Some discussion for the maximum consensus speed is provided as follows.The maximum consensus speed means finding optimalK1andK2to minimize the consensus speed index.Since optimalK2replies onK1and optimalK1depends on the expected consensus function,the aforementioned problem is more difficult than in Ref.[13].On the other hand,the smaller consensus speed indexσmay lead to the higher gainK2.And the high gain may destroy the stability of high-order system Eq.(4),so the reason of which is still open[23].Thus,although the proposed method in this study may not solve the maximum consensus speed,it may properly increase the convergence speed to the allowed extent.

3 Example

Consider the discrete-time double-integrator system with the sampling periodh=0.1 s for agentias follows:

(15)

wherexi 1∈andxi 2∈,respectively,correspond to the velocity and the acceleration of vehicleiat timekh.ui∈is the control input.Obviously,system Eq.(15) is controllable.

Graph G associated with system Eq.(15) is depicted by Fig.1,which has a spanning tree.The adjacency matrix is as follows:

(16)

Fig.1 Communication graph G

All vehicles are required to reach the same constant speed within 5 s,which implies that the consensus functionc(·) is a constant vector.First,byStep3ofAlgorithm1,select 1 and 0.5 as eigenvalues ofAK1.By the function place of Matlab,getK1=[0.0000 -5.0000].Then solving MARE Eq.(11) withσ=1 getsK2=[-1.1125 -0.2843].The protocol Eq.(2) withK1andK2as above is denoted as protocol (a1).Choosingσ=0.9 in MARE Eq.(11),one hasK2=[-12.4516 -2.5390].Protocol Eq.(2) with the aforementionedK1andK2is called protocol (a2).

Thus,the state trajectories of system Eq.(15) are described under protocols (a1) and (a2) for 30 s by Figs.2 and 3,respectively.The time to reach the same constant speed is more than 30 s in Fig.2 and however the convergence time is less than 5 s in Fig.3.It implies that the vehicles may obtain the expected state with an improved consensus speed by protocol (a2).

Fig.2 State trajectories under protocol (a1)

Fig.3 State trajectories under protocol (a2)

Consider the other special case that the vehicles reach the same speed within 4 s.It is obvious that the system matrix of system Eq.(15) has an eigenvalue one and its Jordan block has order 2.Forσ=1，protocol Eq.(2) withK1=[0 0] andK2=[-1.0214 -1.9654] is denoted as protocol (c1); forσ=0.8,protocol Eq.(2) withK2=[-17.0471 -9.3458] andK1=[0 0] is denoted as protocol (c2).The state trajectories of system Eq.(15) are depicted under protocols (c1) and (c2) for 8 s by Figs.4 and 5,respectively.From Figs.4 and 5,it may be deduced that the time reaching the same speed exceeds the prescribed time in Fig.4,and however,the prescribed consensus time is achieved in Fig.5.

Fig.4 State trajectories under protocol (c1)

Fig.5 State trajectories under protocol (c2)

4 Conclusions

The consensus problem for discrete-time MASs with directed graphs has been studied.Provided that each agent’s dynamics is controllable and communication graph has a directed spanning tree,the multi-agent system converges to a predetermined type of consensus function with a prescribed consensus speed.Based on a classical pole placement algorithm and a modified algebraic Riccati equation,the protocol gains may be conveniently constructed so that the convergence speed to consensus is greatly improved.Some interesting topics remain to be solved in the future in this paper.For example,in our results,the consensus function is not accurately foreknown except zero.The results of this paper need to be generalized to the time-varying communication graph case.

[1] Sun Y G,Wang L.Consensus of Multi-agent Systems in Directed Networks with Nonuniform Time-Varying Delays [J].IEEETransactionsonAutomaticControl,2009,54(7): 1607-1613.

[2] Kuang J,Zhu J D.On Consensus Protocols for High-Order Multiagent Systems [J].JournalofControlTheoryandApplications,2010,8(4): 406-412.

[3] Cheng L,Hou Z G,Lin Y Z，etal.Solving a Modified Consensus Problem of Linear Multi-agent Systems [J].Automatica,2011,47(10): 2218-2223.

[4] Yan J,Guan X P,Luo X Y，etal.Formation and Obstacle Avoidance Control for Multiagent Systems [J].Journalof

ControlTheoryandApplications, 2011,9(2): 141-147.

[5] Lin P,Jia Y M.Consensus of Second-Order Discrete-Time Multi-agent Systems with Nonuniform Time-Delays and Dynamically Changing Topologies [J].Automatica,2009,45(9): 2154-2158.

[6] Su Y F,Huang J.Two Consensus Problems for Discrete-Time Multi-agent Systems with Switching Network Topology [J].Automatica,2012,48(9): 1988-1997.

[7] Gu G X,Marinovici L,Lewis F L.Consensusability of Discrete-Time Dynamic Multi-agent Systems [J].IEEETransactionsonAutomaticControl,2011,57(8): 2085-2089.

[8] Li Z K,Duan Z S,Chen G R.Consensus of Discrete-Time Linear Multi-agent Systems with Observer-Type Protocols [J].DiscreteandContinuousDynamicalSystems-SeriesB,2011,16(2): 489-505.

[9] Tuna S E.Synchronizing Linear Systems via Partial-State Coupling [J].Automatica,2008,44(8): 2179-2184.

[10] You K Y,Xie L H.Consensusability of Discrete-Time Multi-agent Systems over Directed Graphs [C].Proceedings of the 30th Chinese Control Conference,Yantai,China,2011: 6413-6418.

[11] Li T,Fu M Y,Xie L H,etal.Distributed Consensus with Limited Communication Data Rate [J].IEEETransactionsonAutomaticControl,2011,56(2): 272-2792.

[12] Li Z K,Liu X D,Lin P,etal.Consensus of Linear Multi-agent Systems with Reduced-Order Observer-Based Protocols [J].Systems&ControlLetters,2011,60(4): 510-516.

[13] You K Y,Xie L H.Network Topology and Communication Data Rate for Consensusability of Discrete-Time Multi-agent Systems [J].InternationalJournalofRobustandNonlinearControl,2011,21(10): 2262-2275.

[14] Wang L,Sun S W,Xia C Y.Finite-Time Stability of Multi-agent System in Disturbed Environment [J].NonlinearDynamics,2012,67(3): 2009-2016.

[15] Wang L,Xiao F.Finite-Time Consensus Problems for Networks of Dynamic Agents [J].IEEETransactionsonAutomaticControl,2010,55(4): 950-955.

[16] Sundaram S,Hadjicostis C N.Finite-Time Distributed Consensus in Graphs with Time-Invariant Topologies [C].The 26th American Control Conference,New York,2007: 711-716.

[17] Xiao F,Wang L.Consensus Problems for High-Dimensional Multiagent Systems [J].IETControlTheory&Applications,2007,1(3): 830-837.

[18] Ren W,Beard R W.Consensus Seeking in Multiagent Systems under Dynamically Changing Interaction Topologies [J].IEEETransactionsonAutomaticControl,2005,50(5): 655-661.

[19] Hu T,Qiu L.Controllable Regions of Linear Systems with Bounded Inputs [J].Systems&ControlLetters,1998,33(1): 55-61.

[20] Shi S,Chen X Z,Du X.Modern Control Theory Foundation [M].Beijing: Higher Education Press,2009.(in Chinese)

[21] Hewer G A.Analysis of a Discrete Matrix Riccati Equation of Linear Control and Kalman Filtering [J].JournalofMathematicalAnalysisandApplications,1973,42(1): 226-236.

[22] Sinopoli B,Schenato L,Franceschetti M,etal.Kalman Filtering with Intermittent Observations [J].IEEETransactionsonAutomaticControl,2004,49(9): 1453-1464.

[23] Seo J H,Shim H,Back J.Consensus of High-Order Linear Systems Using Dynamic Output Feedback Compensator: Low Gain Approach [J].Automatica,2009,45(11): 2659-2664.