梁晓辉 慕永辉 吴北华 江宇

摘要：路径规划算法是智能领域中一项新兴的关键支撑技术;依据路径规划算法的实现原理，将其分为进化型算法与非进化型算法;再依据数学特征将非进化型算法细分为经典数学与几何图论两类;针对每类算法，分别从发展背景、设计思想、优缺点、改进与发展等方面简要归纳分析;最后对路径规划算法的未来发展趋势进行展望。

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]。

②模拟退火算法。

1953年， N. Metropolis等人将模拟退火算法SA的思想提出。它通过模拟热力学中固体物质的退火过程与一般组合优化问题之间的相似性并结合概率突跳特性，使得局部最优解能概率性地跳出并最终趋于全局最优的模式。

模拟退火法在算法实行中需要一个输入作为初始解，在求解的过程中对于坏解具有包容性，不会局限于初始解所在的收敛域内。模拟退火在计算中可跳出局部极小值点，造成了所获得的解不一定是最优解，却一定是全局的次优解，不可避免地使算法整体受参数影响，导致全局搜索能力变差[18]。

1985年，多目标模拟退火算法MOSA被Ulungu提出，解决传统的SA算法只针对单个目标求解并表现出了良好的性能[19]。2011年，SankaraoB等人提出了一种具有鲁棒性的多目标退火算法rMOSA，能够在较少的模拟次数下熟练到Pareto解集，使得在MOSA算法的基础上实施扰动选择新解，从而具有鲁棒性[20]。2005年，田东平等人将适合全局搜索的遗传算法（GA）和适合局部搜索的模拟退火算法（SA）相结合，提出了混合GA-SA计算方法，有效提高了收敛速度，并有效防止种群早熟现象，且验证了该算法的可行性和有效性[21]。

③人工势场法。

1986年，人工势场法由Khatib博士[22]提出。它是一种虚拟力法，通过在目标位置与障碍物周围构造出起共同作用的引力场与斥力场，再通过搜索势函数的下降方向来规划出无碰的最优路径，整个势场力正是由引力部分和斥力部分组成[23]。

由于人工势场法高效的实时控制性，可以实现实时路径规划和平滑轨迹处理，因而也得到了广泛应用。但是当在势场空间中同时出现多个障碍物时，易出现零势能点，使势能法陷入局部最小点，造成混乱，无法完成势场空间中的路径规划任务[24]。

很多学者针对势场原理的几个缺点进行了改进，使其具备学习能力，从而可以适应未知复杂环境或者能在多障碍物情况下消除零势能 [25]。日本的Ya-Chun chang等人结合人工势场法和Voronoi图表法提出了一种混合的路径规划算法，在此计算中分别利用了两种方法的优点同时解决势场信息构造最优路径的选择[26]。乔莎莎等人对于遗传算法与人工势场法进行结合仿真，有效避免基于行为的盲目性，增加了路径节点和平滑度，但对于全局规划带来的问题把握不够[27]。

④A*算法。

1968年，A*算法由Stanford研究院的Peter Hart等人共同发表，是一种常用的路径查找和图形遍历算法。它通过寻找最小路径来估算节点的代价评估函数并作为节点的综合优先级，当选择下一个需要遍历的节点时，再选取综合优先级最高的节点一步步地找到最优路径。A* 算法的一般过程可在文献中查到[28]。

A*算法可以方便的找到开销最小，路程最短的路径，但是随着数据量的增大，无用节点会导致A*算法搜索时间增长，同时也可以通过调节启发函数来控制算法的速度和精确度。

Szczerba等人提出了稀疏A*搜索算法（SAS），通过将约束条件与搜索算法结合起来，可有效剪裁搜索空间 [29]。高虾虾等人通过搜索节点进行优化，解决了二维航线中存在的局限性问题，减少运行时间和消耗内存[30]。占伟伟等人也提出一种改进的A*算法解决大范围三维战场环境的无人机航迹规划问题，但是由于战场环境动态变化，无法达到实时航迹规划。

