Distributed consensus on enclosing shapes and minimum time rendezvous

In this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order

Distributedconsensusonenclosingshapes

andminimumtimerendezvous

GiuseppeNotarstefano

6

Abstract—Inthispaperweintroducethenotionofoptimiza-0tionundercontrolandcommunicationconstraintinarobotic0network.Startingfromageneralsetup,wefocusourattention2ontheproblemofachievingrendezvousinminimumtime foranetworkof rstorderagentswithboundedinputsandlimitedrangecommunication.WeproposetwodynamiccontrolepSandcommunicationlaws.Theselawsarebasedonconsensusalgorithmsfordistributedcomputationoftheminimalenclosing 6ballandorthotopeofasetofpoints.Weprovethatthesecontrol lawsconvergetotheoptimalsolutionofthecentralizedproblem ](i.e.,whennocommunicationconstrainsareenforced)astheCboundonthecontrolinputgoestozero.Moreover,wegiveaOboundforthetimecomplexityofoneofthetwolaws.

.I.INTRODUCTION

thaTheinterestingaspectofmotioncoordinationconsistsinmcombiningtogetherproblemsfromcontrolandcommunica-[tiontheory.Themaindif cultydealswithintegratingthe 1sensing,computing,communicationandcontrolaspectsofvproblemsinvolvinggroupsofmobileagents.Awellknown9problemincontroltheoryisoptimalcontrol.Roughlyspeak-6ing,itconsistsin ndingafeedbacklawthatminimizessome1costfunctionalundersomeinputsanddynamicsconstraint.9Inthispaperweintroducethenotionofoptimalcontroland06communicationforanetworkofroboticagents.Wewant0tostudyhowtosolveanoptimizationproblem,inpresence/ofboththeusualmotionconstraintsandthecommunicationthones.Inparticularthispaperisapreliminarycontributionatowardswhatmightbelooselyreferredtoas“distributedmgeometricoptimization.”Infactmanyoptimizationproblems:forroboticnetworkscanbeshowntobeequivalenttothevicomputationofgeometricshapes.WhileinacentralizedXsettingthesolutionisusuallysimple,theproblembecomesrverycomplicatedwhenitmustbesolvedinadistributedaway.Distributedcomputationovernetworkhasbeenlargelystudiedfor xedtopologies;e.g.,see[1].

Inthispaperwepointourattentiononthewellknownrendezvouscoordinationtaskandlookforsolutionsthatsolvesuchtaskinminimumtime.Welookfordistributedsolutionsinnetworksofmobileagentswith rstorderdynamics,boundedinputsandlimited-rangecommunication.The“multi-agentrendezvous”problemanda“circumcen-teralgorithm”havebeenintroducedbyAndoandcoworkers

ThismaterialisbaseduponworksupportedinpartbyAROMURIAwardW911NF-05-1-0219.TheauthorswouldliketothankSoniaMart´ nez,JorgeCort´es,andEmilioFrazzolifornumerousdiscussionsonroboticnetworks.GiuseppeNotarstefanoiswiththetheDepartmentofInformationEn-gineering,Universit`adiPadova,ViaGradenigo6/b,35131Padova,Italy,notarste@dei.unipd.it

FrancescoBulloiswiththeCenterforControl,DynamicalSystemsandComputation,UniversityofCaliforniaatSantaBarbara,SantaBarbara,CA93106,bullo@engineering.ucsb.edu

FrancescoBullo

in[2].Thealgorithmproposedin[2]hasbeenextendedtovarioussynchronousandasynchronousstop-and-gostrate-giesin[3].Arelatedalgorithm,inwhichconnectivitycon-straintsarenotimposed,isproposedin[4].In[5]theclassof“circumcenteralgorithms”hasbeenstudiedinnetworksofagentswhosestatespaceisRd,forarbitraryd,andwithcommunicationtopologycharacterizedbyproximitygraphsspatiallydistributedoverthediskgraph.In[6]the(timeandcommunication)complexityofthisandotheralgorithmshasbeenstudied.Allthesecoordinationschemesarememoryless(staticfeedback).Inthispaperwewanttoexploredynamiccontrolandcommunicationlawsinordertoapproximatetheoptimalsolutionoftheminimumtimerendezvous.Inparticularthecontrolandcommunicationlawsisbasedonreachingconsensusonsomelogicvariablesandatthesametimemovingtowardthecurrentestimation.Asimilarapproachwasusedin[7]wheretheagentstrytoreachaconsensusonasetofvariablescalledcoordinationvariables.Studyingtheminimumtimerendezvousprobleminthecentralizedsettingweshowthat,dependingonthenormusedtoboundthecontrolinput,theoptimalsolutionconsistsofmovingtowardthecenteroftheminimalenclosingball(boundonL2norm)andtowardthecenteroftheminimalenclosingorthotope(boundonthein nitynorm)ofthepointslocatedattheinitialpositionoftheagents.

Ourmainresultisthedesignofacontrolandcom-municationlawbasedonaconsensusalgorithmforthedistributedcomputationoftheminimalenclosingballandtheminimalenclosingorthotopeofasetofpoints.Weprovethecorrectnessofthetwoconsensusalgorithmsandprovideaboundonthetimeofconvergencefortheorthotopecase.Thenweprovethatthecontrolandcommunicationlawthatcombinestheconsensuswiththemotionlawconvergestotheoptimalsolutionasthecontrolboundgoestozero.Moreover,fortheproblemwithinputboundedbythein nitynorm(correspondingtothecomputationoftheminimalenclosingorthotope),weprovethatthecontrolandcommunicationlawisaconstantfactorapproximationofthecentralizedoptimalsolution.

InSectionIIweintroduceaformalmodelofroboticnetworkinspiredbytheoneintroducedin[6].Moreover,wede netheoptimalcontrolandcommunicationproblem.InSectionIIIwecharacterizethesolutionofminimumtimerendezvousinacentralizedsetting.InSectionIVwede netheFloodMEBandFloodMEOalgorithmsforthedistributedcomputationofminimalenclosingballandorthotope,provetheircorrectnessandgiveboundsontimecomplexity.Sec-tionVcontainsthecontrolandcommunicationlawsbasedontheconsensusalgorithmsdescribedinSectionIV.Finallyin

In this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order

SectionV-CandSectionVIweshowsimulationsanddrawtheconclusionswithfutureperspectives.

II.PRELIMINARYDEVELOPMENTS

Inthissectionwerecalltheconceptsofnetworkofroboticagents,coordinationtasksandcomplexitymeasures,andintroducethenotionofoptimizationundermotionandcommunicationconstraints.

A.Notation

WeletN,N0,andR+denotethenaturalnumbers,thenon-negativeintegernumbers,respectively.Welet andthepositiverealnumbers,i∈{1,...,n}SidenotetheCartesianproductofsetsS1,...,Sn.Forp∈R,welet p and p denotethe oorandceilofp.Forr∈R+andp∈Rd,weletB(p,r)denotetheclosedballcenteredatpwithradiusr,i.e.,B(p,r)={q∈Rd| p q 2≤r}andC(p,r)denotetheclosedhypercubecenteredatpwithsidesoflengthrandparalleltothecoordinateaxes,i.e.,C(p,r)={q∈Rd| p q ∞≤r}.

Forf,g:N→R,wesaythatf∈O(g)(respectively,f∈ (g))ifthereexistn0∈Nandk∈R+suchthat|f(n)|≤k|g(n)|foralln≥n0(respectively,|f(n)|≥k|g(n)|foralln≥n0).Iff∈O(g)andf∈ (g),thenweusethenotationf∈Θ(g).

Next,webrie yreviewsomeusefulproximitygraphs.Givenrcmm∈R+,thediskgraphGdisk(rcmm),respec-tivelycubegraphGcube(rcmm),isthestatedependentgraphonRdde ned[n]bythefollowingstatement:foranypointset{p[1],...,p} Rd,thepair(i,j)isanedgeinG[1]disk(rcmm)·({p[1],...,p[n]}),respectivelyGcube(rcmm)·({p,...,p[n]}),ifandonlyifi=jand p[i] p[j] 2≤rcmm

p[i] p[j]∈B(0d,rcmm),

respectively

p[i] p[j] ∞≤rcmm

p[i] p[j]∈C(0d,rcmm).

AnotherusefulgraphisthecompletegraphGcmpl,i.e.,thegraphwithedgesbetweenanypairofnodes.

Finally,givenagraphG(evennotstatedependent),wedenotewithdistG(i,j)thetopologicaldistancebetweeniandj,i.e.,theminimumnumberofagentstogofromitojinthegraphG.Wede nediamG,thediameterofG,tobethemaximumtopologicaldistance,distG(i,j),forall(i,j).B.Modelinganetworkofroboticagents

Wedescribea(uniform)networkofroboticagentsusingtheformalmodelintroducedin[6]modi edforthediscretetimecase.Thenetworkismodeledasatuple(I,A,Ecmm).I={1,...,n}isthesetofuniqueidenti ers(UIDs);A={A[i]}i∈I={(X,U,X0,f)}i∈IiscalledthesetofphysicalagentsandisasetofcontrolsystemsconsistingofadifferentiablemanifoldX(statespace),acompactsubsetUofRm(inputspace),asubsetX0ofX(setofallowableinitialstates)anda(suf cientlysmooth)mapf:X×U→Xdescribingthedynamicsofithagent;Ecmm:Xn→I×Iiscalledthecommunicationedgemap.

Theroboticnetworkevolvesaccordingtoadiscrete-timecommunicationandmotionmodel.

De nition2.1(Controlandcommunicationlaw):LetSbearoboticnetwork.A(uniform,synchronous,dynamic)controlandcommunicationlawCCforSconsistsofthesets:

(i)L,asetcontainingthenullelement,calledthe

communicationlanguage;elementsofLarecalledmessages;

(ii)W,setofvaluesofsomelogicvariablesw[i],i∈I;(iii)W0 W,subsetsofallowableinitialvalues;andofthemaps:

(i)msg:X×W×I→L,message-generationfunction;(ii)stf:W×Ln→W,calledstate-transitionfunction;(iii)ctl:X×W×Ln→U,calledcontrolfunction. Roughlyspeakingthisde nitionhasthefollowingmean-ing:foralli∈I,totheithphysicalagentcorrespondsalogicprocess,labeledi,thatperformsthefollowingactions.First,ateachcommunicationroundtheithlogicprocesssendstoeachofitsneighborsinthecommunicationgraphamessage(possiblythenullmessage)computedbyapplyingthemessage-generation[i]functiontothecurrentvaluesofx[i]andw.Afteranegligibleperiodoftime,theithlogicprocessresetsthevalueofitslogicvariablesw[i]byapplyingthestate-transitionfunctiontothecurrentvalueofw[i],andtothemessagesreceivedattimet.Betweencommunicationinstants,themotionoftheithagentisdeterminedbyapplyingthecontrolfunctiontothecurrentvalueofx[i],andthecurrentvalueofw[i].Thisideaisformalizedasfollows.De nition2.2(Evolutionofaroboticnetwork):LetSbearoboticnetworkandCCbeacontrolandcommunicationlawforS.Theevolutionof(S,x[i][i]

CC)frominitialconditions0∈X0andw0∈W0,i∈I,isthesetofcurvesx[i]:N→Xandw[i]:N→W,i∈I,satisfying

x[i](t+1)=f x[i](t),ctl(x[i](t),w[i](t+1),y[i](t))

,where,fori∈I,

w[i](t+1)=stf(w[i](t),y[i](t)),

withtheconventionsthatx[i](t0)=x[i]

[i]

i∈I.Here,thefunctiony[i]:N→0andw[i](t0)=wLn(describingthe0,messagesreceivedbyagenti)y[i]

Inthepaper

hascomponents

msg(x[j](t),w[j](t),i),if(i,j)∈Ecmm,j(t)=

null,otherwise.

weconsiderthefollowingnetwork.Eachagentioccupiesalocationp[i]∈Rd,d∈N,andmovesaccordingtothe rstorderdiscrete-timeintegrator

p[i](t+1)=p[i](t)+u[i](t).

(1)

Thecommunicationedgemapcanbeeithertheonearisingaccordingtothediskgraph,Edisk,ortheoneaccordingtothecubegraph,Ecube.Eachcontrolu[i]takesvaluesinaboundedsubsetofRd,thatcanbeeitherB(0,rctr)orC(0,rctr),i.e., u[i] 2≤rctror u[i] ∞≤rctr.Noticethat,ingeneral,thetypeofcommunicationedgemapandthetypeofcontrolboundarenotrelated.Finallythecontrolandcommunicationlawwillbede neddependingonthecoordinationtask.

In this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order

C.Coordinationtasksandtimecomplexity

Wearereadytode nethenotionoftaskandoftaskachievementbyaroboticnetwork.

De nition2.3(Coordinationtask):LetSbearoboticnetwork.nA(static)coordinationtaskforSisamapT:X→{true,false}.Additionally,letCCacontrolandcommunicationlawforS.Theforallinitialconditionsx[i]lawCCachievesandw[i]

thetaskTif,

0∈X00∈W0,i∈I,thecorrespondingnetworkevolutiont→(x(t),w(t))hasthepropertythatthereexistsT∈NsuchthatT(x(t))=trueforallt≥T. Weare nallyreadytode nethenotionoftimecom-plexityastheminimumnumberofcommunicationroundsneededbytheagentstoachievethetaskTwithCC.

De nition2.4(Timecomplexity):LetSbearoboticnet-workandletTbeacoordinationtaskforS.LetCCbeacontrolandcommunicationlawforScompatiblewithTThetimecomplexitytoachieveTwithCCfromx0∈X0n

.

isTC(T,CC,x0)=inf{T∈N|T(x(t))=true, t≥T}wheret→(x(t),w(t))istheevolutionof(S,CC)fromtheinitialcondition(x0,w0).

ThetimecomplexitytoachieveTwithCC,TC(T,CC),isthemaximumTC(T,CC,x0)overallinitialconditionsx0.D.OptimalcontrolandcommunicationinroboticnetworksHavingde nedacoordinationtaskforaroboticnetwork,wecanaskwhethersuchtaskcanbeaccomplishedminimiz-ingsomecostfunctional.Inwhatfollowswewillintroducethenotionofoptimalcontrolandcommunicationproblemandofoptimalcontrolandcommunicationlawassolutionoftheproblem.

De nition2.5(Optimalcontrolandcommunication):GivenataskTandacostfunctionalJ(u(·),x(T),T),anoptimalcontrolandcommunicationproblemisthefollowing:minimizeu(·),x(0),x(T),TJ(u(·),x(T),T)

J(u(·),x(T),T)= T

τ=0(l(x(τ),u(τ))+g(x(T)),subj.to

(i)(x(·),u(·))isaninput-statetrajectoryofA,

A={A[i]}i∈I;

(ii)iandjcancommunicateifandonlyif

(i,j)∈Ecmm(x[1](t),...,x[n](t));(iii)T(x(t))=trueforallt≥T,T∈N.

wherel:Xn×Un→Risasuf cientlysmoothand

nonnegative-valuednfunction,calledstagecost,andg:X→Rhasthesamepropertiesplusg(x)=0forallx∈XnsuchthatT(x)=true(foranadmissibleCC). WesaythatacontrolandcommunicationlawCCisoptimalwithrespecttothecoordinationtaskTandthecostfunctionalJ,ifitsolvestheaboveoptimalcontrolandcommunicationproblem.

WecallCCacentralizedoptimalcontrolandcommunica-tionlawifitsolvestheoptimizationproblemforanetworkofroboticagentsthatcommunicateaccordingtothecompletegraph,i.e.,thecommunicationedgemapisEcmpl.

Remark2.6:Thecentralizedsolutionofanoptimalcon-trolandcommunicationproblemistheclassicalsolutionoftheoptimalcontrolproblemforthewholenetworksystemwithoutcommunicationconstraints.

III.CENTRALIZEDMINIMUM

TIMERENDEZVOUS

Inthissectionwestudytherendezvousproblemforaroboticnetworkof rstorderagentswithcommunicationedgemapEdiskorEcubeandlookforacontrolandcommu-nicationlawthatsolvestheprobleminminimumtime.Moreformally,letS=(I,A,Ecmm)beauniformroboticnetwork.The(exact)rendezvoustaskTrndzvs:Xn→{true,false}forSis thestatictaskde nedby

true,

ifx[i]=x[j],Trndzvs(x)=forx=(x[1],...,x[n (i,j)∈Ecmm(x),

false,otherwise.

]).

Thus,giventheuniformnetworkS=(I,A,Ecmm),theminimumtimerendezvousproblemfor rstorderagentswithlimited-rangecommunicationandboundedcontrolinputisthefollowing:

minimizeu(·),p(T)

Tτ=01,subj.to

(i)(p(·),u(·))isaninput-statetrajectoryofA,

A={A[i]}i∈I={(Rd,U,Rd,f)}i∈I,p(0)=p0;(ii)iandjcancommunicateif[nand]onlyif

(i,j)∈Ecmm(p[1](t),...,p(t));

(iii)Trndzvs(p[1],...,p[n])=trueforallt≥T,T∈N.Herei]UiseitherB(0,rctr)orC(0,rctr),f(p[i](t),u[i](t))=p[(t)+u[i](t)andthecommunicationedgemapEcmmiseitherEdiskorEcube.

WerefertotheminimumtimerendezvousproblemwithcommunicationedgemapEcmmandinputsetUasMTR(Ecmm,U).

Next,weprovidesomepreliminaryresultsforthecentralizedsettingoftheaboveproblem,]thatis,forMTR(Ecmpl,U).LetMEB(p[1]···p[n)andMEO(p[1]···p[n])theminimalenclosingballandorthotopeofpoints(p[1]·]··p[n]),andletMBC(p[1]···p[n][n])andMOC(p[1]···p[n[n])thecentersofMEB(p[1]···p)andMEO(p[1]···p)respectively.Wepresentthefollowingtheoremomittingtheproofbasedongeometricargumentsbecauseofspaceconstraints.

Theorem3.1:Forallrctr∈R+,p[i]

),U0∈Rd,i∈{1,...,n}thesolutionofMTR(Ecmpl,U=B(0,rctr)orU=C(0,rctr),isnotunique(theproblemisnotnormal).Ifu[i]∈B(0,rctr),i∈{1,...,n},then

(i)p(T)=prndzvs,disk=MBC(p[1](0),...,p[n](0)),

u[i](t)=min{rctr, prndzvs p[i](t) 2}

·vers(prndzvs p[i](t)),

i∈{1,...,n},

isasolutionofMTR(Ecmpl,B(0,rctr));

In this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order

(ii)if i∈{1,...,n}, p[i] MBC(p[1]···p[n]) 2≤

rctr,thenthesolutionofMTR(Ecmpl,B(0,rctr))isgivenbyp(T)=prndzvs,disk,prndzvs,disk∈∩i∈{1,...,n}B(p[i],rctr),andu[i](t)=prndzvs,disk p[i](t).

Alternatively,ifu[i]∈C(0,rctr),i∈{1,...,n},then

(iii)p(T)=prndzvs,cube,prndzvs,cube∈RMT,ua[i](t)=

min{rctr,|prndzvs,a pa[i](t)|}sign(prndzvs,a pa[i](t)),i∈{1,...,n},a∈{1,...,d}isasolutionofMTR(Ecmpl,C(0,rctr)),where

RMT= MOC(p[1](0),...,p[n](0))

1

a

2

(lmax la)

,

lmaxisthelargestsideofMEO(p[1](0),...,p[n](0))andlaisthesideindirectiona;

(iv)if i∈{1,...,n} p[i] MOC(p[1]···p[n]) ∞≤rctr

thesolutionofMTR(Ecmpl,C(0,rctr))isgivenbyp(T)=prndzvs,prndzvs∈∩i∈{1,...,n}C(p[i],r]ctr),andu[i(t)=prndzvs p[i](t). IV.DISTRIBUTED

CONSENSUSONMINIMALENCLOSING

BALLANDORTHOTOPE

Intheprevioussectionwehaveshownthatminimalenclosingshapesplayakeyroleinthesolutionofminimumtimerendezvous.Infactiftheagentscouldknowthecenterofsuchshapes(ballororthotope)thesolutionofminimumtimerendezvouswouldbejustacontrollawthatdriveseachagenttothispoint.Therefore,inthissection,wewanttoexploretwoconsensusalgorithmstocomputetheminimalenclosingballandtheminimalenclosingorthotopeofasetofgivenpointsinRdinadistributedway.

HereisaninformaldescriptionofwhatweshallrefertoastheFloodMEBalgorithm:

[Informaldescription]Eachagentinitializestheminimalenclosingballtoitsinitialposition,then,ateachcommunicationround,performsthefol-lowingtasks:(i)itacquiresfromitsneighbors(amessagerepresentedby)thecoordinatesoftheminimumsetofpointsdescribingtheboundaryoftheirminimalenclosingballandthecoordinatesoftheirinitialposition;(ii)itcomputestheminimalenclosingballofthepointsetcomprisedofitsanditsneighbors’setofpointsanditsinitialposition(thatitmaintainsinmemory);(iii)itupdatesitslogicvariablesandmessageasin(i).

Beforedescribingthealgorithmmoreformally,weneedtointroducesomenotationandstatesomepropertiesoftheminimalenclosingball.Givenasetofmpoints{q1,...,qm} Rdingenericpositions,wedenotewithMEBbndry({q1,...,qm})theminimumsetofpointsontheboundaryofMEB({q1,...,qm})thatuniquelyidentifysuchboundary.Whenthepointsareingenericposition,weletMEBbndry({q1,...,qm})denoteaminimumsetofpointsontheboundaryofMEB({q1,...,qm})thatidentifysuchboundary.Moreover,letMBR:F(Rd)→Rthefunction

thatassociatestoasetofpointstheradiusoftheminimalenclosingballofsuchpoints.

Lemma4.1(MEBproperties):LetQnasetofnpoints.Thefollowingstatementshold.

(i)thereexistsasubsetQd Qnofd+1elementssuch

thatMEB(Qd)=MEB(Qn);

(ii)forallQn1,Qn2 QnwithQnQ;

1 Qn2,then

MBR(n(iii)ifMBR(Q1)≤MBR(Qn2)nQ1)=MBR(Qn2),thenMBC(Qn1)=

MBC(n(iv)thenumber2);

ofpossiblevaluesofMBR(Qn Q1),forall

Qn1n,is nite.

Remark4.2:AnimportantimplicationofLemma4.1(i)isthatMEBbndry({q1,...,qn})hasatmostd+1points,thenthenumberofpacketsinthemessagesentandstoredbyeachagentisatmostd+1anddoesnotdependonn. :FloodMEBalgorithm.

Goal:Solvetheproblemofcomputingmin-imalenclosingballofasetofLogicstate:w[i]=(P[i]bndry,p[i]

points.

0);Msgfunction:msg(x[i],w[i],i)=w[i];Initialization:

P[i]bndry(0)={p[i](0)},p[i]

0(0)=p[i](0).

In this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order

sequencecorrespondstoaballwhoseradiusismonotonenondecreasing,upperboundedandcanassumea nitenum-berofvalues.Thenweproceedbycontradictiontoprovethatallthelawsconvergetothesameball(sameradiusandcenter)andthatitisexactlytheminimalenclosingballofthenpoints.Supposethatthealgorithmconvergesondifferentballs(differentradiusordifferentcenter)fordifferentagents.Thentheremustexisttwoagentsthatareneighborsandhavedifferentlogicvariables(correspondingtodifferentballs).Butthismeansthat,atthefollowingtimeinstant,theyhavetocomputetheminimalenclosingballofalargersetofpoints,theneitheroneofthemwilltakethevalueoftheotherorbothofthemwillchangetheirvalueandtakeacommonone.Iteratingthisargumentweobtainthatalltheagentsmustconvergetoacommonvalue.Now,theballateachnodecontains,byconstruction,theinitialpositionofthatnode.Sincetheballisthesameforeachnode,itcontainsalltheinitialpositions,thenitistheminimalenclosingballoftheinitialpositions.

Fori∈{1,...,n},agentiexecutesateachtimet∈N:

1:acquirew[j],j∈N(i)2:

compute a∈{1,...,d}

p[i]

=minj∈N(i)∪{i}{p[j]min,a(t+1)p[max,ai]min,a(t)}(t+1)=maxj∈N(i)∪{i}{p[max,aj]

(t)}3:

update a∈{w[ai](t+1)= 1,...,d}p[i]

p[max,ai]min,a(t+1),(t+1)

whereimin,aandimax,aaretheagentsthatcharacterizetheboundaryoftheorthotopeindirectionaandminimizethetopologicaldistancefromi.

ThetimecomplexityofthealgorithmisoforderΘ(n). Proof:InordertoprovethecorrectnessandthetimecomplexityofthealgorithmdescribedinTable??,weneedtoprovethatitisequivalentto2dFloodMaxalgorithmsforleaderelection(twoforeachdirection)runningsimultane-ously.Oncewehaveproventhat,theresultsoncorrectnessandtimecomplexityfollowfromChapter4in[1].

ThealgorithmisclearlyasetofFloodMaxalgorithmsforleaderelection.Infacttheboundaryoftheorthotopeineachdirectionaisgivenbythecoordinatesofthepointsonsuchboundarywhicharecharacterizedbythepropertyofhavingthemaximumandminimumvalueoftheathcoordinaterespectively.

Inordertoprovethattheexactnumberofcommunica-tionroundsneededisTFloodMEO,simplyobservethatitisexactlytheminimumtimeforalltheleaderstopropagatetheirinformationthroughallthenetwork.Hencethisistheminimumtimeforeverypossibleconsensusalgorithmtoconverge.Butthisisexactlythetimetakenby2dFloodMaxalgorithmsrunningsimultaneouslyandthereforethetimetakenbyFloodMEO.

In this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order

theMEB(MEO)ofagenti(forsomei∈{1,...,n})hasnotchangedandthealgorithmhasnotconvergedyet.ThentherewillexistaT>diamGsuchthattheMEB(MEO)ofagentiwillchangetoanewvalue.Butthismeansthatthenewvalue,storedTroundsbeforebysomeotheragentj,tookanumberofcommunicationroundsgreaterthandiamGtoarrivefromjtoiandthiscontradictsthede nitionofdiameterofG.

T∈Nsuchthatfort=

A.TimecomplexityofCCMEBandCCMEO

InthepreviouslemmawehaveproventhatthecontrolandcommunicationlawsCCMEBandCCMEOachieveconsensus.Nowweaskhowfasttheselawsaredependingonthecontrolboundrctrandthenumberofagents.

Theorem5.2:Forrcmm∈R+,d∈N,considerthenetworkSwithcommunicationedgemapeitherEdiskorEcube.Thefollowingstatementshold:

(i)foru[i]∈B(0,rctr),i∈{1,...,n},thecontroland

communicationlawCCMEBasymptoticallyconvergestotheminimumtimerendezvouscentralized+solutionMTR(Ecmpl,B(0,rctr))asrctr→0(forall xedn).(ii)foru[i]∈C(0,rctr),i∈{1,...,n},thecon-trolandcommunicationlawCCMEOconvergestotheminimumtimerendezvouscentralized+solutionMTR(Ecmpl,C(0,rctr))forrctr→0(forall xedn).Moreover,itisaconstantfactorapproximationofMTR(Ecmpl,C(0,rctr)),i.e.,TC(Trndzvs,CCMEO)∈Θ(n

rTctr

+FloodMEO.

(3)

The rststatementisprovenbyobservingthatTFloodMEOdoesnotdependonrctr,therefore,asrctr→0+,TMEOconvergestotheoptimalvalueofthecentralizedcase.

Inordertoprovethesecondstatement,observethatdiam(p[1](0),...,p[n](0))≤(n 1)rcmmandTFloodMEO∈Θ(n).Theresultfollowsbysubstitutingtheseboundsin(3).

In this paper we introduce the notion of optimization under control and communication constraint in a robotic network. Starting from a general setup, we focus our attention on the problem of achieving rendezvous in minimum time for a network of first order

B.DistributedminimumtimerendezvousinonedimensionInonedimension(alltheagentsspreadonaline),wecan ndaconditiononrctrensuringthatthemove-toward-MBCalgorithmisthesolutionofMTR(Edisk,B(0,rctr)).

Theorem5.5:Ford=1,letimaxandimintheagentsinthenetworkSwiththemaximumandminimumpositions.Ifrctr<1

rctr

Proof:Considertheinputsequenceofthecentralizedsolutionfortheagentimin(andequivalentlyforimax).Itisu[imin](t)=rctrforallt<T 1andu[imin](T 1)=MBC(p[1](0),...,p[n](0)) p[imin](T 1).SincetherendezvoustimeisboundedbythetimethatimaxandimintaketoreachMBC(p[1](0),...,p[n](0)),weneedtoprovethat,aslongastheconsensusontheminimalenclosingballisnotreached,thenu[imin](t)= u[imax](t)=rctr.Duetothesymmetryoftheproblemwewillgivetheproofonlyforimin.Itcanbeeasilyshownthatforallt≥1such

[imin]

thatpmax(t)=p[imax](0)(consensusisnotreached),thefollowingholds:

[imin]imin]

p[max(t+1)>pmax(t 1)+rcmm.

.

Itfollows:

MBC[imin](t+1)=

1

2

imin][imin]

(p[(0))max(t 1)+rcmm+p

=MBC[imin](t 1)+

1rcmm.

2

Thisleadsto

rctr+

1

4

rcmm.

Theothertwoassumptionsensuretheconditionfort=0.

本文来源：https://www.bwwdw.com/article/xhjm.html