《蚁群算法及其在移动机器人路径规划中的应用讲解.doc》由会员分享，可在线阅读，更多相关《蚁群算法及其在移动机器人路径规划中的应用讲解.doc（10页珍藏版）》请在三一办公上搜索。
1、蚁群算法及其在移动机器人路径规划中的应用摘要移动机器人路径规划是机器人研究领域的核心内容之一,具有复杂性、约束性和非线性等特点。蚁群算法(ACA)是最近十几年发展起来的仿生优化算法,该算法在解决许多复杂问题方面已经展现出其优异的性能和巨大的发展潜力。本文主要研究静态环境下基于蚁群算法的移动机器人全局路径规划。采用栅格法建立环境模型,并利用做过改进的基本蚁群算法在栅格环境模型中进行路径规划,这些改进有:利用伪随机比例规则代替随机比例规则进行路径转移;限制了蚂蚁行至当前栅格时下一步允许选择的栅格范围;对启发函数进行了重新定义;让蚂蚁根据转移概率利用“轮盘赌”方法选择下一个栅格。关键词:蚁群算法,移
2、动机器人，路径规划,栅格AbstractThe 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 performan
3、ce 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
4、 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.Keywor
5、ds: ACA,mobile robots,path planning,grid1. 引言至今，在工业制造中，机器人学已经取得了伟大的成功。机器人手臂或机械手在装配线中也发挥了越来越重要的作用。但是，所有这些成功的应用，商用机器人都存在着一个根本的缺点：缺乏机动性。相反移动机器人可以行走整个车间，灵活地在它最有效的地方施展它的才能。其中亚马逊物流机器人已经成功地在物流方面得到了应用，所以移动机器人的研究存在着必要性与可行性。移动机器人导航的任务主要由定位、避障和路径规划组成,其中路径规划是机器人控制最为关键的技术。移动机器人路径规划是指在有障碍物的工作环境中按照一定的评价标准(如工作代价最小、
6、行走路线最短、行走时间最短等),寻找一条从起始状态(包括位置和姿态)到达目标状态(包括位置和姿态)的无碰路径。蚁群算法是一种受到生物界中真实蚁群集觅食行为的启发式算法,该算法在求解旅行商()和作业调度等多目标优化问题取得了不错的成果,且大量研究结果表明相对于其它人工智能算法,蚁群算法所取得的结果是最优的。由于机器人路径规划与蚁群觅食行为有着天然的联系,本文将蚁群算法引入到机器人路径规划领域中，通过蚁群算法对移动机器人的路径进行规划验证。2.蚁群算法2.1蚁群算法的基本原理研究发现,蚂蚁寻找食物时,它们总能找到一条从巢穴到食物之间的最优路径，这是因为蚂蚁在寻找路径时，会在路径上释放出一种特殊的信
7、息素(Pheromone).当它们碰到一个还没有走过的路口时,就随机挑选一条路径前行.与此同时释放出与路径长度有关的信息素.路径越长,释放的信息素浓度就越低.当后来的蚂蚁再次碰到这个路口的时候, 选择信息素浓度较高路径的概率相对较大.最优路径上的信息素浓度越来越大,而其它路径上信息素浓度却会随着时间的流逝而消减.不仅如此,蚂蚁还能够适应环境的变化,当蚁群运动路线上突然出现障碍物时,蚂蚁能够很快地重新找到一条最优路径.我们根据这一特性做的仿真效果图如下，图中H代表蚁穴，F代表食物，+为未寻找到食物的蚂蚁，为已找到食物的蚂蚁，蚁群从开始寻找食物，到寻得一条最优路径的过程如图 1.1、1.2 所示.
8、 图1.1初始状态蚂蚁随机挑选路径寻找食物图1.2经过一段时间后蚂蚁成功避开障碍物找到一条合适路径2.2 蚁群算法的数学模型 蚂蚁在运动过程中，运动转移的方向由各条路径上的信息量浓度决定。为方便记录可用来记录第 k 只蚂蚁当前已走过的所有节点，这里可以称存放节点的表为禁忌表；这个存放节点的集合会随着蚂蚁的运动动态的调整。在算法的搜索过程中，蚂蚁会智能地选择下一步所要走的路径。 设 m 表示蚂蚁总数量，用表示节点 i 和节点 j 之间的距离，表示在 t 时刻连线上的信息素浓度。在初始时刻，m只蚂蚁会被随机地放置，各路径上的初始信息素浓度是相同的。在 t 时刻，蚂蚁 k 从节点i转移到节点 j 的
9、状态转移概率为 其中，表示蚂蚁 k 下一步可以选择的所有节点，C 为全部节点集合；为信息启发式因子，在算法中代表轨迹相对重要程度，反映路径上的信息量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间的协作性就越强；可称为期望启发式因子，在算法中代表能见度的相对重要性。是启发函数，在算法中表示由节点i 转移到节点 j 的期望程度，通常可取。在算法运行时每只蚂蚁将根据(2-1)式进行搜索前进。 在蚂蚁运动过程中，为了避免在路上残留过多的信息素而使启发信息被淹没，在每只蚂蚁遍历完成后，要对残留信息进行更新处理。由此，在t+n时刻,路径(i,j)上信息调整如下 (2-2) (2-3) 在式中，常数 表示信
10、息素挥发因子,表示路径上信息量的损耗程度,的大小关系到算法的全局搜索能力和收敛速度，则可用代表信息素残留因子,表示一次寻找结束后路径(i,j)的信息素增量。在初始时刻,表示第 k 只蚂蚁在本次遍历结束后路径(i,j)的信息素。 由于信息素更新策略有所不同，学者Dorigo M 研究发现了三种不同的基本蚁群算法模型，分别记为“蚁周系统”(Ant-Cycle)模型、“蚁量系统”(Ant-Quantity)模型及“蚁密系统”(Ant-Density)模型，三种模型求解 方式存在不同。“蚁周系统”(Ant-Cycle)模型 第k只蚂蚁走过 (2-4)“蚁量系统”(Ant-Quantity)模型 第k只
11、蚂蚁在t和t+1之间走过 (2-5)“蚁密系统”(Ant-Density)模型 第k只蚂蚁在t和t+1之间走过 (2-6)从上边各公式可以看出三种模型的主要区别是：“蚁量系统”和“蚁密系统”中，信息素是在蚂蚁完成一步后更新的，即采用的是局部信息；而在“蚁周系统”中路径中信息素是在蚂蚁完成一个循环后更新的，即应用的是整体信息。在一系列标准测试问题上运行的实验表明，“蚁周系统”算法的性能优于其他两种算法。因此，对蚂蚁系统的研究正朝着更好地了解“蚁周系统”特征的方向发展。3 蚁群算法在移动机器人路径规划中的应用3.1蚁群算法的机器人路径规划原理根据机器人路径规划的定义和蚁群算法的原理,基于蚁群算法的
12、机器人路径规划原理为为:将只蚂蚁放在出发点H,以每只蚂蚁当前节点为中心,采取一定策略选择并走到下一个节点,对新路径的信息素按局部更新规则进行更新。如果有蚂蚁到达目标节点F,由于蚂蚁最先到达,用时肯定最少,这样它获得的路径在蚁群本轮寻优中是最优的,因此对蚂蚁所得路径进行全局信息素更新,并保存该路径为当前最优路径,对当前最优路径进行全局信息素更新。然后从F出发以H为目标继续寻优。如果蚂蚁找到新的路径,那么将新路径与当前最优路径进行比较,如果新路径好于当前最优路径那么就用新路径代替当前最优路径,同时对其全局信息素更新。如果在最近一次全局信息素更新后,又产生新的条路径时,如果当前最优路径还没有得到更新
13、,则对当前最优路径进行全局信息素更新。不断重复,直到满足设定的结束条件或规定的代数完成。蚁群系统流程图如图3.1图3.1蚁群系统流程图3.2 机器人工作环境建模 环境模型的建立是机器人路径规划非常重要的一个环节。机器人的实际工作环境是一个现实的物理空间,而路径规划算法所处理的空间是环境的抽象空间。环境建模就是实现物理空间到抽象空间的一个映射。我们通常利用栅格法建立环境模型，模拟机器人工作的实际工作空间。采用栅格表示机器人工作的环境地图,在处理障碍物边界时,可避免复杂的计算。在栅格法的应用中,栅格粒度的划分非常关键:栅格粒度越小,障碍物的表示会越精确,但同时会占用大量的存储空间,算法的搜索范围会
14、按指数增加;栅格粒度太大,规划出的路径会很不精确。如图3.2，为截取的部分栅格环境，灰色栅格为障碍格，其它栅格为自由格图3.2栅格图4. 结论和展望虽然优化蚁群算法的研究才刚刚起步，但这些初步研究已显示出了蚁群优化算法在求解复杂优化问题（特别是离散优化问题）方面的优越性，证明它是一种很有发展前景的方法。但是必须指出的，蚁群优化算法是一种概率算法，从数学上对它们的正确性和可靠性的证明还是比较困难的。其在移动机器人路径规划中的应用还有很多富有挑战性的课题亟待解决。主要体现在以下几方面: （1）近期对蚁群算法在移动机器人路径规划中的应用研究还处于初期探索阶段, 研究重点主要集中在算法模型的建立与实例
15、仿真方面,而对于算法的理论分析、与其他算法结合等方面的研究较少; （2）近期对蚁群算法在移动机器人路径规划的研究主要集中于静态环境下的路径规划研究,而对动态环境下的路径规划研究相对较少。参 考 文 献1 范路桥，姚锡凡，卞青青，蒋梁中. 蚁群算法及其在移动机器人路径规划中的应用J. 微计算机信息，2008，24：08-02. 2 杜利峰，牛永洁. 蚁群算法在MATLAB中的实现J. 信息技术，2011，06: 115-118.3 张银铃，牛小梅. 蚁群算法在移动机器人路径规划中的仿真研究J. 计算机仿真，2011，06:231-234.4 李士勇等. 蚁群算法及其应用M. 哈尔滨工业大学出版社，2004-09.5 周海滨. 蚁群算法原理及其应用：theory and applicationsM. 科学出版社, 2005-12.6R.西格沃特，I.R.诺巴克什等著，李人厚，宋青松译. 自主移动机器人导论M. 西安交通大学出版社，2013-05.7孟艳，金耀初著，杨文明译，仿生自组织机器人系统M.北京理工大学出版社，2014-05.