⑤Dijkstra算法。

1959年，Dijkstra算法由荷兰科学家Edsger W.Dijkstra提出[31]。该算法是单源路径算法，用来求解一个顶点到其余各项顶点的最短路径问题，它通过起始点为中心向外层层扩展，直至扩展到终点为止得到最短路径。

Dijkstra算法十分简洁，能够有效的找到最优解，不足之处在数据节点庞大时所需的节点繁多，效率随着数据节点的增加而下降，耗费大量内存空间与计算时间。

侯莉莉等人以邻接链表和最小二叉堆的数据结构优化了Dijkstra算法，改进后的算法运行时间有所减少，效率有所提高[32];何少佳等利用Dijkstra算法的优点与蚁群算法进行改进，有效提高了搜索效率，缩短路径长度，改善搜索路径质量[33-34]。

⑥Floyd算法。

1978 年，Floyd 算法由图灵奖获得者教授Robert W. Floyd命名，通过分析有权图的带权邻接矩阵，而后在矩阵中求任意两点的最短路径[11]。Floyd 算法适用于任意两点间的最短路径，同时也被经常用于计算有向图的传递闭包，规划效率要高于Dijkstra算法，但其复杂度达到了三次方的级别，不能直观反映出各个顶点之间最短路径序列的先后关系。

为了提高查找效率，减少顶点之间长度比较，代修宇等人对传统的Floyd 算法进行了优化改进[35];王靖东通过对顶点过滤，顶点计算优化和反比例优化来提高路径规划成功率和效率[36]。程晓蓉等结合 Dijkstra 算法和 Floyd 算法的优点，提出了一种新的求最短路径的优化算法——F.D 算法，并将这种更高效、快捷的方法应用于求解基于 GIS 的電力通信路线最短路径问题上。

1.1.2 几何图论

①Voronoi图算法。

1908年，俄国数学家 Georgy Fedoseevich提出Voronoi图算法。这种空间分割算法的灵感来源于笛卡尔的凸域分割空间的思想，是计算几何中的一个重要分支，对于路径规划的辅助性意义很大。Voronoi图目前的生成算法主要有两大类：矢量法和栅格法[37]。

2007 年，Bhattacharya P 等人提出了一种基于 Voronoi 图解障碍是简单多边形的最短路径问题提供了详细算法的描述，及 Voronoi 图算法的维护和动态的更新，该方法性能优于其他有关路径规划算法[38]; 2010 年，徐鹏飞等人利用半平面与 Voronoi 顶点的位置关系，提出了简单增量构造 Voronoi 图的算法，此算法在处理 Voronoi 边与节点的特殊情况，并且该算法的平均时间复杂度接近线性[39]。

1.2.4 遗传算法

1962年，遗传算法被John Holland[66]提出。它是模拟生物进化论中的自然选择和遗传变异为基础理论而形成的一种搜索算法。遺传算法具有自组织，自适应和自学习性，能够同时处理多个群体中的多个个体，从串集进行搜索，覆盖面大，有利于全局搜索。但是其属于随机类算法，结果的可靠性较差，不能稳定的得到最优解。

王璇通过将遗传算法与粒子群算法和人工免疫算法相结合形成混合遗传算法，有效提高收敛速度，且使算法不易陷入局部最优值，并使用测试函数验证了算法收敛的有效性[67]。在文献[68]中提出了量子遗传算法，它是对量子计算和遗传算法相结合的产物，使得算法的适应性更强，效率更高;2016年，田欣提出新的自适应调整方式，提高了遗传算法的寻优效率，并通过引入模拟退火算法克服遗传算法有容易陷入局部最优的缺点[69]。

1.2.5 粒子群算法

