142传感器与微系统(Transducer and Microsyslem Technologies)2021年第40卷第6期
DOI：10.13873/J.1000-9787(2021)06-0142-03
基于改进蚁群算法的移动机器人路径规划
高茂源，王好臣
（山东理工大学机械工程学院，山东淄博255000）
安全生产总结摘要：针对传统蚁群算法收敛速度较慢，易陷入局部最优，初始信息素匮乏等缺点，提岀一种改进的蚁
群算法。初始阶段在起点与终点的连线上额外增加信息素，提高算法的收敛速度；对原有启发函数中的启
发因子进行改进，提高算法的寻优效率；改进了信息素浓度的挥发公式，使其服从高斯分布，使信息素挥发
动态化。仿真结果表明：改进后的蚁群算法收敛速度更快，收敛性能更稳定，缩短了寻径距离，使机器人有
效避开障碍物，在移动机器人路径规划方面有很好的实用性。
关键词：路径规划；蚁群算法；移动机器人；信息素挥发因子
中图分类号：TP391；TP212文献标识码：A 文章编号：1000-9787（2021）06-0142-03
Path planning for mobile robots bad on improved
ant colony algorithm
GAO Maoyuan,WANG Haochen
(School of Mechanical Engineering,Shandong University of Technology,Zibo255000,China)
Abstract:Aiming al the shortcomings of traditional anl colony algorithm,such as slow convergence speed,easy to
fall into local optimum,and lack of initial pheromone,an improved ant colony algorithm is propod.In the initial
stage, the pheromone is additionally added on the connecting line between lhe starling point and the
ending point
to improve the convergence speed of the algorithm；the heuristic factor in the original heuristic function is improved
to improve the optimizing efficiency of the algorithm；and the volatilization formula of the pheromone concentration
is improved,which let it obeys the Gaussian distribution and makes the pheromone volatilization dynamic.The
simulation results show that lhe improved ant colony algorithm has faster convergence speed,more stable
convergence performance,shortens the path-finding distance,and makes the robot effectively avoid obstacles, it has
good practicality,in mobile robot path.
Keywords:path planning；ant colony algorithm；mobile robot；pheromone volatilization factor
0引言
近年来人工智能领域快速发展，移动机器人路径规划⑴被广泛应用于自动驾驶、物流分拣运输等领域。移动机器人的路径规划在国内外得到广泛的研究，常用算法包括遗传算法、神经网络算法、A”算法等，各个优化方法有各自的优势，同时也并存在了明显的不足⑵。蚁群算法（ant colony algorithm），被用于解决指派问题、旅行商问题以及车辆路由问题等⑶幻。其采用分布式并行计算机制，具有鲁棒性强，易于其他算法相结合等诸多优点，受到研究者们的广泛关注。但蚁群算法也有着收敛速度较慢，搜索效率低且时间长以及易陷入局部最优等不足之处，不利于高效率、高精度的求解优化问题。针对上述问题，本文提出了一种改进的蚁群算法，对算法的局部进行改进，达到提高搜索效率与寻优能力。1问题描述与环境建模
当移动机器人承担某项任务时，首先根据周边环境信息建立环境模型，通过自身算法对环境中的障碍物等进行定位、避障，从而获得最优路径。对移动机器人进行路径优化需要对机器人的运动空间进行数字建模处理，即运动空间与数学模型的转换，便于机器人识别与分析。本文机器人路径规划问题满足以下条件：1）机器人运动空间是二维有限空间，且空间中障碍物位置已知;2）障碍物随机分布在机器人运动空间中，且大小性状不发生变化，忽略其高度;3）不考虑机器人与机器人间和机器人与障碍物之间的碰撞;4）已知机器人起始位置与目标位置。最终经过路径规划实现移动机器人在所搭建的环境模型中寻找到最优路径。
栅格法建模方法简单，易于实现，是进行机器人路径规划中环境建模常用的方法⑸6〕。机器人运动空间中用大小
收稿日期：2019-11-12
第6期高茂源，等：基于改进蚁群算法的移动机器人路径规划143
相同的栅格划分工作区域，将机器人理想化为一个质点，保
证机器人的停留位置全部都在栅格的中心点。在二维运动
空间中的栅格分为黑色栅格和白色栅格，其中白色栅格表
示可行走栅格，用1表示；黑色栅格表示障碍物栅格，用0
表示。将创建的二维空间进行等分，按照从左到右，从上到
下的顺序，对每个栅格进行编号⑺。如图1为利用栅格法
构造的环境模型。
START
1020
图1环境模型
各栅格点的坐标数学表达式为
[X：=6x(mod(j,MM)—0.5)
(1)
Ly,=1)x(MM+0.5—ceil(i/MM))
式中b为栅格边长;mod为取余;MM为地图维度;ceil为
朝正无穷大四舍五入肉"为每个栅格的坐标位置。
2传统蚁群算法
蚂蚁在寻找食物源时，会在走过的路径上释放一种信
息素，并且能够感知其他蚂蚁所留下的信息素。其中信息
素浓度的大小表征路径的远近，信息素浓度越高，表示对应
的路径距离越短，反之，则越长。通常蚂蚁会以较大的概率
优先选择信息素浓度较高的路径并释放一定量的信息素，
以增强该条路径的信息素浓度，同时路径上的信息素浓度
会随时间的推进而逐渐衰减，由此对蚂蚁路径的选择形成
一个正反馈，最终，蚂蚁就能够找到一条从巢穴到食物源的
最优路径，即距离最短⑻。图2为蚁群算法寻优原理图。
图2蚁群算法寻优原理
传统蚁群算法的机器人路径规划执行步骤可描述为:
利用栅格法搭建机器人坏境模型，进行参数的初始化，蚂蚁
根据在各个位置的信息素浓度(初始阶段信息素浓度为常
数，即=C)由当前节点i转移至下一节点j时，根据函
数方程式(2)选择节点j的位置
[©(t)]"•[%(/)]"£[九⑴]“•[加⑴卩k allow匕
0,j E allow.j e allow k
式中T iy(0为栅格节点：J之间的信息素浓度；W=1/%
为启发函数，表示蚂蚁由节点i行走至节点j的期望程度，
心为栅格节点㈡之间的距离;Q〃。叫为下一步待访问节点
的集合;a为信息素重要程度因子;0为启发函数重要程度
因子。
经过一定时刻后，当某一代所有数量的蚂蚁全部寻径
结束后，根据方程式(3)~式(5)更新信息素浓度丁
r,y(t+n)=(l-p)-T(>(0+Ar,y(3)
△心=X M(t)(4)
k=\
£.r Q/S，若k只蚂蚁在本次循环中经过路径ij
A t-(«)={
[0，否则
(5)
式中△◎(/)为蚂蚁在栅格：至栅格j之间路径上的信息
素浓度;P为信息素挥发系数;Q为信息素增加强度系数;
A为蚂蚁鸟从起点到目标点所行走的路径长度。直到达
到规定迭代次数，得到最优解，输出最优路径。
3改进的蚁群算法
3.1启发函数
蚁群算法中启发函数wQ)=1/切，表明蚂蚁从节点i
行走至栅格j的期望程度与节点之间的距离相关联|9'U]o
迭代次数过少，算法可能无法找到最优路径，而随着迭代次
数的增多，算法耗时加大，导致收敛速度较慢。
本文研究针对算法此缺陷对启发函数％(t)进行了改
进，对蚂蚁从栅格i行走至栅格_/的方向进行引导，增强其
行走的期望程度。改进后的启发算子为=
尹，大大增加了算法的有效性，提高了算法寻优的
效率，缩短收敛时间，使蚂蚁以更快的速度朝着最优路径搜
索方向进行。
3.2初始化信息素浓度的改进
在算法初始化参数阶段，设定信息素浓度矩阵Tau时,
虽将所有可能的路径设定为相同值，但蚁群算法的寻径是
蚂蚁从起点岀发行走至终点的过程，故可在起点与终点的
路径以及周围将信息素浓度值设定比其他位置高，这样可
以有利于增强最优路径对蚁群的吸引力，加快最优解的收
敛速度。
3.3信息素挥发因子p的改进
蚁群在其行走的路径上会留下信息素，信息素浓度并
不会一直不变，而是会随着时间挥发。信息素挥发因子表
示蚁群信息素的挥发速度。传统蚁群算法的信息素挥发速
度在寻径过程中为常量。蚁群算法的挥发因子与收敛速度
和全局搜索能力相关联，若挥发因子。的值过小时，蚂蚁会
再次选择已走过的路径，陷入局部最优；反之，若P值过大，
算法的全局搜索能力有所提升，但算法的迭代时间会大幅
增加，导致收敛速度降低⑵。本文提出的改进信息素挥发因子与迭代次数相关联，使信息素挥发因子P随迭代次数佥服从高斯分布。改进的信息素挥发因子P为
pw=----•exp(-歸；0)-a(6) a•v2tt
这里称k服从参数O■，“的高斯分布，其中可根据设定的迭代次数自适应调整；本文取值分别为7.4, 90必表示算法的迭代次数。
这样蚂蚁在寻径时处于不同迭代次数时具有不同的信息素挥发因子P，使其根据迭代次数动态调整，将算法分为前、中、后期。在蚁群寻径的前期，即迭代次数处于［0, 0.4们时，信息素挥发因子为较小值并呈递增趋势，蚁群选择路径主要根据初始化的信息素浓度；随着迭代次数的增加，信息素挥发因子P逐渐增大，当迭代次数处于［0.4k, 0.7k］区间时，各路径上信息素量达到一定程度，此时信息素挥发因子p为较大值，即各路径信息素挥发快，便于使蚁群开展全局搜索；当迭代次数处于［0.7k,k］时，信息素挥发因子P随迭代次数《递减，即在算法的后期，蚁群基本已寻找到最优路径，降低信息素挥发因子P加快最优路径的收敛速度。
4仿真与分析
为验证优化算法的性能，在MATLAB上对改进蚁群算法的正确性和有效性进行测试，并比较利用传统蚁群算法和改进蚁群算法机器人进行路径规划的实际效果。利用栅格法建立二维栅格地图，环境模型为20X20的栅格。单位栅格长度为1，总长20，设置机器人为(0.5,19.5)，终点为(19.5,0.5)。实验过程中蚂蚁数目(皿值)设定为60。设置仿真参数：迭代次数为200次，信息素重要程度因子a= 1，启发函数重要程度因子0=6.8，信息素增加强度系数0=1，传统蚁群算法信息素挥发系数卩=0.5。改进蚁群算法p为上文自适应参数，传统蚁群与改进蚁群算法所设定的蚂蚁数目相同。本文对传统蚁群算法和改进蚁群算法分别进行多次仿真测试，测试结果如表1所示。
表1传统蚁群算法和改进蚁群算法测试结果比较
算法收敛代数最优距离传统蚁群算法16630.4589
改进蚁群算法3128.2132从表1可以看出，改进蚁群算法较传统蚁群算法的收敛代数和最优距离都有所减少，改进蚁群算法收敛代数减少了135代，最优距离减少了2m。
为更直观分析测试过程和仿真结果，将移动机器人寻优路径的收敛代数和所行走的轨迹进行可视化，如图3所示。
由图3(al),(bl)可以看出，两种算法都能为移动机器人规划无障碍路径，从机器人路径轨迹图上看，传统蚁群算
孝昭仁皇后6
2
8
4
2
1
1
04121620
坐标兀
o
o
O
3俞济时
2
1
04080120160
迭代次数
200
4()
(al)机器人运动轨迹(a2)收敛代数0
仗)传统蚁群算法移动机器人最短路径轨迹迭代■
20
16
12
8
4
048121620
坐标％
04080120160
迭代次数
200
40
30
20
10
(bl)机器人运动轨迹(b2)收敛代数
(b)改进蚁群算法移动机器人最短路径轨迹迭代
图3移动机器人路径寻优结果
法寻优路径转弯次数多，运动轨迹曲折，而改进后的蚁群算法运动轨迹转弯次数少，轨迹较平滑。从收敛代数上看，传统蚁群算法收敛速度慢，且收敛性能不稳定，搜索效率低。而改进的传统蚁群算法明显提高了收敛速度，收敛性能更稳定，搜索效率更高，提高了全局寻优能力，说明改进后的蚁群算法在移动机器人寻优方面有着明显的优越性。
与荷花有关的诗句5结束语
本文通过建立环境模型，分析传统蚁群算法的不足，并针对其不足在信息素启发函数、信息素初始值，信息素挥发因子方面对传统蚁群算法进行改进。通过MATLAB进行仿真，仿真结果表明：改进蚁群算法较传统蚁群算法在收敛速度，全局寻优，以及最优路径距离方面有明显的提升，证明了该算法的有效性和可行性。
参考文献：
［1］占伟，屈军锁，芦鑫，等•基于改进蚁群算法的移动机器人全局路径规划［J］•现代电子技术,2018,41(24)：170-173.［2］武凌宇，王晓东，吴建德•基于蚁群算法的机器人系统LQR 最优控制研究［J］•传感器与微系统,2018,37(1):56-59.［3］肖艳秋，焦建强，乔东平，等•蚁群算法的基本原理及应用综述［J］.轻工科技,2018,34(3)：69-72.
［4］王春华，邱立鹏，潘德文•改进蚁群算法的机器人焊接路径规划［J］•传感器与微系统,2017,36(2):75-77.
［5］时丕芳，赵永瑞•移动机器人行走路径环境建模方法综述与解析［J］.现代制造技术与装备,2010(1):1-2,6.
离子选择电极［6］陈至坤•移动机器人目标路径规划的仿真研究［•!］•计算机仿真,2016,33(5)：290-294.
［7］刘宏波，高俊，古尚利•基于栅格化空域的数据链站点选址优化［J］•火力与指挥控制,2015,40(12)：18-21.
［8］尹元元，游晓明，许明乐，等.基于动态启发算子的双种群蚁群算法及其应用［J］•传感器与微系统,2018,37(9)：158-160.
收到基(下转第148
个人总结结尾
页)
为0.5369,DSST由于使用了尺度信息获得的分数比KCF 更高，为0.5613分。然而，本文的追踪器进一步提升了追踪效果，使分数达到了0.5800o
图3提供了一些追踪结果的例子，分别对应光照变化，平面外旋转，杂乱背景以及遮挡等各种干扰因子。相较于其它的算法，本文算法可以更有效地抵制各种不利因素，实现更加准确的追踪效果。
通过添加一个额外的核相关滤波器，可以实现对目标尺度变化的有力应对。此算法在中心距离和交叉面积两方面都优于标准核相关滤波器。若使用传统方法，则需要在每一个尺度上都进行一次标准KCF算法，这会使算法的处理时长增加至大约S倍。但本文算法仅用8倍时间就处理了33个尺度。实验结果表明：本文算法可以有效地处理尺度变化带来的问题。
参考文献：
[1]COMANICIU D,RAMESH V,MEER P,et al.Real-time tracking
of non・rigid objects using mean shift[C]〃Computer Vision and Pattern Recognition,2000:142—149.
[2]NUMMIARO K,KOLLER-MEIER E,GOOL L V.An adaptive
color-bad particle filler[J_.Image and Vision Computing, 2003,21(1):99-110.
[3]ROSS D A,LIM J,LIN R S,et al.Incremental learning for robust
visual tracking[J].International Journal of Computer Vision, 2008,77(1-3)：125-141.
[4]陈秀宏，葛骁倩，傅俊鹏.一种基于局部敏感直方图的时空上
下文跟踪方法[J]•传感器与微系统,2017,36(1)：149-152.
[5]LIU B,HUANG J,YANG L,el al.Robust tracking using local
spar appearance model and K-lection[C]〃Computer Vision and Pattern Recognition,2011：1313—1320.
(上接第144页)
[9]王红君•基于平滑蚁群算法的机器人路径规划[J].燕山大学
学报,2017,41(3)：278-282.
[10]倪壮，肖刚，敬忠良，等•改进蚁群算法的飞机冲突解脱路径
规划方法[J].传感器与微系统,2016,35(4)：130-133. [11]李长生•基于蚁群算法的云计算任务调度优化研究[J]・自动
化技术与应用,2019,38(3)：39-42.[6]HENRIQUES J F,CASEIRO R,MARTINS P,et al.Exploiting the
circulant structure of tracking-by-detection with kernels[C]〃
European Conference on Computer Vision,2012：702—715. [7]DANELLJAN M, KIIAN F S, FELSBERG M, et al.Adaptive color
attributes for real-lime visual tracking[C]//Computer Vision and Pattern Recognition Conf,2014：1090—1097.
6t管理
[8]KRISTAN M,MATAS J丄E ON A RDIS A,et al.The visual object
tracking VOT2015challenge results[C]〃International
Conference on Computer Vision,2015：564—586.
[9]BOLME D S,BEVERIDGE J R,DRAPER B A,et al.Visual
object tracking using adaptive conelalion filters[C J//Computer
Vision and Pattern Recognition Conf,2010：2544—2550.
[10]GALOOGAH1H K,SIM T,LUCEY S,et al.Correlation filters
with limited boundaries[C]〃Computer Vision and Pattern
Recognition Conf,2015：4630—4638.
[11]HENRIQUES J F,CASEIRO R,MARTINS P,et al.High-speed
tracking with kernelized conelalion filters]J].IEEE Transactions on
Pattern Analysis and Machine Intelligence,2015,37(3)：583—596. [12]MUELLER M,SMITH N,GHANEM B.Context-aware correlation
filter tracking[C]〃Computer Vision and Pattern Recognition
Conf,2017：1387-1395.
[13]DAVIS P.Circulant matrices[MJ.Providence:American Mathe
matical Society,2012.
[14]DANELLJAN M,HAGER G,KHAN F S,et al.Discriminative
scale space tracking[J.IEEE Transactions on Pattern Analysis
and Machine Intelligence,2017,39(8)：1561—1575.
[15]WU Y,L【M J,YANG M,et al.Online object tracking：A bench
mark[C~\//Computer Vision and Pattern Recognition Conf,2013:
2411-241&
[16]WU Y,LIM J,YANG M,et al.Object tracking benchmark[J].
IEEE Transactions on Pattern Analysis and Machine Intelligence,
2015,37(9)：1834-1848.
作者简介：
时鹏飞(1994-)，男，硕士研究生，研究方向为图像处理。
高清维(1965-)，男，通讯作者，博士，教授，博士研究生导师，主要从事数字信号处理，小波变换及应用研究工作。
卢一相(1980-)，男，博士，副教授，硕士研究生导师，主要从事稀疏表达及图像处理的理论与应用研究工作。
孙冬(1983-)，男，博士，副教授，硕士研究生导师，主要从事机器学习，稀疏表达研究工作。
[12]刘学芳，曾国辉，刘瑾•基于改进蚁群算法的机器人路径规划
算法[J]•传感器与微系统,2019,38(10)：129-131,138.
作者简介：
高茂源(1996-)，男，硕士研究生，研究方向为机器人技术，智能算法。
王好臣(1962—)，男，通讯作者，教授，研究领域为机器人技术
。
