基于改进蚁群算法的机器人路径规划方法_王星宇.pdf

电子技术应用 2023年 第49卷 第1期Computer Technology and Its Applications计算机技术与应用基于改进蚁群算法的机器人路径规划方法*王星宇1，胡燕海1，徐坚磊2，陈海辉2（1.宁波大学 机械工程与力学学院，浙江 宁波 315211；2.宁波航工智能装备有限公司，浙江 宁波 315311）摘 要：根据传统蚁群算法在机器人的路线规划中具有收敛速度慢、容易陷入局部最优解的缺陷，提供了一个经过改进的蚁群算法。使用栅格法建立路径矩阵，建立一种转角启发函数，增加选择指定路径的概率，提高算法的搜索速度；将 A*算法与改进蚁群算法结合，提出一种改进的距离启发函数，避免了陷入局部最优解；并提出一种可根据迭代次数而改变的信息素挥发因子，增强了全域搜寻能力。根据相关数据分析，与 Ant Colony Algorithm with Multiple Inspired Factor（ACAM）算法相比，改进的蚁群算法对于解决算法收敛速度慢、防止进入局部最优解等方面效果更好。关键词：改进蚁群算法；机器人；栅格法；A*算法中图分类号：TP301.6 文献标志码：A DOI:10.16157/j.issn.0258-7998.222741中文引用格式：王星宇，胡燕海，徐坚磊，等.基于改进蚁群算法的机器人路径规划方法J.电子技术应用，2023，49(1)：75-80.英文引用格式：Wang Xingyu，Hu Yanhai，Xu Jianlei，et al.Robot path planning method based on improved ant colony algorithmJ.Application of Electronic Technique，2023，49(1)：75-80.Robot path planning method based on improved ant colony algorithmWang Xingyu1，Hu Yanhai1，Xu Jianlei2，Chen Haihui2(1.School of Mechanical Engineering and Mechanics，Ningbo University，Ningbo 315211，China；2.Ningbo Hanggong Intelligent Equipment Co.，Ltd.，Ningbo 315311，China)Abstract：An improved ant colony algorithm is provided according to the disadvantage of slow convergence and easy to fall into local optimal solution of traditional ant colony algorithm in robot route planning.The raster method is used to build the path matrix,and a corner heuristic function is established to increase the probability of selecting a specified path and improve the search speed of the algorithm.Combining A*algorithm with improved ant colony algorithm,an improved distance heuristic is proposed to avoid falling into local optimal solution.A pheromone volatile factor which can be changed according to the number of iterations was proposed to enhance the global search ability.Based on the related data analysis,the improved ant colony algorithm is better than Ant Colony Algorithm with Multiple Inspired Factor(ACAM)algorithm in resolving problems such as slow convergence rate and preventing entering local optimal solution.Key words：improved ant colony algorithm；robot；Grid method；A*algorithm0 引言近年来,由于世界科学技术的蓬勃发展,机器人也逐渐走入中国大众的视野。路径规划是机器人控制中一个无法避免的问题。迄今为止，在机器人的路径规划问题上,已经有不少前辈做过难以计量的研究。常规的路径算法有 Dijstra 算法1、A*算法2、人工势场法3等。随着机器人科技的蓬勃发展,传统的算法很难满足当前路径规划的需求,于是智能的仿生算法应运而生，如遗传算法4、粒子群算法5、蝙蝠算法6、蚁群算法7等。蚁群算法可以利用全局搜索找到更优解,并具有很强的并行性,个体间也能够相互传递信息,并可以迅速收敛到解空间的某一子集,从而促进了对解空间的深入研究8。传统的蚁群算法由于其本身的原因，存在收敛速度不足、无法合理避开局部最优解的问题9。为克服传统蚁群算法在路径规划上的不足，王晓燕等人10提出一种全静态环境下的改进蚁群算法，用人工*基金项目：国家自然科学基金（51705263）；宁波市“科技创新 2025”重大专项(2020Z079)75Computer Technology and Its Applications计算机技术与应用www.ChinaAET.com势场求得的初始路径和下一个节点间距离构成距离启发式,并引入启发信息递减系数，避免了陷入局部最优解的情况；牛龙辉等人11构造了一种动态的信息素挥发系数，改变了算法在不同时期的搜索侧重点，加快了算法的收敛速度并且丰富了多样性；李理等人12提出了Ant Colony Algorithm with Multiple Inspired Factor(ACAM)算法，该算法提出一种新的距离启发函数、改进了信息素的更新方式,一定程度上解决了传统蚁群算法收敛速度以及路径平稳性方面的问题。本文提出一种改进的蚁群算法，建立一种转角启发函数,使蚂蚁选择路径有更强的目的性;融合 A*算法改进了距离启发函数,加入了距离的估算代价;并提出一种可根据迭代次数而改变的信息素挥发因子。1 建立栅格地图及机器人移动方向栅格法具有构建方便、表达清晰、测试性能好等优势,因此本文主要使用栅格法构建路径地图,如图 1 所示。栅格法使用黑白二色来代表可以移动的路径以及障碍,矩阵中用 1 来代表黑色即障碍,0 代表白色即可通行的路段。机器人的移动方法使用八叉树搜索策略,即机器人处于栅格地图中时,可以向其周围 8 个方向进行运动,每次只能移动一个栅格。2 蚁群算法及其改进2.1 传统蚁群算法蚁群算法是模拟蚂蚁在路面上移动的算法，蚂蚁在行走的路段上会释放一种包含已知信息的激素，这种激素在空气中会自行挥发，故较长路段所残留下的激素要少于较短路段。而激素残余量的多寡会影响下一只蚂蚁的选择，故多数蚂蚁会选择较短的路径。这种包含已知信息的激素称为信息素。2.1.1 转移概率蚂蚁从当前节点转移到下一节点的行为叫作状态转移，转移概率由距离启发式函数以及信息素的浓度共同确定。转移概率如式（1）所示：pij=ij(t)ij(t)s allowedkis(t)is(t),j allowedk 0,其他(1)式中，为信息素因子，值的大小对蚂蚁的移动有着较大的影响；为距离启发函数因子,反映两节点间的距离对蚂蚁移动的影响；ij(t)表示在 t 时刻蚂蚁从当前节点移动到下一节点的信息素浓度；ij(t)为距离启发函数；dij为当前节点到下一节点的直线距离；allowedk为蚂蚁可选择的下一节点的集合。其中：ij(t)=1dij(2)dij=(xi-xj)2+(yi-yj)2(3)2.1.2 信息素更新策略由于信息素具有挥发性，故每迭代一次，信息素都需要重新计算。信息素更新公式如式(4)式(6)所示：ij=(1-)ij(t)+ij(4)ij=k=1mkij(5)kij=QLk,i k j 0,其他(6)式中，为信息素挥发因子,通常取 0 minmin,其他(11)式中，K 为最大迭代次数；为一常数，可根据迭代情况而改变。2.2.4 改进蚁群算法步骤(1)建立栅格地图、设置迭代次数、蚂蚁数量、信息素因子、启发函数因子、信息素挥发因子、信息素强度等初始参数。(2)将所有蚂蚁置于起点开始寻路。(3)蚂蚁根据转角启发式寻找下一步。(4)更新节点和禁忌表。(5)判断寻找的路线能不能够走到终点，若不能，则重新根据转角启发式寻找下一步；若能，则进入下一步。(6)更新路径信息。(7)根据迭代次数调整信息素挥发因子。(8)判断是否达到最大迭代次数，若没有则返回步骤(3)；若达到最大迭代次数，则输出记录中的最优路径。改进蚁群算法步骤流程图如图 2 所示。3 仿真分析为了验证改进蚁群算法的改善效果，将本文提出的算 法 与 传 统 蚁 群 算 法、ACAM 算 法 加 以 比 较。使 用MATLAB 在栅格总数为 400 的方形栅格地图中进行对比试验。运行多次取其中最优解进行比较。实验设置两种不同的栅格地图，一种为常规的栅格地图，简称常规地图；另一种为包含 U 形障碍的栅格地图，简称 U 形地图。保持 3个算法的初始参数相同。初始参数如表 1所示。其中，本文提出的自适应信息素挥发因子设为 0=0.9，min=0.3。3.1 常规地图运行结果3 种算法在常规地图中运行结果如图 3图 8 所示。常规地图 3 种算法仿真结果如表 2 所示。从以上图表可知，在常规地图中，传统蚁群算法由于其距离启发函数的不足，容易陷入局部最优解，且收敛时间也较慢；ACAM 算法弥补了收敛速度不足的问题，提高了平稳性，对于防止陷入局部最优也有一定的作用；本文的改进蚁群算法在收敛速度以及避免局部最优解方面的表现比 ACAM 算法更优。表 1初始参数参数迭代次数/次蚂蚁数量/个信息素因子启发函数因子信息素挥发因子信息素强度符号KMQ值100501.570.31表 23 种算法常规地图结果对比算法传统蚁群ACAM本文改进稳定次数2028耗时/s4.421 722.840 972.369 48路径长度/mm31.213 2034.485 2829.798 99拐点数目511图 2改进蚁群算法步骤77Computer Technology and Its Applications计算机技术与应用www.ChinaAET.com3.2 U 形地图运行结果为了验证 3 种算法在特殊栅格地图中的表现，设置一种含有 U 形陷阱的地图，简称 U 形地图。3 种 算 法 在 U 形 地 图 中 运 行 结 果 如 图 9 图 14所示。U 形地图 3 种算法仿真结果如表 3 所示。从以上图表可知，传统蚁群算法在 U 形地图中依然存在和常规地图中一样的缺点；与传统蚁群算法相比，ACAM 算法依然存在平稳性好、收敛速度快的优点；本文算法与 ACAM 算法相比依然有收敛速度快、能减小陷入局部最优解概率的优势。综合上述对比实验，可以发现本文所改进的蚁群算法在收敛速度以及避免陷入局部最优解方面有较好的表现。4 结论本文提出的改进蚁群算法，为了增加指定路径的选择性建立了一种转角启发函数，通过引入 A*算法在距离估算上的优势，改进了原有的启发函数，并提出一种可根据迭代次数而改变的信息素挥发因子。仿真结果表明，该算法在机