1995 年， Eberhart 等人提出 PSO 算法[70]。它是通过模拟鸟群的生存行为提出的一种新型群智能优化算法，兼有进化计算和群智能的特点来实现复杂空间中最优解的搜索。PSO算法在初始时并非十分完善，在实际的应用时往往出现早熟收敛和全局收敛性能差等缺点。

PSO在离散域问题特别是组合优化问题的求解研究还比较少，这方面领域的研究被称为离散PSO。1997年，J.Kennedy等人[71]提出了粒子群算法的离散二进制版本，将经过简单的修改，使其应用于搜索二进制的空间。Xiao-Feng Xie等人提出的自组织耗散PSO算法，从热力学的角度指出PSO的社会模型具有自组织耗散结构的特点，进而引入了混乱算子，避免了群体过早的进入稳定状态[72]。

2  未来展望

路径规划算法目前多处于理论研究，试验或试运行阶段，应用到实际层面仍需要一段时间。

同其它技术理论一样，路径规划算法的产生与发展主要来自社会进步和军事需求，同时也受已有技术的限制。针对军事领域或智能控制领域出现的复杂问题，单一算法显然无法高效解决。这就需要多学科知识的交叉融合，将具有不同优势的算法有效结合成更加高效的复合型路径规划算法，这也是目前主流的研究方向。

由于非进化类算法具有运算量小、可实现性较强的优势，依旧占据着一定的生存空间。但随硬件成本的降低，运算能力水平不断提升，具备人工智能的进化类算法必将成为该领域的核心。

未来很大概率会有更高效、实时、精确处理路径规划问题的新算法诞生，使得军事武器和生产生活智能化的前景更加广阔。

参考文献：

[1]谢娟.路径规划算法的研究及应用[D].电子科技大学，2015，03.

[2]马传焱.多无人机飞行路径自动规划算法研究[J].无线电工程，2015，45（2）：5-7，33.

[3]马云红，周德云.一种简单快速的导弹路径规划方法[J].导弹与制导学报，2005，25（3）：23-26.

[4]张佳，陈杰，窦丽华.基于路径规划的智能机器人控制实验[J].实验技术与管理，2010，27（12）：44-47.

[5]温志文，蔡卫军，杨春武.UUV自主航行路径规划方法[J].制造业自动化，2016，38（11）：1-5.

[6]袁成.美国国防高级研究计划局“小精灵”项目[J].兵器知识，2016，9：37-39.

[7]孙兰会，成锋，陆愈实.基于GIS的路径规划算法研究与实现[J].现代电子技术，2016，39（5）：101-109.

[8]李军.城市智能交通中的动态路径规划研究[D].杭州电子科技大学，2017，04.

[9]高小芳.物流配送最优路径规划[D].华侨大学，2017，02.

[10]刘维民AGV路径规划与调度系统研究[D].华南理工大学，2017，02.

[11]张广林，胡小梅，柴剑飞，赵磊，俞涛.路径规划算法及其应用综述[J].现代机械，2011，5：85-90.

[12]曾庆立，李丽华，唐圣学.基于神经网络路径规划的硬件设计[J].吉首大学学报（自然科学版），2007，28（6）：74-76.

[13]L. E. Kavraki， P. Svestka， J. C. Latombe， and M. H. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces [J]. IEEE Transactions on Robotics and Automation， 1996，12（4）：566-580.

[14]Kavrak i L， Svestka P， Latombe J C， et al. Probabilistic Road Maps for Path Planning in High-dimensional  Configuration- Spaces  [J].  IEEE  Transactions  on  Robotics and Automation， 1996，12（4）： 566-580.

[15]夏炎，隋岩.PRM路径规划算法优化研究[J].应用科技， 2010，37（10）：1-5.

[16]Sanchez G.，Latombe J. C. Single-Query Bi-Directional Motion Planning with lazy Collision Checking [C]. International Symposium on Robotics Research， Lorne， Australia， 2001.

[17]Sanchez G.， Latombe J. C. On Delaying Collision Checking in PRM Planning  Application to Multi-Robot Coordination [C]. International Journal of Robotics Research， 2002， 21（1）：  5-26.

