机器人路径规划是机器人导航的重要部分，需要在未知或者已知的环境中，完成机器人最优或者最短路径的选择。传统的路径规划方法如：A*算法[1]、 RRT算法[2]、改进人工势场法[3]等，虽然已经可以满足一般的路径规划需求，但在遇到环境复杂、多目标、动态变化或者路径短、长等优化需求时，常常无法得到满意的结果。仿生智能优化算法在求解问题时不依赖梯度信息，广泛应用于路径规划[4～6]问题中。

蚁群算法适用于解决作业调度、路径规划等复杂的组合优化问题。虽然蚁群算法采用了并行计算的方式，可以加快搜索速度，提高路径规划效率，但蚁群算法仍然存在鲁棒性差、效率低、寻优效果不理想等问题。近年来，众多学者对蚁群算法应用于路径规划存在的问题进行了大量的改进研究[7～12]。

但是，以上改进蚁群算法应用于机器人路径规划时，关注点大多集中于利用与终点的距离进行启发，尽可能追求得到的规划路径最短。对机器人的能耗极少考虑，在复杂环境下的最优路径求解效果也不太令人满意。此外，现有研究的测试场景和实验次数通常比较单一，较少在多种环境下多次测试算法的性能。本文针对移动机器人路径规划问题，提出了一种基于位置和能耗启发的改进蚁群算法，综合考虑机器人行进路径长度、行进路径坡度和转弯带来的能耗，设计了到终点距离启发因子、到起止点直线距离启发因子、综合能耗启发因子的多因子启发函数，综合计算转移概率，同时优化了信息素更新策略，从而为机器人路径规划提供了综合性能更优的算法。

1、蚁群算法思想

蚁群算法包括路径选择和信息素更新2个关键过程。

蚂蚁在通往食物源过程中，如何选择下一步要走的路径要依据状态转移概率。在t时刻，蚂蚁m从当前节点i选择下一个节点j的转移概率可表示为式(1)所示

式中τi,j(t)为蚂蚁在节点i到节点j路径上留下的信息素浓度；ηi,j(t)为蚂蚁在节点i到节点j路径上的启发素，通过式(2)计算，d(i,j)为节点i到节点j之间的欧氏距离；α为信息素权重，表示信息素浓度在蚂蚁选择节点j时的相对重要程度，其值越大，蚂蚁越倾向于选择信息素浓度大的路径；β为启发素权重，表示节点i与节点j之间距离的重要程度，其值越大，蚂蚁越倾向于选择距离目标节点近的节点；allowedi为节点i的可行邻接栅格编号的集合。

信息素更新规则如式(3)和式(4)所示

式中ρ为全局信息素挥发系数，(1-ρ)为信息残留因素；N为蚂蚁总数；Δτi,j(t)为一次迭代结束后在路径i,j上信息素增量，

Δτi,j(t)为所有蚂蚁一次迭代结束后在路径i,j上信息素增量总和；Q为常量，表示信息素增强系数；Lm为蚂蚁m在本次迭代中走过的路径长度。τi,j(0)通常是一个常数。

2、应用于路径规划的改进蚁群算法

2.1 安全因素下栅格地图

采用栅格地图对移动机器人作业环境进行建模是常用方法之一[13]。移动机器人在复杂环境作业过程中，对安全的要求是非常高的，要保证机器人与障碍物不能发生触碰。为了使得规划出来的路径尽量远离障碍物，要求经过栅格节点的路径不能经过障碍物的边缘。同时，机器人实际工作环境通常是三维的，每个栅格具有高度。具体建模如下：构建地图模型矩阵G,0表示自由栅格，用白色表示，1表示障碍栅格，用黑色表示；用peaks函数生成各栅格的高度，模拟路面的坡度变化，用绿色表示，颜色越深，高度越高。构建的20×20的地图模型如图1所示。

图1 栅格地图模型

