蚁群算法及其在移动机器人路径规划中的应用 摘要 移动机器人路径规划是机器人研究领域的核心内容之一,具有复杂性、约束性和非线性等特点。蚁群算法(ACA)是最近十几年发展起来的仿生优化算法,该算法在解决许多复杂问题方面已经展现出其优异的性能和巨大的发展潜力。本文主要研究静态环境下基于蚁群算法的移动机器人全局路径规划。采用栅格法建立环境模型,并利用做过改进的基本蚁群算法在栅格环境模型中进行路径规划,这些改进有:利用伪随机比例规则代替随机比例规则进行路径转移;限制了蚂蚁行至当前栅格时下一步允许选择的栅格范围;对启发函数进行了重新定义;让蚂蚁根据转移概率利用“轮盘赌”方法选择下一个栅格。 关键词:蚁群算法,移动机器人，路径规划,栅格 1
Abstract The path planning for mobile robots is one of the core contents of the filed of robotics research with complex,restrictive and nonlinear characteristics.The ant colony algorithm (ACA)is a new bionics optimization algorithm developed in the past decade,it shows excellent performance and great potential for development when solving many complex problems.This thesis mainly studies global path planning for mobile robots based on ACA in static environment.Grid method is used to establish the environment model and some modifications are made to accommodate ACA to path planning in grid-based environment.These modifications include:using the proportional rule instead of the random proportional rule to choose path;limiting the scope of the next grid allowed to be chosen by the ants;redefining the heuristic function;Using the roulette to choose the next grid for the ants. Keywords: ACA,mobile robots,path planning,grid
2
1.引言 至今，在工业制造中，机器人学已经取得了伟大的成功。机器人手臂或机械手在装配线中也发挥了越来越重要的作用。但是，所有这些成功的应用，商用机器人都存在着一个根本的缺点：缺乏机动性。相反移动机器人可以行走整个车间，灵活地在它最有效的地方施展它的才能。其中亚马逊物流机器人已经成功地在物流方面得到了应用，所以移动机器人的研究存在着必要性与可行性。 移动机器人导航的任务主要由定位、避障和路径规划组成,其中路径规划是机器人控制最为关键的技术。移动机器人路径规划是指在有障碍物的工作环境中按照一定的评价标准(如工作代价最小、行走路线最短、行走时间最短等),寻找一条从起始状态(包括位置和姿态)到达目标状态(包括位置和姿态)的无碰路径。蚁群算法是一种受到生物界中真实蚁群集觅食行为的启发式算法,该算法在求解旅行商(ＴＳＰ)和作业调度等多目标优化问题取得了不错的成果,且大量研究结果表明相对于其它人工智能算法,蚁群算法所取得的结果是最优的。 由于机器人路径规划与蚁群觅食行为有着天然的联系,本文将蚁群算法引入到机器人路径规划领域中，通过蚁群算法对移动机器人的路径进行规划验证。 2.蚁群算法 2.1蚁群算法的基本原理 研究发现,蚂蚁寻找食物时,它们总能找到一条从巢穴到食物之间的最
3
优路径，这是因为蚂蚁在寻找路径时，会在路径上释放出一种特殊的信息素(Pheromone).当它们碰到一个还没有走过的路口时,就随机挑选一条路径前行.与此同时释放出与路径长度有关的信息素.路径越长,释放的信息素浓度就越低.当后来的蚂蚁再次碰到这个路口的时候, 选择信息素浓度较高路径的概率相对较大.最优路径上的信息素浓度越来越大,而其它路径上信息素浓度却会随着时间的流逝而消减.不仅如此,蚂蚁还能够适应环境的变化,当蚁群运动路线上突然出现障碍物时,蚂蚁能够很快地重新找到一条最优路径.我们根据这一特性做的仿真效果图如下，图中H代表蚁穴，F代表食物，+为未寻找到食物的蚂蚁，0为已找到食物的蚂蚁，蚁群从开始**寻找食物，到寻得一条最优路径的过程如图 1.1、1.2 所示. 图1.1初始状态蚂蚁随机挑选路径寻找食物 图1.2经过一段时间后蚂蚁成功避开障碍物找到一条合适路径 4
2.2 蚁群算法的数学模型 蚂蚁k(k?1,2???,m)在运动过程中，运动转移的方向由各条路径上的信息量浓度决定。为方便记录可用tabuk(k?1,2,???,m)来记录第 k 只蚂蚁当前已走过的所有节点，这里可以称存放节点的表为禁忌表；这个存放节点的集合会随着蚂蚁的运动动态的调整。在算法的搜索过程中，蚂蚁会智能地选择下一步所要走的路径。 设 m 表示蚂蚁总数量，用dij(i,j?0,1,???,n?1)表示节点 i 和节点 j 之间的距离，?ij(t)表示在 t 时刻ij连线上的信息素浓度。在初始时刻，m只蚂蚁会被随机地放置，各路径上的初始信息素浓度是相同的。在 t 时刻，蚂蚁 k 从节点i转移到节点 j 的状态转移概率为 ????ij(t)?ij(t) ,j?allowedk????kpij????ij(t)?ij(t) ?2-1? ?k?allowedkkpij?0 , other?? 其中，allowedk??c?tabuk?表示蚂蚁 k 下一步可以选择的所有节点，C 为全部节点集合；?为信息启发式因子，在算法中代表轨迹相对重要程度，反映路径上的信息量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间的协作性就越强；?可称为期望启发式因子，在算法中代表能见度的相对重要性。?ij是启发函数，在算法中表示由节点i 转移到节点 j 的期望程度，通常可取?ij?1/dij。在算法运行时每只蚂蚁将根据(2-1)式进行搜索前进。 在蚂蚁运动过程中，为了避免在路上残留过多的信息素而使启发信息 5
蚁群算法及其在移动机器人路径规划中的应用讲解 - 图文
