移动机器人全局路径规划算法综述

杨 韵，王成彦，巫凯旋，杨诗丹，李佳文（通信作者），翁伟涛

（1 广东海洋大学海运学院 广东 湛江 524005）

（2 广东海洋大学海洋工程学院 广东 湛江 524005）

0 引言

20 世纪60 至70 年代，美国斯坦福研究所研制的世界上第一台能实现移动的机器人——Shakey，标志着移动机器人正式诞生，伴随计算机技术的飞速发展，各种机器人导航算法不断涌现，移动机器人的发展也进入快车道。随着自动化技术的进步和发展，机器工作逐步取代传统人力工作，移动机器人作为高科技自动化工具，可通过内置算法完成指定工作，移动机器人工作的智能化和高效性使之在复杂的作业环境中取代人工，提高作业安全系数。

移动机器人拥有环境感知、自主定位、路径规划等多种高级功能，其中路径规划是指移动机器人利用已构建的环境模型，通过路径规划算法计算得到一条或多条安全系数高、距离短、平滑的线路，从而保证移动机器人自主高效地完成路劲规划作业任务，在救援、智慧交通、自动化生产、航空等领域具有举足轻重的地位[1]。如图1 所示，根据全局路径规划解形式，将其分为完备性规划算法和概率完备算法两大类，根据算法工作原理又将这两类算法分为基于图搜索、基于启发式和基于采样点3 类算法，并结合已有的研究成果，阐述各算法的优势和局限性。

1 完备性规划算法

完备性规划算法是指在起始点和目标点之间有路径解的存在，则一定可以得到路径解；若得不到路径解，则说明该路径不存在[2]。现阶段，以基于图搜索为主的完备性规划算法主要有：Dijkstra 算法、A*算法；以基于启发式为主的完备性规划算法主要有：遗传算法、蚁群算法。

1.1 Dijkstra 算法

Dijkstra 是利用广度优先搜索算法有效解决有向图最短路径的全局路径规划算法。该算法设移动机器人所在的点为初始节点，遍历剩余节点，将与初始节点距离最近的节点加入结点集合，该集合从初始节点向外层层扩散，直至遍历图中所有节点，并根据路径权重的大小找到一条初始节点到目标节点的最短路径。

当前国内外研究学者重点研究Dijkstra 算法的模型优化和减少遍历节点数目。潘成浩等[3]针对传统Dijkstra 算法难以在障碍密集型的复杂空内搜索到最短路径的问题，提出松弛Dijkstra 算法。栅格化作业环境，将整体环境离散化为单元环境，提高对地图的建模效率。仿真结果显示，与采用堆序列实现的Dijkstra 算法搜索速度对比，验证了松弛Dijkstra 算法的优越性。

1.2 A*算法

A*算法是在Dijkstra 算法基础上进行改进和优化后得到的一种启发式搜索算法，设初始节点为父节点，根据启发式函数搜索得到当前代价最低的节点作为子节点，直至搜索到目标节点，最终规划获得一条代价最小的路径，具有搜索速度快和较强的环境适应力。

王红卫等[4]针对在栅格模型下现有A*算法规划得到不平滑路径的局限，提出前后节点之间无障碍物即相接，从而构建平滑A*模型的方法。仿真结果表明，改进后的算法在规划的路径长度较原算法降低约5%，折线数量减少约50%，累计转角度数减少30%～60%。

1.3 遗传算法

遗传算法是一种模拟自然界物种进化和遗传机制的计算模型，该算法参考达尔文的“物种进化论”和孟德尔的“生物遗传学”，对自然选择和遗传因子进行交叉、变异等遗传现象进行仿真，模拟生物朝着最优的方向发展进而寻找最优解的算法，其本质是一种基于基因遗传学原理的全局搜索优化算法。因其自身最大的优点是能在搜索过程中自适应迭代优化得到路径最优解，因而它与其他算法相融合成为目前人工智能科学领域的重要研究对象，并且广泛应用于单一移动机器人的路径规划研究领域。

段俊花等[5]针对GA 算法存在难以解决大规模计算量而陷入“早熟”和因缺乏信息反馈而导致搜索速度慢等缺陷，常利用混合型的GA 算法。GA 算法结合图搜索算法，这样即减少了搜索的盲目性，又能优化原单一算法，实验结果表明，图搜索算法能有效删除冗余算子，二者相结合的算法较原GA 算法在求解最优路径的次数上从363 次增加到492 次，寻优概率从72.6%提升至98.4%。

1.4 蚁群算法

