基于蚁群算法的移动机器人路径规划.doc

基于蚁群算法的移动机器人路径规划第28卷第11期计算机仿真2011年11月文章编号:10069348(2011)11018504基于蚁群算法的移动机器人路径规划刘雄,雷勇,涂国强(四川大学电气信息学院,四川成都610065)摘要:研究移动机器人在已知静态环境下路径规划问题,在避障环境下寻求最优路径.针对蚁群算法搜索时间长,易陷入局部最优等缺陷,导致实时处理困难,且路径准确度低,可跟踪性差不能直接用于机器人.为解决上述问题,首先提取环境的平面几何信息,建立了简单有效地搜索模型.可通过引入终点距离与方向的启发函数,阶梯式伪随机的结点转移规则,引导蚁群有目的的进行搜索;改进信息素更新策略,利用一种奖惩机制以增强蚁群对尽可能好的解的识别能力.并考虑障碍物对路径的影响,运用人工势场法对全局最优路径的结点进行平滑.进行仿真的结果表明,提高了路径的安全性和可跟踪性.证明了改进方法可以有效地找出最优可行路径.关键词:蚁群算法;人工势场法;路径规划;全局寻优中图分类号:TP242文献标识码:BPathPlanningofMobileRobotBasedonAntColonyAlgorithmLIUXiong,LEIYong,TUGuoqiang(ElectricalEngineeringandInformationSchool,SichuanUniversity,ChengduSiehuan610065,China)ABSTRACT:AntColonyAlgorithmneedslongsearchingtime,andeasilyfallsintolocaloptimalsolution,resultinginthedefectsofpoorreal-timeprocessing,andlow.eaccuracyandtraceability.Tosolvetheproblem,asimpleeffi?cientlysearchmodelwasestablishedbasedOntheplanegeometryinformationextracted.TheheuristicfunctionoftheendSdistanceanddirection,andthepseudorandomladdernodetransitionrulewereintroducedtoguideantcolonytosearchwiththepurpose.Pheromoneupdatestrategywasimprovedwithanawardandpenaltymechanismtoenhancetheabilityofantcolonytoidentifythebestpossiblesolution.Finally,theoptimalpathSnodewassmoothedbyartificialpotentialfield.Theexperimentalresultsshowthatthemethodsuggestedcaneffectivelysearchoutthe0ptimalfeasiblepath.KEYWORDS:Antcolonyalgorithm;Artificialpotentialfield;Pathplanning;Globaloptimalpathsearching1引言路径规划作是指在具有障碍物的环境中,按照某些评价标准,寻找一条从起始状态到目标状态的避障的最优或次优运动路径.目前已有很多关于蚁群算法在路径规划方面应用的文献,多数均运用栅格法建立搜索模型,其缺点是:对场地依赖性大,细小的单元划分将大大增加计算的复杂度,使得实时处理变的很困难.为此文献5对环境进行了几何建模,改善了搜索模型,但却没有解决规划效率低的问题.利用蚁群算法找到的路径无可避免的存在折点,在安全性和跟踪性上隐患较大,为机器人后续控制也带来了较大的麻烦.文献6提出了以纯数学方法来进行路径的平滑处理,但忽略了实际环境,不能保证最终路径无碰撞.针对上述情况,本文在对环境建立几何模型的基础上,收稿日期:20101220修回日期:20110l一1O为提高蚁群搜索效率,提出了终点方向启发函数与阶梯式伪随机的结点转移规则,同时采用带有奖惩机制的信息素更新策略,以启发蚁群向全局最优解收敛,最后运用人工势场法以障碍物的几何分布对结点进行平滑,不仅消除了折点,也提高了路径安全性.2问题描述机器人路径规划本质是指在规划空间内,依据环境信息,在某些评价标准下,找出从出发点到目标点最优的运动路线.假设规划空间是一个有限区域的二维平面,区域里存在有限个障碍物.在该区域里建立直角坐标系,目的就是为机器人寻找从起点到终点的一系列点的集合,这个点集所组成的路径不仅要安全避障,且还要最短.目标函数可表示为(1)式.=_(1)i=2一l85式中,(,Y)为点的坐标,为点的个数.蚁群算法是一种优秀的群集智能方法,但存在着硬伤:搜索时间长,准确度低,使得路径规划效率低,导致机器人实时处理慢,无法快速灵活地适应环境.其次无可避免的,运用蚁群算法搜索到的路径因存在折点,在安全和可跟踪方面的性能也无法令人满意.以上两个问题,正是本文要解决的.3蚁群算法的路径寻优3.1环境模型的建立几何建模相比栅格法建模,更为紧凑,在简单环境下或者局部区域内计算量小而且可以获得较高的精度.假设机器人通过感知系统探测到环境的几何信息,如图1所示,实线表示障碍物的边界.以起点S为原点,建立直角坐标系,终点E是(100,100).以外切的正八边形来拟合圆形障碍物以便统一处理,由此引入的最大误差为r/cos(rr/8)一r<9%r,r为半径,在该环境中可忽略不计.为了方便对移动机器人在规划过程中的处理,把障碍物边界至少向外扩展达到机器人本体长,宽方向上最大尺寸的1/2,如图1虚线所示,如此机器人可看做质点.扩展后的障碍物顶点为P1至P26,从起点S到终点E的路径便可以由这些顶点组成,例如其中一条可达路径为:sP5一P16一P24一E.整个环境就被提取为三种几何信息:虚拟障碍物顶点,实际障碍物顶点以及实际障碍物的边界方程.各自用途:虚拟障碍物顶点作为蚁群算法的搜索结点,实际障碍物顶点与实际障碍物的边界方程则用于路径平滑时人工势场法斥力的计算.圈1环境的几何特征3.2基本蚁群算法改进基本蚁群算法存在搜索效率低,收敛速度慢和容易陷入局部最优解等缺陷.因此对基本蚁群算法做了一定改进,主要体现在以下三个方面.1)终点启发函数基本蚁群算法在搜索结点时,启发函数只能反映当前结点与邻接结点的定量关系,以此局部信息启发搜索,很容易使得路径杂乱无章甚至出现搜索失败.蚂蚁有向终点搜索一186一的趋势或者意识,并用启发函数来具体体现.假设i表示蚂蚁当前结点为邻接结点.文献5将与终点的直线距离的倒数作为距离启发函数,即DiE=1/I.同时本文提出了一种方向启发函数:向量的方向可看做是最佳搜索方向,而角厶表征了偏离最佳方向的程度,以此作为启发信息,得到2式.cosiiE)2)伪随机结点转移规则如3式所示,计算蚂蚁k的转移概率:r!望:盘k仇LOelseallowed(3)式中,与叼是基本蚁群算法的启发信息,其中为(i)上的信息素,=l/d(i,)表示当前结点与邻接结点的距离启发函数.(>1),卢,和分别表示四个启发因子.(3)式独保留信息素的指数运算,使之摆脱了其它启发函数的束缚,不仅减小了计算复杂度,而且在算法后期,信息素的主导地位更为明显,使得正反馈作用得到增强.为实现一定程度上对蚁群移动的控制,本文采用了伪随机的结点转移规则,即确定选择和随机选择相结合的选择策略.如4式所示.farg(max;+叩+4+,)q%L按P的大小随机选择else(4)式中,nexti表示蚂蚁k继结点i后达到的结点;q是Co,1内均匀分布的随机变量;q.表示作确定选择的阈值,一般是(0,1)内的常数.考虑蚁群在迭代过程中搜索特性的变化,算法采用时变函数g0(t)来代替原来的常数项:在算法初期,选取较大的值,使得初期信息素分布在有利的路径上;在算法中期,选取很小的值,以利于蚁群展开随机搜索;而在算法后期,选取很大的值,使得算法很快地收敛起来.如选择最简单的阶梯函数来描述q.的变化,具体如(5)式所示.rc11q0(t)=c2T1<t-<r2(5)【式中,e(i=1,2,3)对应函数不同的取值.3)带有奖惩机制的信息素更新策略信息素的更新机制直接影响了算法的收敛速度与全局搜索能力.本文借鉴了MMAS(MaxrainAntSystem)的思想:只对当前迭代得到的局部最优解进行信息素更新,而不是对全局的路径,同时设定结点问路径信息素的上下限.但仅一只迭代最优蚂蚁更新信息素,还远远不够,令所有迭代最优蚂蚁均进行信息素跟新,计算如(6)式所示.ro(t+1)=(1一p)r()+r(6)式中,P表示信息素挥发系数,取值范围为:0,1);At表示第t次迭代中寻得局部最优解的蚂蚁k留在(i)上的信息素,计算如(7)式所示.(minL(z)/(t)?QAr:=z(7)一,式中,2为(iJ)的长度,Q为信息素总量,JL()为第次迭代得到的最优解.第一,()的信息素与长度正相关:增加了较远距离的邻接结点的转移概率,增强了蚁群的全局搜索能力;第二,对每次迭代的信息素总量建立了自适应的奖惩制度:将第t次迭代的最优解与之前所有迭代得到的最优解比较,若较小,本次迭代的信息素总量增加,否则就是相反的结果.4人工势场法的路径平滑处理利用蚁群算法求得的路径是由结点序列组成的,是一条折线,其一阶导数在结点处均不连续,故这条路径对机器人而言可跟踪性较差.文献6以相切圆的弧段来代替尖角,忽略了环境中障碍物的分布,存在着很大的碰壁隐患.人工势场法结构简单,数学计算简明,充分考虑了障碍物对路径安全的影响,广泛应用于机器人的避障和平滑轨迹控制.假设蚁群最终搜索到路径的表达式为:S一一一一一E.针对结点i的局部平滑,本文是如此处理的:始终将结点i看为起点,先以前向结点作为引力点,利用人工势场法来平滑i邻域的前向路径,然而最终路径也可以看作是:E一一Js,再以后向结点作为引力点,完成i邻域的后向路径平滑.具体的数学模型本文参考了文献8.引力函数如(8)式所示.F=lXXgl(8)式中,为引力增益系数,始分别表示当前机器人和终点在环境中的位置.斥力函数如(9)式所示.+南侗【o.ebe式中,Fr,pl南一,F,.pt高一町为斥力增益系数,表示障碍物的位置,P.表示障碍物的影响距离.从(9)式不难看出,斥力大小可以通过n来调节:根据结点处障碍物的具体情况,选择合适的n值以达到最佳平滑效果.仅在引力作用时,即Frep=0,则认为完成了结点i的路径平滑.对所有的结点(不包括起点S和终点E)均进行前向和后向路径平滑,就可得到一条机器人更易跟踪且更安全的路径.因为是结点之间有限范围内的使用人工势场法,所以不用考虑局部极小问题,保证了方案的可行性和适应性.5实验结果本文整个算法的简单流程图如图2所示.Y/输出最/短路径/路径结点平滑一一一一一人工势场法图2算法工作流程图对图1中描述的机器人移动环境利用本文算法进行仿真实验.设定蚁群最大迭代次数N=50,g.(t)参数:c.:0.6,c2=0.2,c=0.9,Tt=5,:35,人工势场法的步长Z=1.实验结果如图3所示,虚线表示蚁群最终搜索到的路径:E一尸3一P8一P26一S,长度为153.9217,这是也该场地的最短路径.现就本文提出的蚁群算法与基本蚁群算法进行统计实验以比较验证,统计运行次数为50次,两种算法的比较结果如表1所示.不难看出与基本蚁群算法比较,本文算法的优越性在于:平均长度和平均最差解减小:蚁群对较优路径的识别能力加强,搜索范围更集中于全局最优解;平均最优解和收敛次数减小:蚁群跳出极小解的能力加强,收敛速度更快;迭代平均耗时减小:算法的计算复杂度变小,更有利于实时处理.实验还发现在N=50时,基本蚁群算法几乎不能收敛到全局最优解,性能也随着参数的不同变化较大,然本文算法的准确率和鲁棒性均表现较好.图3中P3,P8和P26三个结点邻域的弧段,则是利用人工势场法进行平滑之后机器人的轨迹,容易看出不仅三个折点很好地消除一187一法算群蚁,Jf图3全局最优路径及其平滑效果了,而且弧段衔接平滑,前后的长度差也不大于10.图3中实线描述的最终路径可看作是一条机器人更易实现更安全的最优路径.表1两种算法解的结果比较做进一步验证,将本文算法与文献5,9算法对比.图4所示为本文算法在文献5移动场地中的实验结果,在50次重复实验统计到本文算法平均收敛到最优路径的迭代次数是11次(N=50),优于文献5的34次(N:150),且可以看出图中最终路径的表现更好.而在更为简单的环境中,文献9算法的迭代次数反而更大,平均耗时也更多.图4文献5全局最优路径及其平滑效果实际应用本文算法时,机器人会在起点停顿一会,完成模型建立与路径规划后,然后按照最终路径向终点运动,而188一在结点附近的运动控制,则是跟踪平滑后的轨迹,针对不同类型的机器人及其运算处理能力的差异,应选择恰当的步长l值,以达到最优的规划效果.6结论在搜索空间和收敛速度这样一对矛盾中,本文算法更侧重于收敛速度,原因如下:针对较简单的移动环境,纵然缩小搜索空间,算法也可以收敛到全局最优解;快速反应对于机器人来说也是尤为重要的.同时本文算法还充分考虑了最终路径的可跟踪性及机器人运动的安全性.故在实际工业应用中,本文算法非常适合于较小范围内的机器人控制,如地下作业.因为地下作业的环境往往狭隘,恶劣且未知,机器人正常作业的前提就是具有优秀的避障性能,此外当机器人探测到新的场景或目标实时发生变化时,快速的反应也必不可少,这就要求机器人有良好的重规划能力,这两方面正是本文算法的特点.对于大范围复杂环境的路径规划问题,这是本文需要进一步研究的地方.参考文献:1邱小湖,邱永成优化蚁群算法在无人机航路规划中的应用J.计算机仿真,2010,27(9):102-105.2何娟,涂中英,牛玉刚.一种遗传蚁群算法的机