A novel gain design method to improve the consensus performance of output-feedback multi-agent system s

Wei ZHENG ,Qiang LING ?,Hai LIN

1.Department of Autom ation,University of Science and Technology of China,Hefei Anhui 230027,China;

2.Department of Electrical Engineering,University of No tre Dam e,Notre Dam e,IN 46556,U.S.A.

1 Introduction

Nowadays the consensus of m ulti-agent system s(MASs)hascaughtmuch attention due to itsapplications in many areas,such as unmanned air vehicles(UAVs),wireless sensor networks and formation control[1-5].In the current literature,it is usually assumed that the states of agents can be directly measured.When a MAS is noise-free,asymptotic consensus,i.e.,the states of all agents converges to a common value,is well studied.As shown in[2],a necessary and sufficient condition to achieve asymptotic consensus is that the communication topology of the MAS is a connected undirected graph or a digraph with a spanning tree.Early works were mainly done regarding first-order MASs.Recently more efforts have been made for high-order MASs[6],which aremore popular in reality because agents may be required to reach consensus as to more than one state variable,e.g.,not only position but also velocity and acceleration are expected to reach consensus.In[7-9],some consensus conditions and protocols are provided for asymptotic consensus of high-order MASs.

When there is noise,such as process noise,in MASs,asymptotic consensus has to be replaced by practical consensus,i.e.,the deviation of the state of each agent from acomm onvalue can only be guaranteed to be bounded[2].As show n in[10],the state deviation of a MASwith bounded processnoise can beupperbounded by a classKfunction under a good consensus protocol.The H∞performance of high-order MASs with bounded noise can be guaranteed by a neighbor-based protocol in[11].performance analysis of broadcast-based consensus algorithm s in the presence of non-zero-mean stochastic noise was done in[12],which provides some asymptotic upper and lower bounds of the state deviation in the mean square sense.Some sufficient conditions for swarm system s with bounded noise w ere proposed in[13]to ensure that all agents reach practical consensus.The above works put more efforts on whether the practical consensus is achievable under the given noise.As w e know,practical consensus means bounded state deviation.The performance of practical consensus can be measured by the size of the state deviation,e.g.,the ultimate upper bound of the state deviation or the mean square state deviation.Such performance makes great sense in real applications.Unfortunately no much attention has been paid to how to improve the performance of the achievable practical consensus.As a rare example,[14]considered the average consensus problem for first-order integrator MASs with additive noise and provided a method to design the optimal edge w eights,which results in the least mean square deviation of the steady state.It is shown in[14]that the weight optimization problem is convex and can be efficiently solved. More general system dynamics was investigated in[15],where the common state feedback gain of MASs is designed through optimizing the performance measured by either the H∞or H2norm of the transfer function from the process noise to a concerned per for mancevariable.The H2performance optimization of[15]is closely related to our problem,which places equal H2performance requirement on all subsystem s and takes an LM I form.Recently an iterative method was proposed to design the control gain of homogeneous agents[16].The obtained gain in[16]is shown to be able to significantly improve the consensus performance measured by the ultim ate mean-square deviation of the states.The present paper is exactly motivated by[14-16].

In the aforementioned literature,state is assumed to be directly measured.In reality,the availability of state is not always true.In m any MASs,only output can be measured.For such system s,observability,at least detectability,is usually assumed,the state of each agent can be efficiently observed from its output,and the control of each agent is constructed with the estimated states of its own and neighbors.This schem e is also adopted in the present paper.Again the current works regarding the output-feedback consensus mainly focus on the achievability of consensus,or practical consensus.In[17],the joint effects of agent dynamics and the network topology on the consensus of linear discretetime MASs with output feedback were analyzed and a necessary and sufficient condition for consensusability under an observed-based distributed protocol was provided.In[18],an observer-type protocol based on the output differences of neighboring agents was proposed.Besides the control gain of agents,the observation gain of state observers of agents p lays a critical role in the consensus performance because the control of output-feedback MASs is computed with estimated states.Therefore the present paper aim s to find a method to simultaneously design the control and observation gain of agents to optim ize the consensus performance of MASs as an extension of the control gain design method in[16].

