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