An Application of Cooperative Game Theory to Distributed Control

AnapplicationofCooperativeGame TheorytoDistributedControl⋆ J.M.Maestre∗D.Mu˜nozdelaPe˜na∗A.Jim´enezLosada∗∗ E.AlgabaDur´an∗∗ E.F.Camacho∗ ∗Dep.ofSystemsandAutomationEngineering,UniversityofSeville, Spain(e-mail:{pepemaestre,davidmps,eduardo}@cartuja.us.es). ∗∗ Dep.ofAppliedMathII,UniversityofSeville,Spain(e-mail: [email protected],[email protected]) Abstract:Inthis paperweproposetostudytheunderlyingpropertiesofa given distributed controlschemein whichasetofagents switch between differentcommunicationstrategiesthat definewhich networklinksareusedin ordertoregulatetotheorigin asetofunconstrained linearsystems.Theproblemsofhowtodecidethetime-varyingcommunicationstrategy,share thebenefits/costsand detectwhicharethemostcriticallinksin thenetworkaresolved using tools fromgametheory.Theproposedschemeis demonstratedthroughasimulationexample. 1.INTRODUCTION Overthelastfewyearstherehasbeena growinginterestof the controlcommunityin theresearchofdistributedcontrolsystems.Thebasic ideais todividetheoverall system intoseveralsmallersubsystems,eachcontrolled byadifferentlocalcontrolleroragentwhichmayormaynotshare informationwiththerest.Examplesofthesesituationsare largescale systemsornetworkedsystems suchastraffic, waterorpowernetworks;see R.R.Negenbornand Hellendoorn.[2006]. Inaddition,theproliferationofwireless actuator/sensordevicesand their applicationtoenhance thepossibilitiesofadvancedcontrolsystemsalsobringnew challenges;see Neumann [2007]. Issues suchasthe communicationalburdenofthedifferentdistributedarchitectures playaveryimportantrole.Forexample,thebatterylife ofmotesdepend specially onthetimetheradio is onand thenumberofmessages sent.Althoughthereareworks in theliteraturethatdealwiththedynamicsinduced by the communication network(suchastime-varyingdelays and datalosses)(see forexample deWit [2006]) orthe specificdistributedcontrolalgorithmimplemented bythe localcontrollers(see forexample R.R.Negenbornand Hellendoorn.[2006]orVenkat[2006]),in general, there arefewresultsthatdealwiththeunderlyingpropertiesof a given distributedcontrolarchitecture.Moreover,these propertiesmaybedynamicaland distributedcontrolpolicies should beflexible enoughto adapt tothepossible changes. Decentralizedand distributedcontrolschemesoftenassumethat the centralizedsystemis partitionedinto a fixedsetofneighborhoodsInAlessio and Bemporad[2007] adecentralizedamodelpredictive controlschemeand a sufficientcriterionforanalyzing a posterioritheasymptotic stabilityofthe correspondingclosed-loopsystemwere presented.This workis enhanced byAlessio and Bemporad[2008]totakeinto accountpossible datalosses.Liu ⋆FinacialsupportfromtheEuropeanCommission,INFSOICT- 223866, isgratefullyacknowledged. etal. [2008]proposedadecentralizedcontrolarchitecture fornonlinearsystemswithcontinuousand asynchronous measurements.Magniand Scattolini[2006]proposesa predictive controllerunderthemain assumptionsthat the systemis nonlinear,discrete-timeand noinformationis exchanged betweenlocalcontrollers.Thestabilityofthis class ofsystemswas studied byRaimondoetal. [2007]. Ingeneral, the compositionoftheseneighborhoodsis assumedstatic,thatis,thepossibilityoftimevarying neighborhoodsis notconsidered.Inaddition,thereare otherinterestingquestionsthatarenotaddressedsuch aswhichelementsofa given distributedcontrolsystem aremore critical. Motivated bytheseissues,in this paper westudytheunderlyingpropertiesofa given distributed controlschemeusingtools fromgametheory.Froma mathematicalpointofview,gametheoryis anappropriate frameworktostudyall thephenomenathatarisefromthe mutualinteractionofagentsthat taketheir decisionsalone orin cooperation;see Myerson[1997]. Actually,important gametheoryconcepts suchasPareto optimalityand Nash equilibriumhavebeen usedtostudythepropertiesof controlschemes,see forinstance theworkbyVenkatetal. [2005]orbyMaestre etal. [2010]. Inthis paperweuse tools fromcoalitionalgametheorySaadetal. [2009], a branchofgametheorywhichstudiestherole played by communication networksin situationsofconflict. In particular,wefocusonthefollowingthree different problems: •Givenacommunication network,do all thelinkshave tobe enabledall thetime? •Do all thelinksand theagentshavethesamerelevance in anetworkedcontrolsystem? •Whenseveralagentscooperatetoreachacertain objective,dotheyhavetoshare equally the costsor benefitsofthe cooperation? Proceedings of the 18th World Congress The International Federation of Automatic Control Milano (Italy) August 28 - September 2, 2011 978-3-902661-93-7/11/$20.00 © 2011 IFAC 9121 10.3182/20110828-6-IT-1002.00682 2.PROBLEMFORMULATION Inthis paperwe considerdiscretetimelinearsystemsthat can bepartitionedin Nsubsystemswhosedynamicsare given bythefollowingmodel: xi(t+1)=Aiixi(t)+Biiui(t)+di(t), di(t)=X j6=i Aijxj(t)+X j6=i Bijuj(t),(1) wherexi∈R(qi)1and ui∈R(ri)withi=1,...,Nare thestatesand inputsofeachsubsystemrespectively.The variable diis theinfluence oftheneighbors’statesand inputsin theupdateofxi. Eachsubsystemis controlled byadifferentagent thathas access only toits statexiand decidesateachsample timethevalueofitscorrespondinginputui.Inaddition, theagentscancommunicatethroughanetworkwhichis definedasa graph (N,L),whereLis thesetofedges L⊆LN={{i,j}|{i,j}⊆N,i6=j}which definethe available communicationlinksbetweentheagents.Note thatunderthis definitionijand jirepresent thesamelink. Inthis paperweassumethat thenecessaryand sufficient conditionforanytwo agentstocommunicateis that they areatleastindirectly connected bythenetwork,thatis, there existsapathofactivelinksthatconnect them. Additionally,wewill assumethat the communication has acost.In particular,we considerthateachlinkhasafixed costc>0 associatedtoitsuse. The controlobjectiveis toregulatethestateofall the subsystemstotheorigin while minimizing a cost that dependsonthestateand input trajectoriesand the communications.Thestage costofeachagentis defined asfollows ℓi(t)=xT i(t)Qixi(t)+uT i(t)Riui(t), whereQi∈R(qi×qi)and Ri∈R(ri×ri)are constant weightingmatrices. The communicationalcostsdepend onthenumberof linksthatarebeingused.Givenanetwork(N,L),not all thelinksLhavetobeusedall thetime.Wedefine anetworkmodeasasubsetoflinksAin L,composed only bythoselinkswhichare enabled.Anylinkl/∈A is consideredtobedisabledand,thus,absent.Inthe followingsection,wepresentadistributedcontrolscheme thatdecideswhich networkmodeAhastobeactivebased onananalysis ofthetrade-offbetweencontrolperformance and communicationalcosts 3.DISTRIBUTEDCONTROLALGORITHM Inthis sectionwepresentadistributedcontrolscheme thatateachsamplingtime,implementsacertain communicationstrategydefined byanetworkmodeA.The communicationstrategyAis choseneveryDsample times. Tothis end,theagentsmustbroadcast their stateand take adecisionabout the communicationstrategythatwill be usedin thenextDtimesteps.This leadsto a double sample rate controlsystem.Asaresult ofthis policy,the agentsareseparatedintoseparatedgroupsCthatareable tocommunicatedefinedascommunicationcomponents. 1Withalittleabuseofnotation,wewill usethenotationR(n) to denoteRn. Wewill denotebyN/Athesetofall communication componentsin whichthesetNis partitioned.Notethat S ∀i∈N/A Ci=Nand CiTCj=0forall i6=j. Weassumethatateachsamplingtime eachcommunicationcomponentC⊆N/Aimplementsalinearcontroller basedonall theavailable stateinformation uC=KA CxC, whereuC∈R(Pi∈Cri)is theinputofa givencommunicationcomponentdefinedasuC={ui}i∈C,xC∈ R(Pi∈Cqi)is thethestateofa givencommunication componentdefinedasxC={xi}i∈Cand KA Cis thematrix which definesthe controllerimplemented bythe communicationcomponentCforthenetworkmodeA.Notethat wehavedroppedthetimedependence ofuCand xCin ordertosimplifythenotation. ThesetofthematricesKA Cdefineacentralizedlinear controllerfortheglobalsystem.This controlleris characterized bytheabsence ofcommunication betweenagents thatbelongtodifferentcommunicationcomponents.Thus, the equivalentcentralizedcontrollawis given by u=KAx, whereu∈R(Pi∈Nri)is theinputofthe centralized systemdefinedasu={ui}i∈N,x∈R(Pi∈Nqi)is thethe stateofthe centralizedsystemdefinedasx={xi}i∈Nand KAis thematrix which definesthe centralizedcontroller implementedforthenetworkmodeA. Weassumethat there existsaquadratic functionthat satisfies xTPAx≥X j∈NX k=0,..,∞ ℓj(k),(2) thatis,PAis aweightmatrix thatprovidesan upper bound ofthe cost toinfinityofthe centralizedsystemin closed-loopwiththe controlleru=KAxstartingfromthe initialstatex(0)=x.The calculation details ofthematrix PAis presentedin section5. Once thesetsofmatricesPAand KAaredefined,the functionr(A,x)is definedasfollows: r(A,x)=xTPAx+c|L(A)|,∀A⊆L,(3) where|L(A)|standsforthenumberofactivelinksin thenetworkmodeA.This functionassignsavalueto eachcommunicationmodeAbasedontheupperbound ofthe cost-to-go ofall the communicationcomponentsin thenetworkand the correspondingcommunicationcosts. Thedecisionaboutwhatcommunicationstrategyshould beused duringthenextDsamplesis mademinimizing r(A,x)overA. Algorithm1.Ateachsample time,theproposed distributedcontrolschemeis implementedasfollows: (1)Ifthesample timeis amultiple ofD,all theagents broadcast their stateand calculatewhichis thenetworkmodeAthatminimizesthefunctionr(A,x). Otherwise,eachagentsendshis stateonly tothose agentsthatbelongtohis communicationcomponent. (2)Eachagentusesthestateinformationreceivedin ordertoupdateitscontrolaction usingitscorrespondingcommunicationcomponentfeedbackmatrix KC A.Globally,this impliesthat thelinearcontroller u=KAxis applied. 18th IFAC World Congress (IFAC'11) Milano (Italy) August 28 - September 2, 2011 9122 Remark:Thematrix KAtakesinto account the communicationsconstraintsin A.Forexample,if thei-th elementofuand thej-thelementofxbelongtodifferent communicationcomponents,thenKA(i,j)=0;thatis, thei-thinputdoesnotdepend onthej-thstate.Forthe particularcasein whicheachcommunicationcomponent is composed bysystemswithconsecutivenumerationin thesetN,thenKA=diag(KA C1,KA C2,...). Remark:All thematricesKA Chavetobedesignedsothat KAguaranteesclosed-loopstabilityforthe centralized system.Ifa givenmodeis notable tostabilizethesystem, thenit is not takeninto account. Remark:Theon-lineimplementationofthealgorithm may besimplified bylimitingthepossible networkmodesA thatare considered,forexample assumingthateveryD samplingtimesonly onlinkcan beactivatedordeactivated. 4.AN ANALYSISOFTHERELEVANCEOFAGENTS ANDLINKS Inthis sectionweanswerthesecond and thirdquestions thatwemadein theintroduction.Intheprevious section wepresentedacontrolschemetoswitch dynamically the stateofthe communicationlinksbasedonthefunction r(A,x).Thepresentedcontrolproblemis mathematically equivalent to a cooperativegame.Cooperativegametheorystudies situationsofmutualinteraction betweenaset ofplayerswhichcan negotiateamongthemand commit themselvestofollowcommon bindingstrategies.Asa result ofthebargainingprocess,thesetofplayersmight bedividedintoseveralsubsetscalledcoalitions.Therole of gametheoryis tostudywhichcoalitionsofagents should beformedand to analyze howthe costsorbenefitsfrom cooperationshould bedistributedamongthemembersof acoalition. Initsmostbasic form,acooperativegameis definedonly withtwoelements,asetNofplayersand acharacteristic functionvthatassignsavaluetoeachofthepossible coalitionsSofagents.AcoalitionSis definedasasubset ofN.Incasethat the coalitionis formed byall the playersin N,thetermgrandcoalitionis used.Thefunction v(S)representsthevalueofthe coalition,thatis,the costsorbenefitsofreachingthe commongoalwithout theassistance oftheagentsthatarenotpresentin the coalition. Thedefinitionofacooperativegamerequiresthe exhaustive evaluationofthefunctionvforeach possible coalitionofplayersS.This description providestoo much informationforasimple analysis oftherelevance ofthe agentsand thelinks.All this informationcan besynthesized bymeansofapayoffrule,whichis amathematical toolwhich providestheindividualoutcomesofthegame, thatis,apayoffvectorthatspecifiesthebenefitorcost thateach playermayreasonably expectfromthegame. Mathematically,apayofforallocationvectoris definedas o=(oi)i∈N∈R(N)and specifiesforeach playerithe profitorcostoiwhen he cooperateswithotherplayers. Therearemanydifferentpayoffrulesin theliterature.In this paperwewill usetheShapley value,whichis the only allocationrule γ(N,v) thatverifiesthe efficiency, additivityand symmetryproperties(see Myerson[1997]). TheShapley valueassignsavalueγi(N,v) toeachagent i∈Nin acooperativegamewhosevaluefunctionis given byv.TheShapley valueofa gameis definedas γi(N,v)=X S⊆N\{i} |S|!(N−|S|−1)! N!(v(S∪{i})−v(S)). Fromacentralized pointofview,theShapley valueofthe game(N,v)is thepayoffvectorthatgivestoeachagent his expectedmarginalcontributionto a randomcoalition. Weproposetousetheseideasfromcooperativegame theoryfortheanalysis oftherelevance ofthedifferent agentsand linksofadistributedcontrolscheme.Tothis end,it is necessarytoextend thedefinitionofcooperative gamesothatboththenetworkand the communicational costsare considered.Thus,wedefineacost-extendedcom- municationsituationHasasthetuple (N,v,L,c).We already knowthe componentsofthetuple:Nis theset ofplayers,vis the characteristic functionofthegame, Lis thesetsoflinksthatcomposethenetworkand c is the communicationalcostassociatedtotheuseofa link.TogetherwiththeShapley value,cost-extendedcom- municationsituationsallowonetostudyseveralinherent propertiesoftheagentsand thenetwork.Inthenext subsectionsweshowhowtodeterminewhatagentand linkplaythemostimportantrole ata giventime. 4.1Linkanalysis Whenmodeling a distributingcontrolproblemasacooperativegame,themostnaturalwaytoproceedis to assumethat the controlagentsaretheplayersofthe game.Nevertheless,it is possible tochangethefocusto linksinsteadofagents,justasit is proposedin Borm etal. [1992]. Thus,thegainsorcostsfromcooperation areattributedtocommunicationlinks,whichlead usto defineacost-extended“linkgame” asatuple (L,rH)associatedtothe cost-extendedcommunicationsituationH. The characteristic functionforthis gameis definedas rH(A)=X C∈N/A v(C)+c|L(A)|,∀A⊆L,(4) whichis definedforall thepossible subsetsAoflinks containedin theoriginalnetworkL.Inthe characteristic functionofthelinkgamedefined byequation(4),the grand coalitionis dividedintoitscommunicationcomponentsand itsvalueis thesumofthevaluesofthe correspondingcomponentsand the costofthelinksthat are employedforthe communication defined bythesetA. Weproposetousethefunctionr(A,x)definedin equation(3) todefinethelinkgame characteristic function, thatis,rH(A)=r(A,x).Therefore,givenastatex,it is possible toconstruct thelinkgameand aqualitativeand quantitativeanalysis oftherelevance ofthelinksin the gamemaybeobtainedfromthe correspondingShapley valueγ(L,rH).Eachcomponentofthis vector represents the costofa givenlinkforthesystemwhenthestateis x. Inotherwords,thelowervaluealinkhas,thehigherutility it hasforthesystem. 18th IFAC World Congress (IFAC'11) Milano (Italy) August 28 - September 2, 2011 9123 4.2Agentanalysis Inthis casetheplayersofthegamearethedifferentagents. Letusconsideracooperativegame(N,wH)defined by characteristic functionwH(S)whichassignstoeachcoalitionthefollowingcost wH(S)=X C∈S/L v(C)+c|L(S)|,∀S⊆N,(5) where|L(S)|is thenumberoflinksthatareused bythe coalitionSand cis thelinkcost.Wedenotethis gameas the“agentgame”.Notethataccordingto(5) thevalue ofacoalitionSis thesumofthevaluesofitsmembers separatedintotheir correspondingcommunicationcomponents. Aqualitativeand quantitativeanalysis oftherelevance of theagentsofthesystemcan beobtainedfromtheShapley valueγ(N,wH)ofthe corresponding agentgame.Tobuild suchgameit is necessarytodefinethe characteristic functionthatassignsavaluetoeachcoalitionSofagents fora given networkL.Tothis end,it is notpossible touse the controllersdefinedforeachcommunicationcomponent fora given networkmodeAbecausethose controllerstake into account theparticularcommunicationconstraintsof networkmodeA.Forthis reason,foreachcommunication componentofL,weneedacontrollerKCand aweight matrix PCsuchthat xT CPCxC≥X j∈CX k=0,..,∞ ℓj(k) (6) wherexcis obtainedfromthe currentstatexand is composedofthestatesofall thesubsystemsthatbelong toC;PCis aweightmatrix thatprovidesan upperbound forthe cost toinfinityofthesystemsthatbelongto Cin closed-loopwiththe controlleruC(t)=KCxC(t) startingfromtheinitialstatexC(0)=xCassumingthat all theinputsand statesthatbelongto agentsoutsidethe coalitionare zero.This assumptionallowsonly tocalculate asimple approximationoftheShapley valueoftheagent game.Mostconservative choicescould havebeenmade,for example theagentsoutsideofthe coalitioncould havebeen consideredasdisturbancesand thenamin-maxapproach used.Thedetails about the calculationofthe controller can befound in section5. Then,the characteristic functionoftheagentgamethat definestheutilityofacoalitionSis definedas wH(S)=X C∈S/L xT CPCxC+c|L(S)|,∀S⊆N. TheShapley valueofthegame(N,vH)is knownas theMyersonvalueofthegameand providesconcise informationabout therelevance ofall theagentsin the game.Thelowerthevaluetheis,themorerelevantrole theagenthasin thegame.Itis important toremarkthat theShapley valueoftheagentgame,asit is defined,does nothaveanyphysicalmeaning. 5.CONTROLLERDESIGNPROCEDURE Inthis sectionwepresentamethodtodesignall thematricesthatdefinethe controllersand their corresponding upperboundsonthe cost.Tothis end,weprovidetwo theorems,onetodesignthematricesthatdefine eachcommunicationmode,and anotheroneto obtain thematrices thatdefine each possible coalition. Theorem1.LetA∈Lbeasetofactivelinksin a distributedcontrolsystem.Thedynamicsofthewhole systemaregiven byAN={Aij},∀i,j∈Nand BN= {Bij},∀i,j∈Nand its stage costdefined byQN= diag(Qi)and RN=diag(Ri),∀i∈N.Ifthere exist matricesWN={Wij},∀i,j∈N,whereWi,j∈R(qi×qj), and YN={Yij},∀i,j∈N,whereYi,j∈R(ri×qj),such that thefollowingconstraintsaresatisfied    WNWNAT N+YT NBT NWNQ1/2 NYT NR1/2 N ANWN+BNYNWN0 0 Q1/2 NWN0I0 R1/2 NYN0 0 I   >0 (7a) s.t. Wij=0,Yij=0∀i,jsuchthatxi∈C,xj/∈C(7b) thenmatricesPA=W−1 Nand KA=YNW−1 Nsatisfy(2), all the communicationconstraintsimposed bythenetwork modeAand stabilizethewhole system. Intheagentgametheapproximationofthe costof the communicationcomponentCis basedonthe cost toinfinitygiven bythexT CPCxC.This upperbound is calculatedassumingthat therestoftheagents statesand inputsare zero.Theagentgameonly providesgrounds fordistributingthebenefitsorcostsbetweentheagents duringthegameand theresultingfeedbackgainsare neverusedtocontrolthesystem,soit is notnecessary toimpose centralizedstabilityasarequirement.The followingtheorempresentsanLMIconstraint thatcan be usedtosolvethis design problem. Theorem2.LetC∈S/Lbeasetofindependentcommunicationcomponentsfora givencommunicationsituation Hwhosedynamicsaregiven byAC={Aij},∀i,j∈C and BC={Bij},∀i,j∈Cand its stage costdefined by QC=diag(Qi)and RC=diag(Ri),∀i∈C.Ifthere exist matricesWCand YCsuchthat thefollowingconstraintis satisfied    WCWCAT C+YT CBT CWCQ1/2 CYT CR1/2 C ACW+BCYWC0 0 Q1/2 CWC0I0 R1/2 CYC0 0 I   >0(8) thenmatricesPC=W−1 Cand KC=YCW−1 Csatisfy(6) and stabilizethestatesofCassumingthat thestate and inputsthatdonotbelongtothatcommunication componentare zero. Boththeoremscan beproved usingstandardtechniques basedontheapplicationofSchur’s complement. 6.SIMULATIONRESULTS Inthis sectionweshowanacademic example thatillustratesthetechniquesproposedin thepaper.Thesystem is shownin figure1.Theagentscancommunicatewith anetworkdefined byfourlinks.Wewill refertothe agentsusing arabic numbersand tothelinksusingroman letters.Inordertoimplement theproposedcontrolscheme, matricesKAand PAhavetobedesignedforeachofthe possible modes.Giventhat therearefourlinks,thereare 18th IFAC World Congress (IFAC'11) Milano (Italy) August 28 - September 2, 2011 9124 1,5,6,7 1 2 3 4 3,6,8,10 4,7,9,10 2,5,8,9 11-14: 3/4 links 15: 4 links I II III IV Fig.1.Linksenabledin eachmode. 16 possible networkmodeswhich havebeen numbered from0to 15.Thenetworksmodesforwhichalinkis enabledareshown next toit in figure1. Thematricesthatdefinethesubsystemdynamicsarethe following: A11 =1 0.8 0 0.7B11 =0 1A22 =1 0.6 0 0.7B22 =0 1 A33 =1 0.9 0 0.8B33 =0 1A44 =1 0.8 0 0.5B44 =0 1 Aij=0 0 0 0Bij=0 0.15∀i6=j (9) wherexi∈R(2)withi∈{1,.., 4}arethestatesof eachsubsystemand ui∈R(1)withi∈{1,.., 4}are the correspondinginputs.Thestage costsℓiofall the subsystemsaredefined bymatricesQi=diag(1,1),Ri= 1withi={1,2,3,4}. 6.1Distributedcontrolscheme Foreachmode,adifferentLMIproblemdesignedaccordingtoTheorem1havebeensolvedto obtain the correspondingmatricesKAand PAusingMatlab’s LMI toolbox.Forexample,formode4,whichcorrespondstothe casein whichagents1 and 3communicateand coordinate their actions.Theresultingmatricesare: KT 4=       −0.25 0.00 0.02 0.00 −0.53 0.00 0.06 0.00 0.00 −0.26 0.00 0.00 0.00 −0.45 0.00 0.00 0.01 0.00 −0.23 0.00 0.05 0.00 −0.63 0.00 0.00 0.00 0.00 −0.27 0.00 0.00 0.00 −0.43       P4=       4.56 5 0 0 −0.36 −1.1 0 0 5 9.61 0 0 −0.8−2.48 0 0 0 0 5.48 5.14 0 0 0 0 0 0 5.14 8.34 0 0 0 0 −0.36 −0.8 0 0 4.17 5.08 0 0 −1.1−2.48 0 0 5.08 11.69 0 0 0 0 0 0 0 0 5.37 5.44 0 0 0 0 0 0 5.44 8.40       Itcan beseenthatKAsatisfiesthe communication constraintsofmode4. Once thematricesPAthatdefinetheupper-bound onthe differentcost-to-go valuesareobtained,it is possible to determinetheoptimalnetworkmodefora givenstate. Wepresentnextsomesimulationsoftheproposed distributedcontrollerwhichcan beseenasahierarchical 0 5 10 15 −2 0 2 4 k x1 x11 x12 0 5 10 15 −0.3 −0.2 −0.1 0 0.1 k x2 x21 x22 0 5 10 15 −0.3 −0.2 −0.1 0 0.1 k x3 x31 x32 0 5 10 15 −0.05 0 0.05 0.1 0.15 k x4 x41 x42 Fig.2.Statestrajectories. 0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 k Mode Fig.3.Networkmodes. 0 2 4 6 8 10 12 14 80 90 100 110 120 130 140 150 k Cumulated costs Network changing algorithm Grand coalition Decentralized Fig.4.Cumulatedcost. controlscheme.Thesimulation presented herehavebeen donewithvaluesofD=3 and fortheinitialstate: x1(0)=2 1.8x2(0)=0 0x3(0)=0 0x4(0)=0 0 Figures2showsthe evolutionofthesystemstatesasa functionoftime.Notethatwheneveranagentsis notat theorigin,it disturbstherestoftheagentsfromtheir equilibriumpoint.Figure3showsthedifferentnetworkmodes activeduringthesimulation.In figure4the cumulated costofthe coalitionaldistributedalgorithmis comparedto the cumulatedcostofapplyingfull communicationateach sample.Theadditionalcommunicationalcostproduced by thenetworkmode choice explain thehighercostduringthe firststeps. 6.2Linkanalysis UsingthematricesPA,thelinkgame can be constructed fora givenstatexin orderto analyze whichlinksaremore relevant.Thesetofplayersforthis gameis defined bythe 18th IFAC World Congress (IFAC'11) Milano (Italy) August 28 - September 2, 2011 9125 links,whichare enumerated byromanlettersin figure1. Notethat the conceptsofcoalitionoflinksand network modeare equivalent.Forexample,the characteristic functionforeachofthepossible playersofthelinkgamefor thestate x1=4 3.6x2=2.1 −3x3=0.4 0.8x4=0 0,(10) is thefollowing v(I)=440.84 v(II)=437.61 v(III)=439.24 v(IV)=364.54 v(I,II)=402.93 v(I,III)=439.74 v(I,IV)=358.35 v(II,III)=430.53 v(II,IV)=361.81 v(III,IV)=365.95 v(I,II,III)=354.01 v(I,II,IV)=354.01 v(I,III,IV)=354.01 v(II,III,IV)=354.01 v(I,II,III,IV)=354.51 Thesevalues showthat theoptimalnetworkmodeAfor this stateis anyofthefourcomposed bythree links.The Shapley valueforthis gameis γ(L,rH,x)=[98.94 96.91 104.28 54.36]. This payoffvectorguaranteesthat theplayers(links)are theresponsible ofthe costsorbenefitsthegrand coalition gets.This impliesthat thehighervaluealinkhas,theless usefulforthesystemis.Itis clearthat thelinkthatis morenecessaryis linknumberIV,theonethatconnects agents1 and 3,and forthis reasonthis linkhasthelowest value.Ontheotherhand linknumberIII,theonethat connectsagents3 and 4,is theonethatcontributesless totheglobalobjective,and soit hasthehighestvalue. 6.3Agentanalysis Usingthesetofcontrollersdesigned usingtheorem2,we evaluatethe characteristic functionfortheagentgamefor statex: v(1)=391.12 v(2)=35.99 v(3)=13.22 v(4)=0v(1,2)=427.61 v(1,3)=328.55 v(1,4)=391.12 v(2,3)=49.21 v(2,4)=33.26 v(3,4)=12.13 v(1,2,3)=358.35 v(1,2,4)=389.70 v(1,3,4)=329.96 v(2,3,4)=39.40 v(1,2,3,4)=354.01 Ifwe calculatetheShapley valueforthis gamethefollowingvectoris obtained γ(N,wH,x)=[349.89 28.46 −19.07 −5.26]. TheShapley valueis helpfulfromtwopointsofview.In firstplace,thesumofitscomponentsaddsup exactly thevaluethat thegrand coalition hasassignedin the game.Incaseswherethe characteristic function hasan economic meaningthis is veryhelpfulbecauseit provides apossible allocationvectortodistributetheprofitsfrom cooperation.Insecond place,theShapley valueshows whichagentshavegreaterneedofcommunicationand help fromtheir neighbors. 7.CONCLUSIONS This papercontributestothe constructionofabridge betweencoalitionalgametheoryand control. Themain contributionsofthepaperaretwofold.In firstplace,we haveproposedadistributedcontrolschemethatdynamically switchesthenetworktopologyin orderto optimize boththe controlperformance and the communicational burden.Inthis sense,anoptimization basedcontroller designmethod hasbeen providedsothatall therequested matricescan be calculated.Insecond place,wehavepresentedanovelinterpretationofcooperativegametheory tools to analyze therelevance ofagentsand linksin a distributedcontrolsystem.Asit hasbeenseen,avaluable insightintothe communicationstructureofadistributed systemis obtainedfromtheanalysis ofShapley values. REFERENCES A.Alessio and A.Bemporad.Decentralizedmodelpredictive controlofconstrainedlinearsystems.InProceedings ofthe2007 EuropeanControlConference,pages2813– 2818,2007. A.Alessio and A.Bemporad.Stabilityconditionsfordecentralizedmodelpredictive controlunderpacketdrop communication.InProceedingsofthe2008 American ControlConference,pages3577–3582,2008. P.Borm,G.Owen,and S.Tijs.Onthepositionvaluefor communicationsituations.SIAMJournalonDiscrete Mathematics,5:305–320,1992. C.CanudasdeWit.Invitedsessiononadvancesin networkedcontrolledsystems.InProceedingsofthe25th AmericanControlConference,2006. J.Liu,D.Mu˜nozdela Pe˜na,B.Ohran,P.D.Christofides, and J.F.Davis.Atwo-tierarchitecturefornetworked process control. ChemicalEngineeringScience,63:5349– 5409,2008. J.M.Maestre,David Mu˜nozdela Pe˜na,and E.F. Camacho.Distributedmodelpredictive controlbased onacooperativegame.OptimalControlApplications andMethods,pageIn press,2010.doi: 10.1002/oca.940. L.Magniand R.Scattolini. Stabilizingdecentralized modelpredictive controlofnonlinearsystems.Automatica,42:1231–1236,2006. R.B.Myerson.GameTheory.AnalysisofConflict. HardvardUniversityPress,1997. P.Neumann.Communicationin industrialautomation -whatis going on?ControlEngineeringPractice,15: 1332–1347,2007. B.DeSchutterR.R.Negenbornand H.Hellendoorn. Multi-agentmodelpredictive controloftransportation networks.InProceedingsofthe2006 IEEE InternationalConference onNetworking,SensingandControl (ICNSC2006),2006. D.M.Raimondo,L.Magni, and R.Scattolini. DecentralizedMPCofnonlinearsystem:Aninput-to-state stabilityapproach.Int.J.RobustNonlinearControl, 17:1651–1667,2007. W.Saad,Z.Han,M.Debbah,A.Hjorungnes,and T.Basar.Coalitionalgametheoryforcommunication networks.IEEE SignalProcessingMagazine,Special IssueonGameTheory,26(5):77–97,September2009. A.N.Venkat.DistributedModelPredictive Control: TheoryandApplications.PhDthesis,Universityof Wisconsin-Madison,2006. A.N.Venkat,J.B.Rawlings,and S.J.Wright.Stability and optimalityofdistributedmodelpredictive control. InProceedingsofthe44thIEEE Conference onDecision andControl,andtheEuropeanControlConference ECC 2005,pages6680–6685,Seville,Spain,2005. 18th IFAC World Congress (IFAC'11) Milano (Italy) August 28 - September 2, 2011 9126