More specifically,the present paper considers a general discrete-time MAS with homogeneous agents.Each agent is modelled as a general high-order linear system perturbed by zero-mean white process and observation noises.Under the observability assumption,the state of each agent can be estimated from its output by a Luenberger observer.Each agent computes the differences between its ow n estimated state and the ones of neighboring agents and multiplies such state differences with a control gain to generate its control.Both the observation gain(of the state observer)and the control gain can surely affect the consensus performance,which is measured by the ultim ate mean-square deviation of the states as[16].It makes great sense to design appropriate observation and control gains to optim ize the concerned consensus performance,which is the main task of the present paper.That optimization of the observation and control gains,how ever,is not convex and difficult to handle.In order to efficiently solve that optimization problem,we extend the iterative method in[16]to the output-feedback case.As shown later,under the given observation and control gains,the consensus performance can be computed by solving a group of LM Is(linear matrix inequality),which provide some intermediate matrix variables as by-products.By perturbing the obtained intermediate matrix variables and the given observation and control gains,w e obtain another group of LM Is,which yield a descent direction of observation and control gains to improve the concerned consensus performance.By moving observation and control gains along the obtained descent direction,we can hopefully improve performance.The updated observation and control gains can again be used to compute the intermediate matrix variables,i.e.,work as the starting point of the next iteration.Although the philosophy of the method of the present paper is close to that of[16],the output-feedback situation greatly complicates the optimization problem and special attention is needed.

The rest of this paper is organized as follow s.Section 2 presents mathematical models and some preliminary results.Our method is given in Section3.Section 4 demonstrates some simulation results,which confirm the effectiveness of our method.Finally,some concluding remarks are given in Section5.

The following notation will be used throughout this paper.θm×nrepresents am×n-dimensional matrix with its elements denoted as θij(i=1,...,m;j=1,...,n).Particularly,1N×1represents aN-dim ensional vector with all 1 while 0N×1represents aN-dim ensional vector with all 0.Rm×ndenotes the set ofm×n-dimensional real matrix.?denotes the Kronecker product[19].For a given vector or matrix ξ,ξTdenotes its transpose.E(·)stands for the expectation of a stochastic variable.tr(·)is the trace operator of a square matrix.

2 Mathematical models

2.1 Model of the communication topology

We assume that the communication topology of multipleagents is modelled as a connected undirected asaconnected undirected graphG=(V,E),whereV={1,...,N}is a set of vertices andE?V×Vis a set of edges.Each vertex stands for an agent.A link represents that two vertices(agents)are neighbors.Due to the undirected nature,(i,j)∈Eimplies(j,i)∈E.The neighbor set of agentiis denoted byN i={j∈V:(j,i)∈E}.

The weighted ad jacency matrixA=[aij]∈ RN×Nof a graph is defined according to the following rule,

The Laplacian matrixL=[lij]of a graph is defined as

2.2 Dynamics of agents

The dynamics of homogeneous agents can be modelled as the following high-order linear system:

wherexi(k)∈ Rn×1is the state of agenti,ui(k)∈ R is the control input of agenti,ωi(k)∈ Rn×1is the white zero-mean process noise with the constant covarianceis the output to be directly measured,is the white zero-mean output noise with the constant covarianceA∈ Rn×n,B∈ Rn×1andC∈ Rm×n.It is assumed that(A,B)is controllable and(A,C)is observable.

For each agent,a Luenberger observer is constructed to estimate its state as1For each agent,the state estimation can also be generated by a Kalm an filter,which has time-varying observation gain.It is usually the case that a Kalm an filter yields smaller transient state estimation error than the Luenberger observer in(2).However,when k→∞,the time-varying observation gain of the Kalm an filter converges to a constant gain and the Kalm an filter reduces into the Luenberger observer.Because this paper is concerned with the asymptotic consensus performance when k→∞,the Kalman filter and the Luenberger observer in(2)make no difference from the performance’s perspective.

whereHis the common observation gain of all homogeneous agents.The estimated state?xi(k)takes the p lace of the statexi(k)and generates the control as

whereKis the common control gain of all agents.

