您好，
访客
登录/注册
摘要：路径规划技术已经成为各大领域研究的话题，在生活中被广泛使用，具有很高的研究价值。而路径规划技术的主要核心在于路径规划算法。首先，对路径规划技术进行概述。其次，对常用的路径规划相关算法进行分析和总结，提出其所存在的缺点及问题。再着重对目前各种改进算法、混合算法的使用等方面进行分析，对其改进方向、使用场景等方面进行总结。最后，对路径规划算法所存在的问题进行提出，对下一步的改进与研究趋势进行展望。
关键词：路径规划技术; 算法; 混合算法
Abstract： Path planning technology has become a research topic in various fields， is widely used in life， and has high research value. The main core of the path planning technology is the path planning algorithm. First， an overview of path planning technology. Secondly， it analyzes and summarizes the commonly used path planning related algorithms， and puts forward their shortcomings and problems. Then focus on the analysis of the current various improved algorithms and the use of hybrid algorithms， and summarize their improvement directions and usage scenarios. Finally， the problems of the path planning algorithm are put forward， and the next improvement and research trends are prospected.
Key words： path planning technology; algorithm; hybrid algorithm
路径规划技术[1]目前在很多领域均有着广泛的应用，其主要内容是根据路径规划算法[2]来实现最优路径的搜索，所得路线即起始点到目标点之间的无障碍安全通路。路径规划算法包括传统算法和智能仿生算法，从传统的算法到之后的智能仿生算法根据路径规划算法各自的特点选择适合场景应用都已经取得了很大的进展。
文章主要从常见的路徑规划算法进行分析其优缺点;再通过对相关文献的学习，总结出A*算法、Dijkstra算法、蚁群算法、粒子群算法等改进;最后对路径规划算法改进方向做出一些总结与展望。
1 路径规划算法综述
路径规划技术是一种应用于智能领域的新型支撑技术，其中的路径规划算法依据其实现原理的不同分为传统型路径规划算法和智能仿生学算法。近年来，路径规划已经是国内外学者研究的热点问题，目前在众多科技领域中已有很大的成就及突破。
路径规划技术在众多领域中都有着广泛的应用，在高科技领域中的具体应用场景有：自动引导车、智能搜救机器人、机场巡检机器人等;在军事领域中的具体场景有：无人水面艇避障、碰撞预测、海上应急物流;在日常生活中的具体应用场景有：GPS导航、旅行商问题（TSP）、车辆路径规划问题（VRP）等;在网络通信中的具体应用场景有：路由选择问题等;在物流管理领域中的具体应用场景有：包裹分拣、快递配送路径选择等。
路径规划算法的实现主要是通过高级语言编写而完成的，主要分为传统算法和智能仿生算法，其常用的人为算法包括：A*算法、Dijkstra算法、Floyd算法;智能仿生算法包括：遗传算法、蚁群算法、模拟退火算法等。从传统算法、智能仿生算法发展到传统算法与仿生算法结合的算法都体现出路径规划技术的发展。
2 常见人工算法及其优缺点
Dijkstra算法[3]：该算法从起点遍历到其他各节点计算其距离直到目标节点的最短路径。该算法的主要特点是确保每一次的迭代路径均是最短的。该算法鲁棒性好但其搜索效率低。
A*算法[4]：该算法从起点开始，检查其从起点开始，遍历起点周围邻近的点，然后再遍历已经遍历过的点邻近的点，逐步的向外扩散，直到找到终点。该算法准确性高、性能好，但可能出现目标不可达而浪费性能的现象。
Floyd算法[5]：该算法引用的是动态规划思想，在两顶点间插入一个或以上的中转点，比较经过和未经过中转点的距离哪个更短。其主要用于求一条带权值有向图的任意两点间的最短路径。该算法实现简单，但实现复杂度高。
3 常用智能仿生算法及其优缺点
蚁群算法[6]：该算法思想来自对蚁群觅食行为的探索，每个蚂蚁觅食时都会在走过的道路上留下一定浓度的信息素，相同时间内最短的路径上由于蚂蚁遍历的次数多而信息素浓度高，加上后来的蚂蚁在选择路径时会以信息素浓度为依据，起到正反馈作用，因此信息素浓度高的最短路径很快就会被发现，进而找到蚁群从蚁巢开始经过若干个觅食地所寻找出一条近距离且无障碍的可行路径。该算法鲁棒性强、信息正反馈性、自适应性、有并行性和可扩展性，但可能出现前期搜索效率低、易收敛、易陷入局部最优解等问题。
遗传算法[7]：该算法是一种模拟达尔文遗传选择和自然淘汰的生物进化过程中的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是按照基因遗传学原理而实现的一种迭代过程的搜索算法。其中采用随机方式搜索，利用交叉变异的操作提供多样性来适应不同情形。该算法全局搜索力强并可以有效处理复杂的最优解问题，但所占空间大、运行效率低、运算周期较长。
粒子群算法[8]：该算法通过设计一种无质量的粒子来模拟鸟群中的鸟，每个粒子在搜索空间中单独的搜寻最优解，并将其记为当前个体极值，再将个体极值与整个粒子群里的其他粒子共享，找到最优的那个个体极值作为整个粒子群的当前全局最优解。该算法易实现、收敛速度快，但性能不太稳定。
甲壳虫须搜索[9]：是一种新型的智能仿生学算法。该算法由天牛通过食物气味的强弱来觅食引来的，将食物气味当成一种函数，该函数在三维空间中的各点数值各不相同，天牛通过天牛须寻最近两点间的气味数值，最终找到气味数值最大的点。该算法运算量小、易于实现，但其局部搜索能力不足。
针对常见的人工算法和智能仿生算法的优缺点，国内外学者都对其提出了改进方案，总结出：研究并改进算法的有关影响因子;人工算法与智能仿生算法结合;图形学方法与智能仿生算法结合;改进算法与传统算法结合;全局路径规划算法和局部路径规划算法相结合。
4 改进算法综述
从国内外学者对路径规划算法的研究，得出：利用各算法的优缺点实现多个算法结合提出改进策略。文章主要从A*算法、Dijkstra算法、蚁群算法、遗传算法、神经网络算法和粒子群算法来总结：算法的改进、多个算法的结合、多领域的应用。为优化第二节和第三节的各算法，所提出的改进方案主要包括：调整各算法的重要影响因子和多个算法结合的方式，并且将改进算法应用于不同领域中。
1） 算法的改进
李学现等人[10]通过计算各节点的转移概率来修改启发因子，对信息素进行动态更新等改进蚁群算法，提高蚁群整体的搜索能力，从而搜索路径最优。龚铭凡等人[11]利用势场合力作为启发信息，将自身与目标之间的距离作为启发信息的重构，这样有效地避开屏障。通过信息素的更新策略的更改，使得蚁群搜索路径更具有目的性。通过对信息素的挥发系数调整，使得蚁群算法的全局搜索能力提高。李静等人[12]提出利用logistic回归分析来修改信息素更新的方式，从而提高收敛速度及搜索能力的提高。同时修改环境模型的建立，使用栅格法和概率选择函数，从而降低死锁现象，增加路径的平滑程度。贝前程等人[13]通过改进蚁群算法的启发函数，解决蚁群算法在前期搜索过慢且易陷入局部最优的问题。胡立华等人[14]利用行驶路线的环境信息和栅格法进行了环境建模，为解决蚁群算法的回路问题，利用初始信息素的分配方法特点来取代信息素均衡分配。通过修改启发函数和信息素的更新方式，提高蚁群的搜索能力和算法的收敛速度。侯远韶[15]文章中通过优化信息素的更新策略并结合遗传算法搜索全局路径最优，其中通过非线性的强化搜索提高局部搜索能力。为提高前期算法的收敛速度，对信息素更新方式提出优化方案。
2）多个算法结合
杨红果等人[16]利用光学寻求产生初始群種，计算其适应程度寻找局部最优和全局最优解，再与最优的个体和全局最优进行交叉和变异的处理并用混沌扰动来进行优化，最后迭代计算其适应度和最优值。付兴武等人[17]通过粒子群算法和甲壳虫须搜索算法的结合，有效地应用到三维空间中搜索路径问题上。利用甲壳虫须搜索算法的特点，解决粒子算法前期易收敛的问题。程鹏举等人[18]使用A*算法与蚁群算法结合，分析得出在一般环境下使用A*算法，在规模比较大并且障碍物多的环境下使用蚁群算法。徐美清等人[19]提出一种将遗传算法和神经网络算法结合来实现在未知且动态环境下机器人路径规划方法，机器人可以在短时间内找到一条平滑且避障的路径，完成从起点到目标地点的有效移动。刘建胜等人[20]提出一种遗传算法与粒子群算法相结合的改进算法，该算法引入遗传算法在全局搜索能力较强上并结合粒子群算法的收敛速度快的特征而设计的，能够解决复杂的路径规划问题。马向华等人[21]在预先规划路径上组建一个初始信息素矩阵，避免蚁群算法在前期盲目搜索的问题;并将改进后的蚁群算法和A*算法融合，从而提高蚁群算法收敛速度和搜索有向性。朱永强等人[22]提出了在蚁群算法的基础上结合A*算法的一种改进算法。利用A*算法得到阈值作为蚁群算法搜索的条件来更新信息素，从而提高算法搜索速度。徐波等人[23]利用Dijkstra算法和DWA算法结合提出了一种混合算法。该算法先进行全局路径规划，再进行局部路径规划，从而提高机器人避障的效率。杨海清等人[24]根据蚁群算法和遗传算法的理论，对其增添目标信息素并改进信息素的浓度，结合使用栅格法构建环境模型，有效地规划出一条从初始点到目标点的无碰撞且安全路径。
3） 多领域应用
路径规划算法在车辆运输、船舶运输、机器人、智能小车、移动机械臂、医学、农业、火灾救援等领域都有着很大的发展。
徐梦颖等人[25]提高机器人的路径规划性能，解决了遗传算法在搜索路径中易陷局部最优的问题，提出一种基于遗传算法的基础上增加免疫克隆因子 ，缩短其运动的路径长度，以此提高避障性。 郑治武等人[26]将遗传算法应用于船舶路径规划上，在传统遗传算法的基础上改进其信息素，首先构建出最优路径模型结构，选取路径点的中间值，从而提高免障碍物的安全通路。马天等人[27]将粒子群算法应用在医学领域上，基于粒子群算法的研究将采用多粒子群算法进行路径规划，有效地缩小路径搜索范围，提高路径搜索速度。李丹莲等人[28]将遗传算法应用于配送路径的选择上，提出对软时间窗下便利店在配送路径规划中的带时间窗口的遗传算法改进。该算法提出了一种多染色体来改进遗传算法，从而减少车辆运输成本且进行最短路径求值。王怀江等人[29]应用在建筑行业中通过对遗传算法的改进，搜索在规定范围内对各工位位置的寻优，解决了传统移动机械臂在路径规划算法上的低效率等问题，提出了一种基于改进遗传算法的移动机械臂拣选路径优化方法，运用改进后的遗传算法，规划出一条移动机械臂抓取的最短路径和多工位点间移动的最优路径。
本文通过对相关算法的研究分析并结合学者们提出的改进方案，总结了几个改进思路，包括：算法重要因子的调整;信息素更新过程的调节;启发函数的调节;提出自适应性函数和多个算法的有效结合。
4 展望
随着互联网时代和大数据及云计算技术的快速发展，现有的路径规划算法是远远不足以解决较复杂情形下的路径规划问题，这需要路径规划算法能够适应于复杂环境下的有效搜索能力。从上述学者研究中可以看出，对蚁群算法的改进策略是非常多的。但是，未来需要在路径规划技术上的各个方面都需要改进：
1） 算法的适应能力。一个算法能够完成应用于现有环境的过程中会遇到各种问题，因为算法本身就有很多约束性条件，为更好地解决实际性问题，需要对算法提出有效地改进策略。
2） 多个算法结合。传统算法、人工算法及智能仿生学算法都有各自的优缺点，各个算法如何能够有效地结合在一起，需要投入更多的研究。
3） 多维路径规划的研究。现有的算法运用于多维路径规划还是不多的，面对复杂环境下的环境建模技术需要加强，并结合路径规划算法有效地解决这一问题。
4） 多智能化的算法研究。随着高新科技的不断发展，各个领域都已出现智能化设备，比如：智能机器人、引导机、扫地机器人等。以后可能会出现多机器人共同协作完成某项任务，这就意味着算法更加复杂，考虑的问题更加多样性。
参考文献：
[1] 魏灵康.基于避碰规则的无人船路径规划技术研究[D].武汉：湖北工业大学，2020.
[2] 顾蕾.车辆路径规划算法及其应用综述[J].物流工程与管理，2019，41（8）：100-101，33.
[3] 徐波，陈欢，田定胜，等.基于Dijkstra的智能巡检机器人避障算法[J].供用电，2020，37（12）：74-80.
[4] 程鹏举，孟凡坤，李爽，等.A*与蚁群算法在火灾逃生中的应用分析[J].通信技术，2020，53（11）：2680-2686.
[5] 易小泉.出租车最优路径Floyd算法求解[J].计算机产品与流通，2020（6）：134-136.
[6] 龚铭凡，徐海祥，冯辉，等.基于改进蚁群算法的智能船舶路径规划[J].武汉理工大学学报（交通科学与工程版），2020，44（6）：1072-1076.
[7] 徐美清，刘洞波.基于神经网络和遗传算法的移动机器人路径规划[J].南方农机，2020，51（21）：13-14，19.
[8] 杨红果，谷利芬.基于混合粒子群算法的农业机器人全局路径规划研究[J].农机化研究，2021，43（10）：33-36，41.
[9] 付兴武，胡洋.基于改进粒子群算法的三维路径规划[J].电光与控制，2021，28（3）：86-89.
[10] 李学现，顾清华，阮顺领，等.考虑能耗动态变化的露天矿卡车运输最优路径规划[J/OL].煤炭学报：1-12[2020-12-18].
[11] 龚铭凡，徐海祥，冯辉，等.基于改进蚁群算法的智能船舶路径规划[J].武汉理工大学学报（交通科学与工程版），2020，44（6）：1072-1076.
[12] 李静，高俊钗.基于改进蚁群算法的机器人路径规划[J].自动化与仪表，2020，35（11）：39-43.
[13] 贝前程，裴云成，刘海英，等.基于改进经典蚁群算法的机器人路径规划[J].山东电力技术，2020，47（11）：24-27.
[14] 胡立华，马瑞，张名师，等.基于改进蚁群算法的智能小车路径规划方法[J].太原科技大学学报，2020，41（6）：463-469.
[15] 侯远韶.基于改进蚁群算法在机器人路径优化中的应用[J].安阳工学院学报，2020，19（6）：39-42.
[16] 杨红果，谷利芬.基于混合粒子群算法的农业机器人全局路径规划研究[J].农机化研究，2021，43（10）：33-36，41.
[17] 付兴武，胡洋.基于改进粒子群算法的三维路径规划[J].电光与控制，2021，28（3）：86-89.
[18] 程鹏举，孟凡坤，李爽，等.A*与蚁群算法在火灾逃生中的应用分析[J].通信技术，2020，53（11）：2680-2686.
[19] 徐美清，刘洞波.基于神经网络和遗传算法的移动机器人路径规划[J].南方农机，2020，51（21）：13-14，19.
[20] 刘建胜，谭文越.应用混合遗传算法的多集货中心多车型整车路径规划研究[J].机械设计与制造，2020（11）：236-240.
[21] 马向华，张谦.改进蚁群算法在机器人路径规划上的研究[J].计算机工程与应用，2021，57（5）：210-215.
[22] 朱永强，孙宗涛.改进蚁群算法在物流机器人路径规划中的应用[J].科学技术与工程，2020，20（30）：12467-12471.
[23] 徐波，陈欢，田定胜，等.基于Dijkstra的智能巡检机器人避障算法[J].供用电，2020，37（12）：74-80.
[24] 楊海清，芦斌.基于改进蚁群算法的水下无人机路径规划研究[J].计算机测量与控制，2020，28（10）：216-220.
[25]徐梦颖，王娇娇，刘宝，等.基于改进遗传算法的机器人路径规划[J/OL].石河子大学学报（自然科学版）：1-6[2020-12-18].
[26] 郑治武.改进遗传算法的舰船导航路径规划系统设计[J].舰船科学技术，2020，42（22）：121-123.
[27]马天，杨秦，李占利.基于改进多粒子群的牙齿正畸路径规划[J/OL].图学学报：1-9[2020-12-1].
[28] 李丹莲，曹倩，徐菲.基于改进遗传算法的连锁便利店配送路径优化[J].计算机工程与科学，2020，42（11）：2096-2102.
[29] 王怀江，刘晓平，王刚，等.基于改进遗传算法的移动机械臂拣选路径优化[J].北京邮电大学学报，2020，43（5）：34-40.
【通联编辑：唐一东】