[18]郑秀敏，顾大鹏，刘相术.基于栅格法-模拟退火算法的机器人路径规划[J].机器人技术，1008- 0570（2007）02-2-0247-02.

[19]杨理云.用模拟退火算法求解旅行商问题[J].微电子学与计算机，2007（05）：193-196.

[20]卜文浩.模拟退火算法综述[D].西安理工大学，2007，08.

[21]田东平，迟洪钦.混合遗传算法和模拟退火法[J].计算机工程与应用，2006（22）：63-65.

[22]Khatib O.Realtime Abstract Avoidance for Manipulators，and Mobile Robots in Proe[J].IEEE Int Conf.On.Robotics and Automation March 25-381985.500-505，also in Int JRobot Res，1986，5（1）：90-98.

[23]王肖青，王奇志.传统人工势场的改进[J].计算机技术与发展，1005-3751（2006）04-0096-03.

[24]王奇志.基于改进人工势场法的多障碍机器人运动控制[C].北京：2003年中国智能自动化会议论文论文集（上册）.

[25]许亚.基于改进的人工势能场的移动机器人的路径规划研究[J].科技展望，2016（33）.

[26]Chang  Y-C，Yamamoto Y.Pathplanning of whelled mobile robot with simultaneous free space locating capability，Intelligent Service Robotics，2009，2（1）：19-22.

[27]乔莎莎，吴勇，张建东，史国庆.基于遗传算法和人工势场法的路径规划[J].现代电子技术，2012，35：75-78.

[28]熊壬浩，刘羽.A*算法的改进及并行化[J].计算机应用，2015，35（7）：1843-1848.

[29]NILSSON N.Problem-solving methods in artificial intelligence[M].IEEE Transactions on Aerospace and Electronic System，2000，36（3）：869-878.

[30]高虾虾，郭国龙，徐成华，冯蓉.基于改进A*算法的三维飞行航线规划.第三届高分辨率对地观测学术年会论文集[C].2014，12.

[31]Dijkstra E. A note on two problems in connexi on with graphs[J].Numerische Mathematik，1951，1（1）：269-271.

[32]赵磊，侯莉莉.一种Dijkstra算法的优化实现算法-学术研究，2014.

[33]何少佳，史剑清，王海坤.基于改进蚁群粒子群算法的移动机器人路径规划[J].桂林理工大学学报，2014，34（4）：765-770.

[34]王辉，朱龙彪，王景良，陈红艳，邵小江，朱志慧.基于Dijkstra-蚁群算法的泊车系统路径规划研究[J].工程设计学报，2016，05.

[35]代修宇，程国忠.Floyd算法的改进与优化[J].西昌学院学报·自然科学版，2012，03：63-65.

[36]王靖东，杨凌.基于优化Floyd算法的室内机器人路径规划研究[D].西北农林科技大学，2015.

[37]徐政超.基于voronoi图算法的航路规划方法研究[D].长安大学，2015.

[38]BHATTACHARYA， GAVRILOVA M L. Voronoi Diagrami n Optimal Path Planning[C]. The 4th Int-ernational Symposium on Voronoi Diagrams in Science and Engineering， 2007： 38-47.

[39]徐鹏飞，陈志刚.增量构造Voronoi区域的改进算法[J].计算机工程与应用，2010，46（8）：8-10.

[40]SHAMOS M I， HOEY D. Closest Point Problems[C]. In Proceedings of 16th IEEE Symposium on Foundations of Computer Science， 1975： 151-162.

[41]BARRY J， WANG C A. Duality of Constrained Voronoi Diagrams and Delaunay Triangulations[J]. Algorithmica， 1999， 9（2）： 142-155.

[42]徐鵬.基于模拟退火算法的机器人路径规划与研究[J].信息与通信，1671-4792-（2011）1-0042-03.