As seen in(1),the evolution ofxi(k)is determined byui(k).Therefore,the consensus of the MAS is determined by the control policy in(3).By(2)and(3),we know that bothHandKmake impact onui(k)and play a critical role in the consensus performance of the concerned MAS.Therefore,this paper attempts to provide an efficient way to design the observation and control gains,HandK,for the purpose of optimizing the consensus performance.

To facilitate our ongoing gain design,we integrate the dynamics and observers ofNagents into the following com pact form:

2.3 De finition of consensus performance

As[14],w e introduce a deviation vector δ(k),

whererepresents the average state of all agents,i.e.,It can be shown that

whereis the average of estimated statesAn estimated version of δ(k)

J(k)provides a concrete way to measure the consensus performance of the MAS in(1).The time-varying nature ofJ(k),however,prevents its applications.Therefore we compute its ultimate limit

Jcan measure how w ell the system asymptotically reaches consensus.For the noise-free MASs,J=0.Under the process noise ωi(k)and the observation noisevi(k),the smaller isJ,the better consensus the agent can reach.Therefore,we will minimizeJin the subsequent section.

3 Main results

3.1 Problem formulation

As mentioned in Section2.3,we want to minimize the performance indexJ.In order to formulate this per-for mance optimization(minimization)into a tractable form,we need the following transformation of δ(k).

Defineandwhere Φ is the unitary matrix defined in Section 2.1 and can transform sLinto a diagonal matrix.withz(k)and(4)can be rewritten into

Partitionz(k)and?z(k)as

wherez1(k)and?z1(k)are the firstnelements ofz(k)and ?z(k),respectively.Because,we obtain

(10)can,therefore,be reduced into

Considering the unitary nature of Φ,we obtain

Due toweknowJcan beequivalently defined as

We want to minimizeJwith respect to the control gainKand the observation gainH,which can be form ulated into

It is difficult to solve the above optimization problem directly.Therefore,we will give an equivalent and tractable form of this optimization problem.Before that,we define the feasible sets ofKandH.

De finition 1The feasible set of the control gainKis

whereZN-1={1,...,N-1},ρ(·)represents the spectral radius of a square matrix and λ2,...,λNare the eigenvalues ofL,which are defined in Section 2.1.

De finition 2The feasible set of the observation gainHis

According to(Theorem 3.1,[9]),ΩKis non-em pty if and only if

whererepresent the unstable eigenvalues ofA.ΩHcan also be guaranteed to be non-em pty due to the observability of(A,C).Note that the convexity of ΩKand ΩH,however,cannot be guaranteed for general system s in(1).

with ΩKand ΩH,w e provide an equivalent form of the optimization problem(16)in the following Lemma.Although the proof of Lemma 1 closely follow s the technical procedures of[9]and[14],it is still provided in the Appendix for self-containedness.

Lemm a 1WhenK∈ΩKandH∈ΩH,the optimization problem(16)is equivalent to the

where

WhenK∈ΩKandH∈ΩH,Az2is stable.Therefore,the solutionPto the constraint in(20)can be expressed as

As shown in(21),the observation gainHhas direct effects onPthrough?H.Therefore,KandHhave to be simultaneously considered in the performance optimization(20),where the independence between the controllerdesign and the state observer design no longer holds.

BecauseAz2is com posed of four block diagonal matrices.Phas the same structure asAz2,i.e.,

whereQ1,Q2andQ3are block diagonal matrices.Qi(i=1,2,3)hasN-1 diagonal blocks,which are denoted asQijwithj∈ZN-1.Then w e define new variablesP1,P2,...,PN-1as

ThenPisatisfies the following equation:

The optimization problem(20)is equivalent to

When(A,C)is observable and the condition in(19)is satisfied, ΩKand ΩHare non-em pty and the optimization problem(25)has at least one feasible solution.The optimization problem(25)has two groups of decision variables,the intermediate matrix variables{P1,...,PN-1}and the gainsKandH.Unfortunately,the optimization problem(25)has some product term s,such asBecauseAiis com posed ofKandintroduces some product term s betweenPiandK(orH)and the optimization problem(25)falls into a class of bilinear matrix inequality(BM I)problem s[20].As we know,BM I optimization problem s are NP-hard and difficult to solve[20,21].Moreover,the non-convexity of ΩKand ΩHyields the non-convexity of the optimization problem(25).Due to such nonconvexity of the optimization problem(25),the uniqueness of its optimal solution cannot be guaranteed and its solution is further complicated.To overcome the aforementioned optimization difficulty,w e introduce an iterative method to solve the optimization problem(25)in Section 3.2.

