EdgeAgreementofMulti-agentSystemwithQuantizedMeasurementsviaDirectedEdge

Laplacian

arXiv:1501.06678v1 [cs.SY] 27 Jan 2015ZhiwenZenga,XiangkeWanga,ZhiqiangZhenga,aCollegeofMechatronicsandAutomation,NationalUniversityofDefenseTechnology,410073,China

1Introduction

Thegraphtheorycontributessigni?cantlyintheanalysisandsynthesisofmulti-agentsystems,sinceitprovidesnaturalabstractionsforhowinforma-tionissharedbetweenagentsinanetwork.Specially,thespectralpropertiesofthegraphLaplacianareextensivelyexploredrecentlytoprovideconvergenceanalysisinthecontextofmulti-agentcoordinationbehaviour[1][2].Despitetheunquestionableinterestoftheresultsconcerningtheconvergenceproper-tiesintheseliteratures,wealsonotethat,anotherinterestingtopicwithre-gardtohowcertainsubgraphs,suchasspanningtreesandcycles,contributetotheanalysisofmulti-agentsystems,hasariseninmorerecently.Anim-portantthemeinthisdirectionistoobtaintheexplicitconnectionsbetweenthetopologystructureandthecontrolsystem.Consideringthis,anattractivenotionabouttheedgeagreementdeservespecialattention,inwhichtheedgeLaplacianplaysanimportantrole.Pioneeringresearchesonedgeagreementunderundirectedgraphnotonlyprovidetotallynewinsightsthathowthespanningtreesandcyclese?ecttheperformanceoftheagreementprotocol,butalsosetupanovelsystematicframeworkforanalysingmulti-agentsys-temsfromtheedgeperspective[3][4][5].Theedgeagreementin[3]providesatheoreticanalysisofthesystem’sperformanceusingbothH2andH∞norms,andtheseresultshavebeenappliedinrelativesensingnetworksreferringto

[4].Moreover,basedonthealgebraicpropertiesoftheedgeLaplacian,[5]examineshowcyclesimpacttheH2performanceandproposedanoptimalstrategyforthedesignofconsensusnetworks.AlthoughtheedgeLaplaciano?ersmoretransparentunderstandingofthegraphstructure,itstillremainsanundirectednotioninaforementionedliteratures.Morerecently,theedgeLaplacianisusedtoexaminethemodelreductionofnetworkedsystemas-sociatedwithdirectedtreesthroughclusteringin[6];howeveritcannotbedirectlyextendedtomoregeneraldirectedgraphsyet.

Constraintsoncommunicationhaveaconsiderableimpactontheperformanceofmulti-agentsystem.Tocopewiththelimitationsofthe?nitebandwidthchannels,measurementsarealwaysprocessedbyquantizers.Duetothefactthatquantizationintroducesstrongnonlinearcharacteristicssuchasdiscon-tinuityandsaturationtothesystem,theresearchofthecoordinationbe-haviourofmulti-agentsysteminthepresenceofquantizedmeasurementsisstillquitechallenging.Recently,thegossipingalgorithms[7][8]aswellasthecoding/decodingschemes[9][10][11]havebeenproposedtosolvethequan-tizedconsensusproblem,wheretheconvergencetimeisthemainresearchfocus.Whilethesemethodsaremainlydevisedfordiscrete-timesystems,thecontinuous-timesystemshasalsoattractedmuchattention.Thespectralprop-ertiesoftheincidencematrixisusedtoanalyzetheconvergencepropertiesofmulti-agentsystemunderquantizedcommunicationin[12].Besides,thesample-databasedcontrol[13]andnonsmoothanalysis[14]arealsoemployed

2

totacklethequantizedmeasurements.However,onlythe?rstorderdynamicshasbeenconsideredintheaboveapproaches.Asknownthat,multi-agentsys-temwithsecond-orderdynamicscanhavesigni?cantlydi?erentcoordinationbehaviourevenwhenagentsarecoupledthroughsimilartopologycondition[15].Uptodate,tothebestofauthors’knowledge,therearestilllittleworksexplorethequantizatione?ectsonsecond-orderdynamics.[15]studiestheef-fectsofdi?erentquantizersonthesynchronizationbehaviourofmobileagentswithsecond-orderdynamics.In[16],thecollectivecoordinationofsecond-orderpassivenonlinearsystemsunderquantizedmeasurementsareconsidered.Byusingnonsmoothanalysis,someconvergenceresultsunderquantizationconstraintsarederivedforsecond-orderdynamicssystemin[17].However,theseworksrequirethatthenetworktopologiesareundirected.Tomorere-centliterature[18],theauthorsaddressthequantizedconsensusproblemofsecond-ordermulti-agentsystemsviasampleddataunderdirectedtopology.Consideringthedrawbacksofthesampleddataapproachmentionedin[16],theresearchonthequantizatione?ectsonsecond-ordermulti-agentunderdirectedtopologyisstillverychallenging.

