路径规划的主要算法与展望应用数学论文数学论文.docx

1、路径规划的主要算法与展望应用数学论文数学论文路径规划的主要算法与展望-应用数学论文-数学论文文章均为WORD文档，下载后可直接编辑使用亦可打印 摘要：路径规划算法是智能领域中一项新兴的关键支撑技术；依据路径规划算法的实现原理，将其分为进化型算法与非进化型算法；再依据数学特征将非进化型算法细分为经典数学与几何图论两类；针对每类算法，分别从发展背景、设计思想、优缺点、改进与发展等方面简要归纳分析；最后对路径规划算法的未来发展趋势进行展望。 关键词：路径规划; 进化型算法; 非进化型算法; 未来展望; Summary of Path Planning Algorithms LIANG Xiao-hu

2、i MU Yong-hui WU Bei-hua JIANG Yu Shijiazhuang Campus of Army Engineering University 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

3、 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 backgro

4、und of development,design ideas, advantages and disadvantages, improvement. Finally the future development trend of the path planning algorithm is forecasted. 0 引言 路径规划（Path Planning)1是智能技术中的热点研究问题，已在多领域有所突破并成功得以应用。 在军事领域涉及到的有无人机飞行路径自动规划2，导弹回避威胁3，智能机器人控制4，水下无人航行器（Unmanned underwater vehicle UUV）的自主航

5、行5以及美国国防高级研究计划局小精灵项目6等；在日常方面涉及的有基于地理信息系统（Geographic Information System,GIS）的路径规划7，城市智能交通动态路径规划8，物流或外卖配送9以及自动导引装置（Automated Guided Vehicle,AGV）的路径规划与调度10等。11 路径规划的实现主要依靠高级语言编制出的算法，其主要包含：模拟退火法，A*算法，Dijkstra算法，遗传算法，粒子束算法，人工势场法，Voronoi法等。少部分路径规划也可通过硬件加以改善，例如可以使用微电子器件或光学器件解决路径规划在实时系统中速度慢的缺陷12。 1 路径规划算法 依