3.2 An iterative method to solve the performance optimization problem

The procedure of our iterative method is described in Algorithm 1.It consists of four major steps,“So lve Pi under given K and H”,“compute a descent direction of(K,H)”,“perform a line search along the descent direction of(K,H)”,“Stop iterations if necessary”,which are introduced in the sequel.

Algorithm 1Framework of our iterative method:InitializeK,H;

Step 1SolvePiunder givenKandH;

Step 2Compute a descent direction of(K,H);

Step 3Perform a line search along the descent direction of(K,H);

ifstopping conditions are NOT satisfied,then

Go to Step 1;

else

ReturnK,H.

end if

3.2.1Solve Pi under given K and H

The first step is to solve the intermediate matrix variables,P1,...,PN-1,to minimizeJunder given qualifiedKandH.An initial qualifiedKcan be generated by the method in[9]while an initialHcan be easily picked due to the observability assumption of(A,C).

WhenKandHare fixed,the constraint of(25)becom es linear with respect toP1,...,PN-1and the optimization problem(25)can be solved by the following LM I with negligible error:

optimization problem(26)is a typical LM I problem and can be solved efficiently[22].For any givenK∈ΩKandH∈ ΩH,w e can surely find matrix variablesP1,...,PN-1,which will be used to compute the performance measureJand a descent direction of(K,H).

3.2.2Compute a descent direction of(K,H)

In Section3.2.1,we compute the performanceJunder the givenKandH.Actually,that performanceJis a function ofKandH.In order to improveJ,we want to find a descent direction of(K,H),which can be obtained through the following perturbation method.

We introduce perturbation intoK,HandPi,i.e.,

Under the above perturbation,

We want to find a descent direction of(K,H)to minimize ΔJ.Such minim ization must be performed without violating the constraints of(25),which are changed into

Due to(27)is equivalent to

We can find a descent direction,(ΔK,ΔH),by solving the following optimization:

subject to

The optimization(30)cannot be easily solved due to the high-order term s of the constraints.To resolve such issue,we first introduce the following constraint,

It can be show n that the above constraint does not hurt the achievability of the desired descent direction of(K,H).Now we add a non-negative term,,to the right side of(30)to yield

(32)places a stricter constraint than(30),i.e.,the satisfaction of(32)im p lies that of(30).Im p lementing the Schur com plement technique to(32)yields

where.The above equations are LM Is and can be efficiently solved.

In summ ary,a descent direction can be generated by solving the following LM I optimization through the methods in[22],

3.2.3Line search along the descent direction o f(K,H)

In Section 3.2.2,w e obtain a descent direction,(ΔK,ΔH).We can move(K,H)along this descent direction to further minimizeJ.More specifically,w e choose the following new control and observation gains,

where ? is the step size to be determined. ? can surely affect the consensus performanceJ.In order to emphasize this effect,Jis denoted asJ(?)which can be computed by solving the following LM I under a given ?,

We want to find an appropriate step size ? to improve the consensus performanceJ,i.e.,

We can borrow the line search algorithm in[16]to fulfill the task of determining a“suboptimal”?,which is given below.

Algorithm 2Framework of the line search algorithm:

Initialize ?0=0.01,?=0;

repeat

ifJ(?+ ?0)≤J(?)then

else

end if

until|?0|＜ δ?;return?

3.2.4Stopping criterion

with the computed ? by Algorithm 2,we can generate better control and observations gains,K+andH+,according to(35).withK+andH+,optimization problem(26)can be solved to yield newPi(i=1,...,N-1),with which the procedure in Sections 3.2.2 and 3.2.3 can be repeated.In a word,iterations of Section3.2.1-3.2.3 are executed to keep im provingJ.These iterations will be stopped when the following criterion is satisfied:

