文档介绍：该【基于变步长蚁群算法的移动机器人路径规划 】是由【住儿】上传分享，文档一共【8】页，该文档可以免费在线阅读，需要了解更多关于【基于变步长蚁群算法的移动机器人路径规划 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第16卷第2期智 能 系 统 学
DOI:
网络出版地址:.
基于变步长蚁群算法的移动机器人路径规划
徐玉琼1,2,3,娄柯2,3,李志锟2,3
(,广东广州511370;
验室,安徽芜湖241000;,安徽芜湖241000)
摘要:针对传统蚁群算法以及双层蚁群算法在路径规划中存在搜索效率低、收敛性较慢以及成本较高的问
题,本文提出了变步长蚁群算法。该算法扩大蚁群可移动位置的集合,通过对跳点的选择以达到变步长策略,
有效缩短移动机器人路径长度;初始化信息素采用不均匀分布,加强起点至终点直线所涉及到栅格的信息素浓
度平行地向外衰减;改进启发式信息矩阵,调整移动机器人当前位置到终点位置的启发函数计算方法。试验结
果表明:变步长蚁群算法在路径长度及收敛速度两方面均优于双层蚁群算法及传统蚁群算法,验证了变步长蚁
群算法的有效性和优越性,是解决移动机器人路径规划问题的有效算法。
关键词:传统蚁群算法;双层蚁群算法;路径规划;变步长;信息素;启发函数;收敛;移动机器人
中图分类号::A文章编号:1673−4785(2021)02−0330−08
中文引用格式:徐玉琼,娄柯,[J].智能系统学报,2021,16(2):
330–337.
英文引用格式:XUYuqiong,LOUKe,-stepantcolonyalgorithm[J].
CAAItransactionsonintelligentsystems,2021,16(2):330–337.
Mobilerobotpathplanningbasedonvariable-stepantcolonyalgorithm
XUYuqiong1,2,3,LOUKe2,3,LIZhikun2,3
(,SongtianCollege,GuangzhouUniversity,Guangzhou511370,China;
LaboratoryofAdvancedPerceptionandIntelligentControlofHigh-EndEquipment,MinistryofEducation,Wuhu241000,China;-
huiProvincialKeyLaboratoryofElectricTransmissionandControl,AnhuiPolytechnicUniversity,Wuhu241000,China)
Abstract:Toaddresstheproblemsofthetraditionalanddouble-layerantcolonyalgorithms,suchastheirlowsearchef-
ficiency,slowconvergence,andhighpath–planningcost,inthispaperweproposeavariable-stepantcolonyalgorithm.
Theproposedalgorithmexpandsthesetofmobilelocationsoftheantcolony,andusesthevariable-stepstrategyofse-
lectingthehoppingpoints,
adoptsanunevendistribution,whichincreasesthepheromoneconcentrationofthegridinastraightlinefromthestartto
endpoints,
experimentalresultsshowthattheperformanceofthevariable-stepantcolonyalgorithmissuperiortothoseofthe
double-layerandtraditionalantcolonyalgorithmswithrespecttopathlengthandconvergencespeed,whichprovesitseff-
,theproposedalgorithmiseffectiveinsolvingthepath-planningproblemofmobilerobots.
Keywords:traditionalantcolonyalgorithm;double-layerantcolonyalgorithm;pathplanning;variable-step;pher-
omone;heuristicfunction;convergence;mobilerobot
在移动机器人领域,路径规划技术一直都是
收稿日期:2020−04−:2020−07−,其任务是在地图环境中为移动机
基金项目:国家自然科学基金项目(61572032);安徽省高校自
然科学研究重点项目(KJ2019A0151,KJ2019A0150);器人从起点至终点避开障碍物而规划出的最优路
2018年度皖江高端装备制造协同创新中心开放基
金项目(GCKJ2018009).径。目前国内外学者针对路径规划技术做了诸多
通信作者:-mail:******@,并取得相应成果,常用的传统路径规划算
第2期徐玉琼,等:基于变步长蚁群算法的移动机器人路径规划·331·
法有遗传算法、模拟退火算法、人工势场法、径规划,因此,需要对移动机器人工作环境进行
A*算法[1]等。随着人工智能技术的高速发展,群建模,常规环境建模方法如栅格图法[16-18]、可视
智能算法在路径规划技术中得到广泛应用和发图空间法、自由空间法、几何信息法等。本文选
展,如人工鱼群算法、蜂群算法、蚁群算法[2-4]、蛙取栅格图法对移动机器人二维空间进行建模,将
跳算法等,人工鱼群算法是一种擅长随机搜索的栅格分为黑色区域和白色区域,其中黑色区域为
算法,其算法原理简单,对初始值要求较低,但在障碍物栅格,白色区域为自由栅格,机器人可以
算法后期存在收敛速率缓慢、计算结果不够精在白色区域自由移动,如图1所示,假设每个栅
确。蜂群算法作为模仿蜜蜂行为提出的启发式算格为边长为1m的正方形,不考虑机器人自身身
法,通过对单一的蜜蜂进行局部寻优,突出全局高和体积的影响,机器人始终处于正方形的正中
最优值,容易陷入局部最优,其算法鲁棒性不
心位置。
强。传统的群智能算法已经无法满足移动机器人20
在复杂环境下进行路径规划,因此,大量学者通
过对传统的群智能算法进行改进,如多策略人工15
鱼群算法[5-7]、双层蚁群算法[8]、启发机制下的蚁群
10
算法[9]等。改进的群智能算法已经明显提高复杂
环境下移动机器人的路径规划[10-15]能力。
5
蚁群算法作为启发式全局优化算法是由意大
利学者Dorigo在1992年提出,该算法得益于采用
02468101214161820单位:m
正反馈机制,收敛性能大幅提升,通过分布式计
算方式进行搜索以及不同个体同时并行计算,提图1栅格地图
高了该算法的运算效率以及计算能力,但仍存在
收敛速度慢以及死锁问题。因此,文献[9]
群算法进行改进,提出了基于启发式机制的蚁群传统蚁群算法中蚁群为单步长√[19-20]移动方
算法,该算法通过当前节点到终点的距离动态的式,每步移动距离为1或2个单元格,在不碰撞
调整启发函数,当算法处于局部最优时,引入惩障碍物的情况下,可以向四周共8个方向移动,如
罚函数机制,降低最优路径的信息素,减少蚁群图2所示。
算法的正反馈影响而跳出局部最优。文献[14]主
要针对于蚁群算法收敛速度慢进行改进,合理分
配信息素初始浓度,动态调整信息素挥发因子,
进行二次路径规划,有效缩短了移动机器人的路
径长度。文献[8]设计了双层蚁群算法,对移动
机器人二维栅格环境进行凸化处理,同时用外层
蚁群探索出一条路径作为一个小环境,内层蚁群
在该环境下重新探索,两条路径择优筛选,提高
蚁群算法路径搜索质量。
为了提高蚁群算法收敛速度以及缩短路径长
度,本文提出变步长蚁群算法,寻找移动机器人图2移动方式
可以达到的跳点,得到不同长度的路径,根据路
径长度的不同,不均匀分配初始信息素浓度,以蚁群在寻路过程中,利用信息素相互通信,
降低边缘障碍物对移动机器人的影响,从而提高在经过的路径上释放信息素,当某一条路径通
算法的计算能力。改进启发式信息矩阵,提高蚁过的蚂蚁越来越多时,该路径的信息素浓度就
群避障能力,增强蚁群全局路径搜索能力,快速越高,其他蚂蚁选择该路径的概率就越大,起到
找到最优路径。正反馈作用,同时也容易陷入局部最优及存在
1蚁群算法原理死锁现象。信息素会随着时间的增长而挥发,
动态的调整各路径的信息素浓度,蚂蚁在选择
,会对信息素浓度、启发因子、路径方向
移动机器人需要在二维空间环境下进行路等因素进行综合判断选择下一步移动位置,并
·332·智 能 系 统 学 报第16卷
利用***,节点2至节点3路径长度为2m,因此,方
概率:,方案2为节点1变步
[τ(t)]α·[η(t)]β455
∑ijij,∈长跳跃至节点再到节点,最后由节点单步移
jak
τα·ηβ
k=[is(t)][is(t)]动至终点3,,方案
pij(t)(1)
s∈a
k3为传统蚁群算法的单步长移动方式,从当前节
0,其他
点1到节点6,再移动到节点7,再移动到节点8,
η=1
ij(2)最后再到终点3,,方
dij
τ,η案4为节点1跳跃至节点9,从节点9单步长移动
式中:ij为路径(ij)上的信息素;ij为位置i到
到节点8,最后移动到终点3,该方案路径总长度
位置j的启发因子;ak为蚂蚁k下一步可到达节
,显然,方案2作为变步长移动方式优于
点的集合;α表征信息素重要程度;β表征启发因
其他方案,变步长蚁群算法在寻路过程中,对每
子重要程度;dij是蚂蚁从位置i到位置j构建的
种方案的路径长度进行评估,最终挑选出路径最
路径长度。
短的方案。
为了避免蚂蚁选择已经达到过的节点,采用
禁忌表记录蚂蚁k当前所达到过的位置,经过t
1
时刻,所有蚂蚁都已完成了一次路径规划,计算
所有蚂蚁完成的有效路径长度,筛选出最短路径
9
长度,同时更新各路径上的信息素,经过时间的67
增长,信息素将挥发一部分:
τ=−ρτ4
ij(1)ij(3)8
式中:ρ是信息素挥发系数,同时,蚂蚁也将在路
径中释放信息素:5
∑m23
τ=τ+∆τk
ijijij(4)
k=1
图3步长选择
式中:∆τk是第k只蚂蚁在所经过的路径上释放的
信息素,定义如下:
k在图3中,节点1为起始点,节点3为终点,
1/dij,边(i,j)在路径T上
∆τk=(5)移动机器人进行路径规划时,将节点1作为父节
ij0,其他
点,通过变步长选择策略,将下一步移动机器人
(5)dij
由式可知,蚂蚁所构建的路径长度越要到达的节点4作为子节点,再将节点4作为父
小,那么各路径将得到更多的信息素,在以后的节点确定下一子节点,以此方法进行迭代,最终
迭代中该路径被其他蚂蚁选择的概率也将更大。确定了本轮迭代后的最优路径{1,4,5,3},结合变
2变步长蚁群算法步长蚁群算法的优点,移动机器人对于下一步所
选择的节点越接近于终点,则可以减少节点转折
传统蚁群算法步长选择为单步长,蚁群仅能的次数,同时,转折点越接近于障碍物,则可以减
向相邻栅格位置移动,不能满足移动机器人实际少无效路径,因此,为了缩短移动机器人路径长
需求,且搜索效率低及路径长度无法满足最优,度,引入终点诱导因子ϕ及障碍物诱导因子µ,其
因此,本文提出变步长选择策略,在避开障碍物选择概率为
的条件下,移动机器人可以从当前位置向全局地[τ(t)]α·[η(t)]β
k·ϕ·µ·∑ijij,j∈a
αβk
图的任何位置移动,大幅提高移动机器人搜索kτη
p(t)=[is(t)][is(t)](6)
ij
s∈ak
效率。
0,其他
∑
γε
跳点的选择即步长的选择,所谓跳点就是移[is(t)]
s∈a
ϕ=k(7)
动机器人在搜索过程中从当前节点可以到达下一σε
∑
步的节点。如图3所示。移动机器人从起点到终ω
[γis(t)]
点有4条路径可供选择,方案1为当前节点1跳s∈a
µ=k(8)
跃至节点2再到终点3,节点1到节点2步长为λω
第2期徐玉琼,等:基于变步长蚁群算法的移动机器人路径规划·333·
式中:k为常数,保证概率范围为(0,1);ε为终点免蚂蚁集中在某条路径上,将每条路径的信息素
ωγτ,τ
诱导系数;为障碍物诱导系数;is为移动机器设置上下限为[minmax],当该条路径信息素浓度
人当前节点到下一步可到达所有节点的距离总低于信息素下限时,将该条路径信息素设置为
τ
和,σ为移动机器人下一步到达的节点与终点之min,当该条路径信息素浓度高于信息素上限时,
τ
间的距离,其值越小,则距离终点越近,被选择的该条路径信息素设置为max,这样可以避免算法
概率也将越大,λ为移动机器人下一步到达的节陷入局部最优解,当蚁群经过一轮迭代后,挑选
点与其最近的障碍物之间的距离,优先考虑障碍出最优路径,对其信息素进行更新,加强对最优
物相邻的节点,可以有效缩短无效路径,提高移路径的利用,当所有蚂蚁完成一次迭代后,对路
动机器人避障能力。径上的信息素进行全局更新:
τ(t+1)=(1−ρ)·τ(t)+∆τbest(t),ρ∈(0,1)(11)
1
在移动机器人路径规划之前,需要给栅格地,边(i,j)包含在最优路径内
∆τbest=Lbest(12)
图环境的信息素进行初始化,初始化信息素采用ij
0,其他
不均匀分布,障碍物栅格的信息素设置为0,加强
起点至终点直线所涉及到栅格的信息素浓度,平为了提高搜索效率,一只蚂蚁在一轮迭代中
行的向外衰减,将栅格地图建立直角坐标系,如走过的完整路径将不被以后的蚂蚁所选择,对于
需要更新信息素的路径,可以是本轮迭代的最优
图4所示。
y解,也可以是全局最优解。
结合变步长蚁群算法的优点,在直角坐标系
中,利用蚁群下一步到达的节点距离起点至终点
连线的长短,对启发函数进行改进,传统蚁群算
法的启发函数为蚁群下一步所选择的节点到终点
之间距离的倒数,如式(2)所示,该函数收敛性不
强,且容易使蚁群寻优路径冗长,改进后的启发
函数如下:
0x√
12
ηij=·(13)
图4信息素分布策略dij|xi+yj−C|
,
式中,(xiyj)为下一步所选择节点的坐标,当其距
连接移动机器人的起始点及终点,则该直线离起点至终点对角线的长度越小,被选择概率则
方程为越大,与传统蚁群算法的启发函数相比,改进后
∗
y=−x+C,C∈N(9)的启发函数促使移动机器人将下一步选择的节点
在本文中,C取值为20或30,分别对应简单趋近于移动机器人起点到终点连线处,使移动机
τ=τ
栅格环境和复杂栅格环境,令ij(0)0为信息素器人在路径寻优中能更快地找到最优解,提高了
浓度的初始值,根据初始信息素浓度的衰减方算法的收敛速度,因此,改进后的启发函数作用
τ
式,障碍物栅格的初始信息素0直接取0,非障碍得到加强,有利于提高算法的收敛速度,提高算
物栅格初始信息素取值如下:
法的全局搜索能力。
T,y=−x+C
−3改进算法步骤
C1·,=−+
TyxC1
C
−图5为变步长蚁群算法的流程图,算法的具
τ=C2
0·T,y=−x+C2(10)
C体步骤如下:
···1)针对各项相关参数进行初始化:路径规划
α
1的起始点及终点、信息素重要程度参数、启发
·T,y=−x+1或y=−x+2C−1
C因子重要程度参数β、迭代次数、蚂蚁数量、信息
式中:T为调整系数,T∈(1,20),初试信息素的分素挥发系数及增强系数等相关参数,建立地图二
布有利于蚁群提高搜索速度,快速收敛。维栅格模型,邻接矩阵模型。
为了防止某条路径的信息素过高或过低,避2)初始化信息素采用不均匀分布,加强起点
·334·智 能 系 统 学 报第16卷
至终点直线所涉及栅格的信息素浓度,平行的向环境为20×20的栅格环境,对传统蚁群算法、本
外衰减;改进启发式信息矩阵,调整移动机器人文算法进行仿真,与文献[8]进行对比,复杂环境
当前位置到终点位置的启发函数计算方法,建立为30×30的栅格环境,对本文算法进行仿真,与
启发式信息矩阵。文献[8]进行对比。
3)建立禁忌表以及对禁忌表初始化,将起点、×20栅格环境
障碍物节点、引起死锁的节点均加入禁忌表中。在20×20的栅格环境下,对传统蚁群算法和
4)计算启发信息,根据信息素浓度以及概率本文算法进行仿真,其中,路径规划仿真分别如
公式确定蚂蚁下一步可以到达的节点,记录路径图6、7所示,实验数据如表1所示,传统蚁群算
并更新,更新禁忌表。,文献[8]算法路径规
5)当所有蚂蚁完成一次迭代后,,本文算法路径规划长度为
径,更新信息素及禁忌表,,显然,本文算法在路径规划方面优于文
代,则继续开始下一只蚂蚁路径寻优。献[8]算法及传统蚁群算法,本文算法较文献[8]
6)如果蚂蚁完成所有迭代次数,则输出最优算法、%
路径及收敛迭代次数,%。本文算法提出信息素不均匀分布策
略,提高了最优路径上节点被选择的概率,通过
数,则继续开始下一次迭代。
节点距离起点至终点对角线的距离,改进启发函
开始数,提高了算法的全局搜索能力,有效缩短了全
局最优路径的长度。
各项参数初始化,建立地图模型及
20
邻接矩阵
18
16
14
信息素浓度不均匀分布,建立启发
12
式信息矩阵
10
8
6
建立禁忌表
4
2
02468101214161820:m
确定蚂蚁下一步可前往的节点单位
图6传统蚁群算法路径规划(20×20)
记录路径并更新,
20
N18
一轮迭代是否结束
16
14
Y
12
保存最优路径,更新信息素,更新禁忌表10
8
6
N4
是否完成所有迭代2
Y02468101214161820单位:m
输出全局最优路径,收敛迭代次数图7本文算法路径规划(20×20)
结束
表1各算法实验结果对比
Table1Comparisonofexperimentalresultsofvariousal-
图5变步长蚁群算法流程gorithms
算法路径长度/m迭代次数
文献[8]
为了验证变步长蚁群算法的有效性,本文分
别在简易环境和复杂环境下进行仿真对比,简易
第2期徐玉琼,等:基于变步长蚁群算法的移动机器人路径规划·335·
收敛迭代仿真分别如图8、9所示,×30栅格环境
算法收敛迭代次数为25次,文献[8]算法收敛迭在30×30栅格环境下,采用文献[8]中的同
代次数为4次,本文算法收敛迭代次数为2次,一个栅格地图,对本文算法进行仿真实验,实验
显然,本文算法在收敛速度方面优于文献[8]算数据如表2所示,本文算法的路径规划如图11所
法及传统蚁群算法,本文算法较文献[8]算法、示,,文献[8]
,本文算法较文献[8]
50%及92%。%,因此,在复杂栅
蚂蚁最优路径规划路线,各代路线集中于起点格环境下,本文算法依然保持良好的路径规划能
至终点的连线处,表明信息素不均匀分布的有力,通过变步长蚁群算法,有效地缩短了最优路
效作用,在20×20栅格环境中,本文算法无论是径长度,收敛迭代效率如图12所示,本文算法的
在最优路径上还是在收敛速度上,都优于其他收敛迭代次数为6次,文献[8]算法的收敛迭代次
两种算法。数为8次,本文算法较文献[8]算法关于收敛迭代
70次数减少了25%,栅格地图越复杂,本文算法的
60优越性越明显,各代最优路径规划路线如图13
/m50所示,各代路径规划的路线依然集中于起点至终
40点的连线处,移动机器人将快速的寻找出最优
30
路径。
20
最优解路径长度10表2两种算法实验结果对比
Table2Comparisonofexperimentalresultsofvariousal-
05101520253035404550gorithms
迭代次数
算法路径长度/m迭代次数转弯次数
图8传统蚁群算法收敛曲线
文献[8]
-
30
30
25
/m25
20
20
15
15
10
10
最优解路径长度5
5
05101520253035404550
051015202530单位:m
迭代次数
图9本文算法收敛曲线图11本文算法路径规划(30×30)
(30×30)
thispaper
45
2040
1835
/m
1630
1425
12
20
10
15
8
10
6最优解路径长度
45
2
05101520253035404550
02468101214161820单位:m迭代次数
图10本文算法各代蚁群最优路径规划(20×20)图12本文算法收敛曲线(30×30)
colonyinthisalgorithm(20×20)thispaper(30×30)
·336·智 能 系 统 学 报第16卷
30表3各算法路径规划实验数据
25Table3Experimentaldataofpathplanningforeachal-
gorithm
20
/m/s
15算法路径长度耗时
051015202530单位:m5结束语
图13本文算法各代蚁群最优路径规划(30×30)
colonyinthisalgorithm(30×30)
搜索效率低、路径过长、收敛较慢等问题,本文在
本文采用自主搭建的移动机器人进行实验行改进,扩充蚁群可以到达节点的集合,在不触
验证,如图14及图15所示,一个纸箱代表两个碰障碍物的条件下,从蚁群当前位置的相邻位置
正方形障碍物栅格,空白场地为自由栅格,实验扩大至全局地图的任意自由栅格位置,达到变步
场景为20×20的栅格环境,实验数据如表3所长策略,改进信息素分布策略以及调整启发函数
示,,移动计算方法,大幅提高本文算法的收敛速度,快速
,传统蚁群算法地寻找到最优路径。本文基于变步长蚁群算法在
,,验证收敛速度和路径寻优方面有着较好的性能,不仅
了本文算法在移动机器人实际应用中能够较快适用于简单栅格环境,也适用于复杂的栅格环
地找到最优路径,有效地提高了路径规划的工境,使本文算法在实际应用场景中得到较好的应
用,通过对整个地图状态空间的探索点进行采
作效率。
样,能够增加搜索区域,适合解决移动机器人在
复杂环境下的路径规划。
参考文献:
[1]CONFESSOREG,FABIANOM,
flowbasedheuristicapproachforoptimisingAGVmove-
ments[J].Journalofintelligentmanufacturing,2013,24(2):
405–419.
[2]张毅,权浩,
人路径规划[J].华中科技大学学报(自然科学版),2020,
48(1):127–132.
ZHANGYi,QUANHai,
图14移动机器人起点位置
[J].
JournalofHuazhongUniversityofScienceandTechno-
logy(NatureScienceEdition),2020,48(1):127–132.
[3]刘可,李可,宿磊,
人三维路径规划方法[J].农业机械学报,2020,51(1):
29–36.
LIUKe,LIKe,SULei,
methodbased