Whiletheanalysisofthenodeagreement(consensusproblem)hasmatured,workrelatedtotheedgeagreementhasnotbeendeeplystudied.Notethatthequantizedmeasurementsbringenormouschallengestotheanalysisofthesynchronizationbehaviourofthesecond-ordermulti-agentsystem,sointhispaper,wearegoingtoexploremoredetailsaboutthistermcombiningtheedgeagreement.Themaincontributionscontainthreefolders.First,weextendourpreliminarywork[19]totheweighteddirectededgeLaplacianandfurtherex-plorethealgebraicpropertiesforanalysingtheinteractingmulti-agentsystem.Sinceitsundirectedcounterparthasshowngreatpotentialforexploringthesystemperformancein[3][20],webelievethatthenovelgraph-theoretictooldeservesmoreattention.Second,undertheedgeagreementframework,theclosed-loopmulti-agentsystemcanbetransformedintoanoutputfeedbackinterconnectionstructure.Correspondingly,basedontheobservationthattheco-spanningtreesubsystemcanbeservedasaninternalfeedback,amodelreductionrepresentationcanbederived,whichallowsaconvenientanalysis.Third,basedonthereducededgeagreementmodel,weproposeageneralanal-ysisoftheconvergencepropertiesforsecond-ordernonlinearmulti-agentsys-temunderquantizedmeasurements.Particularly,fortheuniformquantizers,weprovidetheexplicitupperboundoftheradiusoftheagreementneighbor-hoodandalsoindicatethattheradiusincreaseswiththequantizationinterval.Whileforthelogarithmicquantizers,theagentsconvergeexponentiallytothedesiredagreementequilibrium.Additionally,wealsoprovidetheestimatesoftheconvergencerateaswellasindicatethatthecoarserthequantizeris,theslowertheconvergencespeed.

Therestofthepaperisorganizedasfollows:preliminariesandproblemfor-mulationareproposedinSection2.ThedirectededgeLaplacianwithits

3

algebraicpropertiesareelaboratedinSection3aswellastheedgeagreementmechanism.Thequantizededgeagreementproblemwithsecond-ordernon-lineardynamicsunderdirectedgraphisstudiedinSection4.ThesimulationresultsareprovidedinSection5whilethelastsectiondrawstheconclusions.2BasicNotionsandPreliminaryResults

Inthissection,somebasicnotionsingraphtheoryandpreliminaryresultsaboutthesynchronizationofmulti-agentsystemunderquantizedinformationarebrie?yintroduced.

2.1GraphandMatrix

Inthispaper,weuse|·|and??·??todenotetheEuclideannormand2-normforvectorsandmatricesrespectively.ThenullspaceofmatrixAisdenotedbyN(A).DenotebyIntheidentitymatrixandby0nthezeromatrixinRn×n.Let0bethecolumnvectorwithallzeroentries.LetG=(V,E)beadirectedgraphoforderNspeci?edbyanodesetVandanedgesetE?V×VwithsizeL.Foraspeci?cedgeek=(j,i),letv?(ek)denotesitsinitialnodejandv⊙(ek)theterminalnodei.ThesetofneighboursofnodeiisdenotedbyNi={j:ek=(j,i)∈E}.WeuseA(G)torepresentaweightedadjacencymatrix,wheretheadjacencyelementsassociatedwiththeedgesarepositive,i.e.,ek=(j,i)∈E?aij>0,otherwise,aij=0.DenotebyW(G)theL×Ldiagonalmatrixofwk,fork=1,2···,L,wherewk=aijforek=(j,i)∈E.ThenotationD(G)representsadiagonalmatrixwith?i(G)denotingthein-degreeofnodeionthediagonal.ThecorrespondinggraphLaplacianofGisde?nedasLn(G):=D(G)?A(G),whoseeigenvalueswillbeorderedanddenotedas0=λ1≤λ2≤···≤λN.TheincidencematrixE(G)∈RN×Lforadirectedgraphisa{0,±1}-matrixwithrowsandcolumnsindexedbynodesandedgesofGrespectively,suchthatforedgeek=(j,i)∈E,[E(G)]jk=+1,

[E(G)]ik=?1and[E(G)]lk=0forl=i,j.Thede?nitionimpliesthateachcolumnofEcontainsexactlytwononzeroentriesindicatingtheinitialnodeandtheterminalnoderespectively.WeillustrateFigure1asanexample.AdirectedpathindirectedgraphGisasequenceofdirectededgesandadirectedtreeisadirectedgraphinwhich,fortherootiandanyothernodej,thereisexactlyonedirectedpathfromitoj.AspanningtreeGT=(V,E1)ofadirectedgraphG=(V,E)isadirectedtreeformedbygraphedgesthatconnectallthenodesofthegraph;aco-spanningtreeGC=(V,E?E1)ofGTisthesubgraphofGhavingalltheverticesofGandexactlythoseedgesofGthatarenotinGT.GraphGiscalledstronglyconnectedifandonlyifanytwo

4

?=?

??

Fig.1.Theincidencematrixofasimpledirectedgraph.

distinctnodescanbeconnectedviaadirectedpath;quasi-stronglyconnectedifandonlyifithasadirectedspanningtree[21].Aquasi-stronglyconnecteddirectedgraphGcanberewrittenasaunionform:G=GT∪GC.Inaddition,