where ‖·‖2stands for the 2-norm of a vector and δKHis a sm all positive threshold.Besides(37),the iteration is also stopped when the number of iterations reaches a given threshold,e.g.,1000.

As mentioned before,w hen(A,C)is observable and the condition in(19)is satisfied,we can surely find qualifiedKandHas the initial solution of the optimization problem(25).Starting from this initial(K,H),the above iterative procedure is follow ed to search for“better”(K,H)in order to improve the consensus performanceJ.Due to the non-convexity of the optimization problem(25),the optimal(K,H)cannot be guaranteed to be achieved.Fortunately w e can at least ensure that the stopped(K,H)yields no worse performance than the initial(K,H),i.e.,we improve(K,H)to our best efforts,which is demonstrated by simulation results in Section 4.

4 Illustrative examples

In this section,the effectiveness and efficiency of our iterative method is verified through a third-order MAS with the following system matrices:

The variances of the process noise and observation noise areW=0.25I3andV=0.25.

We choose δ?=0.00001 and δKH=0.00001.Tw o different communication topologies in[16],including a large eigenratio one and a small eigenratio one,were simulated.

4.1 The large eigenratio case

The communication topology of the large eigenratio exam p le is illustrated in Fig.1.

Fig.1 The communication topology of a large eigenratio case.

The second sm allest eigenvalue is λ2=8 and the largest eigenvalue is λ10=10.Therefore,the eigenratio λ2/λ10is 0.8.The product of the unstable eigenvalues of the system matrixAis 1.716.An initial control gainKcan be obtained by the method in[9]while an initial observation gainHis chosen to stabilizeA-HC.Based on the initial gains,the iterations of our method were executed,which are shown in Fig.2.We see that after about 40 iterations,the improvement ofJbecomes quite small.

The initial and optimizedKandHare quantitatively com pared in Table 1.It can be seen thatJis improved by about 50%by the optimizedKandH.

The state of agenti,xi(k)is a 3-dimensional vector and can be expressed asWe takexi,2(k)as example to show the deviation of states from the average state under the optimizedKandHin Fig.3.It can be seen thatxi,2(k)reaches the desired practical consensus whenk＞10.xi,1(k)andxi,3(k)behave similarly asxi,2(k).

Fig.3 Deviation of xi,2(k)of the large eigenratio case under the optimized K and H.

4.2 The sm all eigenratio case

The sm all eigenratio topology is illustrated in Fig.4.

Fig.4 The communication topology of a small eigenratio case.

The second smallest eigenvalue is λ2=3.7466 and the largest eigenvalue is λ10=10.The initialKandHare similarly chosen as the large eigenratio case.The iterations of our method were executed,which are shown in Fig.5.After 20 iterations,we cannot obtain any significant improvem ent ofJ.

The initial and optimizedKandHare quantitatively compared in Table 2.Jis improved by about 90%with the optimizedKandH.

Similar to Fig.3,w e show the deviation of states from the average state under the optimizedKandHthrough the second com ponent ofxi(k),xi,2(k),in Fig.6.It can be seen thatxi,2(k)reaches the desired practical consensus w henk＞30.xi,1(k)andxi,3(k)behave similarly asxi,2(k).

Fig.5 The iteration procedure of our method for the small eigenratio case.

Table 2 The gain and performance comparison for the small eigenratio case.

Fig.6 Deviation of xi,2(k)of the small eigenratio case under the optimized K and H.

5 Conclusions

This paper investigates the problem of designing the control and observation gains to improve the consensus performance of output-feedback multi-agent system s.That gain design problem is formulated into a nonlinear optimization and hard to solve.We introduce an iterative method to solve that optimization.Simulation results demonstrate the effectiveness and efficiency of our method in improving the consensus performance.We,however,have to point out that our method only aim s to improve the consensus performance and cannot guarantee the optimality of the obtained control and observation gains because the original gain optimization problem isnotconvex.One of future research directions is to further investigate such optimality.

References

[1]R.O lfati-Saber,R.M.Murray.Consensus protocols for networks of dynamic agents.Proceedings of the American Controls Conference,Denver:IEEE,2003:951-956.

