1、2023 年 2 月 25 日第 7 卷第 4 期现代信息科技Modern Information Technology Feb.2023 Vol.7 No.475752023.022023.02收稿日期：2022-09-30路径规划算法的研究综述林梓健，刘凯，林群煦（五邑大学 轨道交通学院，广东 江门 529020）摘 要：路径规划算法广泛应用于机器人、无人驾驶设备、自动导航等领域，是推动自动化和智能化发展的技术支撑。文章对几何搜索算法、智能搜索算法、人工智能算法、混合算法和局部规划算法等路径规划算法进行了简要介绍，内容包括若干典型算法以及由不同算法相互模仿混合而成的混合算法的特点、优缺点和
2、重要改进。对路径规划算法的发展趋势进行总结，对路径规划算法的发展前景进行展望，以期为相关的研究提供参考。关键词：路径规划；算法综述；自动导航中图分类号：TP242 文献标识码：A 文章编号：2096-4706（2023）04-0075-06Research Review of the Path Planning AlgorithmsLIN Zijian,LIU Kai,LIN Qunxu(School of Rail Transportation,Wuyi University,Jiangmen 529020,China)Abstract:The path planning algorithm
3、s are widely used in robots,driverless equipments,automatic navigation and other fields,and they are the technical support for promoting the development of automation and intelligence.This paper briefly introduces path planning algorithms such as geometric search algorithm,intelligent search algorit
4、hm,artificial intelligence algorithm,hybrid algorithm and local planning algorithm,including the characteristics,advantages and disadvantages and important improvements of several typical algorithms as well as hybrid algorithms formed by mutual imitation and mixing of different algorithms.Summarize
5、the development trend of path planning algorithms,and prospect the development prospect of path planning algorithms,in order to provide reference for relevant research.Keywords:path planning;algorithm review;automatic navigation0 引 言路径规划是机器人、自动驾驶等领域里的一个重要部分，包括移动设备的路径规划、机械臂的轨迹规划等内容。规划良好的路径对设备的工作能力和工作
6、效率，乃至工作场所的安全等要素有至关重要的影响。本文将介绍其中一些典型的算法，如图 1 所示，分为几何搜索算法、智能搜索算法、人工智能算法、混合算法和局部规划算法 5 个部分进行介绍。路径规划算法几何模型算法智能搜索算法局部规划算法人工智能算法A*算法Dijkstra算法蚁群算法遗传算法随机算法DWA局部优化Q学习深度学习人工势场法Voronoi图算法混合算法图 1 路径规划算法分类图1 几何搜索算法1.1 A*算法A*算法是一种经典的寻路算法，该算法的核心公式是DOI:10.19850/ki.2096-4706.2023.04.020每一步的代价G加估算代价H得到总代价F，常用的H是“曼哈顿
7、距离”，此外也有欧氏距离、对角线距离等可以选择，系统选择F最小的路线作为结果。该算法计算快，应用广泛，但考虑的信息较少，得到的路径会不够平顺或出现多余的段落。Zhang1等人通过加进类似人工势场法的目标引力和障碍物斥力，把合力作为一个要素加进 A*算法的代价函数里，使得改进后的算法更充分考虑地图信息，并用 B 样条曲线进行平滑处理，得到比传统 A*算法更平顺更合理的路径，在实验中同样直线距离的情况下算法会选择更平直、更少转弯的路线。Tang2等人通过设置函数对传统 A*算法的路径进行过滤修整，去除交叉或锯齿形等不合理的路径，并用 B样条曲线平滑处理，得到更合理、更适合设备执行的路径。Hong3
8、等人通过优化数据结构，并且让算法在距离目标点只剩一段距离之前不执行传统 A*算法中搜索终点是否在列表中的步骤，因为在大部分时间里这一步都是没什么意义的，尤其是在尺寸比较大的地图上，因而大大提升了计算速度和适用范围。1.2 Dijkstra 算法Dijkstra 算法是一种经典的路径搜索算法，该算法基于贪婪策略，从起始点开始，一层层地向外搜索直到到达目标。不过传统的 Dijkstra 算法有不考虑平滑度等局部情况、某些情况下计算量大和计算复杂、搜索速度慢等不足。Sun4等通过改进让Dijkstra算法在8个方向上进行搜索，76762023.022023.02第 4 期现代信息科技得到比 4 个方
9、向进行搜索的传统 Dijkstra 算法更平顺、更优化的路径。Dijkstra 算法的不足也可以通过与其他算法混合使用以弥补，比如 Zhao5等使用 Dijkstra 算法搜索初始的路径后，再使用蚁群算法进行进一步优化。1.3 Voronoi 图算法Voronoi 图是一种基于几何图形的路径规划算法，该算法先按移动设备的尺寸等条件给障碍物“膨胀”处理确保安全距离，并且提取特征点，然后按边界与两特征点保持相同距离的方式把区域划分成若干单元，得到 Voronoi 图路径，边界线就是可行路径。Huang6等在传统的 Voronoi 图算法的基础上，通过在两个机器人相遇时在低优先权的机器人上添加 Vo
10、ronoi 特征点使低优先权的机器人使用的 Voronoi 图和路径发生改变并绕开高优先级机器人的方式，进行多机器人的路径规划。AL-Dahhan7等通过在传统的 Voronoi 图得到的初步结果上，删除一些不必要的点，增加一些新的引导点，使路径得到进一步优化。Chi8等通过 1 个特征矩阵“过滤”传统的 Voronoi图得到的特征点，删除不必要的特征点，得到更优化的路径。2 智能搜索算法2.1 蚁群算法蚁群算法由Dorigo9提出，源于对蚂蚁寻找食物的研究，蚂蚁释放信息素也受已有信息素的影响，在一定的时间后蚂蚁们会由于信息素而集中在比较理想的路线上。随后出现了精英蚁群算法、极大极小值蚁群算法
11、、等级蚁群算法等改进10。该算法被广泛使用，是效率和适用性很高的一种算法。但是蚁群算法有陷入局部最优解、过度依赖信息素、初始时盲目搜索等不足。Abolhosein11等人通过让蚁群算法的每一次更新都按一定的权重考虑前面已经获得结果，设计了一种“带有记忆”的动态蚁群算法，每次更新都在考虑已有结果的基础上进行而不是地图稍有改变就从头开始搜索，大大减少了动态环境下所需的计算时间。Pohan12等人通过让启发函数不只是考虑当前节点到下一节点的距离，也考虑节点到目标点的距离来设定启发因子，使得蚂蚁不必搜索所有节点，也不必每次都搜索最接近的下一个节点，减少了搜索的盲目性，提高了效率。Zhang13等人通过
12、在更新信息素时考虑当下迭代得到的最优解和目前最流行的解，额外增强两者共同包括的节点的信息素，并且让信息素能辐射出去影响周边的其他节点，增加了蚂蚁之间的协作性，比传统的蚁群算法能获得更快更优化的路径。Li14等人通过引入适应策略，根据信息素的浓度动态调整各点信息素的挥发系数，不让系统过早收敛而陷入局部最优解，增加了系统的全局搜索能力。Song15等在已有的精英蚁群算法基础上引入序列，找出一群精英蚂蚁并排序，同时在信息素更新环节加入模糊逻辑，不仅提升了蚁群算法的计算速度和动态环境搜索能力，还能同时考虑多种其他条件的约束而不只是最短路径。2.2 遗传算法遗传算法由约翰 H 霍兰16等人提出，模仿遗传
13、物质在适应环境的过程中优胜劣汰，使遗传物质得到优化。该算法让各个解进行交换、突变、繁殖复制，淘汰不能适应的解，由“适应度”决定繁殖和淘汰。在著作中约翰H霍兰解释道，突变的作用是以免过早收敛陷入局部最优解，比如一个早先因某些原因恰好被删掉的信息，是有可能在遇到其他信息后组合出更好的解的，还能增加多样性；而交换则能在大程度保持众多优秀小片段的同时，打乱由这些小片段组成的大片段来增加多样性，实现众多小片段逐渐优化，同时由这些小片段组合出多样的大片段以供选择，并且这两个操作都能扩大搜索空间，使搜索不局限于初始条件。遗传算法不断改进以提高搜索能力，缓解该算法计算量大、计算时间长等不足。Wang17等人在
14、传统的遗传算法的基础上，增加了直接保留适应度高的个体，删除和替换掉效果不太好的基因段的步骤，提高了遗传算法的计算速度和求解性能。Xing18等人通过引入精英直接复制到下一代和分组进行适应不同的目标，然后混合并在下一代再分组适应不同目标的策略，提高计算速度的同时使得改进后的遗传算法能求解多目标的优化问题。Li19等在传统的单一种群进行求解的遗传算法的基础上，设置若干个种群同时求解，并通过“迁徙”让种群之间互相流通，改进基因交叉的算法，并且也设置让较优的个体直接保留下来，提高了算法的性能和求解速度，如图 2 所示。开始结束最优种群扩大若干种群最佳染色体迁移遗传算法2号种群迁移迁移1号种群最佳染色体
15、遗传算法m号种群最佳染色体遗传算法满足收敛条件？否是图 2 带有“迁徙”的遗传算法流程图Li20等为适应度判别引入了奖惩因素提高搜索能力，并且每轮搜索直接保留第一维基因里的优秀个体，和由这些优秀个体产生二维基因，使得遗传算法能求解多维度的问题。遗传算法的突变和交叉概率是一个重要的改进方向，比如袁梦飞21等让群体在早期扩大突变和交叉的概率以扩大搜索空间，后期则减少突变和交叉的概率以加速收敛，提高了算法的搜索性能和计算速度；王吉岱22等通过模糊推理设置动态的突变概率和交叉概率，在种群适应度方差过低或进化速度过慢时增大概率，扩大搜索空间和避免系统早熟或陷入局部最优解，反之则减小概率，加速算法的收敛。
16、2.3 人工势场法人工势场法来自对物理学的力场的模仿，让目标发出“吸引力”，障碍物则发出“排斥力”，形成一个组合力场。该算法简单而高效，广泛应用在局部路径优化、避障等。但是77772023.022023.02第 4 期该算法也有一些明显的不足，例如陷入力平衡而锁死，由于排斥力的作用要和障碍物保持一端距离导致路线有时候达不到最短、在目标周围或前往目标的途中的障碍物的排斥力使得机器人无法前往目标点等问题。针对陷入力平衡的死锁问题，以往有通过增加虚拟障碍物或虚拟目标打破死锁的做法，主要是随机添加的，但该方法被认为不稳定，甚至导致偏离目标。Yuan23等通过在陷入死锁时，计算一个相邻范围内的障碍物数量和整个空间的障碍物数量，并由此数量关系产生额外的斥力使得路线因此发生膨胀绕开死锁地点。Yang24等人通过在目标点附近添加一些虚拟目标点供路线陷入死锁时切换目标为这些虚拟目标点以脱离死点，并且在距离目标点小于某设定值后，使吸引力保持为常数或增大，确保路线能到达目标点，如图 3 所示。F阻力机器人F引力障碍目标虚拟目标半径图 3 用于脱离死点的虚拟目标点Wang25等通过在判断有陷入死锁的危险时，在
