Distributed consensus on enclosing shapes and minimum time r

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说医药卫生Distributed consensus on enclosing shapes and minimum time r在线全文阅读。