[2]R.O lfati-Saber,J.A.Fax,R.M.Murray.Consensus and cooperation in networked multi-agent system s.Proceedings of the IEEE,2007,95(1):215-233.

[3]W.Ren,R.W.Beard.Consensus seeking in multiagent system s under dynamically changing interaction topologies.IEEE Transactions on Automatic Contro l,2005,50(5):655-661.

[4]L.Fang,P.J.Antsaklis.information consensus of asynchronous discrete-time m ulti-agent system s.Proceedings of the Am erican Controls Conference,Portland:IEEE,2005:1883-1888.

[5]R.Olfati-Saber,R.M.Murray.Consensus problem s in networks of agents with switching topology and time-delays.IEEE Transactions on Automatic Contro l,2004,49(9):1520-1533.

[6]W.Ren,K.Moore,Y.Chen.High-order consensus algorithm s in cooperative vehicle systems.Proceedings of the IEEE International Conference on Networking,Sensing and Control,Ft Lauderdale:IEEE,2006:457-462.

[7]J.A.Fax,R.M.Murray.information flow and cooperative control of vehicle formations.IEEE Transactions on Automatic Control,2004,49(9):1465-1476.

[8]C.Ma,J.Zhang.Necessary and sufficient conditions for consensusability of linear m ulti-agent system s.IEEE Transactions on Automatic Control,2010,55(5):1263-1268.

[9]K.You,L.Xie.Network topology and communication data rate for consensusability of discrete-time multi-agent system s.IEEE Transactions on Automatic Contro l,2011,56(10):2262-2275.

[10]L.Wang,Z.Liu,L.Guo.Robust consensus of multi-agent system s with noise.Proceedings of the 26th Chinese Control Conference,Hunan:Beijing Univ.Aeronautics&Astronautics Press,2007:737-741.

[11]L.Mo,Y.Jia.H∞consensus control of a class of high-order multiagent system s.IET Control Theory And Applications,2011,5(1):247-253.

[12]Y.Yang,R.S.Blum.On the performance of broadcast based consensus under non-zero-mean stochastic disturbances.IEEE 12th International Workshop on Signal Processing Advances in Wireless communications,San Francisco:IEEE,2011:231-235.

[13]X.Dong,J.Xi,Z.Shi,et al.Practical consensus for highorder linear time-invariant swarm systems with interaction uncertainties,time-varying delays and external disturbances.International Journal of System s Science,2013,44(10):1843-1856.

[14]X.Lin,S.Boyd,S.J.Kim.Distributed average consensus with least-mean-square deviation.Journal of Parallel and Distributed computing,2005,67(1):3-46.

[15]Z.Li,Z.Duan,G.Chen.On H∞and H2performance regions of m ulti-agent systems.Automatica,2011,47(4):797-803.

[16]Q.Ling,W.Zheng,H.Lin.An iterative method for control gain design of multi-agent system s with process noise.submitted toIEEE Transactions on Control System s Technology(revised and under review,Mar.2016):http://staff.ustc.edu.cn/qling/dow nload/tcst.pd f.

[17]K.You,L.Xie.Coordination of discrete-time multi-agent system s via relative output feedback.International Journal of Robust and Non linear Control,2011,21(13):1587-1605.

[18]Z.Li,Z.Duan,G.Chen.Consensus of discrete-time linear multi-agent system s with observer-type protocols.Discrete and Continuous Dynamical System s-Series B,2011,16(2):489-505.

[19]J.W.Brewer.Kronecker products and matrix calculus in system theory.IEEE Transactions on Circuits and System s,1978,25(9):772-781.

[20]J.G.VanAntwerp,R.D.Braatz.A tutorial on linear and bilinear matrix inequalities.Journal of Process Control,2000,10(4):363-385.

[21]A.Hassibi,J.How,S.Boyd.A path-following method for solving BM I problem s in control.Proceedings of the American Controls Conference,San Diego:IEEE,1997:1385-1389.

[22]S.Boyd,L.E.Ghaoui,E.Feron,et al.Linear Matrix Inequalities in System and Contro l Theory.Philadelphia:SIAM,1997.