《蚁群算法及其在移动机器人路径规划中的应用讲解》由会员分享，可在线阅读，更多相关《蚁群算法及其在移动机器人路径规划中的应用讲解（13页珍藏版）》请在装配图网上搜索。
1、蚁群算法及其在移动机器人路径规划中的应用摘要移动机器人路径规划是机器人研究领域的核心内容之一 ，具有复杂性、 约束性和非线性等特点。蚁群算法(ACA)是最近十几年发展起来的仿生优化算 法,该算法在解决许多复杂问题方面已经展现出其优异的性能和巨大的 发展潜 力。本文主要研究静态环境下基于蚁群算法的移动机器人全局路径 规划。采 用栅格法建立环境模型，并利用做过改进的基本蚁群算法在栅格环 境模型中 进行路径规划，这些改进有：利用伪随机比例规则代替随机比例规 则进行路 径转移；限制了蚂蚁行至当前栅格时下一步允许选择的栅格范围 对启发函数 进行了重新定义；让蚂蚁根据转移概率利用“轮盘赌”方法选择 下一个
2、栅 格。关键词:蚁群算法,移动机器人，路径规划，栅格AbstractThe path pla nning for mobile robots is one of the core contentsof the filed of robotics research with complex,restrietive and non li nearcharacteristics. The ant colony algorithm (ACA)is a new bionics optimization algorithm developed in the past decade, it shows ex
3、cellent performanee and great potentialfor development whensolving manycomplex 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
4、path planninginen vir onmen t Thesemodificati ons in clude:us ing theproporti onal rule in stead of the ran dom proporti onalrule to choosepath;limitingthe scope of the next grid allowed to be chosen by theants;redefiningthe heuristicfunction;Usingthe roulette to chooseKeywords：the n ext grid for th
5、e an ts.ACA,mobile rob ot s,pa th pla nnin g,grid1引言至今，在工业制造中，机器人学已经取得了伟大的成功。机器人手臂 或机 械手在装配线中也发挥了越来越重要的作用。但是，所有这些成功的 应用，商 用机器人都存在着一个根本的缺点：缺乏机动性。相反移动机器人可以行走整 个车间，灵活地在它最有效的地方施展它的才能。其中亚马 逊物流机器人已经 成功地在物流方面得到了应用，所以移动机器人的研究存在着必要性与可行 性。移动机器人导航的任务主要由定位、避障和路径规划组成，其中路径规 划是机器人控制最为关键的技术。移动机器人路径规划是指在有障碍物的工作 环境中按
6、照一定的评价标准（如工作代价最小、行走路线最短、行走时间最短 等），寻找一条从起始状态（包括位置和姿态）到达目标状态（包括位 置和姿态） 的无碰路径。蚁群算法是一种受到生物界中真实蚁群集觅食行为的启发式算 法，该算法在求解旅行商（TSP ）和作业调度等多目标优化问题取得了不错的 成果，且大量研究结果表明相对于其它人工智能算法，蚁群算法所取得的结果 是最优的。由于机器人路径规划与蚁群觅食行为有着天然的联系，本文将蚁群算 法引入到机器人路径规划领域中，通过蚁群算法对移动机器人的路径进行规划 验证。2.蚁群算法2.1蚁群算法的基本原理研究发现，蚂蚁寻找食物时，它们总能找到一条从巢穴到食物之间的最优路
7、径，这是因为蚂蚁在寻找路径时，会在路径上释放出一种特殊的信息素(Pheromone).当它们碰到一个还没有走过的路口时，就随机挑选一条路径前行.与此同时释放出与路径长度有关的信息素 .路径越长，释放的信息 素浓度就越低当后来的蚂蚁再次碰到这个路口的时候，选择信息素浓度较高路径的概率相对较大.最优路径上的信息素浓度越来越大，而其它路径上信 息素浓度却会随着时间的流逝而消减.不仅如此,蚂蚁还能够适应环境的变化， 当蚁群运动路线上突然出现障碍物时，蚂蚁能够很快地重新找到一条最优路径. 我们根据这一特性做的仿真效果图如下，图中H代表蚁穴，F代表食物，+为未 寻找到食物的蚂蚁， 为已找到食物的蚂蚁，蚁群
8、从开始 寻找食物，到寻得一条最优路径的过程如图1.1、1.2所示.FoodHone 0$图1.1初始状态蚂蚁随机挑选路径寻找食tf - 711 ET r- STS11 . ! I r r *I. RL呱咖t i i hi hi Mil，I川讥 imi iIiiI：i|iJ)； ill iij H(| fflll 11 !i ill illIIIIIH). ll)：. -INtEUnnninnHijei1LO (嘛illI聊illVmi* Q 亠 * O G IHome 201i |j I k I I 1 J * J J； | IJ1- | i n 11(. u IBIUIIHii1yfii .
9、i ；. YI I ii.川(II ;ii m ；iih:汕，1(11 .Hl I 1J i )ilH l|iH Ji, 1i MJ i II1J,.1 .i 1i ! “;Hi . i j i), hi：lll iW. I.o.j;U,ill ,U 11) 111hiJ. I iill ILH1I Ilf! ii. i4 Illi I IIII.Jfi1Jill (IIItII 哪iill; IN： ll H | i. .lO ： IUfl i IK 卜3 b HUi IlCLIH !Illi lllb 111HL1I I i ,111 I I2.2蚁群算法的数学模型蚂蚁k(k=l,2,m)
10、在运动过程中，运动转移的方向由各条路径上的信息 量浓度决定。为方便记录可用tabujk =1,2, r m)来记录第k只蚂蚁当前已走 过的所有节点，这里可以称存放节点的表为禁忌表；这个存放节点的集合 会随 着蚂蚁的运动动态的调整。在算法的搜索过程中，蚂蚁会智能地选择 下一步所 要走的路径。设m表示蚂蚁总数量，用dj(i, j =0,1,n1)表示节点i和节点j之间的距离，j(t)表示在t时刻ij连线上的信息素浓度。在初始时刻，m只蚂蚁会被随机地放置，各路径上的初始信息素浓度是相同的在t时刻，蚂 蚁k从节点i转移到节点j的状态转移概率为rkPj。口 F(t)吋F,jc allowed2-1all
11、owed kpk = 0 , other其中，allowedk- ； c-tabUk /表示蚂蚁k下一步可以选择的所有节点，C为 全部节点集合；:为信息启发式因子，在算法中代表轨迹相对重要程度， 反映 路径上的信息量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间 的协作性 就越强；可称为期望启发式因子，在算法中代表能见度的相对 重要性。j是 启发函数，在算法中表示由节点i转移到节点j的期望程 度，通常可取可j /dj。在算法运行时每只蚂蚁将根据(2-1)式进行搜索前在蚂蚁运动过程中，为了避免在路上残留过多的信息素而使启发信息被淹没，在每只蚂蚁遍历完成后，要对残留信息进行更新处理。由此，在 t+
12、n时刻，路径(i,j)上信息调整如下ij t nj(t) -Mt)(2-2)m ij(tws： (t)(2-3)k=1在式中，常数*00,1表示信息素挥发因子，表示路径上信息量的损耗程度，的大小关系到算法的全局搜索能力和收敛速度，则可用代表信息素残留因子，一ik(t)表示一次寻找结束后路径(i,j)的信息素增量。在初始时 刻一=。，(1)表示第k只蚂蚁在本次遍历结束后路径(i,j)的信息素。由于信息素更新策略有所不同，学者Dorigo M研究发现了三种不同的基本 蚁群算法模型，分别记为“蚁周系统”(An t-Cycle)模型、“蚁量系统”(An t-Qua ntity)模型及“蚁密系统”(An
13、 t-De nsity)模型，三种模型求解(t)方式存在不同。“蚁周系统”(Ant-Cycle)模型匚，第k只蚂蚁走过j0, ot her“蚁量系统”(An t-Qua ntity)模型Q_时二乜，第k只蚂蚁在t和t+1之间走过 j (2-5)0, ot her“蚁密系统”(An t-De nsity)模型k q,第 k 只 蚂蚁在 t 和 t+1 之间走过 ij (2-6) Wo,ot her“蚁周系统”中路径中信息素是在蚂蚁完成一个循环后更新的，即应用的是整体信息。在一系列标准测试问题上运行的实验表明,“蚁周系统”算法的性能优于其他两种算法。因此，对蚂蚁系统的研究正朝着更好地了解“蚁周系统
14、”特征的方向发展。3蚁群算法在移动机器人路径规划中的应用3.1蚁群算法的机器人路径规划原理根据机器人路径规划的定义和蚁群算法的原理，基于蚁群算法的机器 人路径规划原理为为：将m只蚂蚁放在出发点h,以每只蚂蚁当前节点为中心， 采取一定策略选择并走到下一个节点，对新路径的信息素按局部更新规则进行 更新。如果有蚂蚁k到达目标节点几由于蚂蚁k最先到达，用时肯定 最少，这 样它获得的路径在蚁群本轮寻优中是最优的，因此对蚂蚁k所得路径进行全局信息素更新，并保存该路径为当前最优路径，对当前最优路径进行 全局信息素更新。然后k从f出发以h为目标继续寻优。如果蚂蚁找到 新的路 径，那么将新路径与当前最优路径进行
15、比较，如果新路径好于当前最优路径那 么就用新路径代替当前最优路径，同时对其全局信息素更新。如果在最近一次 全局信息素更新后，又产生新的m条路径时，如果当前最优路径还没有得到更 新，则对当前最优路径进行全局信息素更新。不断重复，直到3.1满足设定的结束条件或规定的代数完成。蚁群系统流程图如图幵始设置参数浜初始化蚁群 _ i丁”.蚂蚁构造路径应用局部更新规则吕切盾环结束崔二匚q 应用全局更 找出最短路径K仝终左73X.结束图 3.1 蚁群系统流程图3.2 机器人工作环境建模环境模型的建立是机器人路径规划非常重要的一个环节。机器人的实 际工作环境是一个现实的物理空间，而路径规划算法所处理的空间是环境
16、 的抽象空 间。环境建模就是实现物理空间到抽象空间的一个映射。我们通常利用栅格法建立环境模型， 模拟机器人工作的实际工作空间。采用栅格表示机器人工作的环境地图，在处理障碍物边界时，可避免复杂的 计 算。在栅格法的应用中，栅格粒度的划分非常关键：栅格粒度越小，障碍物 的表 示会越精确，但同时会占用大量的存储空间，算法的搜索范围会按指数 增加；栅 格粒度太大，规划出的路径会很不精确。如图 3.2，为截取的部分栅 格环境，灰 色栅格为障碍格，其它栅格为自由格图32栅格图4.结论和展望虽然优化蚁群算法的研究才刚刚起步，但这些初步研究已显示出了蚁群优 化算法在求解复杂优化问题（特别是离散优化问题）方面的
17、优越性，证明它是 一种很有发展前景的方法。但是必须指出的，蚁群优化算法是一种概率算法， 从数学上对它们的正确性和可靠性的证明还是比较困难的。其在移动机器人路 径规划中的应用还有很多富有挑战性的课题亟待解决。主要体现在以下几方 面：（1）近期对蚁群算法在移动机器人路径规划中的应用研究还处于初期探索阶段，研究重点主要集中在算法模型的建立与实例仿真方面，而对于算法的理论分析、与其他算法结合等方面的研究较少；（2）近期对蚁群算法在移动机器人路径规划的研究主要集中于静态环 境 下的路径规划研究，而对动态环境下的路径规划研究相对较少。参考文献1 范路桥，姚锡凡，卞青青，蒋梁中蚁群算法及其在移动机器人路径规
18、划中的应用J微计算机信息， 2008， 24： 08-02.杜利峰，牛永洁.蚁群算法在MATLAB中的实现J.信息技术，2011， 06: 115-1183 张银铃，牛小梅.蚁群算法在移动机器人路径规划中的仿真研究J.计算机仿真， 2011， 06:231-234.4 李士勇等蚁群算法及其应用M.哈尔滨工业大学出版社，2004-09.5 周海滨.蚁群算法原理及其应用：t heory and applica ti onsM.科学出版社,2005-12.6 R.西格沃特，I.R.诺巴克什等著，李人厚，宋青松译.自主移动机器人导论 M.西安交通大学出版社， 2013-05.7 孟艳，金耀初著，杨文明译，仿生自组织机器人系统M.北京理工 大学出 版社， 2014-05.
蚁群算法及其在移动机器人路径规划中的应用讲解
