[doc格式] 基于改进蚁群算法的移动机器人全局路径规划

[doc格式] 基于改进蚁群算法的移动机器人全局路径规划 基于改进蚁群算法的移动机器人全局路径 规划 Vo1.26No.1 January2009 安徽工业大学(自然科学版) J.ofAnhuiUniversityofTechnology(NaturalScience) 第26卷 2009年 第1期 1月 文章编号:1671—7872(2009)OI一0077,04? 基于改进蚁群算法的移动机器人全局路径规划 乔茹,章小兵,赵光兴 (安徽工业大学电气信息学院,电力电子与运动控制重点,安徽马鞍山243002) 摘要:对已栅格化的机器人运动空间中的障碍物预处理,在蚁群算法原理的基础上,改进了伪随机比例规则,使蚂蚁的下一节点 选择更加倾向于目标点,提高了蚂蚁的搜索效率.引入最优一最差蚂蚁思想来更新全局信息素轨迹的强度,增强搜索过程的指导 性.为了防止早熟收敛现象的发生,采用最大一最小蚂蚁思想来限制 信息素的强度.仿真研究表明:该算法具有高适用性和灵活 性,对解决静态路径规划问题是可行的,有效的. 关键词:移动机器人;路径规划;蚁群算法;最优一最差蚂蚁 中图分类号:rI’P24文献标识码:A GlobalPathPlanningofMobileRobotBasedonImprovedAntColonyAlgorithm QIAO-Ru,ZHANGXiao-bing,ZHAOGuang-xing (SchoolofElectricalEngineering&Information,AnhuiUniversityofTechnology,KeyLaboratoryofPower ElectrionicandMotionControl,Ma’anshan243002,China) Abstract:Obstaclesintherobotsworkingspacewhichisdealedwithdmethodaredisposaledfirstly.Inorderto makeantcolony’schoicebeapttogoalandenhanceantssearchefficiency,pseudo-randomproportionruleofant colonyalgorithmisimproved.Atthesametime,Best-Worstantsystemisadoptedinordertostrengthenthesearch processguidanceandupdateglobalpheromoneintensity.Furthermore,inordertopreventtheprecocious convergence,Max-Minantsystemwhichcanlimitglobalpheromoneintensityisadopted.Simulationresultsshowthat theobviouscharacteristicoftheproposedmethodisbetterapplicabilityandismoreeffectiveforsolvingstaticpath planning. Keywords:mobilerobot;pathplanning;antcolonyalgorithm;best——worstantsystem 移动机器人路径规划是机器人领域的核心问题之一.按照机器人对环境信息的掌握程度,可将路径规划 分为全局规划和局部规划两大类.针对全局路径规划问题,国内外学者做了大量的研究,提出了许多解决方 法[1-o-],主要有自由空间法,算法,人工势场法,栅格法,臭虫法(BUG),随机位图法,快速随机树,神经网络 法,遗传算法等.这些算法有着各自的优势,然而在总体上,这些路径规划算法都存在不足,如计算复杂度,局 部最优解,缺乏算法的灵活性与实用性,对不同地图的适应性不强等. 蚁群算法是由意大利学者M.Dorigo在1991年提出的一种通用的新型优化算法,具有极强的鲁棒性和发 现较好解的能力.但是传统的蚂蚁算法也有缺陷:路径点的转移方向不能快速确保为收敛方向,收敛速度慢, 易出现停滞现象;所有路径点同时转移容易导致各点配合不好而使总距离长度产生振荡[71. 针对以上不足,提出一种改进的蚁群算法,并编制相应的程序.多次仿真实验表明该算法的收敛速度快, 不管障碍物是何种形状,该改进算法总可以在最短的时间内找到一条最优或近似最优的无碰路径且不会产 生死锁现象. 收稿日期:2008—07—31 作者简介:乔茹(1982-),女,河北石家庄人,硕士生,主要研究方向为机器人全局路径规划. 78安徽工业大学(自然科学版)2009年 1改进蚁群算法的原理 将m只蚂蚁放在出发点,每只蚂蚁都以当前点为中心,按照改进的伪随机比例规则选择并走到下一节 点.当m只蚂蚁都到达目标点后,找出这m条路径长度的最大值与最小值,将最小值与当前最优路径的长度 比较,若最小值小于当前最优路径的长度,则将最小值的路径作为当前的最优路径.根据最优最差蚂蚁系统 的思想,对当前最优路径和最差路径按照不同的更新原则进行全局信息素更新.这样可使最优解更大限度地 增强,最差解进一步被削弱,属于最优路径的边与属于最差路径的边之间的信息素差异进一步增大,增强了 搜索过程的指导性,蚂蚁的搜索更集中于到当前循环为止找出的最优路径的邻域内.同时为了防止早熟收敛 行为的发生,将每个解的元素上信息素量的值域范围限制在某一区间,可避免某些路径上的信息素轨迹量远 高于其它边而使蚂蚁的运动停滞.信息素更新完毕后,m只蚂蚁改变 寻优方向,开始新一轮的寻优.如此反复 到规定的迭代次数为止. 1.1蚂蚁数目的选择 蚂蚁数目较多时,可以提高蚁群算法的全局搜索能力及算法的稳定性,但数目过多,也会使大量的曾被 搜索过的路径上的信息量变化趋于平均,信息正反馈作用减弱,虽然这时全局搜索的随机性得到了加强,但 收敛速度减慢.若蚂蚁数目较少,全局搜索的随机性减弱,虽然这时收敛速度加快,但算法稳定性变差,且容 易出现过早停滞现象.本算法中所用栅格地图大小为12~12,根据地图规模大概是蚂蚁数目的1.5倍这一原 则阎,文中选取蚂蚁数目m=10. 1.2,P的组合配置 启发式因子与期望启发式因子分别反映蚂蚁在运动过程中积累的信息量和启发式信息在指导蚁群 搜索中的相对重要程度.信息素残留因子P的大小对蚁群算法的收敛性影响非常大,它与迭代次数?近似成 正比.目前已公布的这3个参数最好的取值范围是0??5,0?卢?5,0.1?p?0.99.在蚁群算法中,各参数 间的关系很紧密,如果组合配置不当,会导致求解速度很慢且所得解的质量特别差.经多次实验,本算 法中三者的最优组合为a=l,=5,p=0.7. 1.3参数8及q.的选择 是对最差蚂蚁所经过的路径进行削弱的参数,其值越大则削弱的越多.q.的大小决定了利用先验知识 与探索新路径之间的相对重要性,蚂蚁每次在选择下一路径点前,都要比较9与g.的大小,q的取值范围是 0?口?1.通过实验比较,文中选取s=10,qo:0.9. 2环境描述 假设机器人的有限活动空间为矩形,其内部分布着多个静止的障碍物.首先将每个障碍物扩展成各自的 外切四边形的形状,可使凹形障碍变为凸形障碍,避免蚂蚁进人死胡同,提高了搜索效率;然后以机器人长宽 的最大值作为步长,将活动空间划分为等间距的栅格图.含有障碍物的栅格为障碍栅格,不含障碍物的为自 由栅格.对栅格划分的场地采用序号法进行编号,如图1所示. 栅格序号值与其所在的行列及其坐标的对应关 系: )=+xq-I) i=mod(g,N j=g 』v - +1 式中:横坐标对应着列数,Y纵坐标Y对应着其行 数;)表示位于i行列的栅格的序号值,代表 每行的栅格数,代表每列的栅格数,mod是求余运 算. 地图中的障碍栅格用0表示,自由栅格用其对 应的栅格序号表示.这样机器人从起点到目标点的图1栅格坐标与序号的关系 第1期乔茹等:基于改进蚁群算法的移动机器人全局路径规划79 以当前点为中心,比较随机数g与q.的大小,按式(1)选择其下一节点,并 将选择好的节点:,)放人自己的禁忌表中: fargmax[r(g(i,j),)叼,g,9?g0 一【s,否则按式(2)概率式搜索 ‘m’× ., ?×77嘲?E 1,gEam 0otherwise (2) 其中:是指当前点)与其相关联的可达节点g(间的信息素值,叼是指当前点的下一可行 节点到目标点的距离的倒数;分别反映蚂蚁在运动过程中积累的信 息和启发信息在蚂蚁选择路径中 的相对重要性.0[值越大,说明蚂蚁选择以前走过路径的可能性就越大;值越大,说明蚂蚁选择局部最短路 径的可能性就越大.‰是允许蚂蚁m下一步行走的节点的集合(指除去蚂蚁已经走过的节点和障碍点);q是 在IXf~-J[o,1】内的随机数;5为根据式(2)给出的概率分布中,将具有最大值的节点作为其下一节点; (3)该蚂蚁以刚选择好的节点,7f)作为此时的当前节点,重复步骤(2),直到到达目标点,然后保留此局 部解; (4)再次重复步骤(2),直至所有蚂蚁都由起点到达目标点; (5)计算各个蚂蚁的路径长度,找出此次循环中路径长度的最大值与最小值,将最小值与当前最优路径 的长度比较,若小于当前最优路径的长度,则将其替换为当前最优解.利用式(3)对当前最优解上的任意两栅 格间进行全局信息素更新,利用式(4)X,-J此次循环中最差路径上的栅格进行全局信息素更新;若更新后某段 路径上的信息素值大于最大信息素值,则将其值设为最大信息素值,若更新后某段路径上的信息素值小于最 低信息素值,则将其赋值为最低信息素值. r(g(ij),g(kd9)}x7-),)+(1X?.『ij),g(koO)(3) f0如果(g(q),g(ka9)隹全局最优路径曲 ?(g()){1如果),?全局最优路径L曲【gb /- (g())+×(g())一占×喧(4) *-’best 式中:P为信息素的残留系数;Ar为信息素的增量;一和为本次迭代中路径长度的最大值与最小值; 为算法引入的一个参数. (6)令循环次数N=N+1,如果?>?呲,则循环结束,跳出整个循环,输出最优路径,否则,清空禁忌表并以 当前点为起点,返回步骤(2),重新开始搜索. 4实验结果 根据以上思路,用matlab7.0编制了机器人路径规划的程序.算法所用参数设置.m=lO,?m=50,0[=1= 5,0=0.7,qo=0.9,1O,=O.1.图2-6加粗的黑线即为最终规划出的最优路径.本实验的起点s==2,2),终点 go=g(11,11). 8O安徽工业大学(自然科学版)2009正 图2,3中,将与障碍物相邻的自由栅格也定义为 障碍栅格,这样虽可以找到一条安全无碰的路径,但限 制了蚂蚁搜索最优解的范围,加大了最优路径的长度, 而且,对地图的密集度也有一定的要求,即地图中的障 碍栅格间的最近距离至少是2个栅格的长度. 如果只将障碍栅格序号值所在的行,列的交叉点 定为不可通栅格,这样搜索到的路径会靠近障碍物的 边界,对机器人是不太安全的,解决是在搜索路径 前,先对障碍物进行膨胀,这样即使机器人沿着障碍物 边界搜索,也不会发生碰壁的危险. 为了增强对比性,用图3的场景进行此方法的验 证,如图4所示.该方法找出的最优路径的长度是 】4.4,而图2,3中的路径长度是15.6,该方法要优于图 2,3所用的方法.图5是在图3场景的基础上将其复 杂化,图6是将目标点设在凹形障碍物内部.仿真结果 表明,算法对地图的复杂度及起点与终点的位置没有 任何要求,只要地图中存在一条从起点到目标点的可 通路径,蚂蚁总会在最短的时间里将其搜索到. 0 4 8 12 初始的栅格模型 0 4 8 12 5结论 在蚁群算法的基础上改进了伪随机比例规则,使 得蚂蚁下一节点的选择更加倾向于目标点.提高了蚂 蚁的搜索效率.引入最优一最差蚂蚁系统的思想,增强 了搜索过程的指导性,使得蚂蚁的搜索更集中于到当 前循环为止所找出的最优路径的邻域内.为了防止早 熟收敛现象的发生,引入最大一最小蚂蚁思想.多次仿 真实验表明,该算法具有很高的适用性和灵活性,但该 算法还需要进一步改进,主要是对最后输出的最优路 径的优化,如何找到一种简便可行的路径优化方法,是 本课题今后要解决的问题. 参考文献:. 【1】AlexopoulosC,Gri~nPM.Pathplanningforamobilerobot[J】. IEEETransactionsonsystems,Man,andCybernetics,1992,22(2): 318-322. 【2]ParkMG,leeMC.Artificialpotentialfieldbasedpathplanning formobilerobotsusingavirtualobstacleconcept[C]//IEEE/ASME IntemalionallC0I1ferenceonAdvancedIntelligentMeohatronics.2003: 735-740 图2蚁群路径规划场景1 栅格模型 ]?_——Llii!i 1T, }??_1_lllI 】I’,IIIII — l\ji: 【一 { I;!{r’/- ll!}]l I;:1 图3蚁群路径规划场景2 栅格模型 .!};lI【f ?_=,曩墨 【3]ZhaoDB,YiJQ.LectureNotesinComputerScienceJ_ Heidelberg:SpringerBerlin,2006:222-231. [4]于红斌,李孝安.基于栅格法的机器人快速路径规划[J].微电子1 学与计算机,2005,22(6):98—100. 图4蚁群路径规划场景3 例(口,J一瑚仃r冗兰 j『 ? I{l1一?_r}? —— j_ —_——L———— j II?? iT,一 『??_l1,Jl J}If{T I}l}I1 图5蚁群路径规划场景4 初始的栅格模型 IIl』\——lj I; 一 _’?\ ,J——一 -_\ ??]?L— _啊__l【 一?? 一 曼:妻法的机器人路径规划快速搜图6蚁群径规划场景5索随机数算法【J】. 南京师范大学,2007,7(2):58—61.一”一…,…一一…. [6J司应涛,朱庆保,国海涛.基于正反馈遗传算法的机器人全局路径规划[J].计算机工程与应用,2008,44(1):54—56. [7】王俭,肖金球.一种改进的机器人路径规划蚂蚁算法[J].微计算机信息,2005,21(5):53—54.