6、据算法实现原理，可将路径规划算法归类为非进化型与进化型两种。 1.1 非进化型算法 非进化型算法具有简洁的设计思想流程和较高效率的处理能力。但在机械式解决路径规划问题时，不易产生最优路径，且无法在过程中实现自我学习和自我完善，不具备记忆能力。在处理高维空间形式下的路径规划问题时，结果与期望有较大偏差。 依据算法数学特征，可将非进化型算法分成经典数学与几何图论两类型。 1.1.1 经典数学 (1)图搜索概率法。 20世纪90年代初期，M.H.Overmars提出PRM(Probabilistic Roadmaps Method）图搜索概率法13,14。PRM主要包含离线学习阶段和在线学习阶段，依

7、据搜索算法在终始点之间的优化规则形成路标图，并在一定条件的约束下有效的解决在多维空间和复杂环境中的路径规划问题。 PRM图搜索概率法的寻径方式简便，整个规划场景的大小与构形空间的多维性没有特别强烈的关系，因此复杂度较低，不需要精确建模。但由于所采集样点随机分布，无法覆盖自由空间中的全部路径，易出现搜索路径不是所需的最优路径，同时在规划路径时遇到狭窄通路或是复杂度较高的障碍集合时，算法效率就会显得十分低下。 在对PRM的改进中，夏炎等人通过节点增强法将原路径上的节点代替，利用圆弧替代路径上的折线，达到减小节点拐点个数，缩短规划路径长度，并实现搜索路径有较高的平滑度15。G.Sanchez等人在P

8、RM的基础上提出了SBL-PRM算法，即通过从两个基本位姿点出发，找到路径后再经过碰撞检测等手段使得计算更加实时高效16,17。 (2)模拟退火算法。 1953年，N.Metropolis等人将模拟退火算法SA的思想提出。它通过模拟热力学中固体物质的退火过程与一般组合优化问题之间的相似性并结合概率突跳特性，使得局部最优解能概率性地跳出并最终趋于全局最优的模式。 模拟退火法在算法实行中需要一个输入作为初始解，在求解的过程中对于坏解具有包容性，不会局限于初始解所在的收敛域内。模拟退火在计算中可跳出局部极小值点，造成了所获得的解不一定是最优解，却一定是全局的次优解，不可避免地使算法整体受参数影响，导

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

10、tib博士22提出。它是一种虚拟力法，通过在目标位置与障碍物周围构造出起共同作用的引力场与斥力场，再通过搜索势函数的下降方向来规划出无碰的最优路径，整个势场力正是由引力部分和斥力部分组成23。 由于人工势场法高效的实时控制性，可以实现实时路径规划和平滑轨迹处理，因而也得到了广泛应用。但是当在势场空间中同时出现多个障碍物时，易出现零势能点，使势能法陷入局部最小点，造成混乱，无法完成势场空间中的路径规划任务24。 很多学者针对势场原理的几个缺点进行了改进，使其具备学习能力，从而可以适应未知复杂环境或者能在多障碍物情况下消除零势能25。日本的Ya-Chun chang等人结合人工势场法和Vorono

11、i图表法提出了一种混合的路径规划算法，在此计算中分别利用了两种方法的优点同时解决势场信息构造最优路径的选择26。乔莎莎等人对于遗传算法与人工势场法进行结合仿真，有效避免基于行为的盲目性，增加了路径节点和平滑度，但对于全局规划带来的问题把握不够27。 (4)A*算法。 1968年，A*算法由Stanford研究院的Peter Hart等人共同发表，是一种常用的路径查找和图形遍历算法。它通过寻找最小路径来估算节点的代价评估函数并作为节点的综合优先级，当选择下一个需要遍历的节点时，再选取综合优先级最高的节点一步步地找到最优路径。A*算法的一般过程可在文献中查到28。 A*算法可以方便的找到开销最小，

12、路程最短的路径，但是随着数据量的增大，无用节点会导致A*算法搜索时间增长，同时也可以通过调节启发函数来控制算法的速度和精确度。 Szczerba等人提出了稀疏A*搜索算法（SAS），通过将约束条件与搜索算法结合起来，可有效剪裁搜索空间29。高虾虾等人通过搜索节点进行优化，解决了二维航线中存在的局限性问题，减少运行时间和消耗内存30。占伟伟等人也提出一种改进的A*算法解决大范围三维战场环境的无人机航迹规划问题，但是由于战场环境动态变化，无法达到实时航迹规划。 (5)Dijkstra算法。 1959年，Dijkstra算法由荷兰科学家Edsger W.Dijkstra提出31。该算法是单源路径算法

13、，用来求解一个顶点到其余各项顶点的最短路径问题，它通过起始点为中心向外层层扩展，直至扩展到终点为止得到最短路径。 Dijkstra算法十分简洁，能够有效的找到最优解，不足之处在数据节点庞大时所需的节点繁多，效率随着数据节点的增加而下降，耗费大量内存空间与计算时间。 侯莉莉等人以邻接链表和最小二叉堆的数据结构优化了Dijkstra算法，改进后的算法运行时间有所减少，效率有所提高32；何少佳等利用Dijkstra算法的优点与蚁群算法进行改进，有效提高了搜索效率，缩短路径长度，改善搜索路径质量33,34。 (6)Floyd算法。 1978年，Floyd算法由图灵奖获得者教授Robert W.Floy

14、d命名，通过分析有权图的带权邻接矩阵，而后在矩阵中求任意两点的最短路径11。Floyd算法适用于任意两点间的最短路径，同时也被经常用于计算有向图的传递闭包，规划效率要高于Dijkstra算法，但其复杂度达到了三次方的级别，不能直观反映出各个顶点之间最短路径序列的先后关系。 为了提高查找效率，减少顶点之间长度比较，代修宇等人对传统的Floyd算法进行了优化改进35；王靖东通过对顶点过滤，顶点计算优化和反比例优化来提高路径规划成功率和效率36。程晓蓉等结合Dijkstra算法和Floyd算法的优点，提出了一种新的求最短路径的优化算法F.D算法，并将这种更高效、快捷的方法应用于求解基于GIS的电力通

15、信路线最短路径问题上。 1.1.2 几何图论 (1)Voronoi图算法。 1908年，俄国数学家Georgy Fedoseevich提出Voronoi图算法。这种空间分割算法的灵感来源于笛卡尔的凸域分割空间的思想，是计算几何中的一个重要分支，对于路径规划的辅助性意义很大。Voronoi图目前的生成算法主要有两大类：矢量法和栅格法37。 2007年，Bhattacharya P等人提出了一种基于Voronoi图解障碍是简单多边形的最短路径问题提供了详细算法的描述，及Voronoi图算法的维护和动态的更新，该方法性能优于其他有关路径规划算法38;2010年，徐鹏飞等人利用半平面与Voronoi顶

16、点的位置关系，提出了简单增量构造Voronoi图的算法，此算法在处理Voronoi边与节点的特殊情况，并且该算法的平均时间复杂度接近线性39。 (2)矢量法。 矢量法包括以下几种经典型算法：分治法、增量法、和间接法-Delaunay三角网法。矢量法提高了运算的复杂程度，缩短了运算时间，不影响全局空间的分割，具有精度高，效率高的特性，但是也造成生成图像的精准度不够，储存结构也相对复杂37。 在Voronoi图的发展历程中，矢量法的出现要早于栅格法。1975年，谢姆斯等人提出的采用分治法构造平面点集Voronoi图算法40;1993年，Barry J等人把线状障碍物的VSP-VD和Delaunay

17、三角网分别定义为有限制的Voronoi图和有限制的Delaunay三角网41。 (3)栅格法。 1968年，栅格法由W.E.Howden提出，它将路径规划所占用的环境分解成具有二值信息的网络单元42。这种方法的特点是简单、易于实现，它同时具有表达不规则障碍物的能力。其缺点是表示效率不高，存在着时空开销与求解精度之间的矛盾。 路径规划时栅格法多以环境建模形式存在，采以栅格（grid）来表示环境信息，以此避免复杂的计算。单位栅格越小，障碍物的表示越精确，但也会浪费大量的存储空间，搜索的范围会以指数的形式激增。单位栅格过大，由算法规划的路径会变得很不精确。43 目前基于对栅格法改进方案多是通过与其它

18、算法的复合。2009年，雷艳敏等提出通过对栅格属性的设置来弥补势场法和栅格法的缺点，仿真结果表明该方法是可行有效的44;2007年，郑秀敏等提出将栅格法与模拟退火法进行结合，采用栅格法表示环境信息，模拟退火法来进行局部的路径规划成功提高了路径规划的效率，增强了可靠性45。 1.2 进化型算法 进化型算法可以理解成智能算法，是人们受自然（生物界）规律得到的启迪而模仿出的算法，具有一定的自我学习，自我更新和记忆能力。对问题的解决方式较为复杂，能够处理复杂的路径规划问题，但是在庞大的计算量下易造成效率低下，无法高效的完成实时控制。 1.2.1 禁忌搜索法 1986年，禁忌搜索算法（Tabu Sear

19、ch,TS）由Glover教授正式提出，是一种亚启发式（meta-henristic）的搜索算法46,47,48。TS通过引入一个灵活的存储结构和与之对应的禁忌准则，并通过藐视准则赦免一些被禁忌的优良状态，借此保证多样化的有效搜索来实现最终的全局优化。其最主要的特点就是采用了禁忌技术和特赦规则，使得算法可以跳出局部最优解，进行有效的计算，最终实现全局的优化49。 禁忌搜索算法易于实现，通用性及局部开发能力较强，收敛速度快，但全局开发能力相对较弱，搜索结果完全依赖于初始解和领域的映射关系。 混合算法的出现，尤其是遗传算法和模拟退火算法的有效结合对于算法性能和效率有较大幅度的改善50,51,52,

20、53。2012年，王超利用禁忌搜索算法和遗传算法的特点将二者结合，得到较强的全局搜索能力和局部搜索能力的混合算法54;2010年，兰任55在其论文中利用粒子群PSO算法前期收敛速度快和TS的优点对蛋白质结构进行预测，通过对结果的分析验证了混合型算法的优越性。 1.2.2 神经网络算法 神经网络算法（Neural Network）是一种以人脑的神经网络作为启发，通过简化，抽象与模拟人脑存储和处理信息的过程并用数学语言加以描述而衍生出来的智能化信息处理技术56。根据学习算法与网络结构两个方面相结合的角度来对神经网络进行分类57，有以下几个类别，单层前向网络，多层前向网络，反馈神经网络，随机神经网络

21、和竞争神经网络等。神经网络算法具有自学习，联想存储，具备高速寻找最优解的能力，但是算法的网络参数较多，属于黑盒状态，不可观察结果，学习时间较长，容易陷入局部最小值。 BP(Back Propagation）算法是人工神经网络中研究最为成熟，应用也是最为广泛的人工神经网络模型之一58，它由Rumelhart等人在1986年提出，按照误差逆向传播算法训练的多层前馈神经网络，其结构简单，可塑性强，具有自我学习的特性，但是学习速率固定，不储存学习过程中的参数，因此无记忆能力59。 神经网络算法与其它算法的有机结合是目前改进劣势的重要方式。2016年，王和杰提出用遗传算法来优化BP神经网络，改善初始值和

22、阈值，可充分发挥BP神经网络的局部搜索能力，提高算法稳定性，避免陷入局部最优值60。2017年，刘品提出采用高阶神经网络对BP网络模型结构进行优化，能够产生更好的拟合，可以解决高度复杂问题61。 1.2.3 蚁群算法 二十世纪九十年代，意大利学者Dorigo Mden通过模拟蚂蚁的行为规律，以蚂蚁在自然界中协同工作寻找食物为数学模型提出了蚁群算法（Ant Colony Optimization），这是一种贪婪启发式的搜索算法。 传统蚁群算法具有正反馈机制，加强了算法的寻优能力，个体与个体建立的信息共享，互相合作，促进该算法能够搜索到最优解。蚁群算法易于与其他算法结合使用，拥有更强大的搜索能力。

23、但是无法实现实时在线搜索，尤其是面对空间较大，不易在有限时间内找到最优解，且其易陷入局部最优的局面。 Gambardella等人在1995年提出Ant-Q蚁群算法，此算法通过最优信息的反馈，以较大的概率选择信息素强度最大的路径62;Stutzle and Hoos在1997年改进扩展了蚁群算法的全局搜索范围，减小了算法陷入局部最优导致早熟现象发生的几率63；徐精明等人首次提出了多态蚁群算法，对人工蚁进行合理分工，结合局部与全局搜索，加快了算法收敛速度 ;2013年，李擎等人提出了粒子群参数优化的改进蚁群算法，通过全局异步和精英策略成功减少粒子群算法调用蚁群算法的迭代次数65。 1.2.4 遗传

24、算法 1962年，遗传算法被John Holland66提出。它是模拟生物进化论中的自然选择和遗传变异为基础理论而形成的一种搜索算法。遗传算法具有自组织，自适应和自学习性，能够同时处理多个群体中的多个个体，从串集进行搜索，覆盖面大，有利于全局搜索。但是其属于随机类算法，结果的可靠性较差，不能稳定的得到最优解。 王璇通过将遗传算法与粒子群算法和人工免疫算法相结合形成混合遗传算法，有效提高收敛速度，且使算法不易陷入局部最优值，并使用测试函数验证了算法收敛的有效性67。在文献68中提出了量子遗传算法，它是对量子计算和遗传算法相结合的产物，使得算法的适应性更强，效率更高；2016年，田欣提出新的自适应

25、调整方式，提高了遗传算法的寻优效率，并通过引入模拟退火算法克服遗传算法有容易陷入局部最优的缺点69。 1.2.5 粒子群算法 1995年，Eberhart等人提出PSO算法70。它是通过模拟鸟群的生存行为提出的一种新型群智能优化算法，兼有进化计算和群智能的特点来实现复杂空间中最优解的搜索。PSO算法在初始时并非十分完善，在实际的应用时往往出现早熟收敛和全局收敛性能差等缺点。 PSO在离散域问题特别是组合优化问题的求解研究还比较少，这方面领域的研究被称为离散PSO。1997年，J.Kennedy等人71提出了粒子群算法的离散二进制版本，将经过简单的修改，使其应用于搜索二进制的空间。XiaoFen

26、g Xie等人提出的自组织耗散PSO算法，从热力学的角度指出PSO的社会模型具有自组织耗散结构的特点，进而引入了混乱算子，避免了群体过早的进入稳定状态72。 2 未来展望 路径规划算法目前多处于理论研究，试验或试运行阶段，应用到实际层面仍需要一段时间。 同其它技术理论一样，路径规划算法的产生与发展主要来自社会进步和军事需求，同时也受已有技术的限制。针对军事领域或智能控制领域出现的复杂问题，单一算法显然无法高效解决。这就需要多学科知识的交叉融合，将具有不同优势的算法有效结合成更加高效的复合型路径规划算法，这也是目前主流的研究方向。 由于非进化类算法具有运算量小、可实现性较强的优势，依旧占据着一定

27、的生存空间。但随硬件成本的降低，运算能力水平不断提升，具备人工智能的进化类算法必将成为该领域的核心。 未来很大概率会有更高效、实时、精确处理路径规划问题的新算法诞生，使得军事武器和生产生活智能化的前景更加广阔。 参考文献 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温志文，

28、蔡卫军，杨春武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

29、. 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 highdimensional configuration spacesJ. 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 ConfigurationSpacesJ. IEEE Transactions on Robotics and Automation,1996,12(