[43]郑秀敏，顾大鹏，刘相术.基于栅格法-模拟退火算法的机器人路径规划[J].机器人技术，1008-0570（2007）02- 2- 0247- 02.

[44]雷艳敏，冯志彬.改进的势场栅格法在机器人路径规划中的应用[J].长春大学学报，2009，19（1）：38-42.

[45]郑秀敏，顾大鹏，刘相术.基于栅格法-模拟退火法的机器人路径规划[J].机器人技术，1008-0570（2007）02-2-0247-02.

[46]Glover F.and M. Tabu Search. Boston， Kluwer Academic Publishers，1997.

[47]邢文训，谢金星.现代优化计算方法[M].清华大学出版社，2005：51-68.

[48]王凌.智能优化算法及其应用[M].清华大学出版社，2001.

[49]王玉晶.基于禁忌搜索算法的生理信号情感识别研究[D].西南大学，2008，05.

[50]J.A. Hageman et. al.， "Hybrid genetic algorithm-tabu search approach for  optimising multilayer optical coatings"， Analytica Chimica Acta， 490， 2003，211-222.

[51]柯坷，张世英.禁忌一递阶遗传算法研究[J].控制与决策，2001，16（4）：480-483.

[52]孙艳丰，郑加齐.GATS混合算法及其收敛性研究[J].铁道学报，22（2）：94-98.

[53]李大卫，王莉，王梦光.遗传算法与禁忌搜索算法的混合策略[J].系统工程学报，1998，13（3）：28-34.

[54]王超.基于混合遗传禁忌搜索算法的多目标柔性作业车间调度问题研究[D].重庆大学，2012.

[55]兰任.基于并行混合粒子群算法的蛋白质结构预测[D].大连理工大学，2011.

[56]袁曾.人工神经元网络及其应用[M].北京：清华大学出版社，1999，10.

[57]曾显峰.基于人工神经网络的入侵检测技术研究[D].广州市：华南理工大学，2010.

[58]张雨浓.人工神经网络的面向对象软件实现[D].广州：华南理工大学，1999.

[59]刘品.BP神经网络结构优化研究及应用[D].中国地质大学，2017，02.

[60]王和杰.基于遗传算法优化的BP神经网络的汽车油耗计算模型[D].江苏科技大学，2017.

[61]刘品.BP神经网络结构优化研究及应用[D].中国地质大学，2017.

[62]Gambardella L M， Dorigo M.Ant-Q： a reinforcement learning approach to the traveling salesman problem.Proceedings of the 12th International Conference on Machine Learning， 1995： 252-260.

[63]Stutzle T，Hoos H.The MAX-MIN ant system and local search for the traveling salesmanproblem.Proceedings of the IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference，1997：309-314.

[64]徐精明，曹先彬，王煦法.多態蚁群算法[J].中国科学技术大学学报，2005，35（l）：59-65.

[65]李擎，张超，陈鹏.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策，2013，28（6）：873-878.

[66]Holland J.H. Outline for a logical theory of adaptive systems[J]. Journal of the Association for Computing Machinery，1962，9（3）：297-314.

[67]王璇.遗传算法的改进及其应用研究[D].华北电力大学，2010.

[68]Yang Junan， Zhuang Zhenquan. Research of Quantum Genetic Algorithm and Its Application in Blind Source Separation.

[69]田欣.基于改进遗传算法的移动机器人路径规划研究[D].郑州大学，2016.

[70]Kenndy J， Eberhart R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks. 1995， 4： 1942-1948.

[71]J.Kennedy and R.C. Eberhart. A Discrete Binary Version of the Particle Swarm Algorithm. In Proceedings of the Conference on Systems， Man，and Cybernetics，1997：4104-4109.

[72]Xiao-Fen Xie， Wen-Jun Zhang， Zhi-Lian Yang. A Dissipative Particle Swarm Optimization.  Congress  on  Evolutionary Computation.2002：1456-1461.