已阅读5页,还剩9页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 安徽省定远县达标名校2024年中考试题猜想物理试卷含解析
- 安徽省安庆市重点名校2024年中考物理全真模拟试卷含解析
- 2024年浙江省永康市市级名校初中物理毕业考试模拟冲刺卷含解析
- 广西玉林市重点中学2024届高三第二次诊断性检测数学试卷含解析
- 【复合场景版】家具合同上写单价吗
- 【特殊场景版】二手房居间合同陷阱
- 【多场合】商品房租房合同
- 【多场合版】清洁卫生合同
- 【复合附录版】无效的劳动合同有哪些
- 【复杂版】购销合同和买卖合同的区别
- 贵州省暴雨强度公式汇总
- little blue and little yellow绘本 课件
- 手工焊锡知识
- 风管风速对应风量表42025
- 班主任怎样提高自身素养
- 年种植10万亩优质油莎豆及年产万吨油莎豆食用油项目可行性方案研究报告
- 商业银行合规风险管理指引》辅导试题及答案
- 建筑工程建筑面积计算规范(国标)
- 泵房施工组织设计
- 小学低年级写话的指导策略
- 外科学(第9版)十三五教材——重症监测治疗与复苏PPT课件(带内容)1
评论
0/150
提交评论