外文翻译---基准分布式控制规律的运动协调非完整的机器人 英文版.pdf

IEEETRANSACTIONSONROBOTICS,VOL.25,NO.4,AUGUST2009851Vision-Based,DistributedControlLawsforMotionCoordinationofNonholonomicRobotsNimaMoshtagh,Member,IEEE,NathanMichael,Member,IEEE,AliJadbabaie,SeniorMember,IEEE,andKostasDaniilidis,SeniorMember,IEEEAbstractInthispaper,westudytheproblemofdistributedmo-tioncoordinationamongagroupofnonholonomicgroundrobots.Wedevelopvision-basedcontrollawsforparallelandbalancedcir-cularformationsusingaconsensusapproach.Theproposedcon-trollawsaredistributedinthesensethattheyrequireinformationonlyfromneighboringrobots.Furthermore,thecontrollawsarecoordinate-freeanddonotrelyonmeasurementorcommunica-tionofheadinginformationamongneighborsbutinsteadrequiremeasurementsofbearing,opticalflow,andtimetocollision,allofwhichcanbemeasuredusingvisualsensors.Collision-avoidancecapabilitiesareaddedtotheteammembers,andtheeffectivenessofthecontrollawsaredemonstratedonagroupofmobilerobots.IndexTermsCooperativecontrol,distributedcoordination,vision-basedcontrol.I.INTRODUCTIONCOOPERATIVEcontrolofmultipleautonomousagentshasbecomeavibrantpartofroboticsandcontroltheoryresearch.Themainunderlyingthemeofthislineofresearchistoanalyzeand/orsynthesizespatiallydistributedcontrolar-chitecturesthatcanbeusedformotioncoordinationoflargegroupsofautonomousvehicles.Someofthisresearchfocussesonflockingandformationcontrol9,14,16,22,31,andsynchronization2,39,whileothersfocusonrendezvous,distributedcoverage,anddeployment1,5.Akeyassump-tionimpliedinallofthepreviousreferencesisthateachvehicleorrobot(hereaftercalledanagent)communicatesitspositionand/orvelocityinformationtoitsneighbors.Inspiredbythesocialaggregationphenomenainbirdsandfish6,30,researchersinroboticsandcontroltheoryhaveManuscriptreceivedFebruary23,2008；revisedJanuary31,2009.Firstpub-lishedJune10,2009；currentversionpublishedJuly31,2009.ThispaperwasrecommendedforpublicationbyAssociateEditorZ.-W.LuoandEdi-torJ.-P.Laumonduponevaluationofthereviewerscomments.TheworkofA.JadbabaiewassupportedinpartbytheArmyResearchOfficeMultidisciplinaryUniversityResearchInitiative(ARO/MURI)underGrantW911NF-05-1-0381,inpartbytheOfficeofNavalResearch(ONR)/YoungIn-vestigatorProgram542371,inpartbyONRN000140610436,andinpartunderContractNSF-ECS-0347285.TheworkofK.DaniilidiswassupportedinpartunderContractNSF-IIS-0083209,inpartunderContractNSF-IIS-0121293,inpartunderContractNSF-EIA-0324977,andinpartunderContractARO/MURIDAAD19-02-1-0383.N.MoshtaghwaswiththeGeneralRobotics,Automation,Sensing,andPer-ceptionLaboratory,UniversityofPennsylvania,Philadelphia,PA19104USA.HeisnowwithScientificSystemsCompany,Inc.,Woburn,MA01801USA(e-mail:nmoshtaghssci.com).N.Michael,A.Jadbabaie,andK.DaniilidisarewiththeGeneralRobotics,Automation,Sensing,andPerceptionLaboratory,UniversityofPennsylva-nia,Philadelphia,PA19104USA(e-mail:nmichaelgrasp.upenn.edu；jad-babaigrasp.upenn.edu；kostasgrasp.upenn.edu).Colorversionsofoneormoreofthefiguresinthispaperareavailableonlineathttp:/ieeexplore.ieee.org.DigitalObjectIdentifier10.1109/TRO.2009.2022439developedtools,methods,andalgorithmsfordistributedmo-tioncoordinationofmultivehiclesystems.Twomaincollectivemotionsthatareobservedinnatureareparallelmotionandcircularmotion21.Onecaninterpretstabilizingthecircularformationasanexampleofactivityconsensus,i.e.,individualsare“movingaround”together.Stabilizingtheparallelforma-tionisanotherformofactivityconsensusinwhichindividuals“moveoff”together33.Circularformationsareobservedinfishschooling,whichisawell-studiedtopicinecologyandevolutionarybiology6.Inthispaper,wepresentasetofcontrollawsforcoordinatedmotions,suchasparallelandcircularformations,foragroupofplanaragentsusingpurelylocalinteractions.Thecontrollawsareintermsofshapevariables,suchastherelativedistancesandrelativeheadingsamongtheagents.However,theseparam-etersarenotreadilymeasurableusingsimpleandbasicsensingcapabilities.Thismotivatestherewritingofthederivedcontrollawsintermsofbiologicallymeasurableparameters.Eachagentisassumedtohaveonlymonocularvisionandisalsocapableofmeasuringbasicvisualquantities,suchasbearingangle,opti-calflow(bearingderivative),andtimetocollision.Rewritingthecontrolinputsintermsofquantitiesthatarelocallymeasurableisequivalenttoexpressingtheinputsinthelocalbodyframe.Suchachangeofcoordinatesystemfromaglobalframetoalocalframeprovidesuswithabetterintuitiononhowsimilarbehaviorsarecarriedoutinnature.Verificationofthetheorythroughmultirobotexperimentsdemonstratedtheeffectivenessofthevision-basedcontrollawstoachievethedesiredformations.Ofcourse,inreality,anyformationcontrolrequirescollisionavoidance,andindeed,collisionavoidancecannotbedonewithoutrange.Inordertoimprovetheexperimentalresults,weprovidedinteragent-collision-avoidancepropertiestotheteammembers.Inthispaper,weshowthatthetwotasksofformationkeepingandcollisionavoidancecanbedonewithdecoupledadditivetermsinthecontrollaw,wherethetermsforkeepingparallelandcircularformationsdependonlyonvisualparameters.Thispaperisorganizedasfollows.InSectionII,wereviewanumberofimportantrelatedworks.Somebackgroundinfor-mationongraphtheoryandothermathematicaltoolsusedinthispaperareprovidedinSectionIII.TheproblemstatementisgiveninSectionIV.InSectionsVandVI,wepresentthecontrollersthatstabilizeagroupofmobileagentsintoparallelandbalancedcircularformations,respectively.InSectionVII,wederivethevision-basedcontrollersthatareintermsofthevisualmeasurementsoftheneighboringagents.InSectionVIII,collision-avoidancecapabilitiesareaddedtothecontrollaws,andtheireffectivenessistestedonrealrobots.1552-3098/$26.00©2009IEEEAuthorizedlicenseduselimitedto:NanchangUniversity.DownloadedonJanuary12,2010at20:02fromIEEEXplore.Restrictionsapply.852IEEETRANSACTIONSONROBOTICS,VOL.25,NO.4,AUGUST2009II.RELATEDWORKANDCONTRIBUTIONSTheprimarycontributionofthispaperisthepresentationofsimplecontrollawstoachieveparallelandcircularformationsthatrequireonlyvisualsensing,i.e.,theinputsareintermsofquantitiesthatdonotrequirecommunicationamongnearestneighbors.IncontrastwiththeworkofJusthandKrishnaprasad17,MoshtaghandJadbabaie27,Paleyetal.32,33,andSepulchreetal.35,whereitisassumedthateachagenthasaccesstothevaluesofitsneighborspositionsandvelocities,wedesigndistributedcontrollawsthatuseonlyvisualcluesfromnearestneighborstoachievemotioncoordination.Ourapproachonderivingthevision-basedcontrollawscanbeclassifiedasanimage-basedvisualseroving41.Inimage-basedvisualservoing,featuresareextractedfromimages,andthenthecontrolinputiscomputedasafunctionoftheimagefeatures.In8,12,and38,authorsuseomnidirectionalcam-erasastheonlysensorforrobots.In8and38,inputoutputfeedbacklinearizationisusedtodesigncontrollawsforleader-followingandobstacleavoidance.However,theyassumethataspecificverticalposeofanomnidirectionalcameraallowsthecomputationofbothbearinganddistance.IntheworkofPrattichizzoetal.12,thedistancemeasurementisnotused；however,theleaderusesextendedKalmanfilteringtolocalizeitsfollowers,andcomputesthecontrolinputsandguidestheformationinacentralizedfashion.Inourpaper,thecontrolar-chitectureisdistributed,andwedesigntheformationcontrollersbasedonthelocalinteractionamongtheagentssimilartothatof14and22.Furthermore,forourvision-basedcontrollers,nodistancemeasurementisrequired.In25and34,circularformationsofamultivehiclesys-temundercyclicpursuitisstudied.Theirproposedstrategyisdistributedandsimplebecauseeachagentneedstomeasuretherelativeinformationfromonlyoneotheragent.Itisalsoshownthattheformationequilibriaofthemultiagentsystemaregeneralizedpolygons.Incontrastto25,ourcontrollawisanonlinearfunctionofthebearingangles,andasaresult,oursystemconvergestoadifferentsetofstableequilibria.III.BACKGROUNDInthissection,webrieflyreviewanumberofimportantcon-ceptsregardinggraphtheoryandregularpolygonsthatweusethroughoutthispaper.A.GraphTheoryAn(undirected)graphGconsistsofavertexsetVandanedgesetE,whereanedgeisanunorderedpairofdistinctverticesinG.Ifx,yVand(x,y)E,thenxandyaresaidtobeadjacent,orneighbors,andwedenotethisbywritingxy.Thenumberofneighborsofeachvertexisitsdegree.Apathoflengthrfromvertexxtovertexyisasequenceofr+1distinctverticesthatstartwithxandendwithysuchthatconsecutiveverticesareadjacent.IfthereisapathbetweenanytwoverticesofagraphG,thenGissaidtobeconnected.TheadjacencymatrixA(G)=aijofan(undirected)graphGisasymmetricmatrixwithrowsandcolumnsindexedbytheverticesofG,suchthataij=1ifvertexiandvertexjareneighbors,andaij=0otherwise.Wealsoassumethataii=0foralli.ThedegreematrixD(G)ofagraphGisadiagonalmatrixwithrowsandcolumnsindexedbyV,inwhichthe(i,i)-entryisthedegreeofvertexi.ThesymmetricsingularmatrixdefinedasL(G)=D(G)A(G)iscalledtheLaplacianofG.TheLaplacianmatrixcapturesmanytopologicalpropertiesofthegraph.TheLaplacianLisapositive-semidefinitematrix,andthealgebraicmultiplicityofitszeroeigenvalue(i.e.,thedimensionofitskernel)isequaltothenumberofconnectedcomponentsinthegraph.Then-dimensionaleigenvectorassociatedwiththezeroeigenvalueisthevectorofones,1n=1,.,1T.Formoreinformationongraphtheory,see13.B.RegularPolygonsLetd<nbeapositiveinteger,anddefinep=n/d.Lety1beapointontheunitcircle.LetRbeclockwiserotationbytheangle=2/p.Thegeneralizedregularpolygonpisgivenbythepointsyi+1=Ryiandedgesbetweenpointsiandi+1.Whend=1,thepolygonpiscalledanordinaryregularpolygon,anditsedgesdonotintersect.Ifd>1andnanddarecoprime,thentheedgesintersect,andthepolygonisastar.Ifnanddhaveacommonfactorl>1,thenthepolygonconsistsofltraversalsofthesamepolygonwithn/lverticesandedges.Ifd=n,thepolygonn/ncorrespondstoallpointsatthesamelocation.Ifd=n/2(withneven),thenthepolygonconsistsoftwoendpointsandalinebetweenthem,withpointshavinganevenindexononeendandpointshavinganoddindexontheother.Formoreinformationonregulargraphs,see7.IV.PROBLEMSTATEMENTConsideragroupofnunit-speedplanaragents.Eachagentiscapableofsensinginformationfromitsneighbors.Theneigh-borhoodsetofagenti,thatis,Ni,isthesetofagentsthatcanbe“seen”byagenti.Theprecisemeaningof“seeing”willbeclarifiedlater.Thesizeoftheneighborhooddependsonthechar-acteristicsofthesensors.TheneighboringrelationshipbetweenagentscanbeconvenientlydescribedbyaconnectivitygraphG=(V,E,W).Definition1(Connectivitygraph):TheconnectivitygraphG=(V,E,W)isagraphconsistingof1)asetofverticesVindexedbythesetofmobileagents；2)asetofedgesE=(i,j)|i,jV,andij；3)asetofpositiveedgeweightsforeachedge(i,j).TheneighborhoodofagentiisdefinedbyNi.=j|ijVi.Letrirepresentthepositionofagenti,andletvibeitsvelocityvector.Thekinematicsofeachunit-speedagentisAuthorizedlicenseduselimitedto:NanchangUniversity.DownloadedonJanuary12,2010at20:02fromIEEEXplore.Restrictionsapply.MOSHTAGHetal.:VISION-BASED,DISTRIBUTEDCONTROLLAWSFORMOTIONCOORDINATIONOFNONHOLONOMICROBOTS853Fig.1.TrajectoryofeachagentisrepresentedbyaplanarFrenetframe.givenbyri=vivi=ivivi=ivi(1)whereviistheunitvectorperpendiculartothevelocityvectorvi(seeFig.1).Theorthogonalpairvi,viformsabodyframeforagenti.Werepresentthestackvectorofallthevelocitiesbyv=vT1,.,vTnTR2n×1.Thecontrolinputforeachagentistheangularvelocityi.Sinceitisassumedthattheagentsmovewithconstantunitspeed,theforceappliedtoeachagentmustbeperpendiculartoitsvelocityvector,i.e.,theforceoneachagentisagyroscopicforce,anditdoesnotchangeitsspeed(andhence,itskineticenergy).Thus,iservesasasteeringcontrol16foreachagent.Letusformallydefinetheformationsthatwearegoingtoconsider.Definition2(Parallelformation):Theconfigurationinwhichtheheadingsofallagentsarethesameandvelocityvectorsarealignediscalledtheparallelformation.Notethatinthisdefinition,wedonotconsiderthevalueoftheagreeduponvelocitybutjustthefactthattheagreementhasbeenreached.Attheequilibrium,therelativedistancesoftheagentsdeterminetheshapeoftheformation.Anotherinterestingfamilyofformationsisthebalancedcircularformation.Definition3(Balancedcircularformation):Theconfigurationwheretheagentsaremovingonthesamecirculartrajectoryandthegeometriccenteroftheagentsisfixediscalledthebalancedcircularformation.Theshapeofsuchaformationcanberepresentedbyanappropriateregularpolygon.Inthefollowingsections,westudyeachformationanddesignitscorrespondingdistributedcontrollaw.V.PARALLELFORMATIONSOurgoalinthissectionistodesignacontrollawforeachagentsothattheheadingsofthemobileagentsreachanagree-ment,i.e.,theirvelocityvectorsarealigned,thusresultinginaswarm-likepattern.ForanarbitraryconnectivitygraphG,con-sidertheLaplacianmatrixL.We,therefore,defineameasureofmisalignmentasfollows27,35:w(v)=12summationdisplayij|vivj|2=12v,¯Lv(2)wherethesummationisoverallthepairs(i,j)E,and¯L=LI2R2n×2n,withI2beingthe2×2identitymatrix.Thetimederivativeofw(v)isgivenbyw(v)=nsummationdisplayi=1vi,(¯Lv)i=nsummationdisplayi=1ivi,(¯Lv)iwhere(¯Lv)iR2isthesubvectorof¯Lvassociatedwiththeithagent.Thus,thefollowinggradientcontrollawguaranteesthatthepotentialw(v)decreasesmonotonically:i=vi,(¯Lv)i=summationdisplayjNivi,vij(3)where<0isthegain,andvij=vjvi.Remark1:Letirepresenttheheadingofagentiasmeasuredinafixedworldframe(seeFig.1).Theunitvelocityvectorvianditsorthogonalvectorviaregivenbyvi=cosisiniTandvi=sinicosiT.Thus,thecontrolinput(3)becomesi=summationdisplayjNisin(ij),<0.(4)ItisworthnotingthattheproposedcontrolleristheoneusedinthesynchronizationoftheKuramotomodelofcouplednonlinearoscillators,whichhasbeenextensivelystudiedinmathematicalphysicsaswellascontrolcommunities15,19,36.Thesamemodelhasalsobeenusedforphaseregulationofcyclicroboticsystems18.Wehavethefollowingtheorem27thatprovidesasufficientconditiontoobtainaparallelformation.Theorem1:Considerasystemofnunit-speedagentswithdynamics(1).Iftheunderlyingconnectivitygraphremainsfixedandconnected,thenbyapplyingcontrolinput(4),thesystemconvergestotheequilibriaof=1···nT=0.Furthermore,thevelocityconsensussetislocallyattractiveifi(/2,/2).Proof1:See27fortheproof.squaresolidThevelocityconsensussetisthesetofstateswherealltheagentshavethesamevelocityvectors,anditcorrespondstotheparallelformation,whichisdefinedinDefinition2.Notethati(/2,/2)i=1,.,nisthesufficientcondi-tionthatrestrictstheinitialheadingstoahalf-circle.Theresultscanbeextendedtographswithswitchingtopology,asshownin27.VI.BALANCEDCIRCULARFORMATIONSThecircularformationisacircularrelativeequilibriuminwhichalltheagentstravelaroundthesamecircle.Wearein-terestedinbalancedcircularformations,whicharedefinedinDefinition3.Attheequilibrium,therelativeheadingsandtherelativedistancesoftheagentsdeterminetheshapeofthefor-mation,whichcanbeeasilydescribedbyaregularpolygon.Letcirepresentthepositionofthecenteroftheithcirclewithradius1/o,asshowninFig.2；thusci=ri+parenleftbigg1oparenrightbiggvi.Authorizedlicenseduselimitedto:NanchangUniversity.DownloadedonJanuary12,2010at20:02fromIEEEXplore.Restrictionsapply.854IEEETRANSACTIONSONROBOTICS,VOL.25,NO.4,AUGUST2009Fig.2.Centerofthecirculartrajectoryisdefinedasci=ri+(1/0)vi.Fig.3.Byachangeofcoordinatezi=o(rici)=vi,theproblemofgeneratingcircularmotionintheplanereducestotheproblemofbalancingtheagentsonacircle.Theshapecontrolsfordrivingagentstoacircularformationdependontheshapevariablesvij=vjviandrij=rjri.Therelativeequilibriaofthebalancedformationarecharacter-izedbysummationtextni=1vi=0andci=coR2foralli1,.,n,wherecoisthefixedgeometriccenteroftheagents.Thecontrolinputforeachagenthastwocomponents,whicharegivenbyi=o+ui.Theconstantangularvelocityotakestheagentsintoacir-cularmotion,anduisetstheagentsintoabalancedstate.Inordertodesignui,weexpressthesysteminarotatingframe,whichgreatlysimplifiestheanalysis.Bythechangeofvariablezi=o(rici)=vitheproblemreducestobalancingtheagentsonaunitcircle,asshowninFig.3.Thenewcoordinatesystemrotateswithangularvelocityo.Thedynamicsintherotatingframearegivenbyzi=viuivi=ziui,i=1,.,n.(5)Unitvectorziisnormaltothevelocityvector.However,intherotatingframe,zirepresentsthepositionofagentiontheunitcircle,whichismovingwithspeedui(seeFig.3).Letusdefinezij=zjziandqij=zij/|zij|astheunitvectoralongthenewrelativepositionvectorzij.Atthebal-ancedstate,thevelocityofeachagentisperpendicularto¯qi=summationtextjNiqij,whichisavectoralongtheaverageoftherelativepositionvectorsincidenttoagenti.Thus,thequantityvi,¯qivanishesatthebalancedstate.Hence,weproposethefollowingcontrollawforthebalancedcircularformation:ui=vi,¯qi=summationdisplayjNivi,qij,>0.(6)Thefollowingtwotheorems28presenttheresultswhenbalancedcircularformationsareattainedforagroupofunit-speedagentswithfixedconnectivitygraphs.Theorem2isforthecasewhenGisacompletegraph,andTheorem3isfortheringgraph.Theorem2:Considerasystemofnagentswithkinematics(5).GivenacompleteconnectivitygraphGandapplyingcontrollaw(6),then-agentsystem(almost)globallyasymptoticallyconvergestoabalancedcircularformation,whichisdefinedinDefinition3.Proof:See28fortheproof.squaresolidThereasonfor“almostglobal”stabilityofthesetofbal-ancedstatesisthatthereisameasure-zerosetofstateswheretheequilibriumisunstable.Thissetischaracterizedbythoseconfigurationsthatmagentsareatantipodalpositionfromtheothernmagents,where1m<n/2.Next,weconsiderthesituationthattheconnectivitygraphhasaringtopologyGring.Theorem3:Considerasystemofnagentswithkinematics(5).SupposetheconnectivitygraphhastheringtopologyGringandthateachagentappliesthebalancingcontrollaw(6).Then,therelativeheadingswillconvergetothesameangleo.Ifo(/2,3/2),thebalancedstateislocallyexponentiallystable.Proof:See28fortheproof.squaresolidAttheequilibrium,thefinalconfigurationforGringisareg-ularpolygonn/dinwhichtherelativeanglebetweentwoconnectednodesiso=2d/n.FromTheorem3,ifthisan-glesatisfieso(/2,3/2),thenthebalancedstateisstable.Thus,thestableconfigurationcorrespondstoapolygonwithd(n/4,3n/4).Forexample,forn=5,thestableformationsarepolygons5/3and5/4,whicharethesamepolygonsasobtainedwithreverseorderingofthenodes.Forn=4,thestableformationis4/2.Actually,simulationssuggestthatthelargestregionofattractionfornevenbelongstoapolygonn/d,withd=n/2,andfornodd,itisastarpolygonn/d,withd=(n±1)/2.VII.VISION-BASEDCONTROLLAWSNotethatthecontrolinputs(4)and(6)forparallelandcir-cularformationsdependontheshapevariables,i.e.,relativeheadingsandpositions,whicharenotdirectlymeasurableusingvisualsensors,suchasasinglecameraonarobot,becausees-timationoftherelativepositionandmotionrequiresbinocularvision.Thismotivatesustorewriteinputs(4)and(6)intermsofparametersthatareentirelymeasurableusingasimplevisualsensor.Next,wedefinethevisualparametersthatwewillusetoderivethevision-basedcontrollaws.BearingangleLetri=xiyiTbethelocationofagentiinafixedworldframe,andletvi=xiyiTbeitsvelocityvector.Theheadingororientationofagentiisthengivenbyi=atan2(yi,xi).(7)Authorizedlicenseduselimitedto:NanchangUniversity.DownloadedonJanuary12,2010at20:02fromIEEEXplore.Restrictionsapply.