移动机器人3维路径规划方法综述.docx
《移动机器人3维路径规划方法综述.docx》由会员分享，可在线阅读，更多相关《移动机器人3维路径规划方法综述.docx（11页珍藏版）》请在冰点文库上搜索。
移动机器人3维路径规划方法综述
第32卷第4期陈洋等：
移动机器人3维路径规划方法综述573稳定收敛的同时，在自由空间进行随机搜索，比如：
蚁群算法（antcolonyoptimization，ACO）、粒子群算法（particleswarmoptimization，PSO）、遗传与进化算法（geneticalgorithmandevolutionalgorithm，GAandEA、自组织神经网络等．5.1蚁群算法Chen等[46]研究了基于改进蚁群算法的UCAV（unmannedcombatairvehicle）的路径规划问题．以最小化风险和最小化能量消耗为目标函数，对于不可预测的突发威胁，采用重规划技术提高了算法的可靠性和实时性．5.2粒子群算法Hao等[47]将路径规划分为全局规划和局部规划两个阶段，提出了极坐标粒子群路径规划算法．Jung等[48]将PSO算法的应用推广到3维路径规划，初始运动由当前位置与目标点的直线代替，通过最小化敌方威胁和燃料消耗获得路径最优解，最后利用B样条曲线得到一条光滑的最优路径．5.3遗传与进化算法Mittal和Deb[49]采用多目标优化方法NSGA-II（nondominatedsortinggeneticalgorithmII）研究了无人机离线3维路径规划问题．该方法以路径长度和相对地面障碍物的安全系数为代价函数，不必将多目标优化问题转化为单目标优化问题．Zhang等[50]用高程网格地图构建了3维静态环境模型，提出基于GA的路径规划方法，让机器人先爬上一个较低的台阶障碍物，依次再爬上一个相邻更高的障碍物，从而达到逐步越障的目的．Zhao和Murthy[51]在已知无人直升机始末状态和航迹点约束下，用EA算法开发了基于凸或非凸几何形状的障碍物环境的最优飞行路径规划器．但是GA算法最大的不足就是无法满足实时性要求，Allaire等[52]对其进行了充分验证，并且提出在UAV的控制系统中用FPGA（fieldprogrammablegatearray）电路实现基于GA的路径规划模块．用FPGA实现后的算法其效率大大提高，规划周期减小到100ms左右，若以150km/h的普通UAV计算，规划周期内UAV的运动距离与本体尺寸相当，基本上达到实时性要求，但是与军用UAV的要求依然相差甚远．5.4神经网络Moreno和Castro[53]提出一种增长的弹性神经网络，用于计算路径规划解．该方法用自组织、网络互连的神经元集合表示路径，其初始路径由一条连接初始点到目标位置的直线代替．该直线由初始点到目标点之间少量的处理单元定义．网络中起始点和目标点的处理单元静止，而其它神经元都可自适应活动．各处理单元用Kohonen网络进行局部采样与学习，采用简单的强化规则进化避碰路径，最终得到一条完整的路径．此外，贝叶斯网络也可用于设计UAV的安全路径[54]．5.5其它智能方法Zapata和Lepinay[55]针对3维空间飞行机器人的避障和目标跟踪问题，提出一种基于反抗行为的控制策略．将机器人与环境看作是博弈的双方，基于微分博弈论提出了变形虚拟区（deformablevirtualzone）方法．这种方法认为机器人由可变形的椭球曲面包围，动态环境会导致该椭球曲面发生最大的变形，而机器人的运动策略需要对之产生一种反抗行为来极小化这种变形．这种方法的规划变量为机器人的3维运动矢量，包括一个线速度和两个角速度．[56]Mohandas等考虑了障碍物的不确定性，将其看作模糊障碍物，用模糊函数表示其模糊特性，权值越大，其位置的模糊性越大．6多种方法的结合（Integrationofmultiplemethods）Tian等[57]将数据融合理论与支持向量机结合，解决了动态避碰问题．Mettler和Toupet[58]对环境进行多分辨率细胞分解，建立了滚动优化的目标函数，将动力学约束和环境约束加入到MILP模型中，用图搜索技术进行搜索求解．Shi等[59]用简单的规则构建位图，将地形分为可穿越和不可穿越两类，采用ACO在可穿越空间规划路径，同时用PSO算法优化ACO的参数．Masehian等[40]结合了Voronoi图、可视图和人工势场法．在构型空间推广了Voronoi图，在初始点和目标点交替执行双向搜索求解．6.1应用范围移动机器人运动的环境可分为动态时变和静止不变两种．若规划方法实时性较好，则可有较多时间裕量用于动态环境模型在线重构，并重新计算轨迹以达到最优目标．反之若规划方法的实时性较差，则重规划不能满足机器人实时控制要求，其应用范围局限于静态环境．大量文献表明人工势场方法和数学优化方法的实时性较好，可应用于动态环境，而生物智能方法最差，一般只能应用于静态环境．另外，3维空间路径规划必须考虑移动机器人的运动约束，主要包括动力学和运动学约束，以及一些环境的非结构化约束．比如：
空中飞行器的最小飞行半径、最大速度、最小速度、最大爬升加速度
574机器人2010年7月以及飞行通道最小尺寸等．这些约束要以各种适当的形式加入到路径规划模型中．在几何地图中加入这些约束需要对模型进行近似线性化处理，而在数学优化方法和生物智能方法中，则允许使用精确的非线性函数直接计算．6.2算法的复杂度分析如果环境的全局信息已知且不变，那么路径规划可离线进行，这样不必在意规划的时间．如果环境信息是时变的，则算法必须具有在线规划能力．Bruijnen等[60]比较了多种路径规划算法的实时性，指出人工势场法的实时性最好，可以达到毫秒级以下，而波传播算法、基于A*[20]、D*的重规划算法的运算周期也都达到了秒级．此外，基于随机采样的路径规划算法和基于启发式搜索的神经网络算法[61]，也都达到了秒级，甚至更高．算法的实时性与其应用领域紧密相联，只能当其实时性达到一定优良程度时，才可应用于动态环境的在线重规划．否则，只能应用于离线规划或有限制的重规划．关于各种算法的实时性和应用范围的综合评价与比较，见表1．7结论与展望（Conclusionandprospect）本文分析了3维空间路径规划的各种方法，阐述并分析了这些方法的基本工作原理和应用范围，最后比较了它们的实时性、环境适应性、规划路径的光滑性，以及加入动力学约束的难易程度．虽然可以将多种方法组合应用，但仍然不会改变各种算法本身的局限性，分析结论表明：
（1基于几何地图搜索的方法，在构建环境障碍物信息上具有简单方便的优势，可运用各种成熟的图搜索算法求取最优解，适用于静态环境和离线规划，因此可以成为新的搜索算法的最佳验证平台．（2基于虚拟势场与导航函数的方法的最大优点是实时性好，而且可得到非常光滑的路径，因此优先在局部规划器中选用这种方法．（3基于数学优化的方法在解决动力学约束问题时占优势，可综合考虑路径的安全性、可靠性和优化性能．（4基于生物智能的方法可以解决异常复杂的非结构化约束和各种难以近似处理的动力学约束等难题．但是最大不足是规划周期太长，一般不可能在移动机器人可容忍的控制周期内处理完毕，因此不宜在规划过程中频繁调用，只能应用于调用周期较大的情形或全局的初始规划．通过各种算法的对比分析，3维路径规划研究领域有以下几个方面的问题亟待解决：
（1复杂环境建模问题．目前的路径规划算法大多数建立在规则的理想障碍物假设上，如果能提出新的建模方法来应对复杂环境中任意几何外形的障碍物，则必将为最优路径规划算法提供重要的基础．（2算法实时性问题．该问题已成为3维路径规划方法的一个关键问题．现有算法通常是通过对象的线性化和假设各种理想情况进行研究，但这显然不是解决实时性问题的最好办法．未来的研究应当充分结合环境建模和具体应用背景来寻求更加快速有效的路径规划算法．（3动力学约束及其它约束问题．3维路径规划问题存在的约束相当复杂且形式各异，如果能提出一种解决异类约束的统一方法，则有可能建立3维路径规划的理论框架，从而推动相关理论研究和应用研究的飞速发展．表1各种路径规划算法的性能比较Tab.1Comparisonamongvariouspathplanningalgorithms方法基于几何地图搜索的方法基于虚拟势场和导航函数的方法基于数学最优化的方法基于生物智能的方法实时性较好好好差动态／静态环境静态静态／动态静态／动态静态[3][4]路径是否光滑不光滑光滑光滑不光滑考虑动力学约束较难难容易容易局部／全局规划全局全局／局部全局／局部全局参考文献（References）[1]LaddAM,KavrakiLE.Measuretheoreticanalysisofprobabilisticpathplanning[J].IEEETransactionsonRoboticsandAutomation,2004,20（2:
229-242.HrabarSE.Vision-based3Dnavigationforanautonomoushelicopter[D].USA:
UniversityofSouthernCalifornia,2006.[2][5]LaValleSM.Planningalgorithms[M].2nded.NewYork,USA:
CambridgeUniversityPress,2006.FahimiF.Autonomousrobotsmodeling,pathplanning,andcontrol[M].Boston,USA:
SpringerScience+BusinessMedia,LLC,2009.KuwataY,HowJ.ThreedimensionalrecedinghorizoncontrolforUAVs[C]//AIAAGuidance,Navigation,andControlCon-
第32卷第4期陈洋等：
移动机器人3维路径规划方法综述575[6][7][8][9][10][11][12][13]ference.Reston,VA,USA:
AIAA,2004:
2100-2113.YangK,SukkariehS.3DsmoothpathplanningforaUAVinclutterednaturalenvironments[C]//IEEE/RSJInternationalConferenceonIntelligentRobotsandSystems.Piscataway,NJ,USA:
IEEE,2008:
794-800.KimJ,OstrowskiJP.Motionplanningofaerialrobotusingrapidly-exploringrandomtreeswithdynamicconstraints[C]//IEEEInternationalConferenceonRoboticsandAutomation.Piscataway,NJ,USA:
IEEE,2003:
2200-2205.ReddingJ,AminJN,BoskovicJD,etal.Areal-timeobstacledetectionandreactivepathplanningsystemforautonomoussmall-scalehelicopters[C]//AIAAGuidance,NavigationandControlConference.Reston,VA,USA:
AIAA,2007:
989-1010.WilliamsM,JonesDI.Arapidmethodforplanningpathsinthreedimensionsforasmallaerialrobot[J].Robotica,2001,19（2:
125-135.CocaudC,JnifeneA,KimB.EnvironmentmappingusinghybridoctreeknowledgeforUAVtrajectoryplanning[J].CanadianJournalofRemoteSensing,2008,34（4:
405-417.JungD,TsiotrasP.Multiresolutionon-linepathplanningforsmallunmannedaerialvehicles[C]//AmericanControlConference.Piscataway,NJ,USA:
IEEE,2008:
2744-2749.HwangJY,KimJS,LimSS,etal.Afastpathplanningbypathgraphoptimization[J].IEEETransactionsonSystems,Man,andCybernetics,PartA,2003,33（1:
121-128.肖秦琨，高晓光．基于空间改进型Voronoi图的路径规划研究[J]．自然科学进展，2006,16（2:
232-237.XiaoQinkun,GaoXiaoguang.Astudyonpathplanningbasedon3DimprovedVoronoidiagram[J].ProgressinNaturalScience,2006,16（2:
232-237.SakaharaH,MasutaniY,MiyazakiF.Real-timemotionplanninginunknownenvironment:
AVoronoi-basedStRRT（SpatiotemporalRRT[C]//TheSocietyofInstrumentandControlEngineers（SICEAnnualConference.Hongo,Bunkyo-ku,Tokyo,Japan:
SICE,2008:
2326-2331.WuXJ,TangJ,LiQ,etal.Developmentofaconfigurationspacemotionplannerforrobotindynamicenvironment[J].RoboticsandComputer-IntegratedManufacturing,2009,25（1:
13-31.CarstenJ,FergusonD,StentzA.3DfieldD*:
Improvedpathplanningandreplanninginthreedimensions[C]//IEEE/RSJInternationalConferenceonIntelligentRobotsandSystems.Piscataway,NJ,USA:
IEEE,2006:
3381-3386.SathyarajBM,JainLC,FinnA,etal.MultipleUAVspathplanningalgorithms:
Acomparativestudy[J].FuzzyOptimizationandDecisionMaking,2008,7（3:
257-267.YangIH,ZhaoYJ.Real-timetrajectoryplanningforautonomousaerospacevehiclesamidststaticobstacles[C]//AIAA’s1stTechnicalConferenceandWorkshoponUnmannedAerospaceVehicles.Reston,VA,USA:
AIAA,2002.DolgovD,ThrunS,MontemerloM,etal.Practicalsearchtechniquesinpathplanningforautonomousdriving[C]//FirstInternationalSymposiumonSearchTechniquesinArtificialIntelligenceandRobotics（STAIR-08.MenloPark,CA,USA:
2008:
32-37.LikhachevM,FergusonD,GordonG,etal.AnytimedynamicA*:
Ananytime,replanningalgorithm[C]//ProceedingsoftheInternationalConferenceonAutomatedPlanningandScheduling（ICAPS.MenloPark,CA,USA:
AAAI,2005:
262-271.[14][15][16][17][18][19][20][21]YershovaA,LaValleSM.Improvingmotion-planningalgorithmsbyefficientnearest-neighborsearching[J].IEEETransactionsonRobotics,2007,23（1:
151-157.[22]KitamuraY,TanakaT,KishinoF,etal.3-Dpathplanninginadynamicenvironmentusinganoctreeandanartificialpotentialfield[C]//IEEE/RSJInternationalConferenceonIntelligentRobotsandSystems.Piscataway,NJ,USA:
IEEE,1995:
474481.[23]KimJO,KhoslaPK.Real-timeobstacleavoidanceusingharmonicpotentialfunctions[J].IEEETransactionsonRoboticsandAutomation,1992,8（3:
338-349.[24]FahimiF,NatarajC,AshrafiuonH.Real-timeobstacleavoidanceformultiplemobilerobots[J].Robotica,2009,27（2:
189198.[25]ZhangY,ValavanisKP.A3-Dpotentialpanelmethodforrobotmotionplanning[J].Robotica,1997,15（4:
421-434.[26]LiuC,WeiZ,LiuC.Anewalgorithmformobilerobotobstacleavoidancebasedonhydrodynamics[C]//IEEEInternationalConferenceonAutomationandLogistics.Piscataway,NJ,USA:
IEEE,2007:
2310-2313.[27]KonoligeK.Agradientmethodforrealtimerobotcontrol[C]//IEEE/RSJInternationalConferenceonIntelligentRobotsandSystems.Piscataway,NJ,USA:
IEEE,2000:
639-646.[28]OhTS,ShinYS,YunSY,etal.AfeatureinformationbasedVPHforlocalpathplanningwithobstacleavoidanceofthemobilerobot[C]//4thInternationalConferenceonMechatronicsandInformationTechnology.ProceedingsoftheSPIE,vol.6794.Bellingham,WA,USA:
SPIE,2007:
679425.[29]PrazenicaRJ,KurdilaAJ,SharpleyRC,etal.Multiresolutionandadaptivepathplanningformaneuverofmicro-airvehiclesinurbanenvironments[C]//AIAAGuidance,Navigation,andControlConference.Reston,VA,USA:
AIAA,2005:
1761-1772.[30]WeissB,NaderhirnM,delReL.Globalreal-timepathplanningforUAVsinuncertainenvironment[C]//IEEEInternationalSymposiumonIntelligentControl.Piscataway,NJ,USA:
IEEE,2006:
2725-2730.[31]DoganA.ProbabilisticapproachinpathplanningforUAVs[C]//IEEEInternationalSymposiumonIntelligentControl.Piscataway,NJ,USA:
IEEE,2003:
608-613.[32]ShihCL,LeeTT,GruverWA.Aunifiedapproachforrobotmotionplanningwithmovingpolyhedralobstacles[J].IEEETransactionsonSys
升级会员 