搜索
32420107ROBOTVol.32,No.4Jul.,2010DOI10.3724/SP.J.1218.2010.0056831;2;3111.1100162.4300813.100049343TP24A1002-0446(2010)-04-0568-09Reviewof3DPathPlanningMethodsforMobileRobotCHENYang1;2;3ZHAOXingang1HANJianda1(1.StateKeyLaboratoryofRobotics,ShenyangInstituteofAutomation,ChineseAcademyofSciences,Shenyang110016,China;2.CollegeofInformationScienceandEngineering,WuhanUniversityofScienceandTechnology,Wuhan430081,China;3.GraduateSchooloftheChineseAcademyofSciences,Beijing100049,China)Abstract:Avarietyofthree-dimensionalpathplanningmethodsaredividedintofourcategoriesaccordingtotheirmod-elingprinciples.Theworkingprinciplesofthosemethodsareintroduced,andtheadvantagesanddisadvantagesarepointedoutinvariousapplications.Allofthemarecomparedfromtheviewpointswhethertheycanbeusedinreal-timeanddy-namicenvironment,whethertheycanachievesmoothpathandglobalplanning,andwhethertheycanadddifferentdynamicconstraintsconveniently.Conclusionsaredrawnfromthecomparisonthatthemethodbasedonvirtualpotentialfieldandnavigationfunctionissuperiortoothersforitsreal-timeperformanceandwillbeapriorityinlocalplanners.Themethodbasedonmathematicoptimizationiscapableofdealingwithavarietyofdynamicconstraints.Incontrasttomathematicop-timization,thebio-inspiredoneislimitedinsolutionsoflongcallingcycleforitslargeplanningperiodalthoughitisefficienttodescribeintractableconstraints.Keywords:threedimensionalspace;obstacleavoidance;environmentmodeling;dynamicconstraint;searchingalgorithm;real-time1Introduction2233MAVmicroairvehicleUAVunmannedaerialvehicleUUVunmannedunderwa-tervehicleAUVautonomousunderwatervehicle2[1-4]336077505660705028chenyang@sia.cn2009-08-21/2009-09-18/2010-02-075683243569332MethodsbasedongeometricalmodelsearchingVoronoi2.1probabilisticroadmapPRMprobabilisticallycomplete[1]1k3[1]Hrabar[2]3A*32.2232KuwataHow[5]3UAV3SMNG313Fig.13DPRMpath22Fig.2Visibilitygraphintwodimensions33Fig.3Visibilitygraphinthreedimensions2.3rapidly-exploringrandomtreeRRTLaValle[3]RRT4freespaceRRTYangSukkarieh[6]RRT570201073RRTbiased-greedyRRT34RRTFig.4PrincipleoftheRRTalgorithm(Endofthearrowisthenewnodeofthetree)KimOstrowski[7]RRTblimpsystemRedding[8]RRTreplanningR-502.4[8]WilliamsJones[9][10]33JungTsiotras[11]UAVfastliftingwavelettransformFLWTA*D*-lite5SGSMNGSM0N0GHwang[12]35Fig.5Multi-resolutioncelldecompositionviasquare2.5VoronoiVoronoiVoronoi[13-14]Voronoi3[13]VoronoiDijkstra2.6[15-21]A*DijkstraD*-liteWu[15]A*233fieldD*[16]32435713[10][17]UAVA*D*BellmanFordFloydw[18]A*[19]A*50ms300ms[20]anytimedynamicA*[21]AryaMountKDTkd-treePRMRRT3Meth-odsbasedonvirtualpotentialfieldandnavigationfunction23artificialpotentialfieldharmonicfunctionfieldflowfield3.12Kitamura[22]3A*33.22[23-24]3[4;25]3normalvelocityoflineobstacle33.3[26][27]virtualforcefield[28]4Methodsbasedonmathematicoptimization4.1recedinghorizoncontrolRHCMAV3[29](1)(2)(3)(4)MAV[10]3iterativestepmethodISM[30-31]3UAVUAVISM4.2Shih[32]linearpro-grammingLPNonLinearProgram-mingNLP[31]LPmixedintegerlinearprogrammingMILP[5;33-34]6H(xh;yh;zh)L(xl;yl;zl)xhxlyhylzhzlHL6(1)(1)MILP57220107(2)Mbi01i=1;2;¢¢¢;6x6xlORy6ylORz6zlORxxhORyyhORzzh(1)8:x6xl+M¢b1y6yl+M¢b2z6zl+M¢b3xxh¡M¢b4yyh¡M¢b5zzh¡M¢b66åi=1bi65bi2f0;1g;i=1;2;¢¢¢;6(2)6MILPFig.6MILPmethodMILP3[5]3MILP3[33]MILPMILP[35]MILPAMPLCPLEXMILP[8]4.3levelsetCecilMarthaler[36]2[37]33SinghBussa[38]2S-KShiandKarllevelset4.43Delaunay[39-40]4.53[41]marginmaximizationprinciple4.6Shanmugavel[42]UAVPHPythagoreanHodographcurveUAVTwigg[43]342Geiger[44]3directcollocationwithnonlinearprogrammingKanchanavally[45]3feedbacklinearizationUAVUAVUAV5Methodsbasedonbiologicalintelligence3243573antcolonyoptimizationACOparticleswarmoptimizationPSOgeneticalgorithmandevolutionalgorithmGAandEA)5.1Chen[46]UCAVunmannedcombatairvehicle5.2Hao[47]Jung[48]PSO3B5.3MittalDeb[49]NSGA-IInondominatedsortinggeneticalgorithmII3Zhang[50]3GAZhaoMurthy[51]EAGAAllaire[52]UAVFPGAfieldprogrammablegatearrayGAFPGA100ms150km/hUAVUAVUAV5.4MorenoCastro[53]KohonenUAV[54]5.5ZapataLepinay[55]3deformablevirtualzone3Mohandas[56]6IntegrationofmultiplemethodsTian[57]MettlerToupet[58]MILPShi[59]ACOPSOACOMasehian[40]VoronoiVoronoi6.13574201076.2Bruijnen[60]A*[20]D*[61]17Conclusionandprospect3(1)(2)(3)(4)3(1)(2)3(3)331Tab.1ComparisonamongvariouspathplanningalgorithmsReferences[1]LaddAM,KavrakiLE.Measuretheoreticanalysisofprob-abilisticpathplanning[J].IEEETransactionsonRoboticsandAutomation,2004,20(2):229-242.[2]HrabarSE.Vision-based3Dnavigationforanautonomoushe-licopter[D].USA:UniversityofSouthernCalifornia,2006.[3]LaValleSM.Planningalgorithms[M].2nded.NewYork,USA:CambridgeUniversityPress,2006.[4]FahimiF.Autonomousrobotsmodeling,pathplanning,andcontrol[M].Boston,USA:SpringerScience+BusinessMedia,LLC,2009.[5]KuwataY,HowJ.ThreedimensionalrecedinghorizoncontrolforUAVs[C]//AIAAGuidance,Navigation,andControlCon-3243575ference.Reston,VA,USA:AIAA,2004:2100-2113.[6]YangK,SukkariehS.3DsmoothpathplanningforaUAVinclutterednaturalenvironments[C]//IEEE/RSJInternationalConferenceonIntelligentRobotsandSystems.Piscataway