基于改进蚁群算法的盘点型机器人路径规划

2019年7月July摇2019COMPUTERTECHNOLOGYANDDEVELOPMENT

基于改进蚁群算法的盘点型机器人路径规划

马金科,王摇直

(江苏科技大学计算机学院,江苏镇江212003)

摘摇要:针对盘点型机器人盘点物品过程中路径规划实时性和稳定性差的问题,以传统的蚁群算法为基础,提出了一种改进型的蚁群算法。改进型的蚁群算法包括三点优化:第一是提出了自适应的挥发系数设置方法,即算法前期设置较小的挥发系数,减小蚂蚁间互相吸引;算法后期,挥发系数设置较大,提高算法收敛速度。第二是对各个路径上的初始浓度做出调整,加大了起始点和终点连线附近的信息素浓度。这样能较大提高前期搜索的速度。第三是全局信息素更新时,按单次迭代出的路径长短,在较短路径上加强信息素浓度,在较长路径上削减信息素浓度。研究结果表明,当对传统算法做出这三点优化后,改进后的算法不仅路径规划收敛的速度更快,效率更高,而且寻得的路径也更优更稳定。经仿真实验验证,在类旅行商问题上,改进后的算法确实有更快的收敛速度,且能避免陷入局部最优解,而得到全局最优路线。关键词:机器人;路径规划;蚁群算法;参数自适应;旅行商问题

中图分类号:TP242.6摇摇摇摇摇摇文献标识码:A摇摇摇摇摇摇文章编号:1673-629X(2019)07-0084-04doi:10.3969/j.issn.1673-629X.2019.07.017

PathPlanningofInventoryRobotBasedonImproved

AntColonyAlgorithm

(SchoolofComputing,JiangsuUniversityofScienceandTechnology,Zhenjiang212003,China)

Abstract:Aimingattheproblemofpoorreal-timeandstabilityofpathplanningininventoryprocessofinventoryrobots,weproposeanimprovedantcolonyalgorithmbasedontraditionalantcolonyalgorithm.Itincludesthree-pointoptimization.Thefirstistoproposeanadaptivevolatilizationcoefficientsettingmethodwhichsetsasmallvolatilizationcoefficientintheearlystagetoreducemutualattractionbetweentheants,andinthelaterstage,setsalargevolatilizationcoefficienttoimprovetheconvergencespeed.Thesecondistoadjusttheinitialconcentrationoneachpathtoincreasethepheromoneconcentrationnearthestartandendpoints.Thiscangreatlyimprovethespeedoftheprophasesearch.Thethirdistheglobalpheromoneupdate,thelengthofthepathbyasingleiteration,thepheromonecon鄄centrationisenhancedontheshorterpath,andthepheromoneconcentrationisreducedonthelongerpath.Theresearchshowsthatwhenthesethreeoptimizationsaremadetothetraditionalalgorithm,theimprovedalgorithmnotonlyconvergesfasterandmoreefficiently,butalsofindsbetterandmorestablepaths.Thesimulationexperimentprovesthattheimprovedalgorithmhasafasterconvergencespeedonthetravelingsalesmanproblem,andcanavoidfallingintothelocaloptimalsolutionandgettheglobaloptimalroute.Keywords:robot;pathplanning;antcolonyalgorithm;parameteradaptation;travelingsalesmanproblem

MAJin-ke,WANGZhi

0摇引摇言

盘点型机器人是指能够精确盘点仓库中的货品以及可以引导上架新货品的机器人。移动机器人的路径规划是移动机器人研究的重要分支之一,是机器人实现智能化移动的关键[1]。移动机器人在有障碍物的工作环境中,按照某一性能指标(如工作代价最小、行走时间最少、行走路线最短等)搜索一条从起始状态到

目标状态的安全的、无碰的最优或次优路径[2]。

目前,常用于移动机器人路径规划的算法主要有

人工势场法、A*算法、神经网络法、蚁群法、遗传算法等[3]。A*算法虽然对比较简单的地图搜索速度非常快,也能找到最优路径,但全局性较差,启发函数选择不当的话容易陷入死循环。神经网络法虽然能收敛到最优路径,但环境改变后必须重新学习,在环境信息不

收稿日期:2018-08-09摇摇摇摇摇摇修回日期:2018-12-12摇摇摇摇摇摇网络出版时间:2019-03-21基金项目:江苏省自然科学基金(BK20151330)

作者简介:马金科(1991-),男,硕士研究生,研究方向为机器人运动控制和路径规划;王摇直,硕士,教授,研究生导师,研究方向为应用电子技