为了便于存储可行路径信息，构建二维矩阵D记录当前栅格与其八邻域栅格的邻接关系。设栅格的边长为1,则邻接矩阵D可取值分别为：1、1.4和无穷大inf(不可行)。相邻栅格i和j,如果状态均为0,且处于同一水平或者垂直方向时，邻接矩阵取值1;相邻栅格i和j,如果状态均为0,且处于斜角方向时，根据机器人不能触碰障碍物边缘的安全性能要求，只有在斜向栅格和与该方向垂直的2个直向栅格均为自由栅格时，邻接矩阵取值1.4,否则取inf。

2.2 多因子启发函数

对于移动机器人来说，在实际环境作业时，在确保安全性能下，路径规划不仅仅要考虑路径长度最短的需求，还要考虑崎岖路面路径高度差和机器转弯带来的额外能耗问题。机器人每一次经过具有高度差的地面，都会产生颠簸，高度差越大，对机器损坏越大。机器人每一次进行拐弯操作时，对器械也产生磨损，转弯角度越大，磨损越大。综合考虑这些因素，将能耗因子添加到蚁群算法的启发函数中，改进后的多因子启发函数如式(5)所示

2.2.1 到终点距离启发因子

在蚁群算法早期，所有路径上信息素的浓度相同，增加了前期搜索代价。因此，将终点栅格对待选栅格的距离影响合理放大，对蚁群在早期给予方向指引。修正的到终点距离启发因子函数如下

式中φ(i,j)为修正的到终点距离启发因子函数，表示待选栅格到终点栅格E的修正距离；MAXd为可选栅格到终点的最大距离；MINd为可选的栅格到终点的最小距离；allowedi为当前栅格i中蚂蚁可选的栅格集合；eps为一个极小值，防止分母为0时无法计算；0≤p≤1为系数，可根据具体情况设置。

2.2.2 到起止点直线距离启发因子

在几何学中，两点之间直线距离最短。大部分最优路径都在起点和终点之间连线的附近[14]。计算所有可选栅格到起止点直线的距离，如式(9)所示

dli=|det([E-A,Pi-A])/norm(E-A)| (9)

式中dli为待选栅格i到起止点直线的距离；A,E分别为栅格地图中起点和终点的列向量坐标；Pi为栅格i的列向量坐标；det()为计算矩阵行列式的函数；norm()为求范数函数。

待选节点与起止点直线距离越短，起到的启发作用也大，提出到起止点直线距离启发因子函数如下

式中υ(i,j)为到起止点直线距离启发因子函数，dl为待选栅格j到起止点直线的距离；MAXdl,MINdl分别为可选栅格到起止点直线的最大距离和最小距离；系数p含义同前。

2.2.3 能耗启发因子

传统搜索方法通常出现较多的转弯次数和较大的转弯角度，导致能耗增多，提出了转弯能耗约束机器人路径选择。从上一节点到当前节点与当前节点到待选节点的转弯角度越大，能耗越大，该待选节点被选择的可能性越小。在栅格地图上，机器人的行进路径是从当前栅格到下一个栅格的积累过程，可转移的栅格为当前栅格邻接的8个方向的栅格。如图2所示，设8个邻接栅格的角度向量为集合Angle={3/4π,1/2π,1/4π,0,-1/4π,-1/2π,-3/4π,π}。则机器人转弯角度能耗的计算公式如式(13)所示

式中ωAngle(i,j)为从节点i到待选节点j的转弯角度能耗；θi为转移到节点i的角度；θj为转移到节点j的角度；ζ为转弯能耗系数，可根据具体情况设置。

图2 八邻域角度向量

在实际环境中，还要考虑坡度能耗。机器人从当前栅格节点到待选栅格节点的高度差越大，说明坡度越陡，对机器人损耗越大。为了让机器人行进路径尽量平缓，引入坡度能耗约束因子使得机器人行走路径更平滑。坡度能耗函数计算公式如式(14)所示

式中ωEng(i,j)为当前栅格节点到待选栅格节点坡度能耗；MAXh和MINh分别为地图中最大高度和最小高度；h(i),h(j)分别为栅格节点i和栅格节j的高度；ξ为坡度系数，可根据具体情况设置。

综合考虑转弯角度能耗和坡度能耗，可得综合能耗为

