January2015 Control of Networked Multiagent Systems † with Uncertain Graph Topologies 5 1 0 2 n ∗ TanselYucelen andJohnDanielPeterson a J DepartmentofMechanicalandAerospaceEngineering 4 MissouriUniversityofScienceandTechnology 1 ] KevinL.Moore C DepartmentofElectricalEngineeringandComputerScience O ColoradoSchoolofMines . h t a m Abstract—Multiagentsystemsconsistofagentsthatlocallyexchangeinformationthrough [ a physical network subject to a graph topology. Current control methods for networked mul- 1 tiagentsystemsassumetheknowledgeofgraphtopologiesinordertodesigndistributedcon- v 9 trollawsforachievingdesiredglobalsystembehaviors. However,thisassumptionmaynotbe 3 4 valid for situations where graph topologies are subject to uncertaintieseither due to changes 3 in the physical network or the presence of modeling errors especially for multiagent systems 0 . involving a large number of interacting agents. Motivating from this standpoint, this paper 1 0 studiesdistributedcontrolofnetworked multiagentsystemswithuncertaingraphtopologies. 5 Theproposedframeworkinvolvesacontrollerarchitecturethathasanabilitytoadaptitsfeed- 1 : backgainsinresponsetosystemvariations.Specifically,weanalyticallyshowthattheproposed v i controllerdrivesthetrajectoriesofanetworkedmultiagentsystemsubjecttoagraphtopology X r withtime-varyinguncertaintiestoacloseneighborhoodofthetrajectoriesofagivenreference a modelhavingadesiredgraphtopology.Asaspecialcase,wealsoshowthatanetworkedmulti- agentsystemsubjecttoagraphtopologywithconstantuncertaintiesasymptoticallyconverges tothetrajectoriesofagivenreferencemodel.Althoughthemainresultofthispaperispresented in the context of average consensus problem, the proposed framework can be used for many otherproblemsrelatedtonetworkedmultiagentsystemswithuncertaingraphtopologies. Keywords — Networked multiagent systems; uncertain graph topologies; distributed con- trol;adaptivecontrol;stability † ThisresearchwassupportedinpartbytheUniversityofMissouriResearchBoard. ∗ Correspondingauthor: 400West,13thStreet,Rolla,MO65409(Address);+15733417702(Phone);+1573341 6899(Fax);[email protected](Email). 1. Introduction Multiagent systems consist of agents that locally exchange information through a physical network subject to a graph topology. Current control methods for networked multiagentsys- temsassumetheknowledgeofgraphtopologiesinordertodesigndistributedcontrollawsfor achievingdesiredglobalsystembehaviors(see,forexample,[1]andreferencestherein). How- ever,thisassumptionmaynotbevalidforsituationswheregraphtopologiesaresubjecttoun- certainties either due to changes in the physical network or the presence of modeling errors especiallyformultiagentsystemsinvolvingalargenumberofinteractingagents. Uncertainnatureofnetworkedmultiagentsystemshasreceivedaconsiderableattentionre- cently,includingnotableresults[2–10]. Forachievingdesiredmultiagentsystembehavior,[2,3] make a specific assumptionon thenetwork connectivityother thanthestandard assumption ontheconnectednessofnetworkedagents. Theauthorsof[4]excitethemultiagentsystemin ordertodetectandisolatetheuncertainagentsfromthenetworktopology. Like[2,3],acom- putationallyexpensiveandnotscalablealgorithmisproposedin[5,6]basedoninputobservers technique,wheretheeffectofuncertainagentsontheoverallmultiagentsystemperformance is quantified. An extension of this work is also given in [7] that focuses on the detection and isolationofuncertainagents.Theauthorsof[8,9]useanadaptivecontrolapproachinorderto suppresstheeffectofuncertainagentsontheoverallmultiagentsystemperformancewithout making specific assumptions on the fraction of misbehaving agents. A common similarityof theapproachesdocumentedin[2–9]isthattheymodeluncertaintiesintheagentdynamicsas additive perturbationsthat do not depend on the state of agents, where these results are not applicabletothenetworkedmultiagentsystemswithgraphtopologyuncertaintiessincesuch uncertaintiesdependonthestateofagents. Onerelevantworktotheresultsofthispaperisrecentlyappearedin[10],wheretheauthors utilizeadaptiveandslidingmodecontrolmethodologiesinordertoenforceanetworkedmul- tiagentsystemsubjecttoanuncertaingraphtopologytofollowagivenreferencemodelhaving a desired graph topology. However, the result in [10] may require a centralized information 1 exchangeamongnetworkedagentsingeneralduetothestructureoftheproposedcontrolal- gorithm (see (8) or (18) of [10]). Other important results, which are related to this paper, are presentedin[11–13]withoutrequiringacentralizedinformationexchange. However,thesere- sultsholdforgraphtopologiessubjecttoconstantuncertaintiesonly. Inthispaper,we studydistributedcontrolofnetworked multiagentsystemswithuncertain graph topologies. The proposed framework involves a novel controller architecture that has anabilitytoadaptitsfeedbackgainsinresponsetosystemvariations. Specifically,weanalyti- callyshowthattheproposedcontrollerdrivesthetrajectoriesofanetworkedmultiagentsystem subjecttoagraphtopologywithtime-varyinguncertaintiestoacloseneighborhoodofthetra- jectoriesofagivenreferencemodelhavingadesiredgraphtopology. Asaspecialcase,wealso showthatanetworkedmultiagentsystemsubjecttoagraphtopologywithconstantuncertain- tiesasymptoticallyconvergestothetrajectoriesofagivenreferencemodel. Althoughthemain result of this paper is presented in the context of average consensus problem, the proposed frameworkcanbeusedformanyotherproblemsrelatedtonetworkedmultiagentsystemswith uncertaingraphtopologies. 2. Notation,Definitions,andGraph-TheoreticNotions Thenotationusedinthispaperisfairlystandard. Specifically,Rdenotesthesetofrealnum- bers,Rndenotesthesetofn×1realcolumnvectors,Rn×m denotesthesetofn×mrealmatrices, R denotesthesetofpositiverealnumbers,Rn×n (resp.,Rn×n)denotesthesetofn×npositive- + + + definite(resp.,nonnegative-definite)realmatrices,Sn×n (resp.,Sn×n)denotesthesetofn×n + + symmetricpositive-definite(resp.,symmetricnonnegative-definite)realmatrices,0 (resp.,1 n n )denotesthen×1vectorofallzeros(resp.,ones),andI denotesthen×nidentitymatrix.Fur- n thermore,wewrite(·)T fortranspose,k·k fortheEuclidiannorm,λ (A)(resp.,λ (A))for 2 min max theminimum(resp.,maximum)eigenvalueoftheHermitianmatrixA,λ (A)forthei-theigen- i valueof A(Aissymmetricandtheeigenvaluesareorderedfromleasttogreatestvalue),diag(a) forthediagonalmatrixwiththevectora onitsdiagonal,and[A] fortheentryofthematrix A ij onthei-throwand j-thcolumn. 2 Next, we recall some of the basic notions from graph theory, where we refer to [1] for fur- therdetails. Inthemultiagentliterature,graphsarebroadlyadoptedtoencodeinteractionsin networkedsystems. AnundirectedgraphG isdefinedbyasetVG ={1,...,n}ofnodesandaset EG ⊂VG×VG of edges. If (i,j)∈EG, then thenodes i and j areneighbors and theneighboring relation is indicated with i ∼ j. The degree of a node is given by the number of its neighbors. Letting d be the degree of node i, then the degree matrix of a graph G, D(G)∈Rn×n, is given i by D(G) , diag(d), d = [d ,...,d ]T. A path i i ...i is a finite sequence of nodes such that 1 n 0 1 L i ∼i , k =1,...,L,anda graphG is connected ifthereisa pathbetweenanypairofdistinct k−1 k nodes. Theadjacency matrixofagraphG,A(G)∈Rn×n,isgivenby [A(G)] , 1, if(i,j)∈EG, ij ½ 0, otherwise. The Laplacian matrix of a graph, L(G)∈Sn×n, playing a central role in many graph theoretic + treatmentsof multiagentsystems, is given by L(G),D(G)−A(G), where thespectrumof the Laplacianofaconnected,undirectedgraphG canbeorderedas 0=λ (L(G))<λ (L(G))≤···≤λ (L(G)), (1) 1 2 n with1 astheeigenvectorcorrespondingtothezeroeigenvalueλ (L(G))andL(G)1 =0 and n 1 n n eL(G)1 =1 . n n 3. ProblemFormulation Consider a multiagent system consisting of n agents that locally exchange information ac- cording to a connected, undirected uncertain graph G with nodes and edges representing u agents and interagent information exchange links, respectively. We assume that the network isstatic,andhence,agentevolutionwillnotcauseedgestoappearordisappearinthenetwork. Specifically,letx (t)∈Rdenotethestateofnodei attimet ∈R ,whosedynamicsisdescribed i + by x˙ (t) = −α (t)x (t)+ β (t)x (t)+u (t), x (0)=x , (2) i i i ij j i i i0 iX∼j 3 (a) (b) 1.1 1.1 1 1 0.9 0.9 ts0.8 ts0.8 n n e0.7 e0.7 g g A0.6 A0.6 0.5 0.5 0.4 0.4 0.3 0.3 0 1 2 3 4 5 6 0 1 2 3 4 5 6 Time (sec) Time (sec) (c) (d) 2 1 1.8 0.8 1.6 s 0.6 s1.4 t t en 0.4 en1.2 Ag 0.2 Ag 1 0.8 0 0.6 −0.2 0.4 −0.4 0 1 2 3 4 5 6 0 1 2 3 4 5 6 Time (sec) Time (sec) Figure1:Trajectoriesofthreeagentsonalinegraphsubjecttoinitialconditions(x ,x ,x = 10 20 30 (0.2,0.4,1.2) for (a) (α ,α ,α ) = (1,2,1) and (β ,β ,β ,β ) = (1,1,1,1), (b) 1 2 3 12 21 23 32 (α ,α ,α ) = (1,1.1,1) and (β ,β ,β ,β ) = (1,0.1,1,1), (c) (α ,α ,α ) = 1 2 3 12 21 23 32 1 2 3 (1,2,1) and (β ,β ,β ,β ) = (−1,−1,1,1), and (d) (α ,α ,α ) = (1,1.5,1) and 12 21 23 32 1 2 3 (β ,β ,β ,β )=(1,1,1,1). 12 21 23 32 whereα (t)∈Randβ (t)∈RareunknownboundedcoefficientsofthegraphG withbounded i ij u timederivatives,andu (t)∈R,t ∈R ,isthecontrolinputofnodei. Inthispaper,weareinter- i + estedtodesignadistributedcontrolinputu (t),t ∈R ,suchthat(2)achievesaverageconsen- i + susapproximately(orasymptotically,i.e.,x(t)→(1 1T/n)x ast →∞,x(t)=[x (t),...,x (t)]T∈ n n 0 1 n Rn)inthepresenceofanuncertaingraphtopology. Remark1. In the absence of proper control inputs u (t)∈R, t ∈R , (2) cannot necessarily i + achieveaverageconsensus.Toelucidatethispoint,letunknowncoefficientsofthegraphG be u constant,i.e.,(α (t),β (t))=(α ,β ),andconsiderfourcasesgiveninFigure1thatshowtra- i ij i ij jectoriesofthreeagentsonalinegraphsubjecttoinitialconditions(x ,x ,x )=(0.2,0.4,1.2). 10 20 30 Since α = β and β = β in case (a), this case results in average consensus at point i i∼j ij ij ji P (1 1T/n)x =0.6. Sinceβ 6=β incase(b),thiscasedoesnotresultinaverageconsensusat n n 0 12 21 point0.6.Case(c)considersamultiagentsystemwithantagonisticinteractions[14],andhence, 4 itdoesnotresultinaverageconsensusduetotheexistenceofmultipleequilibriumpoints. Fi- nally, since α 6= β for i = 2 in case (d), this case does not result in average consensus i i∼j ij P as well. In summary, (2) results in average consensus if αi = i∼jβij and βij =βji ∈R+ [15]. P However,thiscannotbejustifiedduetounknowncoefficientsofthegraphG ,andhence,one u needstodesignpropercontrolinputsu (t)∈R,t ∈R . i + Next, we propose a control input u (t)∈R, t ∈R , to drive the trajectories of (2) to a close i + neighborhood of a given reference model having a desired graph topology without requiring a centralized informationexchange among networked agents. For this purpose, consider the referencemodelthatlocallyexchangeinformationaccordingtoaconnected,undirectedgraph G givenby r˙ (t) = − r (t)−r (t) , r (0)=x , (3) i i j i i0 iX∼j¡ ¢ wherer (t)∈R,t ∈R ,denotesthestateofthereferencemodelfornodei. Notethat i + lim r(t)=(1 1T/n)x , (4) n n 0 t→∞ wherer(t)=[r (t),...,r (t)]T∈Rn.Throughoutthispaperweassumethatthenodesandedges 1 n ofgraphsG andG coincide,howeverthegraphG issubjecttounknowncoefficientsα (t)and u u i β (t),asdiscussedearlier. ij Remark2. Thereferencemodelgivenby(3)canbeeasilyextendedto r˙ (t) = − ξ r (t)−r (t) , r (0)=x , (5) i ij i j i i0 iX∼j ¡ ¢ withoutchangingthefollowingresultsofthispaper,whereξii = i∼jξij andξij =ξji ∈R+. P Remark3. Notethat(3)canbeequivalentlywrittenas r˙ (t) = −d r (t)+ r (t), r (0)=x , (6) i i i j i i0 iX∼j whered isthedegreeofnodei ongraphG. Therefore,ifoneknowsthecoefficientsα (t)and i i β (t)of2,thenthecontrolinput ij u (t) = − d −α (t) x (t)+ 1−β (t) x (t), (7) i i i i ij j ¡ ¢ iX∼j¡ ¢ 5 resultsinaverageconsensusatpoint(1 1T/n)x . n n 0 Sincethecontrolinput(7)giveninRemark3isnotfeasibleduetounknowncoefficientsα (t) i andβ (t),weproposetheadaptivecontrolinputgivenby ij u (t) = −k x (t)−r (t) −wˆ (t)x (t)− wˆ (t)x (t), (8) i i i i i i ij j ¡ ¢ iX∼j where k ∈R for at leastone agentor a subsetof agents(and k =0 for others), and theesti- i + i mateswˆ (t)∈Randwˆ (t)∈R,t ∈R ,satisfytheupdatelaws i ij + w˙ˆ (t) = γ Proj wˆ (t), x (t) x (t)−r (t) , wˆ (0)=wˆ , (9) i i i i i i i i0 ³ ´ ¡ ¢ w˙ˆ (t) = γ Proj wˆ (t), x (t) x (t)−r (t) , wˆ (0)=wˆ , (10) ij ij ij j i i ij ij0 ³ ´ ¡ ¢ withγi ∈R+andγij ∈R+beingthecorrespondinglearningrates.Intheupdatelawsgivenby(9) and(10),Projdenotestheprojectionoperator[16,17],whichisusedtokeeptheestimateswˆ (t) i and wˆ (t)boundedfor all t ∈R . In thenextsection,we analyticallyshowthattheproposed ij + adaptivecontrolinputgivenby(8)alongwiththeupdatelaws(9)and(10)drivesthetrajectories of(2)toacloseneighborhoodofthereferencemodeltrajectoriesgivenby(5). 4. StabilityAnalysis Inthissection,weestablishstabilitypropertiesoftheproposedadaptivecontrolinputgiven by(8)alongwiththeupdatelaws(9)and(10). Forthispurpose,let e (t),x (t)−r (t), t ∈R , (11) i i i + denotethelocalerrordynamicsthatsatisfy e˙ (t) = −α (t)x (t)+ β (t)x (t)+u (t)+d r (t)− r (t) i i i ij j i i i j iX∼j iX∼j = −α (t)x (t)+ β (t)x (t)+u (t)+d r (t)− r (t)+d x (t) i i ij j i i i j i i iX∼j iX∼j −d x (t)+ x (t)− x (t) i i j j iX∼j iX∼j = −d e (t)+ e (t)+ d −α (t) x (t)+ β (t)−1 x (t)+u (t) i i j i i i ij j i iX∼j ¡ ¢ iX∼j¡ ¢ 6 = − e (t)−e (t) +w (t)x (t)+ w (t)x (t)+u (t) i j i i ij j i iX∼j¡ ¢ iX∼j = − e (t)−e (t) +w (t)x (t)+ w (t)x (t)−k e (t) i j i i ij j i i iX∼j¡ ¢ iX∼j −wˆ (t)x (t)− wˆ (t)x (t) i i ij j iX∼j = −k e (t)− e (t)−e (t) −w˜ (t)x (t)− w˜ (t)x (t), e (0)=0, (12) i i i j i i ij j i iX∼j¡ ¢ iX∼j where w˜ (t) , wˆ (t)−w (t), t ∈R , (13) i i i + w˜ (t) , wˆ (t)−w (t), t ∈R , (14) ij ij ij + wi(t),di−αi(t),t ∈R+,andwij(t),βij(t)−1,t ∈R+. Inaddition,itfollowsfrom(9)and(10) that w˙˜ (t) = γ Proj wˆ (t), x (t) x (t)−r (t) −w˙ (t), w˜ (0)=w˜ , (15) i i i i i i i i i0 ³ ´ ¡ ¢ w˙˜ (t) = γ Proj wˆ (t), x (t) x (t)−r (t) −w˙ (t), w˜ (0)=w˜ , (16) ij ij ij j i i ij ij ij0 ³ ´ ¡ ¢ where w˜ ,wˆ −w and w˜ ,wˆ −w . Note that w˙ (t)and w˙ (t) areboundedsinceit i0 i0 i ij0 ij0 ij i ij isassumedthatunknownboundedcoefficientsα (t)andβ (t)haveboundedtimederivates. i ij Wenowstatethefollowinglemmanecessaryfortheresultsofthissection. Lemma1. Let K =diag(k), k =[k ,k ,...,k ]T, k ∈R , i =1,...,n, andassumethatatleast 1 2 n i + oneelementofk isnonzero. Then,fortheLaplacianofaconnected,undirectedgraph, F(G),L(G)+K ∈Sn×n, (17) + anddet(F(G))6=0. Proof. Consider the decomposition K =K +K , where K ,diag([0,...,0,φ ,0,...,0]T) and 1 2 1 i K ,K −K , where φ denotes the smallest nonzero diagonal element of K appearing on its 2 1 i i-thdiagonal,sothatK ∈Sn×n. FromtheRayleigh’sQuotient[18],theminimumeigenvalueof 2 + L(G)+K canbegivenby 1 λ (L(G)+K )=min{xT L(G)+K x|xTx=1}, (18) min 1 1 x ¡ ¢ 7 where x istheeigenvectorcorrespondingtothisminimumeigenvalue. NotethatsinceL(G)∈ Sn×n andK ∈Sn×n, andhence, L(G)+K isrealandsymmetric, x isarealeigenvector. Now, + 1 + 1 expanding(18)as xT(L(G)+K )x = (x −x )2+φ x2, (19) 1 i j i i iX∼j andnotingthattherighthandsideof(19)iszeroonlyifx≡0,itfollowsthatλ (L(G)+K )>0, min 1 and hence, L(G)+K ∈Sn×n. Finally, let λ be an eigenvalue of F(G)= L(G)+K +K . Since 1 + 1 2 λ (L(G)+K )>0 and λ (K )=0, it follows from Fact 5.11.3of [19] thatλ (L(G)+K )+ min 1 min 2 min 1 λ (K )≤λ,andhence,λ>0,whichimpliesthat(17)holdsanddet(F(G))6=0. (cid:4) min 2 Thenexttheorempresentsthefirstresultofthissection. Theorem1. Considerthenetworkedmultiagentsystemgivenby(2)subjecttoanuncertain graph topology, thereference modelgiven by (3), theadaptivecontrol inputgiven by(8), and theupdatelawsgivenby(9)and(10). Then,thesolution e (t),w˜ (t),w˜ (t) oftheclosed-loop i i ij ¡ ¢ dynamicalsystemgivenby(12),(15),and(16)isboundedforall 0,w˜ ,w˜ ,t ∈R ,and(i,j). i0 ij0 + ¡ ¢ Proof. Firstconsiderthequadraticfunctiongivenby 1 V (e ,w˜ ,w˜ ) = e2+γ−1w˜2+ γ−1w˜2 , (20) i i i ij 2³ i i i iX∼j ij ij´ and notethatV (0,0,0)=0 andV (e ,w˜ ,w˜ )∈R , (e ,w˜ ,w˜ )6=(0,0,0). Furthermore,V (e , i i i i ij + i i ij i i w˜ ,w˜ ) is radially unbounded. Differentiating (20) along the closed-loop trajectories of (12), i ij (15),and(16)yields V˙ e (t),w˜ (t),w˜ (t) ≤ −e (t) e (t)−e (t) −k e2(t)+w∗, (21) i i i ij i i j i i i ¡ ¢ iX∼j¡ ¢ where w∗ is an upper bound satisfying γ−1 wˆ (t)−w (t) w˙ (t)+ γ−1 wˆ (t)−w (t) i i i i i i∼j ij ij ij ¯¯ ¡ ¢ P ¡ ¢ ·w˙ (t) ≤ w∗, t ∈ R . Note that w∗ exi¯s¯ts since all the terms inside the norm operator are ij 2 i + i ¯¯ ¯¯ boundedandprojectionoperatorisusedfortheestimateswˆ (t)andwˆ (t). Now,considerthe i ij Lyapunovfunctioncandidategivenby n V(·) = V (e ,w˜ ,w˜ ). (22) i i i ij iX=1 8 Thetimederivativeof(22)isgivenusing(21)as n V˙(·) ≤ −eT(t) L(G)+K e(t)+w∗, w∗, w∗, (23) i ¡ ¢ iX=1 where L(G) denotes theLaplacian matrixof (3), K ,diag(k), k =[k ,k ,...,k ]T, k ∈R , and 1 2 n i + e(t) = [e (t),...,e (t)]T. From the definition of the adaptive control input in (8), notice that 1 n at least one element of k is nonzero. This implies from Lemma 1 that L(G)+K ∈ Sn×n and + det(L(G)+K)6=0,andhence,λ L(G)+K ke(t)k ≤eT(t) L(G)+K e(t). Now, sinceV˙(·)≤0 min 2 ¡ ¢ ¡ ¢ when ke(t)k ≥w∗/λ L(G)+K , itfollows thattheclosed-loop dynamicalsystem givenby 2 min ¡ ¢ (12),(15),and(16)isboundedforall 0,w˜ ,w˜ ,t ∈R ,and(i,j). (cid:4) i0 ij0 + ¡ ¢ Remark4. In order to drivethe trajectories of (2) to a close neighborhoodof the reference ∗ modeltrajectoriesgivenby(5),theperturbationtermw in(25)needstobesmall. Thisholds ifthetimederivativeofunknowncoefficients α (t)andβ (t)issmall. Ifthisisnottrue,then i ij ∗ onecanincreasethelearningratesγ andγ tomakew small. i ij As a special case when theunknown coefficients are constant, i.e., (α (t),β (t))=(α ,β ), i ij i ij the next theorem shows that the proposed adaptive control input given by (8) along with the updatelaws(9)and(10)asymptoticallydrivesthetrajectoriesof(2)tothereferencemodeltra- jectoriesgivenby(5). Theorem2. Considerthenetworkedmultiagentsystemgivenby(2)subjecttoanuncertain graph topology, thereference modelgiven by (3), theadaptivecontrol inputgiven by(8), and theupdatelawsgivenby(9)and(10). Then,thesolution e (t),w˜ (t),w˜ (t) oftheclosed-loop i i ij ¡ ¢ dynamical system given by (12), (15), and (16) is Lyapunov stable for all 0,w˜ ,w˜ , t ∈R , i0 ij0 + ¡ ¢ and(i,j),andlim e (t)=0foralli. Inaddition,lim x(t)=(1 1T/n)x . t→∞ i t→∞ n n 0 Proof. To show the Lyapunov stability of the closed-loop dynamical system given by (12), (15),and(16),firstconsiderthequadraticfunctiongivenby(20). Differentiating(20)alongthe closed-looptrajectoriesof(12),(15),and(16)yields V˙ e (t),w˜ (t),w˜ (t) ≤ −e (t) e (t)−e (t) −k e2(t). (24) i i i ij i i j i i ¡ ¢ iX∼j¡ ¢ Now,considertheLyapunovfunctioncandidategivenby(22),wherethetimederivativeof(22) 9