术、智能机器人研究等。

网络出版地址:http://kns.cnki.net/kcms/detail/61.1450.TP.20190321.0909.040.html

摇第7期摇摇摇摇摇摇摇摇摇摇摇摇马金科等:基于改进蚁群算法的盘点型机器人路径规划·85·

琢

茁

完整或环境经常改变的情况下应用起来很困难[4]。模糊推理法虽然避开了其他算法中存在的对环境信息依赖性强等缺点,但自身的适应能力比较差[5]。遗传算法虽有鲁棒性强、全局优化等优点,但计算速度不快,容易提前收敛。相对而言,蚁群算法具有分布式计算、信息正反馈和启发式搜索特征,在求解移动机器人路径规划问题时更加合适。但基本蚁群算法执行过程依赖于大量的迭代和循环,缺乏实时性;运行过程中信息素不断累积,优质路径不突出,对于最优解的求取有很大影响[6]。对此,文中重点对蚁群算法中的全局初始ìï[子ij(t)][浊ij(t)],j沂allowedkï琢茁k[子(t)][浊(t)]pij(t)=í移isiss沂allowedïï

î0,others

k

的转移概率;子ij(t)为t时刻节点i与节点j连接路径上的信息素浓度;浊ij(t)为蚂蚁由节点i去往节点j的期望值,浊ij(t)=

其中,pkij(t)为t时刻第k只蚂蚁由节点i到节点j

(1)

1

,dij为节点i和j之间的距离;dij

信息素分配、挥发系数随时间进行相应变化,信息素在迭代中更新的方式等方向提出相应的改进方法。

1摇基本蚁群算法

自然界的蚁群在外出觅食时,会在它们走过的路

径上散发出一类有特殊气味的信息素[7]靠这种化学物质实现信息的交互,并实时引导后续的。蚂蚁之间依运动方向。每只蚂蚁在没有预先知道食物所在地的前提下开始搜索食物,并在经过的路径上分泌信息素。而蚁群算法的核心就是:通过若干数量的蚂蚁共同寻路,在各个途径带上分泌信息素来提高食物搜索的效果,最终以最短路径找到食物。

由上可知,在整个过程中有两个因素会对得出的最优路径造成大的影响:

蚁影响很大(1)在选择下一个目标节点时,浓度大的蚂蚁选择该路径的几率更高,信息素浓度对蚂。

径,会以较高概率得到保留(2)蚂蚁在寻路过程中,,相应浓度低的路径会在迭节点路径上浓度高的路代中被舍弃。

蚁群算法的特点,决定了它在路径规划的范围较大,且在用户节点较多的情况下,能表现出更强的适应性和兼容性,同时在这种应用场景下,得到的最优路径结果也更稳定。

旅行商问题(travelingsalesmanproblem,TSP)是在组合型优化问题中的一个典型代表。经典的TSP是这样描述的:一个推销员要在所有推销的城市推销产品,要求他能够从一个起点出发,最后遍历所有城市,并回到起点。过程中应如何选择行进路线,以使总的行程最短[8]法中可以将N。个蚂蚁比作各个推销员以TSP(旅行商问题)为背景,这些蚂蚁并不,蚁群算是在同一个起点出发,而是分布在各个节点出发。食物所在地则类比为需推销的城市,蚁穴是集散中心,所有蚂蚁对所有食物的地方访问完后,会回到集散中心。通过多次迭代,所有蚂蚁寻出的路径会收敛出一条最优的路径[9]蚁选择下一个节点的规则如下。为量化阐述蚁群算法:

,路网中第k只蚂allowedk为蚂蚁待访问节点的集合;琢为信息素浓度对蚂蚁运动的影响大小;茁为能见度对蚂蚁运动的影响大小。

随着时间的推移,路途上的信息素会慢慢减弱,每次各个蚂蚁访问完全部节点之后,路段上的信息素需要进行更新,更新公式为:

子ij(t+移1)m=(1-籽)子ij(t)+驻子ij(2)驻子ij=

驻kk=1

子

ij

(3)

其中,籽为信息素的挥发系数;驻子kij为第k只蚂蚁从节点i到节点j之间释放的信息素量;驻子ij表示所有蚂蚁在节点i与节点k之间释放的信息素量之和。

驻子ij按下列公式更新:

驻子k

ij

