摘要：路径规划算法是智能领域中一项新兴的关键支撑技术;依据路径规划算法的实现原理，将其分为进化型算法与非进化型算法;再依据数学特征将非进化型算法细分为经典数学与几何图论两类;针对每类算法，分别从发展背景、设计思想、优缺点、改进与发展等方面简要归纳分析;最后对路径规划算法的未来发展趋势进行展望。
Abstract： Path planning algorithm is an emerging key supporting technology in the field of intelligence; According to the implementation principle of path planning algorithm， it is divided into evolutionary algorithm and non-evolutionary algorithm; Then based on the mathematical characteristics， the non-evolutionary algorithm can be divided into two types： classical mathematics and geometric graph theory; For each type of algorithm， the paper will give a brief summary and analysis from some aspects： the background of development，design ideas， advantages and disadvantages， improvement. Finally the future development trend of the path planning algorithm is forecasted.
關键词：路径规划;进化型算法;非进化型算法;未来展望
Key words： path planning;evolutionary algorithm;non-evolutionary algorithm;future development
中图分类号：TP242 文献标识码：A 文章编号：1006-4311（2020）03-0295-05
0 引言
路径规划（Path Planning）[1]是智能技术中的热点研究问题，已在多领域有所突破并成功得以应用。
在军事领域涉及到的有无人机飞行路径自动规划[2]，导弹回避威胁[3]，智能机器人控制[4]，水下无人航行器（Unmanned underwater vehicle UUV）的自主航行[5]以及美国国防高级研究计划局“小精灵”项目[6]等;在日常方面涉及的有基于地理信息系统（Geographic Information System，GIS）的路径规划[7]，城市智能交通动态路径规划[8]，物流或外卖配送[9]以及自动导引装置（Automated Guided Vehicle，AGV）的路径规划与调度[10]等。[11]
路径规划的实现主要依靠高级语言编制出的算法，其主要包含：模拟退火法，A*算法，Dijkstra算法，遗传算法，粒子束算法，人工势场法，Voronoi法等。少部分路径规划也可通过硬件加以改善，例如可以使用微电子器件或光学器件解决路径规划在实时系统中速度慢的缺陷[12]。
1 路径规划算法
依据算法实现原理，可将路径规划算法归类为非进化型与进化型两种。
1.1 非进化型算法
非进化型算法具有简洁的设计思想流程和较高效率的处理能力。但在“机械式”解决路径规划问题时，不易产生最优路径，且无法在过程中实现自我学习和自我完善，不具备记忆能力。在处理高维空间形式下的路径规划问题时，结果与期望有较大偏差。
依据算法数学特征，可将非进化型算法分成经典数学与几何图论两类型。
1.1.1 经典数学
①图搜索概率法。
20世纪90年代初期，M.H.Overmars提出PRM（Probabilistic Roadmaps Method）图搜索概率法[13-14]。PRM主要包含离线学习阶段和在线学习阶段，依据搜索算法在终始点之间的优化规则形成路标图，并在一定条件的约束下有效的解决在多维空间和复杂环境中的路径规划问题。
PRM图搜索概率法的寻径方式简便，整个规划场景的大小与构形空间的多维性没有特别强烈的关系，因此复杂度较低，不需要精确建模。但由于所采集样点随机分布，无法覆盖自由空间中的全部路径，易出现搜索路径不是所需的最优路径，同时在规划路径时遇到狭窄通路或是复杂度较高的障碍集合时，算法效率就会显得十分低下。
在对PRM的改进中，夏炎等人通过节点增强法将原路径上的节点代替，利用圆弧替代路径上的折线，达到减小节点拐点个数，缩短规划路径长度，并实现搜索路径有较高的平滑度[15]。G.Sanchez等人在PRM的基础上提出了SBL-PRM算法，即通过从两个基本位姿点出发，找到路径后再经过碰撞检测等手段使得计算更加实时高效[16-17]。
推荐访问： 算法 路径 综述 规划 相关
