路径规划算法及其应用综述

《路径规划算法及其应用综述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、路径规划算法及其应用综述*张广林，胡小梅,柴剑飞，赵磊，俞涛（上海市机械自动化与机器人重点实验室上海人学，上海200072）SummaryofPathPlanningAlgorithmanditsApplicationZHANGGuanglin,HUXiaomei,CHAIJianfei,ZHAOLei,YUTaoAbstract:PathplanningtechnologyisahotspotofmanyareaatpresentIthasbroadapplicationprospectsandscientificvalueAndtheresearchof

2、thepathplanningalgorithmisthecoreofitInthispaper,thedomesticandforeignresearchofnowadayjpathplanningalgorithmweresummarizedAndtheiradvantagesanddisadvantageswereanalyzedandcomparedThen,thehoiproblemsthatappliedthesepathplanningalgorithmwereclassifiedandsummarized,andthealgorithmsth

3、atappliedtotheseproblem;wereana-lyzedAtlast,thefurtherresearchdirectionofpathplanningwasproposedKeywords：pathplanning:geneticalgorithm:antcolonyalgorithm:A*algorithm:particleswarmoptimization:dijkstraalgorithmArtificialpotentialfield0引言路径规划技术悶在很多领域都具有广泛的应用。在高新科技领域的应用有:机器人的自主无碰行动;无

4、人机的避障突防E行;巡航导弹躲避雷达搜索、防反弹袭击、完成突防爆破任务等。在日常牛活领域的应用有:GPS导航:基于GIS系统的道路规划;城市道路网规划导航等。在决策管理领域的应用有:物流管理中的车辆问题（VRP：，及类似的资源管理资源配置问题。通信技术领域的路由问题等。凡是可拓扑为点线网络的规划问题基本上都可以采用路径规划的方法解决。路径规划的核心就是算法的设计，路径规划算法⑶0前已经得到了广泛的关注，从传统算法，到后来的结合仿生学发展起来的算法，钢能算法已经取得了巨大的进展。不同的解能算法特点不同，适用范围和领域也就不同，因而从算法本身特点及其应用来研究路

5、径规划智能算法，对路径规划技术的发展具有重要意义。1路径规划及其智能算法综述1.1路径规划问题的分类根据对环境信息的把握程度可把路径规划划分为基于先验完全信息的全局路径规划和基于传感器信息的局部路径规划“7o其中，从获取障碍物信息是静态或是动态的和度看，全局路径规划属丁•静态规划｛又称离线如划），局部路径规划属于动态规划（又称在线规划）。全卮路径规划盂要学握所有的环境信息，根据环境地图的所有信息进行路径规划；局部路径规划只需要由传感器实时采集环境信息，了解环境地图信息，然后确定出所在地图笊位fit及其局部的障碍物分布情况，从而可以选出从当前辭点到某一子目标结

6、点的最优路径。根据所研究环境的信息特点，路径规划还可分为庚散域范围内的路径规划问题和连续域范围内的路径规划问题。离散域范圉内的路径规划问题属于一维静态优化问题,相当于环境信息简化后的路线优化问题；而连续吗范围内的路径规划问题则是连续性多维动态环境下的问题。1.2路径规划的一般步骤一般的连续域范围内路径规划问题，如机器人、飞行器等的动态路径规划问题，其一般步骤主耍包括环境建模眾各径搜索左各径平滑三个环节"'別oD环境建模。环境建模是路径规划的重要环节，U的是建立一个便于计算机进行路径规划所使用的环境模型，即将实际的物理空间抽象成算法能够处理的抽彖空间,实现相互

7、间的映射。2）路径搜索。路径搜索阶段是在环境模型的基础上应用相应算法寻找-条行走路径，使预定的性能函数获得最优值。3）路径平滑。通过相应算法搜索出的路径并不一定是--条运动体可以行走的可行路径,需要作进一步处理与平滑才能使其成为一条实际可行的路径。对于离散域范围内的路径规划问题，或者在环境建模或路径搜索前已经做好路径可行性分析的问题，路径平滑环节可以省去。1.3常用路径规划算法路径规划的方法有很多，根据其自身优缺点，其适用范围也各不相同。根据对各领域常用路径规划算法的研究，按照各种算法发现先后时序及算法基本原理,将算法大致分为四类：传统算法、图形学的方法、智

8、能伪生学算法和其他算法®血o（1）传统算法传统的路径