蚁群算法最初是从蚂蚁觅食行为中获取灵感进而设计的一种启发式仿生智能优化算法。蚂蚁在觅食道路上释放信息素，随着时间的推移，信息素浓度与路径长度成反比，蚂蚁对信息素具有感知能力，后来的蚂蚁以信息素浓度大小作为判断依据，引导自身运动并找寻到最优觅食路径。此过程具有正反馈调节机制，因此该算法能够快速搜索到最短路径。

蚂蚁觅食路径优化图见图2。

封声飞等[6]针对蚁群算法发挥正反馈机制时间长、易陷入局部最优等问题提出一种自适应蚁群算法。该算法在蚁群算法的基础上调整初始化信息素，引入转角约束以限制算法随机性，并对路径尖峰进行平滑处理。实验结果证明，改进后的算法迭代次数降低至原来的1/4 到1/3，规划得到的路径更加平滑，保证了移动机器人运动的平衡性。

2 概率完备算法

概率完备算法是指在起始点和目标点之间存在路径解，只要规划或者搜索时间足够长，则最终能找到一条路径解[7]。现阶段，以基于采样点的概率完备算法主要有：PRM 算法、RRT 算法。

2.1 PRM 算法

针对移动机器人在高维空间和复杂约束环境中运动轨迹受到动态约束的问题，20 世纪90 年代提出了PRM（随机路标图法），是概率完备算法中基于采样点的全局路径规划算法，将连续空间转化为离散空间，使得路径规划与搜索算法的准确度有关而与空间复杂程度无关。刘洋等[8]针对传统PRM 算法在狭窄空间难以进行路径规划的缺陷，提出一种结合人工势场的PRM 算法。该方法在地图中引入人工势场以增加非障碍区域内的节点数量。仿真结果显示，改进后的算法提高了对节点的空间利用率，在采样次数不变的情况下更好地解决移动机器人在狭小空间中难以快速规划出最优路径的问题。

2.2 RRT 算法

RRT 算法最初由Lavalle 提出，此算法具有灵活快速搜索的能力，且无需建立环境模型和设置任何参数，在复杂环境中具有搜索速度快的优势，因此在移动机器人路径规划技术中被广泛使用。王坤等[9]针对RRT-Connect 在存规划高质量路径时运算时间长、随机性大和步长不灵活等问题，提出一种基于改进的双向快速扩展随机树算法。仿真对比实验显示，改进后的算法与原算法相比在迭代次数上减少32.3%，在规划路径的速度上提高了50%。

3 移动机器人全局路径规划技术发展趋向

3.1 多种算法融合优势互补

在现实应用中，单一算法均具有局限性，仅靠一种算法难以满足所有任务场景，但直接研究一种新的具有多功能的算法难度大。国内外许多学者通过实验证明，不同算法在不同任务场景中具有差异性和各自的优势，因此多种算法的相互融合能更好地形成优势互补、取长补短，最大限度发挥各自算法的性能。

3.2 多移动机器人与智能化信息技术协同路径规划

随着工业自动化和科学技术日新月异的发展，机器人被广泛应用于各生产领域，移动机器人的工作任务也日益复杂，单机器人已难以满足当今社会多元复杂的需求，因此需要多个机器人之间进行协同规划，在保证任务安全有序进行的同时提高生产效率。在实际生产应用中，单机器人无法满足工作需求，而多机器人协作又有着单机器人无法媲美的优势[10]。

3.3 移动机器人传感信息对算法敏感度的提升

传感器是移动机器人与外界环境感知的交互信息，也是机器人系统控制的基础。移动机器人通过安装双目视觉相机、激光雷达避障、GPS 等传感器感知并获取外界环境信息从而进行地图模型的构建、识别障碍物以及提供精确的位置信息，然后算法进行路径规划[11]。整个过程中，各传感器对收集到的信息进行分析处理，并剔除冗余信息，删除错误信息。最后，算法整合各传感器的有效信息，建立并提高模型精度，从而提高路径规划算法的避障和规划能力。

4 讨论

针对上述6 种算法进行简要分析，罗列每个算法的优缺点、规划后的路径是否最优以及算法适用范围，结果见表1。

表1 6 种全局路径规划算法总结表

5 结语

随着智能技术和工业自动化的发展，移动机器人全局路径规划是国内外机器人领域的研究热点之一。本文首先简要介绍移动机器人的产生与发展，然后对当今全局路径规划算法的应用领域及他人对算法的改进优化进行综述，最后从单一算法性能的优化、多算法优势互补融合、多机器人协同规划、结合传感器信息4 个方面提出路径规划技术未来改进和优化方向的评价，作为路径规划算法当前的研究及其未来发展奠定的参考依据。