综合能耗启发因子归一化函数为

式中ψm(i,j)为蚂蚁m从当前节点i到待选节点j的综合能耗启发函数；MAXω,MINω分别为可选栅格综合能耗最大值和最小值；系数p含义同前。

2.3 优化信息素更新

2.3.1 信息素限制

随着迭代次数的增加，某条路径上的信息素会残留过多导致其他路径信息素被覆盖掉，使得路径搜索容易陷入局部最优。因此，利用最优蚂蚁和最差蚂蚁策略[15]将信息素设置在一个合理的范围[τMax,τMin]内，信息素限制计算公式如式(19)所示

2.3.2 改进信息素增量

当蚂蚁寻找到一条可行路径之后，会在路径上留下信息素引导后续蚂蚁选择该路径。在所有蚂蚁完成一次迭代后，对留在路径上的信息素进行一次全局更新，规则如式下

Δτi,j(t+1)为所有蚂蚁在第t次迭代结束时留在路径ij上的信息素总量；Sm(t)为第t次迭代时第m只蚂蚁找到可行路径解的综合指标，综合指标越小路径越优；Lm(t),Tm(t)分别为第t次迭代时第m只蚂蚁走过路径的长度和总能耗；w为路径长度权重系数，(1-w)为能耗权重系数，可根据具体情况设置；Q为信息素增强系数，一般为常数。

2.3.3 动态信息素挥发因子

采取动态信息素挥发策略设置信息素挥发因子ρ,以适应蚂蚁搜索的整个迭代过程。设置ρ初始值为0.3,最小值为0.2,每迭代一次，ρ自动调节为原来的0.95倍，当ρ小于最小值时，强制设置为最小值，计算公式如式(23)所示

通过对ρ进行动态设定，在算法初期，ρ取较大值，加快收敛，在算法中后期，ρ取较小值，避免陷入局部最优。

2.4 改进算法流程

应用于路径规划的改进蚁群算法流程如下：

1)初始化栅格地图、定义地图高度差矩阵、定义到终点距离矩阵、定义到起止直线的距离矩阵、定义八邻域角度向量、初始化信息素、将栅格地图坐标转换为栅格编号、初始化算法参数。

2)蚂蚁路径选择。将当前节点i加入禁忌表中，通过对八邻域矩阵D获取可选栅格，通过式(6)计算待选栅格到终点距离启发值、通过式(10)计算待选栅格到起止点直线距离启发值、通过式(15)计算待选栅格能耗启发值，最终通过式(5)计算待选栅格的多因子启发值。依据式(1)计算转移概率，通过轮盘赌选择下一个栅格节点j,并将节点j加入禁忌表中，如此循环，直到蚂蚁到达终点或无路可走。

3)当所有蚂蚁完成一次迭代后，根据式(22)计算本轮迭代所有找到可行解的蚂蚁的综合性能，记录本轮迭代综合性能最优的蚂蚁的路径长度、能耗、转弯次数、高度均方差和综合性能。

4)更新全局信息素。根据式(23)获取信息素挥发因子，通过式(20)对全局信息素更新，并检查信息素上下限，确保信息素浓度在范围内。

5)将禁忌表和转移方向矩阵清零，结束本次迭代。判断是否到达最大迭代次数，如果达到则输出综合性能最优蚂蚁的路径长度、能耗、转弯次数、高度均方差和综合性能；否则，迭代次数自加，重复第二步，直到迭代次数达最大值，获得综合性能最优路径，结束搜索。

3、仿真实验与分析

3.1 实验环境和参数

为了验证本文提出的改进算法在移动机器人路径规划中的有效性和可行性，利用MATLAB R2021b开展仿真实验。实验运行的软硬件环境为：Windows 10 专业版64位；处理器为11th Gen Intel®CoreTMi7—11700;主频2.50 GHz; 内存32 GB。为了更公平地与文献[7]的算法进行对比，所有仿真实验公共参数设置都与文献[7]一致，如表1所示。

表1 参数初始化设置

3.2 仿真结果分析