={

LQ

,第k只蚂蚁经过节点(i,j)

,Q0,k

为常量others

(4)

其中;Lk为第k只蚂蚁在本次循环所经过的路径长度。

2摇2.1摇改进的蚁群算法

挥发系数籽的优化

挥发系数籽指信息素浓度逐渐减弱的系数值,它的设置决定着蚂蚁的搜索效果,也极大影响着算法实现的性能。若挥发系数设置太小,蚁群对蚂蚁的引导作用会过强,导致蚂蚁本身搜索的能力降低;若挥发系数设置太大,蚁群对蚂蚁引导作用会过小,再次选择已经搜索过的路径可能性会大大增加,降低了算法的全局搜索能力[10]置方法,即算法前期设置较小的挥发系数。基于此,提出了自适应的挥发系数设,减小蚂蚁间互相吸引,提高搜索效率;算法后期,挥发系数设置较大,提高算法收敛速度。

挥发系数籽自适应公式为:籽(t)=

{

0籽.9籽(t-1),籽(t)逸籽minmin

(5)

其中,籽min为挥发系数可以取到的最小值。挥发

系数随时间逐渐减小。

·摇86摇·摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第29卷

2.2摇开始阶段信息素分配的优化

度相同,为一个常数[11]。这种情况导致的结果就是算法在初期阶段搜索的速度很慢,要经过一段时间的处理,实现浓度不同对蚁群的影响。所以,文中对各个路径上的初始浓度进行调整,加大了起始点和终点连线附近的信息素浓度。这是因为,最优路径往往分布在起点和终点连线附近。其他区域出现最优路径的几率相对较小。这样在大多数情况下,改进后的算法会更快地找到最优路径,提高了搜索的整体效率。在传统算法中,开始阶段各个路径上的信息素浓

进行信息素挥发因子设置。

(4)按照式1选择移动的下一个节点。

实时信息素更新。

(5)当所有蚂蚁完成一次搜索后,按照式6进行(6)判断所有蚂蚁完成一次迭代与否,完成则转(7)按式7和式8完成全局信息素更新。(8)判断是否达到最大迭代次数,若未达到,则开

步骤7,未完成转步骤4。

始下一次迭代,达到后则马上结束迭代,得到最优的路径。

2.3摇信息素更新方式的优化

信息素浓度是蚂蚁在寻优过程中主要参照的依据[12]算法的准确性和效率,所以,信息素浓度更新的方式直接影响到蚁群。蚂蚁每移动一次称为一次搜索,经过n次搜索后,所有蚂蚁就完成了一次迭代。在传统算法中,信息素的更新只依赖于全局信息素更新,这使得算法容易陷入局部最优的陷阱[13]浓度的更新分为实时更新和全局更新能有效改善这种。将信息素情况。

蚂蚁的实时信息素更新公式为:子ij其中(t+,滓1)为实时信息素挥发因子=(1-滓)子ij(t)+滓子0

;子(6)

始值。

0为信息素初全局信息素更新时,每个蚂蚁迭代完成,都会得到

这个蚂蚁的路径[14]列,在较短路径上进行信息素加强。比对这些路径,在较长路径上进行,按路径长短排信息素削减。则全局更新的公式为:

子ij(t+1)ì=(1-籽)子ij(t)+籽驻子ij

(7)ï着Li吟子ïLij=í

b

,Li>Lbïï(8)

î着LLi

b

,Li臆Lb其中,Li为本次迭代的最优路径;L优路径;着为一个可调参数,满足一次迭代后b为当前的最

,加强接近最优路径的路径上的信息素浓度削减远离最优路径上信息素浓度。

通过实时和全局信息素更新,蚂蚁能够摆脱求得局部最优的陷阱,同时又能提高寻优的效率。2.4摇算法的实现步骤

改进算法的实现步骤如下:

始信息素分配时在起点和终点连线上设置较大的信息(1)初始化信息素的分配及其他各种参数[15]。初

素浓度。对信息素重要程度因子琢、能见程度因子茁、最大迭代次数等参数进行初始化。

(2)初始化蚁群,构造解空间[16](3)把蚂蚁放到起始点进行路径规划。

,按照式5

算法实现流程如图1所示。

图1摇改进的蚁群算法实现流程

3摇仿真实验

为了验证改进算法的有效性,利用MATLAB平台对改进算法进行验证。依据改进算法的实现步骤,把对应参数初始化为:蚂蚁数目60,迭代数初始值200,4,信息素浓度影响因子琢=1,能见度影响因子茁=统蚁群算法和改进蚁群算法在挥发因子按前述自适应的方式设置MATLAB。分别采用传环境下进行编程仿真,其仿真结果对比如图2和图3所示。

图2摇基本蚁群算法规划出的路径

摇第7期摇摇摇摇摇摇摇摇摇摇摇摇马金科等:基于改进蚁群算法的盘点型机器人路径规划·87·

图3摇改进蚁群算法规划出的路径

从以上对比可知,传统蚁群算法在搜索初期陷入了局部最优,虽然最终也找到了一条最优路径,但路径质量不如改进蚁群算法。而改进蚁群算法在改进了挥发因子自适应,初始浓度分布以及信息素更新方式后,最终规划出的最优路径明显优于传统蚁群算法。

为了更好地验证蚁群算法在收敛速度和最短路径上的优势,文中给出了传统蚁群算法和改进蚁群算法各次迭代路线的平均距离和最短距离的对比曲线,如图4和图5所示。

图4摇基本蚁群算法各代迭代的路径距离

图5摇改进蚁群算法各代迭代的路径距离由图4和图5可知,在改进算法中,算法的搜索能力有所提升,最优路径得出的收敛速度也更快。对比原始算法,能以不到40次的迭代次数就得到比原算法更优的解,且后续迭代过程中,最优解未出现波动,证明该优化算法的可靠性和高效性。

4摇结束语

针对盘点型机器人路径规划特点,设计了改进型蚁群算法。改进的蚁群算法通过对挥发因子自适应优化,初始路径浓度设置以及信息素更新方式的优化,有效地使传统算法避免了局部最优问题,同时提高了算法的收敛速度和最优解的质量。实验结果表明,改进的蚁群算法能更快更准确地找到最优解,具有更高的稳定性和有效性。基于这个改进效果,该算法可以应用盘点型机器人,以提高盘点型机器人盘点物品的能力。

参考文献:

[1]摇段海滨.蚁群算法原理及其应用[M].北京:科学出版社,[2]摇2005.

[TIZHOOSHligentJ].JournalHR.Opposition-basedreinforcementlearning

InformaticsofAdvanced,2006,10(4):578-585ComputationalIntelligence.&Intel鄄[3]摇俞器人路径规划摇烨,贺乃宝[,J]高.物联网技术摇倩,等.基于改进蚁群算法的移动机

,2017,7(3):46-49.[4]摇FAKOORbotpathplanningM,KOSARIwithfuzzyA,JAFARZADEHMarkovdecisionM.processesHumanoid[Jro鄄

].JournalofAppliedResearch&Technology,2016,14(5):300-[5]摇310ARDIYANTO.

domizedkinodynamicI,MIURAplanningJ.Real-withtimearrivalnavigationtimeusingfield[ran鄄

J].RoboticsandAutonomousSystems,2012,60(12):1579-[6]摇1591叶炜垚.

人路径规划方法,王春香,[杨J]摇.机器人明,等.,2011,33(3):273-278基于虚拟障碍物的移动机器

.[7]摇[郑卫国J].计算机仿真,田其冲,,2010,27(7):191-193张摇磊.基于信息素强度的改进蚁群算法[8]摇潘.

路径规划摇杰,王雪松[J].中国矿业大学学报,程玉虎.基于改进蚁群算法的移动机器人

,2012,41(1):108-113.[9]摇[孟文俊J].控制工程,刘忠强,2014,21(3):321-325.视觉导引AGV的.

路径跟踪控制研究[10]曾划方法摇碧,[杨宜民J].计算机应用研究.动态环境下基于蚁群算法的实时路径规

,2010,27(3):860-863.[11]吴登峰器人路径规划新算法,梅志千,尹立伟[J,]等..机电工程一种未知环境下室内移动机

,2015,32(3):3-[12]392段海滨.

版社,2011:130-143,张祥银,徐春芳.

.仿生智能计算[M].北京:科学出

[13]祁若龙制及3D,周维佳运动仿真的有效实现方法,刘金国,等.VC平台下机器人虚拟运动控

[J].机器人,2013,35[14](5):594-599苏海锋径自动选择,杨摇.

[阔J],.梁志瑞电力自动化设备.基于改进蚁群算法的输电线路路

,2018,38(1):87-92.[15]TUNCERbilerobotsAwith,YILDIRIMimprovedM.geneticDynamicalgorithmpath[planningJ].Computersofmo鄄

&

ElectricalEngineering,2012,38(6):15-1572.

[16]孙先成器人路径规划研究,尹志宏,林清霖[J].,机械与电子等.基于改进蚁群算法的移动机

,2017,35(5):73-75.