外文翻譯---實(shí)時(shí)自適應(yīng)運(yùn)動(dòng)規(guī)劃在動(dòng)態(tài)環(huán)境下移動(dòng)機(jī)器人無(wú)法預(yù)見(jiàn)的變化 英文版.pdf

IEEETRANSACTIONSONROBOTICS,VOL.24,NO.5,OCTOBER20081199Real-TimeAdaptiveMotionPlanning(RAMP)ofMobileManipulatorsinDynamicEnvironmentsWithUnforeseenChangesJohnVannoyandJingXiao,SeniorMember,IEEEAbstractThispaperintroducesanovelandgeneralreal-timeadaptivemotionplanning(RAMP)approachsuitableforplan-ningtrajectoriesofhigh-DOForredundantrobots,suchasmobilemanipulators,indynamicenvironmentswithmovingobstaclesofunknowntrajectories.TheRAMPapproachenablessimultaneouspathandtrajectoryplanningandsimultaneousplanningandexe-cutionofmotioninrealtime.Itfacilitatesreal-timeoptimizationoftrajectoriesundervariousoptimizationcriteria,suchasmin-imizingenergyandtimeandmaximizingmanipulability.Italsoaccommodatespartiallyspecifiedtaskgoalsofrobotseasily.Theapproachexploitsredundancyinredundantrobots(suchaslo-comotionversusmanipulationinamobilemanipulator)throughloosecouplingofrobotconfigurationvariablestobestachieveob-stacleavoidanceandoptimizationobjectives.TheRAMPapproachhasbeenimplementedandtestedinsimulationoveradiversesetoftaskenvironments,includingenvironmentswithmultiplemobilemanipulators.Theresults(andalsotheaccompanyingvideo)showthattheRAMPplanner,withitshighefficiencyandflexibility,notonlyhandlesasinglemobilemanipulatorwellindynamicenviron-mentswithvariousobstaclesofunknownmotionsinadditiontostaticobstacles,butcanalsoreadilyandeffectivelyplanmotionsforeachmobilemanipulatorinanenvironmentsharedbymultiplemobilemanipulatorsandothermovingobstacles.IndexTermsAdaptive,dynamicobstaclesofunknownmotion,loosecoupling,mobilemanipulators,partiallyspecifiedgoal,realtime,redundantrobots,trajectoryoptimization.I.INTRODUCTIONMOTIONPLANNINGisafundamentalprobleminrobotics1,2concernedwithdevisingadesirablemo-tionforarobottoreachagoal.Motionplanningforhigh-DOFarticulatedmanipulatorsormobilemanipulatorsismorechal-lengingthanformobilerobotsbecausethehigh-dimensionalconfigurationspaceofarobothaslittleornoresemblancetothephysicalspacethattherobotworksin,andhowtoconstructManuscriptreceivedMay16,2007；revisedDecember13,2007andMarch5,2008.FirstpublishedOctober10,2008；currentversionpublishedOctober31,2008.ThispaperwasrecommendedforpublicationbyAssociateEditorK.YamaneandEditorL.Parkeruponevaluationofthereviewerscomments.ApreliminarypartofthispaperwaspresentedattheIEEEInternationalCon-ferenceonIntelligentRobotsandSystems,Sendai,Japan,2004.TheauthorsarewiththeIntelligent,MultimediaandInteractiveSystems(IMI)Laboratory,DepartmentofComputerScience,UniversityofNorthCarolinaatCharlotte,Charlotte,NC28223USA(e-mail:；).Thispaperhassupplementarydownloadablematerialavailableat,providedbytheauthors:avideoshowingthereal-timeplanningandexecutionofmobilemanipulatormotionbyourRAMPalgorithm.Thisvideois14MBinsize.Colorversionsofoneormoreofthefiguresinthispaperareavailableonlineat.DigitalObjectIdentifier10.1109/TRO.2008.2003277aconfigurationspacehigherthanthreedimensionsefficientlyremainsalargelyunsolvedproblem.A.RelatedResearchonMotionPlanningRandomizedalgorithms,suchasthepopularprobabilisticroadmap(PRM)method3andrapidlyexploringrandomtree(RRT)method4,arefoundtobeveryeffectiveinfindingacollision-freepathforarobotwithhighDOFsofflinebe-causesuchalgorithmsavoidbuildingtherobotsconfigurationspaceexplicitlybysamplingtheconfigurationspace.ThePRMmethodhasinspiredconsiderableworkonimprovingsamplingandroadmapconstruction2,includingarecentpaper5onproducingcompactroadmapstobettercapturethedifferentho-motopicpathgroups.Bybuildingatreeratherthanagraph,theRRTmethodismoresuitableforgeneratingapathinoneshotorgeneratingatrajectorydirectlyandthusmoresuitableforonlineoperation6.Bothmethodshaveseenmanyvariants2.Therearealsomethodsforpathplanningbasedonge-neticalgorithms(GAs),ormorebroadly,evolutionarycom-putation7,8,whicharegeneralframeworksofrandomizedsearchsubjecttouser-definedoptimizationcriteria.Suchop-timizationtechniqueshavebeenusedwidelyandsuccessfullyinmanyapplicationdomains8,9totackleNP-hardopti-mizationproblems.Therearetwomajorwaysofapplications.Onestraightforwardwayistomapaproblemintotheformsuitableforastandard,off-the-shelfGA,solveitbyrunningtheGA,andthen,maptheresultsbacktotheapplicationdo-main.Thisone-size-fit-allapproachisoftennoteffectivebe-causeitforcesartificialtransformationofaproblemintosome-thingelsethatisconfinedintheformatofastandardGAbutmaylosecertainimportantnatureoftheoriginalproblem.SomeGA-basedpathplanningmethods10,11adoptsuchanap-proach,whereC-spaceisdiscretizedintoagrid,andapathisintermsofafixed-lengthsequenceofgridpoints.AsthestandardGAoperatesonfixed-lengthbitstrings,searchisoftenveryslow.Amoreeffectiveapproachistoadoptthegeneralideaofevolutionarycomputationtosolveaprobleminamorenaturalandsuitablerepresentation.Thepathplanningmethodsreportedin1214belongtosuchacustomizedapproach.Areal-timepathplanningmethodisreportedin12for2DOFpointmobilerobots,whichisextendedin13for3DOFpointflyingrobotswithspecificconstraints.Amultiresolutionpathrepresentationisproposedin14forpathplanning.However,allevolution-aryalgorithmshaveanumberofparametersthatmustbesetappropriately,whichisoftennotatrivialtask.1552-3098/$25.002008IEEE1200IEEETRANSACTIONSONROBOTICS,VOL.24,NO.5,OCTOBER2008Unlikepathplanning,motionplanninghastoproduceanexecutabletrajectoryforarobotinconfigurationtimespace,orCT-space,andnotmerelyageometricalpath.Acommonapproachistoconducttrajectoryplanningonthebasisofapathgeneratedbyapathplanner.Anotableframeworkistheelasticstripmethod15,whichcandeformatrajectoryforarobotlocallytoavoidmovingobstaclesinsideacollision-free“tunnel”thatconnectstheinitialandgoallocationsoftherobotina3-Dworkspace.Sucha“tunnel”isgeneratedfromadecomposition-basedpathplanningstrategy16.Theotherapproachistoconductpathandtrajectoryplanningsimultaneously.However,mosteffortinthiscategoryisfocusedonofflinealgorithmsassumingthattheenvironmentiscompletelyknownbeforehand,i.e.,staticobjectsareknown,andmovingobjectsareknownwithknowntrajectories1720.Asfordealingwithunknownmovingobstacles,onlyrecentlysomemethodswereintroducedformobilerobots21,22.Thecombinationofmobilityandmanipulationcapabilitymakesamobilemanipulatorapplicabletoamuchwiderrangeoftasksthanafixed-basemanipulatororamobilerobot.Foramobilemanipulator,ataskgoalstateisoftenpartiallyspecifiedaseitheraconfigurationoftheend-effector,whichwecallaplace-to-placetask,oradesiredpath(ortrajectory)oftheend-effector,whichwecallacontour-followingtask,andthetargetlocation/pathofthebaseisoftenunspecified.Here,amajorissueofmotionplanningisthecoordinationofthemobilebaseandthemanipulator.Thisissue,asitinvolvesredundancyresolution,presentsbothchallengesandopportu-nities.Thereexistsarichliteratureaddressingthisissuefrommanyaspects.Someresearcherstreatthemanipulatorandthemobilebasetogetherasaredundantrobotinplanningitspathforplace-to-placetasks2325.Somefocusedonplanningasequenceof“commutationconfigurations”forthemobilebasewhentherobotwastoperformasequenceoftasks26,27subjecttovariousconstraintsandoptimizationcriteria.Othersfocusedoncoordinatingthecontrolofthemobilebaseandthemanipulatorinacontour-followingtask28,29bytryingtopositionthemobilebasetomaximizemanipulability.Manyconsiderednonholonomicconstraints.Whilemostoftheexistingworkassumesknownenviron-mentswithknownobstaclesforamobilemanipulator,afewresearchersconsideredlocalcollisionavoidanceofunknown,movingobstaclesonline.Onemethod30usedRRTasalocalplannertoupdatearoadmaporiginallygeneratedbyPRMtodealwithmovingobstacles.Forcontour-followingtasks,anef-ficientmethod31allowsthebasetoadjustitspathtoavoidamovingobstacleifpossiblewhilekeepingtheend-effectorfol-lowingacontour,suchasastraightline.Anothermethod29allowedthebasetopauseinordertoletanunexpectedobsta-clepasswhilethearmcontinueditscontour-followingmotionunderanevent-basedcontrolscheme.Othermethodsincludeonebasedonpotentialfield32toavoidunknownobstaclesandonebasedonaneuro-fuzzycontroller33tomodifythebasemotionlocallytoavoidamovingobstaclestably.Thereisalsoanonlineplannerforthespecialpurposeofplanningthemotionsoftworobotarmsgettingpartsfromaconveyerbelt34.However,wearenotawareofanyexistingworkthatcanplanmotionsofhigh-DOFrobotsgloballyamongmanyunknowndynamicobstacles.B.OurProblemandApproachPlanninghigh-DOFrobotmotioninsuchanenvironmentofmanyunknowndynamicobstaclesposesspecialchallenges.First,planninghastobedoneinrealtime,cannotbedoneof-fline,andcannotbebasedonacertainprebuiltmapbecausetheenvironmentisconstantlychanginginunforeseenways,i.e.,theconfigurationspaceobstaclesareunknownandchanging.Examplesofsuchenvironmentsincludealargepublicsquarefullofpeoplemovingindifferentways,awarehousefullofbusy-movingrobotsandhumanworkers,andsoon.Suchanenvironmentisverydifferentfromstaticorlargelystaticenvi-ronmentsorknowndynamicenvironments(i.e.,withotherob-jecttrajectoriesknown),wheremotionplanningcanreasonablyrelyonexploringC-space(forknownstaticenvironments)orCT-space(forknowndynamicenvironments)offline(suchasbyPRM).Theelasticstripmethodprovidestheflexibilitytomakesmalladjustmentsofarobotmotiontoavoidunknownmotionsofobstacles,iftheunderlyingtopologyoftheC-spacedoesnotchange.ForanenvironmentwithchangingC-spacetopologyinunknownways,aplannedpath/trajectorycanbeinvalidatedcompletelyatanytime,andthus,real-timeadaptiveglobalplan-ningcapabilityisrequiredformakingdrasticchangesofrobotmotion.Planningandexecutionofmotionshouldbesimulta-neousandbasedonsensingsothatplanninghastobeveryfastandalwaysabletoadapttochangesoftheenvironment.Bynature,totacklemotionplanninginanunknowndynamicenvironmentcannotresultinacompleteplanningalgorithm.Thatis,noalgorithmcanguaranteesuccessinsuchanunknownenvironment.Wecanonlystriveforarationalalgorithmthatservesasthe“bestdriverofahigh-DOFrobot,buteventhebestdrivercannotguaranteetobeaccident-freeifotherthingsintheenvironmentarenotunderhis/hercontrol.Thispaperaddressestheproblemofreal-timesimultaneouspathandtrajectoryplanningofhigh-DOFrobots,suchasmobilemanipulators,performinggeneralplace-to-placetasksinadynamicenvironmentwithobstaclemotionsunknown.Theobstaclemotionscanobstructeitherthebaseorthearmorbothofamobilemanipulator.Weintroduceauniqueandgeneralreal-timeadaptivemotionplanning(RAMP)approach.OurRAMPapproachisbuiltuponboththeideaofrandomizedplanningandthatoftheanytime,parallel,andoptimizedplanningofevolutionarycomputation,whileavoidingthedrawbacks.Theresultisauniqueandoriginalapproacheffectivefortheconcernedproblem.TheRAMPapproachhasthefollowingcharacteristics.1)WholetrajectoriesarerepresentedatonceinCT-spaceandconstantlyimprovedduringsimultaneousplan-ningandexecution,unlikealgorithmsthatbuildapath/trajectorysequentially(orincrementally)sothatawholepath/trajectorycanbecomeavailableonlyattheendoftheplanningprocess.OuranytimeplannercanprovideavalidtrajectoryquicklyandcontinuetoproducebetterVANNOYANDXIAO:REAL-TIMEADAPTIVEMOTIONPLANNING(RAMP)OFMOBILEMANIPULATORSINDYNAMICENVIRONMENTS1201trajectoriesatanylatertimetosuittheneedofreal-timeglobalplanning.2)Differentoptimizationcriteria(suchasminimizingen-ergyandtimeandoptimizingmanipulability)canbeaccommodatedflexiblyandeasilyinaseamlessfash-ion.Optimizationisdonedirectlyintheoriginal,con-tinuousCT-spaceratherthanbeingconfinedtoacertainlimitedgraphorroadmap.Trajectoriesareplannedandoptimizeddirectlyratherthanconditionaltotheresultsofpathplanning.3)Ourplannerisintrinsicallyparallelwithmultiplediversetrajectoriespresentallthetimetoallowinstant,andifnecessary,drasticadjustmentofrobotmotiontoadapttonewlysensedchangesintheenvironment.Thisisdiffer-entfromplannerscapableofonlylocaltrajectoryadjust-mentbasedonaknownsetofhomotopicpaths.Itisalsodifferentfromsequentialplanners,suchasanytimeA*search35,whichalsorequiresbuildingadiscretestatespaceforsearchalimitationthatourplannerdoesnothave.4)Trajectorysearchandevaluation(ofitsoptimality)areconstantlyadaptivetochangesbutbuiltupontheresultsofprevioussearch(i.e.,knowledgeaccumulated)tobeefficientforreal-timeprocessing.5)Asplanningandexecution(i.e.,robotmotionfollowingtheplannedresultsofar)aresimultaneous,partiallyfeasi-bletrajectoriesareallowed,andtherobotmayfollowthefeasiblepartofsuchatrajectory(ifitisthecurrentbest)andswitchtoabettertrajectorytoavoidtheinfeasiblepart.6)Withmultipletrajectoriesfromourplanner,eachtrajec-torycanendatadifferentgoallocationinagoalregion,i.e.,partiallyspecifiedgoals,ratherthanasinglegoalcon-figuration.7)Ourplannerrepresentsatrajectoryforaredundantrobot,suchasamobilemanipulator,aslooselycoupledtrajec-toriesofredundantvariablestotakeadvantageofthere-dundancyinordertobestachieveobstacleavoidanceandvariousoptimizationobjectives.Therestofthepaperisorganizedasfollows.SectionIIpro-videsanoverviewofourRAMPapproach；SectionsIIIandIVdescribeproblemrepresentationandinitialization；SectionVoutlinesouroptimizationcriteriafortrajectoryevaluationanddescribesthestrategiesforevaluation.SectionsVIandVIIde-scribethestrategiestoaltertrajectoriestoproducebetterones.SectionVIIIdescribeshowtheRAMPplannercancreateandpreserveadiversesetoftrajectories.SectionIXprovidesim-plementationandexperimentationresultsanddiscussesperfor-manceoftheplanner.SectionXconcludesthepaper.II.OVERVIEWOFTHERAMPAPPROACHOnebasicpremiseofourapproachisthattheplanningprocessandtheexecutionofmotionareinterweavingtoenablesimul-taneousrobotmotionplanningandexecution.ThisisachievedthroughouranytimeplanningalgorithmthatalwaysmaintainsasetofcompletetrajectoriesintheCT-spaceoftherobotcalledapopulation.Thefeasibilityandoptimalityofeachtrajectory,calledfitness,isevaluatedthroughanevaluationfunctioncod-ingtheoptimizationcriteria.Feasibilityreferstocollision-freeandsingularity-free.Bothinfeasibleandfeasibletrajectoriesareallowedinapopulation.Feasibletrajectoriesareconsideredfit-terthaninfeasibletrajectories.Withineachtype,trajectoriesarecomparedforoptimalityinfitness.Theinitialpopulationisacombinationofrandomlygeneratedanddeliberatelyseededtrajectories.Deliberatelyseededtrajec-toriesincludeonesconstructedtorepresentdistinctsubpopula-tionsinordertoachievecertaindiversityinthepopulation.Iftheenvironmentcontainsknownstaticobstacles,trajectoriesbasedonpreplannedfeasiblepathswithrespecttotheknownstaticobstaclescanalsobeincluded.SeeSectionIVformoredetails.Oncetheinitialpopulationisformed,itisthenimprovedtoafitterpopulationthroughiterationsofimprovements,calledgen-erations.Ineachgeneration,atrajectoryisrandomlyselectedandalteredbyarandomlyselectedmodificationoperatoramonganumberofdifferentmodificationoperators,andtheresultingtrajectorymaybeusedtoreplaceatrajectorythatisnotthefittesttoformanewgeneration.Thefittesttrajectoryisalwayskeptinthepopulationandcanonlyimprovefromgenerationtogeneration.Eachgenerationisalsocalledaplanningcycle.Toimprovethefitnessoftheinitialpopulation,anumberofinitialplanningcyclesmayberunbasedontheinitialsensinginformationoftheenvironmentbeforetherobotbeginsexecut-ingthefittesttrajectory.Therobotneednotwaitforafeasibletrajectorytoemerge；ifnofeasibletrajectoryisavailable,therobotwillbeginmovingalongthefittestinfeasibletrajectorywhilecontinuingthesearchforafitter,andhopefullywilllocateafeasibletrajectorybeforeitcomeswithinadistancethresholdDofthefirstpredictedcollisionorsingularityoftheexecutedtrajectory.Thisstrategymakessensebecause:1)thepresentlypredictedinfeasibletrajectorymaybecomefeasiblelaterandviceversa；2)astobedescribedlater,ourplannermakestherobotswitchtoabettertrajectoryifoneisavailable,andthus,beforetheinfeasiblepartofthecurrentlyfollowedtrajectoryisencountered,therobotmayalreadyswitchtoabettertrajectory；3)thestrategyallowslimitedsensing,inwhichtherobotmaynotsenseanobstacleuntilgettingcloser；and4)itprovidesameasureofsafetyintrajectoryevaluation(seeSectionV).Astherobotmoves,planningcontinuestoimprovethepopu-lationoftrajectoriesuntilthenextcontrolcycle,whentherobotcanswitchtoafittertrajectorysothatitalwaysfollowsthebesttrajectory.Forthatpurpose,eachtrajectoryisalwaysupdatedtostartfromthecurrentrobotconfigurationwiththecurrentvelocitywhenanewcontrolcyclebegins.Forthetrajectorythatisbeingfollowed,thismeansthattheexecutedportionofthetrajectoryisdroppedfromthetrajectory,whileforeveryothertrajectory,itmeansthatonlythestartingconfigurationandve-locityarechangedtherestoftheknotpointsonthetrajectory(seeSectionIII)remainintact.Notethateachcontrolcycleheredoesnotnecessarilyhavetobeaservocycleofthelow-levelcontroller.Ourcontrolcycle,whichishighlevelforcontrollingtherateofadaptation,canbelongerthanaservocycletoensurethatwithinacontrolcycle,therecanbemorethanoneplanningcycle.Thisisbecauseadaptationisguidedbyplanning.1202IEEETRANSACTIONSONROBOTICS,VOL.24,NO.5,OCTOBER2008Fig.1.Relationshipamongplanning,control,andsensingcycles.Changesinadynamicenvironmentaresensedandfedtotheplannerineachsensingcycle,whichleadtoupdatedfitnessvaluesoftrajectoriesinthesubsequentplanningcycles,andunknownmotionsofmovingobstaclesarepredictedinfitnessevaluationofrobottrajectories.Thepresenceofadiversepopu-lationofever-improvingtrajectoriesenablestherobottoquicklyadapttochangesintheenvironment.Itdoessobyfollowingthefittesttrajectoryundereachcircumstance:whenthecurrenttra-jectorythattherobotfollowsbecomesworseorcannolongerbefollowedduetoimminentcollision(i.e.,thethresholdDisreached),therobotmaynotneedtostopitsmotionandreplanfromscratch；rathertheplanneroftenmerelyneedstoswitchtherobottoafeasibleorbettertrajectoryinthepopulationswiftlyinaseamlessfashion.Thechosentrajectorycanbeofaverydifferenthomotopicgroupfromthepreviousonetodealwithdrasticandlargechanges.InthecasewhentherobotreachesDofthecurrenttrajectorybutfindsnobettertrajectorytoswitchto,itwillstopitsmotionatD,whichiscalledaforcedstop.However,theRAMPplanner(i.e.,therobots“thinking”process)neverstops,anditcontinuestoplanandsearchforabettertrajectoryfortherobot.Therobotresumesitsmotiononceabettertrajectoryisfound.Suchplanning/control/sensingcyclescontinuetointeractandmovetherobottowardagoalconfigurationinthebestpossiblewayinrealtime:improvingthetrajectoriesitfollowsifthereisnochangeintheenvironment,orbothadaptingandimprovingthetrajectori