为了验证本文算法对移动机器人在不同规模栅格地图路径规划的可行性和有效性，选用了20×20和100×100这2种不同规模的地图环境进行对比实验。同时，为了验证算法的鲁棒性和稳定性，在多种规模环境各进行20次仿真实验。

3.2.1 直观对比

在20×20和100×100地图环境下，将本文算法与经典蚁群算法、文献[7]改进蚁群算法的实验结果进行对比。由于篇幅限制，仅展示3种算法在20×20地图环境的路径规划和最佳路径长度收敛曲线分别如图3所示。

图3 3种算法在20×20地图路径规划和收敛曲线

从实验结果可见，经典蚁群算法路径寻优能力较差，文献[7]改进蚁群算法收敛性较差，本文算法能够规划出更优的路径且容易收敛，适合用于移动机器人路径规划。

3.2.2 统计分析

为了进一步验证本文算法的稳定性和通用性，在参数不变的情况下，设置障碍物为10 %随机生成地图，分别得到20×20,50×50,100×100,200×200共4种从简单到较大规模的地图环境。3种算法在4种规模环境中均重复实验20次。由于篇幅限制，200×200地图环境的实验结果统计如表2所示。

表2 200×200环境下20次仿真实验结果统计

从实验统计结果可以得出，经典蚁群算法几乎在所有性能指标都比其他两种算法表现更差。在转弯次数指标上，文献[7]改进蚁群算法表现最优。但是，文献[7]改进蚁群算法的稳定性较差。本文算法在路径长度、综合指标和高度均方差这3个指标能获得最优结果，且稳定性最优。随着地图规模越大，本文算法的优势越明显。从综合应用方面考虑，本文算法在各种规模地图环境中都具有较好的最优性、鲁棒性和适用性。

4、结论

针对蚁群算法应用于移动机器人路径规划存在收敛速度慢、综合性能不优、表现不稳定等问题，本文提出了一种基于位置和能耗启发的改进蚁群算法。引入到终点距离启发因子、到起止点直线距离启发因子、路径高度差能耗启发因子和转弯角度能耗启发因子改进了启发函数。同时，优化了信息素更新策略，加快了算法收敛速度，并避免了陷入局部最优。多场景多次仿真实验的统计结果表明，本文改进的蚁群算法在路径长度、高度均方差、综合性能等方面均获得了较好的表现，且比先前算法更加稳定。

参考文献:

[5]戈一航,杨光永,于元滐,等.基于改进麻雀搜索算法的移动机器人路径规划[J].传感器与微系统,2023,42(7):132-135.

[6]陆顺意,何庆,王艺蒙,等.用于移动机器人路径规划的增强型蛇优化算法[J].传感器与微系统,2023,42(12):127-129,133.

[7]李理,李鸿,单宁波.多启发因素改进蚁群算法的路径规划[J].计算机工程与应用,2019,55(5):219-225,250.

[8]王丰,于浩.基于状态转移规则改进蚁群算法的机器人路径规划[J].组合机床与自动化加工技术,2023(11):28-33,37.

[9]周敬东,高伟周,杨文广,等.基于改进蚁群算法的移动机器人路径规划[J].科学技术与工程,2022,22(28):12484-12490.

[10]曾钰桔,陈波,瞿睿,等.基于改进蚁群算法的移动机器人路径规划研究[J].现代制造工程,2023(10):57-63,119.

[11]郝兆明,安平娟,李红岩,等.增强目标启发信息蚁群算法的移动机器人路径规划[J].科学技术与工程,2023,23(22):9585-9591.

[13]朱爱斌,刘洋洋,何大勇,等.解决路径规划局部极小问题的势场栅格法[J].机械设计与研究,2017,33(5):46-50.

[14]李开荣,刘爽,胡倩倩,等.基于转角约束的改进蚁群优化算法路径规划[J].计算机应用,2021,41(9):2560-2568.

基金资助:2022年度广西高校中青年教师科研基础能力提升项目(2022KY0767);

文章来源:李春青,黄勇萍,刘娟.基于位置和能耗启发的改进蚁群算法路径规划[J].传感器与微系统,2024,43(10):132-136.