1、IEEETRANSACTIONSONROBOTICS/VOL/25/NO/4/AUGUST2009851Vision-Based/DistributedControlLawsforMotionCoordinationofNonholonomicRobotsNimaMoshtagh/Member/IEEE/NathanMichael/Member/IEEE/AliJadbabaie/SeniorMember/IEEE/andKostasDaniilidis/SeniorMember/IEEEAbstractInthispaper/westudytheproblemofdistributedmo-
2、tioncoordinationamongagroupofnonholonomicgroundrobots/Wedevelopvision-basedcontrollawsforparallelandbalancedcir-cularformationsusingaconsensusapproach/Theproposedcon-trollawsaredistributedinthesensethattheyrequireinformationonlyfromneighboringrobots/Furthermore/thecontrollawsarecoordinate-freeanddon
3、otrelyonmeasurementorcommunica-tionofheadinginformationamongneighborsbutinsteadrequiremeasurementsofbearing/opticalflow/andtimetocollision/allofwhichcanbemeasuredusingvisualsensors/Collision-avoidancecapabilitiesareaddedtotheteammembers/andtheeffectivenessofthecontrollawsaredemonstratedonagroupofmob
4、ilerobots/IndexTermsCooperativecontrol/distributedcoordination/vision-basedcontrol/I/INTRODUCTIONCOOPERATIVEcontrolofmultipleautonomousagentshasbecomeavibrantpartofroboticsandcontroltheoryresearch/Themainunderlyingthemeofthislineofresearchistoanalyzeand/orsynthesizespatiallydistributedcontrolar-chit
5、ecturesthatcanbeusedformotioncoordinationoflargegroupsofautonomousvehicles/Someofthisresearchfocussesonflockingandformationcontrol9/14/16/22/31/andsynchronization2/39/whileothersfocusonrendezvous/distributedcoverage/anddeployment1/5/Akeyassump-tionimpliedinallofthepreviousreferencesisthateachvehicle
6、orrobot(hereaftercalledanagent)communicatesitspositionand/orvelocityinformationtoitsneighbors/Inspiredbythesocialaggregationphenomenainbirdsandfish6/30/researchersinroboticsandcontroltheoryhaveManuscriptreceivedFebruary23/2008；revisedJanuary31/2009/Firstpub-lishedJune10/2009；currentversionpublishedJ
7、uly31/2009/ThispaperwasrecommendedforpublicationbyAssociateEditorZ/-W/LuoandEdi-torJ/-P/Laumonduponevaluationofthereviewerscomments/TheworkofA/JadbabaiewassupportedinpartbytheArmyResearchOfficeMultidisciplinaryUniversityResearchInitiative(ARO/MURI)underGrantW911NF-05-1-0381/inpartbytheOfficeofNavalR
8、esearch(ONR)/YoungIn-vestigatorProgram542371/inpartbyONRN000140610436/andinpartunderContractNSF-ECS-0347285/TheworkofK/DaniilidiswassupportedinpartunderContractNSF-IIS-0083209/inpartunderContractNSF-IIS-0121293/inpartunderContractNSF-EIA-0324977/andinpartunderContractARO/MURIDAAD19-02-1-0383/N/Mosht
9、aghwaswiththeGeneralRobotics/Automation/Sensing/andPer-ceptionLaboratory/UniversityofPennsylvania/Philadelphia/PA19104USA/HeisnowwithScientificSystemsCompany/Inc//Woburn/MA01801USA(e-mail/)/N/Michael/A/Jadbabaie/andK/DaniilidisarewiththeGeneralRobotics/Automation/Sensing/andPerceptionLaboratory/Univ
10、ersityofPennsylva-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/andalgorithm
11、sfordistributedmo-tioncoordinationofmultivehiclesystems/Twomaincollectivemotionsthatareobservedinnatureareparallelmotionandcircularmotion21/Onecaninterpretstabilizingthecircularformationasanexampleofactivityconsensus/i/e//individualsare“movingaround”together/Stabilizingtheparallelforma-tionisanother
12、formofactivityconsensusinwhichindividuals“moveoff”together33/Circularformationsareobservedinfishschooling/whichisawell-studiedtopicinecologyandevolutionarybiology6/Inthispaper/wepresentasetofcontrollawsforcoordinatedmotions/suchasparallelandcircularformations/foragroupofplanaragentsusingpurelylocali
13、nteractions/Thecontrollawsareintermsofshapevariables/suchastherelativedistancesandrelativeheadingsamongtheagents/However/theseparam-etersarenotreadilymeasurableusingsimpleandbasicsensingcapabilities/Thismotivatestherewritingofthederivedcontrollawsintermsofbiologicallymeasurableparameters/Eachagentis
14、assumedtohaveonlymonocularvisionandisalsocapableofmeasuringbasicvisualquantities/suchasbearingangle/opti-calflow(bearingderivative)/andtimetocollision/Rewritingthecontrolinputsintermsofquantitiesthatarelocallymeasurableisequivalenttoexpressingtheinputsinthelocalbodyframe/Suchachangeofcoordinatesyste
15、mfromaglobalframetoalocalframeprovidesuswithabetterintuitiononhowsimilarbehaviorsarecarriedoutinnature/Verificationofthetheorythroughmultirobotexperimentsdemonstratedtheeffectivenessofthevision-basedcontrollawstoachievethedesiredformations/Ofcourse/inreality/anyformationcontrolrequirescollisionavoid
16、ance/andindeed/collisionavoidancecannotbedonewithoutrange/Inordertoimprovetheexperimentalresults/weprovidedinteragent-collision-avoidancepropertiestotheteammembers/Inthispaper/weshowthatthetwotasksofformationkeepingandcollisionavoidancecanbedonewithdecoupledadditivetermsinthecontrollaw/wheretheterms
17、forkeepingparallelandcircularformationsdependonlyonvisualparameters/Thispaperisorganizedasfollows/InSectionII/wereviewanumberofimportantrelatedworks/Somebackgroundinfor-mationongraphtheoryandothermathematicaltoolsusedinthispaperareprovidedinSectionIII/TheproblemstatementisgiveninSectionIV/InSections
18、VandVI/wepresentthecontrollersthatstabilizeagroupofmobileagentsintoparallelandbalancedcircularformations/respectively/InSectionVII/wederivethevision-basedcontrollersthatareintermsofthevisualmeasurementsoftheneighboringagents/InSectionVIII/collision-avoidancecapabilitiesareaddedtothecontrollaws/andth
19、eireffectivenessistestedonrealrobots/1552-3098/$26/002009IEEEAuthorizedlicenseduselimitedto/NanchangUniversity/DownloadedonJanuary12/2010at20/02fromIEEEXplore/Restrictionsapply/852IEEETRANSACTIONSONROBOTICS/VOL/25/NO/4/AUGUST2009II/RELATEDWORKANDCONTRIBUTIONSTheprimarycontributionofthispaperisthepre
20、sentationofsimplecontrollawstoachieveparallelandcircularformationsthatrequireonlyvisualsensing/i/e//theinputsareintermsofquantitiesthatdonotrequirecommunicationamongnearestneighbors/IncontrastwiththeworkofJusthandKrishnaprasad17/MoshtaghandJadbabaie27/Paleyetal/32/33/andSepulchreetal/35/whereitisass
21、umedthateachagenthasaccesstothevaluesofitsneighborspositionsandvelocities/wedesigndistributedcontrollawsthatuseonlyvisualcluesfromnearestneighborstoachievemotioncoordination/Ourapproachonderivingthevision-basedcontrollawscanbeclassifiedasanimage-basedvisualseroving41/Inimage-basedvisualservoing/feat
22、uresareextractedfromimages/andthenthecontrolinputiscomputedasafunctionoftheimagefeatures/In8/12/and38/authorsuseomnidirectionalcam-erasastheonlysensorforrobots/In8and38/inputoutputfeedbacklinearizationisusedtodesigncontrollawsforleader-followingandobstacleavoidance/However/theyassumethataspecificver
23、ticalposeofanomnidirectionalcameraallowsthecomputationofbothbearinganddistance/IntheworkofPrattichizzoetal/12/thedistancemeasurementisnotused；however/theleaderusesextendedKalmanfilteringtolocalizeitsfollowers/andcomputesthecontrolinputsandguidestheformationinacentralizedfashion/Inourpaper/thecontrol
24、ar-chitectureisdistributed/andwedesigntheformationcontrollersbasedonthelocalinteractionamongtheagentssimilartothatof14and22/Furthermore/forourvision-basedcontrollers/nodistancemeasurementisrequired/In25and34/circularformationsofamultivehiclesys-temundercyclicpursuitisstudied/Theirproposedstrategyisd
25、istributedandsimplebecauseeachagentneedstomeasuretherelativeinformationfromonlyoneotheragent/Itisalsoshownthattheformationequilibriaofthemultiagentsystemaregeneralizedpolygons/Incontrastto25/ourcontrollawisanonlinearfunctionofthebearingangles/andasaresult/oursystemconvergestoadifferentsetofstableequ
26、ilibria/III/BACKGROUNDInthissection/webrieflyreviewanumberofimportantcon-ceptsregardinggraphtheoryandregularpolygonsthatweusethroughoutthispaper/A/GraphTheoryAn(undirected)graphGconsistsofavertexsetVandanedgesetE/whereanedgeisanunorderedpairofdistinctverticesinG/Ifx/yVand(x/y)E/thenxandyaresaidtobea
27、djacent/orneighbors/andwedenotethisbywritingxy/Thenumberofneighborsofeachvertexisitsdegree/Apathoflengthrfromvertexxtovertexyisasequenceofr+1distinctverticesthatstartwithxandendwithysuchthatconsecutiveverticesareadjacent/IfthereisapathbetweenanytwoverticesofagraphG/thenGissaidtobeconnected/Theadjace
28、ncymatrixA(G)=aijofan(undirected)graphGisasymmetricmatrixwithrowsandcolumnsindexedbytheverticesofG/suchthataij=1ifvertexiandvertexjareneighbors/andaij=0otherwise/Wealsoassumethataii=0foralli/ThedegreematrixD(G)ofagraphGisadiagonalmatrixwithrowsandcolumnsindexedbyV/inwhichthe(i/i)-entryisthedegreeofv
29、ertexi/ThesymmetricsingularmatrixdefinedasL(G)=D(G)A(G)iscalledtheLaplacianofG/TheLaplacianmatrixcapturesmanytopologicalpropertiesofthegraph/TheLaplacianLisapositive-semidefinitematrix/andthealgebraicmultiplicityofitszeroeigenvalue(i/e//thedimensionofitskernel)isequaltothenumberofconnectedcomponents
30、inthegraph/Then-dimensionaleigenvectorassociatedwiththezeroeigenvalueisthevectorofones/1n=1///1T/Formoreinformationongraphtheory/see13/B/RegularPolygonsLetd1andnanddarecoprime/thentheedgesintersect/andthepolygonisastar/Ifnanddhaveacommonfactorl1/thenthepolygonconsistsofltraversalsofthesamepolygonwit
31、hn/lverticesandedges/Ifd=n/thepolygonn/ncorrespondstoallpointsatthesamelocation/Ifd=n/2(withneven)/thenthepolygonconsistsoftwoendpointsandalinebetweenthem/withpointshavinganevenindexononeendandpointshavinganoddindexontheother/Formoreinformationonregulargraphs/see7/IV/PROBLEMSTATEMENTConsideragroupof
32、nunit-speedplanaragents/Eachagentiscapableofsensinginformationfromitsneighbors/Theneigh-borhoodsetofagenti/thatis/Ni/isthesetofagentsthatcanbe“seen”byagenti/Theprecisemeaningof“seeing”willbeclarifiedlater/Thesizeoftheneighborhooddependsonthechar-acteristicsofthesensors/Theneighboringrelationshipbetw
33、eenagentscanbeconvenientlydescribedbyaconnectivitygraphG=(V/E/W)/Definition1(Connectivitygraph)/TheconnectivitygraphG=(V/E/W)isagraphconsistingof1)asetofverticesVindexedbythesetofmobileagents；2)asetofedgesE=(i/j)|i/jV/andij；3)asetofpositiveedgeweightsforeachedge(i/j)/Theneighborhoodofagentiisdefined
34、byNi/=j|ijVi/Letrirepresentthepositionofagenti/andletvibeitsvelocityvector/Thekinematicsofeachunit-speedagentisAuthorizedlicenseduselimitedto/NanchangUniversity/DownloadedonJanuary12/2010at20/02fromIEEEXplore/Restrictionsapply/MOSHTAGHetal//VISION-BASED/DISTRIBUTEDCONTROLLAWSFORMOTIONCOORDINATIONOFN
35、ONHOLONOMICROBOTS853Fig/1/TrajectoryofeachagentisrepresentedbyaplanarFrenetframe/givenbyri=vivi=ivivi=ivi(1)whereviistheunitvectorperpendiculartothevelocityvectorvi(seeFig/1)/Theorthogonalpairvi/viformsabodyframeforagenti/Werepresentthestackvectorofallthevelocitiesbyv=vT1///vTnTR2n1/Thecontrolinputf
36、oreachagentistheangularvelocityi/Sinceitisassumedthattheagentsmovewithconstantunitspeed/theforceappliedtoeachagentmustbeperpendiculartoitsvelocityvector/i/e//theforceoneachagentisagyroscopicforce/anditdoesnotchangeitsspeed(andhence/itskineticenergy)/Thus/iservesasasteeringcontrol16foreachagent/Letus
37、formallydefinetheformationsthatwearegoingtoconsider/Definition2(Parallelformation)/Theconfigurationinwhichtheheadingsofallagentsarethesameandvelocityvectorsarealignediscalledtheparallelformation/Notethatinthisdefinition/wedonotconsiderthevalueoftheagreeduponvelocitybutjustthefactthattheagreementhasb
38、eenreached/Attheequilibrium/therelativedistancesoftheagentsdeterminetheshapeoftheformation/Anotherinterestingfamilyofformationsisthebalancedcircularformation/Definition3(Balancedcircularformation)/Theconfigurationwheretheagentsaremovingonthesamecirculartrajectoryandthegeometriccenteroftheagentsisfix
39、ediscalledthebalancedcircularformation/Theshapeofsuchaformationcanberepresentedbyanappropriateregularpolygon/Inthefollowingsections/westudyeachformationanddesignitscorrespondingdistributedcontrollaw/V/PARALLELFORMATIONSOurgoalinthissectionistodesignacontrollawforeachagentsothattheheadingsofthemobile
40、agentsreachanagree-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/andL=
41、LI2R2n2n/withI2beingthe22identitymatrix/Thetimederivativeofw(v)isgivenbyw(v)=nsummationdisplayi=1vi/(Lv)i=nsummationdisplayi=1ivi/(Lv)iwhere(Lv)iR2isthesubvectorofLvassociatedwiththeithagent/Thus/thefollowinggradientcontrollawguaranteesthatthepotentialw(v)decreasesmonotonically/i=vi/(Lv)i=summationd
42、isplayjNivi/vij(3)where0isthegain/andvij=vjvi/Remark1/Letirepresenttheheadingofagentiasmeasuredinafixedworldframe(seeFig/1)/Theunitvelocityvectorvianditsorthogonalvectorviaregivenbyvi=cosisiniTandvi=sinicosiT/Thus/thecontrolinput(3)becomesi=summationdisplayjNisin(ij)/0/(6)Thefollowingtwotheorems28pr
43、esenttheresultswhenbalancedcircularformationsareattainedforagroupofunit-speedagentswithfixedconnectivitygraphs/Theorem2isforthecasewhenGisacompletegraph/andTheorem3isfortheringgraph/Theorem2/Considerasystemofnagentswithkinematics(5)/GivenacompleteconnectivitygraphGandapplyingcontrollaw(6)/then-agent
44、system(almost)globallyasymptoticallyconvergestoabalancedcircularformation/whichisdefinedinDefinition3/Proof/See28fortheproof/squaresolidThereasonfor“almostglobal”stabilityofthesetofbal-ancedstatesisthatthereisameasure-zerosetofstateswheretheequilibriumisunstable/Thissetischaracterizedbythoseconfigur
45、ationsthatmagentsareatantipodalpositionfromtheothernmagents/where1mn/2/Next/weconsiderthesituationthattheconnectivitygraphhasaringtopologyGring/Theorem3/Considerasystemofnagentswithkinematics(5)/SupposetheconnectivitygraphhastheringtopologyGringandthateachagentappliesthebalancingcontrollaw(6)/Then/t
46、herelativeheadingswillconvergetothesameangleo/Ifo(/2/3/2)/thebalancedstateislocallyexponentiallystable/Proof/See28fortheproof/squaresolidAttheequilibrium/thefinalconfigurationforGringisareg-ularpolygonn/dinwhichtherelativeanglebetweentwoconnectednodesiso=2d/n/FromTheorem3/ifthisan-glesatisfieso(/2/3
47、/2)/thenthebalancedstateisstable/Thus/thestableconfigurationcorrespondstoapolygonwithd(n/4/3n/4)/Forexample/forn=5/thestableformationsarepolygons5/3and5/4/whicharethesamepolygonsasobtainedwithreverseorderingofthenodes/Forn=4/thestableformationis4/2/Actually/simulationssuggestthatthelargestregionofat
48、tractionfornevenbelongstoapolygonn/d/withd=n/2/andfornodd/itisastarpolygonn/d/withd=(n1)/2/VII/VISION-BASEDCONTROLLAWSNotethatthecontrolinputs(4)and(6)forparallelandcir-cularformationsdependontheshapevariables/i/e//relativeheadingsandpositions/whicharenotdirectlymeasurableusingvisualsensors/suchasas
49、inglecameraonarobot/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/