文档分类：
下载后只包含 1 个 PDF 格式的文档，没有任何的图纸或源代码，
下载前请先预览，预览内容跟原文是一样的，在线预览图片经过高度压缩，下载原文更清晰。
您的浏览器不支持进度条
下载文档到电脑，查找使用更方便
还剩?页未读，继续阅读
播放器加载中，请稍候...
该用户其他文档
下载所得到的文件列表基于改进蚁群算法的机器人路径规划（原版论文）.pdf
文档介绍：
誊耻号:工￡盥奠!:1.监一密级: 釜JL南京师鬼火掌顺I:j学位论文固基于改进蚁群算法的机器人路径规划作者:院系:指导教师:学科专业:王俊峰数学与汁抖:帆科学学院朱庆保教授运筹学与控制论(智能控制方向)南京师范大学2005年硕t学位论文基于改进蚁群算法的机器人路径规划摘要移动机器人路径规划是机器人技术中一个重要研究领域,得到了很多研究者的关注,并取得了一系列重要成果。目前已存在许多优化算法用来解决该问题,但不少算法都存在一定局限性,如当算法的约束条件较多时,很难求解复杂环境的路径规划问题等。本文根据机器人路径规划算法的研究现状和向智能化、仿生化发展的趋势,研究了一种基于改进蚁群算法的机器人全局路径规划方法。由于蚁群算法易陷入停滞、死锁等,本文提出了三点改进策略:1.算法在执行过程中,当蚂蚁陷入无路可选的境况时,采用回退策略,使得蚂蚁能及时脱离困境,保证算法的健壮性:2.蚂蚁在搜索过程中,当寻优方向不同的两只蚂蚁相遇时,采取相遇策略,利用两只蚂蚁禁忌表中的信息,生成新路径。这样可充分发挥蚁群的群体协作性,提高生成路径的速度;3.在生成一定数目的路径后,采用带交叉点的路径交叉策略,提高算法的收敛速度。仿真实验证实了该改进算法具有实现简单、效率较高、健壮性强的特点。关键字:移动机器人,全局路径规划,蚁群算法南京师范大学2005年硕士学位论文基于改进蚁群算法的机器人路径规划AbstractThe path planning for mobile robots plays an important role in the field ofrobotics.It is arising many scholars’interesting and it's already got a series of achievements inthis field.At present,there are many advanced algorithms used to solve this optimalproblem.However,for those algorithms,it is very difficult to solve some pathplanning problems containing certain constraint conditions due to plexbackground environment.According to the present condition of the studying and theintellective and bionics tendency ofthe field’S development,this paper presents a newpath planning approach based on the improved ant colony algorithm with three newstrategies.Firstly,in the process of the algorithm the ants without the next node tochoose,employ the retracing strategy to leave the difficult position.So the robustcharacter of the new method is strengthened.Secondly,in the processing when thetwo ants with the different searching direction meet,it uses the meeting strategy to getthe new path by using the records information in the forbidden tables of the twomeeting ants.Then the new method could get the enOUgh cooperation character oftheant colony and the speed of getting new path could be improved.Lastly,when gettingthe fixcd number of the paths.it uses path-crossing strategy toimprove the convergespeed ofthe new method.The results ofthe experiments show that the new method ofthis paper has the characteristics of simple,hi曲efficiency and robust.Keywords:mobile robot,global path planning,ant colony algorithm学位论文独创性声明本人郑重声明:I、坚持以“求实、创新”的科学精神从事研究工作。2、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。3、本论文中除引文外,所有实验、数据和有关材料均是真实的。4、本论文中除引文和致谢的内容外,不包含其他人或其它机构已经发表或撰写过的研究成果。5、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。作者签名:日期:学位论文使用授权声明本人完全了解南京师范大学有关保留、使用学位论文的规定,学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版;有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅;有权将学位论文的内容编入有关数据库进行检索;有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。作者签名日期南京师范大学2005年硕士学位论文基于改进蚁群算法的机器人路径规划序言迄今为止,对于机器人路径规划人们已经探索出了许多有效的求解方法。诸如可视图法、自由空间法、环境地图法和栅格法等。近年来,不少学者用改进的遗传算法、神经网络、随机树等方法对机器人路径进行规划。机器人路径规划算法向智能化、仿生化发展是一个明显的趋势。由于已有算法不同程度的存在一定局限性,诸如搜索空间大、算法复杂、效率不高等,特别是当障碍物的数目增加或地形障碍趋于复杂时,不少路径规划算法的复杂度会大大增加,甚至无法求解。根据目前的研究现状和不足,本文研究了一种基于改进蚁群算法的机器人全局路径规划方法。实验结果表明,本文算法在收敛速度和健壮性等方面都得到了明显改善。一、本课题研究的主要内容本课题在进行场景建模的基础上,重点研究了用于机器人全局路径规划的改进智能蚁群算法,提出了三点改进策略,并从理论上进行了性能分析;在此基础上,用计算机软件实现了一个仿真实验系统,并进行了仿真实验,通过对实验结果统计数据的比较分析,验证了算法的有效性和优良性能。二1
内容来自淘豆网转载请标明出处.基于优化蚁群算法的机器人路径规划_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
基于优化蚁群算法的机器人路径规划
上传于|0|0|文档简介
&&基于优化蚁群算法的机器人路径规划
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢基于改进蚁群算法的移动机器人路径规划
朱颢东, 孙振, 吴迪, 申圳. 基于改进蚁群算法的移动机器人路径规划[J]. 重庆邮电大学学报:自然科学版, ): 849-855
ZHU Haodong, SUN Zhen, WU Di, SHEN Zhen. Path planning for mobile robot based on improved ant colony algorithm[J]. Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition,): 849-855&&
Permissions
基于改进蚁群算法的移动机器人路径规划
郑州轻工业学院 计算机与通信工程学院 河南 郑州 450002
通讯作者:朱颢东
朱颢东(1980-),男,河南虞城人,副教授,博士,硕士生导师,主要研究方向为智能信息处理、计算智能。E-Mail:。
孙 振(1989-),男,河南新乡人,在读硕士研究生,主要研究方向为智能信息处理、模式识别。
吴 迪(1990-),男,河南南阳人,在读硕士研究生,主要研究方向为智能信息处理、图像处理。
申 圳(1989-),男,河南唐河人,在读硕士研究生,主要研究方向为图像处理、模式识别。
基金:国家自然科学基金(); 河南省高等学校青年骨干教师资助计划项目(2014GGJS-084); 河南省科技创新杰出人才计划项目(); 河南省教育厅科学技术研究重点项目 (13A520367); 郑州轻工业学院校级青年骨干教师培养对象资助计划项目(XGGJS02); 郑州轻工业学院博士科研基金(2010BSJJ038); 郑州轻工业学院研究生科技创新基金
针对蚁群算法应用于移动机器人路径规划时存在易于陷入局部最优解、收敛速度慢的问题,提出了一种适用于静态障碍环境下基于改进蚁群算法的移动机器人路径规划方法。该方法改进了节点间的状态转移规则,增加了得到最优路径的概率;自适应调整启发函数,提高了算法的搜索效率;基于狼群法则对信息素进行更新,有效避免了算法陷入局部最优解;动态调整了衰减系数,在后期增加了蚂蚁对最优路径的选择概率,加快了算法的收敛速度。仿真实验表明,与其他算法在相同环境下比较,该改进算法在路径规划结果相同的情况下具有较快的收敛速度;且改进算法在不同复杂程度环境中均得到了最优路径,也表明了该算法的有效性和可靠性。该算法具有良好的寻优能力,可以适用于不同复杂环境中的移动机器人路径规划。
移动机器人;
中图分类号:TP301&&
文献标志码:A&&
文章编号:16)06-0849-07
Path planning for mobile robot based on improved ant colony algorithm
ZHU Haodong,
School of Computer and Communication Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, P.R. China
Fund:The National Natural Science Foundation of China (); The Youth Backbone Teachers Funding Planning Project of Colleges and Universities in Henan Province of China(2014GGJS-084); The Technology Innovation Outstanding Talents Plan Project of Henan Province of China(); The Science and Technology Research Key Project of Education Department of Henan Province of China (13A520367); The Youth Backbone Teachers Training Targets Funded Project of Zhengzhou University of Light Industry of Henan Province of China(XGGJS02); The Ph.D.Research Funded Project of Zhengzhou University of Light Industry of Henan Province of China (2010BSJJ038); The Science and Technology Innovation Fund Project of Postgraduate of Zhengzhou University of Light Industry
In order to solve the problem that the ant colony algorithm was used in path planning for mobile robot, and is easily falls into local optimum and has a slow convergence speed, the paper proposes a method that the improved ant colony algorithm was used in path planning for mobile robot in the static environment. The method improves the transition rule of node state to increase the probability of searching optimal path. An adaptive heuristic function improves the searching efficiency of the algorithm. Updating the pheromone avoids falling into local optimum based on the assignment rule of wolves. Dynamical adjustment of the decay parameter increases the probability of choosing the optimal path by ants at a later stage, thus accelerating the convergence speed. The simulation results show that the improved algorithm has faster convergence speed under the condition of the same result of path planning when compared to other algorithm in the same environment. The improved algorithm obtains the optimal path in the environments of different complexity levels and it shows the efficiency and feasibility of the improved algorithm, which has good optimization ability and can be applied to path planning for mobile robot in the environments of different complexity levels.
mobile robot;
ant colony algorithm;
path planning
0 引 言移动机器人路径规划是近年来机器人研究领域的重要分支和研究热点之一。移动机器人路径规划是指移动机器人在有障碍物的环境中, 找到一条从起始点到目的点最优的无碰路径[, ]。路径规划问题具有复杂性、多约束性和多目标性等特点。传统的路径规划算法有Dijkstra, A* 算法等, Dijkstra是一种经典的最短路径搜索算法, 它是一种贪心算法, 虽然能很好地规划出路径, 但是由于该算法是以起始点向外层层扩展, 直到搜索到目的节点为止, 需要遍历节点, 计算复杂度高, 效率比较低; A* 算法是一种启发式算法, 它是通过估价函数来确定当前点到目标点的距离和搜索方向, 在复杂的环境中一个不理想的估计函数容易导致搜索不到路径或者规划路径效果不理想。近年来, 在移动机器人路径规划方法中, 国内外专家学者提出了许多仿生智能优化算法[], 如:遗传[]、人工鱼群[]、蛙跳[]、神经网络[]以及蚁群[]等算法。1992年, Marco Dorigo在博士论文中提出了蚁群算法, 通过观察蚂蚁寻找食物源时发现路径的行为而获得启发。传统的蚁群算法主要是解决旅行商问题(travelling salesman problem, TSP), 文献[9]借鉴最大-最小蚁群系统的方法, 限制了信息素的值域范围, 有效地避免了算法陷入局部最优解问题。文献[10]构建了权重可调的引力概率函数, 并且把它作为启发因子, 有效地提高了算法的收敛速度。文献[11]改进了算法的信息素更新规则, 并加入拐点作为评价路径质量的参数之一, 提高了算法的效率。文献[12] 分析了影响蚁群优化中的关键参数, 自适应地设置了算法参数, 调高了算法的精度和效率。文献[13]提出了一种基于人工势场法的移动机器人路径规划方法, 定义了一种新的引力函数, 有效地提高了路径规划的性能。文献[14]提出了自适应调整启发函数、路径平滑策略, 有效地提高了路径的质量。目前, 不少算法在求解机器人全局路径问题中存在着局限性, 遗传算法由于运算进化代数众多, 规划路径时占用大量的存储空间, 导致运算速度较慢。人工鱼群算法虽然具有较快的收敛速度, 但是很难得到精确的解, 规划出的路径质量不理想; 混合蛙跳算法易于陷入局部最优解, 求解精度较低, 而且收敛速度较慢, 限制了该算法在路径规划领域的应用; 神经网络算法虽然具有较强的学习能力, 但是当机器人在复杂的环境中, 很难用数学公式来描述。人工势场法是以其数学计算上的简单明了而被广泛应用到路径规划中, 但是, 人工势场法存在局部极小点和目标不可达等问题。而蚁群算法是一种模拟进化算法, 具有自组织性、较强的鲁棒性、分布式计算、寻优能力强、易于和其他算法相结合等优点, 非常适合应用到移动机器人路径规划问题。因此, 论文提出利用改进蚁群算法规划移动机器人路径, 并提出了动态调整挥发系数、自适应调整启发函数等策略, 能够在不同复杂程度的环境中得到全局最优路径, 提高了算法的搜索速率, 并加快了算法的收敛速度, 通过在Matlab软件中仿真实验, 表明了该算法是有效和可行的。1 问题描述与建模机器人路径规划中重要的问题之一是环境建模。建模就是根据已知机器人周围的环境信息, 通过提取和分析, 将现实中物理空间转换为机器人可以理解的空间, 通过建立良好的环境模型, 有效地减少了路径搜索过程中的麻烦。论文中主要用栅格法对机器人的二维环境进行划分, 从左到右, 从上到下对栅格进行编号, 论文中以10× 10的栅格环境为例来说明, 如图1所示。图1Fig.1 图1 栅格坐标与序号关系Fig.1 Grid coordinate relates with serial number图1中, 坐标原点0在左下方, 水平从左向右为x轴正方向, 垂直从下到上为y轴正方向, 栅格的大小由移动机器人自身的大小和它运动步长决定, 为了简化计算路径的长度, 一个栅格的边长为机器人的运动步长, 即一个单位长度。序号与坐标的对应关系如下 xi=mod(Ni/N)-0.5yi=N-ceil(Ni/N)+0.5(1)(1)式中:Ni表示栅格的序号; N表示每一列的栅格数量; mod表示取余数; ceil表示向后取整数。为了建立机器人可以理解的环境, 根据环境地图建立相应的矩阵来表示每个栅格的状态(可行栅格和障碍栅格), 在下面矩阵中, 0代表可行栅格; 1代表障碍栅格, 每一个障碍可能占用一个或多个栅格, 若障碍物占用不足一个栅格, 视为占用一个完整栅格; 机器人被视为一个点状机器人; 将障碍物以机器人半径的大小进行膨化, 确保机器人可以安全地通过障碍物边界。10× 10的棚格环境可用矩阵表示为 Graph=0011000000000010000001100011100000100010010001111001110000000111011000010000000001000010000111000000(2)2 基于改进蚁群算法的路径规化研究表明蚂蚁会在经过的路径上会留下信息素, 并且可以在一定范围内感知信息素进而引导自己的运动, 因此, 蚁群会表现出一种正反馈现象:越多的蚂蚁经过一条路径, 就会在这条路径上释放越多的信息素, 后面的蚂蚁选择这条路径的概率就越大, 蚂蚁之间就是通过这种信息素的交流来选择路径, 进而找到食物源[]。蚁群算法具有局部寻优能力强、自组织性等优点, 能很好地应用到路径规划中, 但传统蚁群算法存在容易陷入局部最优解、收敛速度慢等问题, 为了提高蚁群算法的搜索效率和路径规划质量, 论文对传统蚁群算法做了以下改进。2.1 改进节点状态转移规则蚂蚁会根据启发函数η 和路径上的信息素浓度τ 来选择下一步的可行节点, 设定蚂蚁的种群数量为m, 假设当前蚂蚁k在节点i处, 比较q和q0的大小, 按照(3)式的概率进行选择下一步可行节点j。 (3)-(4)式中:q为[0, 1]的随机数, 而q0 是设定在[0, 1]的阀值。J是根据(4)式的概率分布产生的一个随机变量; j为蚂蚁k选择的下一个可行节点; τ ij(t)是节点i和可行节点j之间的信息素浓度; η ij(t)是启发式信息; α 表示信息素浓度对概率选择影响程度; β 表示启发式信息对概率选择影响程度; allowedk表示当前蚂蚁k下一步可以选择的可行栅格号;
Pijk(t)表示当前蚂蚁k从节点i移动到节点j的概率, 若j不是可行栅格, 则选择概率为0。2.2 自适应调整启发函数在传统的蚁群算法中, 启发函数&#x003b7; 是2个节点之间距离的倒数。A&#x0002A; 算法是一种启发式算法, 表示为f(n)=g(n)+h(n), 其中, g(n) 表示从初始节点到当前节点的实际代价; h(n) 表示当前节点到目的节点的估计代价, 在g值一定的情况下, h值越小, f值就越小, 能保证最短路经的搜索向着目标点方向进行。由启发式A&#x0002A; 算法获得启发, 下一可行节点j和目标点之间的距离可用于启发函数&#x003b7; ij, 即dij和djt被用于启发函数上, 即为 ηij=1dij+djt5(5)式中:dij是当前节点i和可行节点j 间的欧氏距离; djt是可行节点j和目的节点t间的欧式距离, 把目的节点引用到启发函数中, 加强了路径搜索的方向性, 减少了算法的搜索空间, 有效提高搜索的效率。但是过早的引入方向性启发信息, 使得初始的搜索空间太小从而导致算法容易陷入局部最优解; 在初始阶段引进起始节点S和当前节点i之间的距离dsi, 作为衡量搜索空间大小的标准, 随着后期扩大搜索空间后, 方向启发信息将会被引进。启发函数为 ηij=1dij, 其他1dij+djt, ε< dsi< dst-ε(6)(6)式中:dst 是起始节点和目的节点的欧式距离; 阀值&#x003b5; 是一个常数, 由dst的长度具体决定。2.3 改进信息素更新方式在传统的蚁群算法中, 最差蚂蚁的信息素经过正反馈之后可能导致算法搜索陷入局部最优解, 为了避免这个问题, 论文借用狼群法则对信息素进行更新, 在一次循环中, 找到经过局部最优的路径和局部最差路径的蚂蚁, 分别增加和减少释放信息素浓度的量[], 各条路径按照(6)-(8)式进行信息素浓度更新。 &#x00394;
2(ξ+λ)3, (Q/Lbest)局部最优路径经过ij　0　, 其他(8)&#x00394;
τijworst=
2(ξ+λ)3, (Q/Lworst)局部最差路径经过ij0, 其他(9)(7)-(9)式中:&#x00394;
τijk表示在本次循环中第k只蚂蚁留在节点i和节点j路径之间的信息浓度; Q为信息素浓度的常数。Lbest表示这次循环中最优路径长度; Lworst表示本次循环中最差路径长度; &#x003 表示本次循环中局部最优蚂蚁的个数; &#x003 表示本次循环中局部最差蚂蚁的个数。2.4 动态调整衰减系数在全局路径规划中信息素的衰减系数&#x003c1; 起到重要作用, 当环境复杂时, 一个比较大的衰减系数会增加信息素的正反馈, 减少搜索空间以至于降低了找到最优路径的可能性; 一个比较小的衰减系数会增加搜索时间。随着时间和迭代次数的增加, 传统蚁群算法容易陷入局部最优解, 为了避免这个问题, 减少算法搜索时间并且能够保证找到最优路径, 论文提出动态地设置衰减系数, 表示为 ρ(t+1)=ωρmin(t), ωρ(t)< ρmaxρmax, 其他9(9)式中:&#x003c9; =
9NcNmax, 其中, Nmax为最大迭代次数; Nc为当前迭代次数; &#x003c1; min为起始衰减系数; &#x003c1; max 是一个(0, 1)的常数。3 算法流程步骤1 初始化参数。生成已知环境中的障碍物栅格地图, 设置栅格的序号。设定种群个数m, 起始点S, 目的点T, 蚁群最大迭代次数Nmax, 栅格的行数M和列数N, 设置信息素的影响权值&#x003b1; 和启发式信息影响权值&#x003b2; 。步骤2 所有蚂蚁进行路径选择。将m只蚂蚁放到起始点, 蚂蚁k(k=1, 2, 3, …, m)从起始点S出发, 并将起始点添加到禁忌表tabuk中, 按照(3)式寻找下一个可行节点j, 若j&#x02208; allowedk , 选择下一个栅格j, 并将当前节点j添加到禁忌表tabuk中。步骤3 判断蚂蚁是否到达目的点T。若蚂蚁到达目的点T, 则记录蚂蚁走过的栅格序号和长度, 若没有到达目的点T, 则继续搜索下一节点, 直到找到目的点T为止。若某个蚂蚁k陷入停滞, 则剔除蚂蚁k。如果本代中所有蚂蚁都搜索完毕, 转到步骤4。步骤4 更新信息素。计算本代中所有蚂蚁得到的可行路径的长度, 找出本次循环中到达目的节点的局部最优和最差蚂蚁, 按照(6)式对每个栅格进行信息素更新。步骤5 判断是否达到最大的迭代次数Nmax。若算法达到最大迭代次数, 则输出当前群体中最短的路径的长度, 否则, 清空禁忌表tabuk, 令N=N+1, 转到步骤2, 继续搜索, 直到达到最大的迭代次数Nmax, 算法结束, 输当前群体中最短路径的长度。4 算法仿真使用Matlab软件对改进蚁群算法进行了仿真实验, 比较了仿真结果, 并对仿真结果进行了分析。1)用论文提出的算法和文献[11]所提出的算法进行比较, 在文献[11]中的栅格环境(20&#x000D7; 20)进行仿真实验, 设置相同的蚁群数量100, 通过仿真实验, 文献[11]和本文改进算法中路径规划图分别如图2、图4所示, 文献[11]和本文算法迭代图分别如图3、图5所示。图2Fig.2 图2 文献[11]中最优路径规划结果Fig.2 Result of optimal path planning in reference[11]图3Fig.3 图3 文献[11]中算法迭代曲线Fig.3 Iterative curve of algorithm in literature[11]图4Fig.4 图4 本文改进蚁群算法最优路径规划结果Fig.4 Result of optimal path planning based on improved algorithm in the paper图5Fig.5 图5 本文改进蚁群算法迭代曲线Fig.5 Iterative curve of improved algorithm in the paper由于论文中将目标节点引用到启发函数, 以加强算法搜索的方向性, 减少了搜索空间, 有效提高了算法的搜索效率; 自适应地调整了衰减系数, 随着迭代次数的增加衰减系数而增加, 直到达到最大值, 前期一个较小的衰减系数可以增加搜索空间, 以便找到最优解; 后期一个较大的衰减系数增加了信息素的正反馈, 使得在后期越来越多的蚂蚁倾向于经过最优路径, 可以有效地避免算法陷入局部最优解, 同时使得算法更快的收敛于全局最优解, 提高了算法搜索效率和收敛速度。因此, 从以上仿真结果可以看出, 在相同的复杂程度(20&#x000D7; 20)和相同障碍物情况下, 论文提出的算法和文献[11]中提出的算法规划最优路径长度相等, 质量(具有相同拐点)相同, 但是算法收敛速度略高于文献[11], 表明本文提出的算法具有一定的优越性。2)在不同复杂程度的静态环境中仿真实验, 实验数据分别设置为种群数量m=50, 最大迭代次数为100, &#x003c1; min=0.1, &#x003c1; max=0.5, &#x003b1; =1.1, &#x003b2; =7。实验结果如下。①在10&#x000D7; 10栅格环境中进行仿真试验, 路径规划结果如图6所示, 路径长度为13.90, 算法迭代如图7所示。图6Fig.6 图6 10&#x000D7; 10栅格环境中路径规划结果Fig.6 Result of path planning in the 10&#x000D7; 10 environment图7Fig.7 图7 10&#x000D7; 10栅格环境中改进算法迭代曲线Fig.7 Iterative curve of improved algorithm in the 10&#x000D7; 10 environment②在20&#x000D7; 20的栅格环境进行仿真试验, 路径规划结果如图8所示, 路径长度为29.21, 算法迭代如图9所示。图8Fig.8 图8 20&#x000D7; 20栅格中环境路径规划结果Fig.8 Result of path planning in the 20&#x000D7; 20 environment图9Fig.9 图9 20&#x000D7; 20栅格环境中改进算法迭代曲线Fig.9 Iterative curve of improved algorithm in the 20&#x000D7; 20 environment③在30&#x000D7; 30的栅格环境进行仿真试验, 路径规划结果如图10所示, 路径长度为43.36, 算法迭代如图11所示。图10Fig.10 图10 30&#x000D7; 30栅格环境中路径规划结果Fig.10 Result of path planning in the 30&#x000D7; 30 environment图11Fig.11 图11 30&#x000D7; 30栅格环境中改进算法迭代曲线Fig.11 Iterative curve of improved algorithm in the 30&#x000D7; 30 environment通过在不同的静态栅格环境(从简单到复杂的栅格环境)中进行多个仿真试验, 表明算法不仅在简单的环境中可以规划出最优路径, 而且在复杂的环境中也可以规划出最优路径, 并且算法迭代次数较少, 收敛速度较快, 即该算法在路径规划中适用于不同复杂程度的环境, 具有可行性和有效性。5 结束语传统蚁群算法在移动机器人路径规划问题中存在收敛速度慢、易陷入局部最优解、路径效果不理想等问题。针对这些问题, 论文对节点间的状态转移规则、启发函数的自适应调整、信息素更新方式、衰减系数的动态调整进行改进, 通过在相同的环境中和文献[11]中的算法比较, 在得到路径质量相同的情况下, 论文提出的算法可以通过较少的迭代次数找到最优路径和较快的收敛速度; 通过在不同复杂程度的环境中进行多个仿真实验, 该算法都能规划出理想的路径, 表明了该算法的可行性和有效性。通过对比试验和试验仿真, 表明了论文提出的算法具有一定的优越性。论文中主要是针对移动机器人在静态环境中全局路径规划, 没有考虑到存在有限个动态障碍物的情况, 这也是论文的不足之处及后续的研究重点。
The authors have declared that no competing interests exist.
李成兵, 郭瑞雪, 李敏.
改进蚁群算法在旅行商问题中的应用[J]. 计算机应用, 2014, 34(S1): 131-132. LI Chengbing, GUO Ruixue, LI Min.
Application of improved ant colony algorithm in travelling salesman problem[J]. Journal of Computer Applications, 2014, 34(S1): 131-132.
[本文引用:1]
张琦, 马家辰, 谢伟, 等.
基于改进蚁群算法的移动机器人路径规划[J]. 东北大学学报: 自然科学版, 2013, 34(11): 1521-1524. ZHANG Qi, MA Jiachen, XIE Wei, et al.
Improved Ant Colony Algorithm-Based Path Planning for Mobile Robot[J]. Journal of Northeastern University: Natural Science, 2013, 34(11): 1521-1524.
[本文引用:1]
RAJA P, PUGAZHENTHI S.
Optimal path planning of mobile robots: A review[J]. International Journal of Physical Sciences, 2012, 7(9): 1314-1320.
[本文引用:3]
潘桂彬, 潘丰, 刘国栋.
基于改进混合蛙跳算法的移动机器人路径规划[J]. PAN Guifeng, PAN Feng, LIU Guodong.
Path planning for mobile robots based on improved shuffled frog leaping algorithm[J].
[本文引用:1]
段俊花, 李孝安.
基于改进遗传算法的机器人路径规划[J]. 微电子学与计算机, 2005, 22(1): 70-72. DUAN Junhua, LI Xianan.
Robot Path Planning Based on Improved Genetic Algorithm[J]. Microelectronics &#x00026; Computer, 2005, 22(1): 70-72.
[本文引用:1]
聂黎明, 周永权.
基于人工鱼群算法的机器人路径规划[J]. NIE Liming, ZHOU Yongquan.
Path planning of robot based on artificial fish-swarm algorithm[J].
[本文引用:1]
王爱民, 史庆国, 吕晨亮.
机器人路径规划的神经网络算法及优化[J]. 河北工业大学学报. 1999, 28(6): 13-16. WANG Aimin, SHI Qingguo, LV Chenliang.
Path Planning and
Optimizing Algorithm of Robot Based on Neural Network[J]. Journal of Hebei University of Technology. 1999, 28(6): 13-16.
[本文引用:1]
柳长安, 鄢小虎, 刘春阳, 等,
基于改进蚁群算法的移动机器人动态路径规划方法[J]. LIU Changan, YAN Xiaohu, LIU Chunyang, et al.
Dynamic Path Planning for Mobile Robot Based on Improved Ant Colony Optimization Algorithm[J].
[本文引用:1]
张毅, 高永琪, 牛兴江.
一种改进蚁群优化算法的仿真研究[J]. 武汉理工大学报: 交通科学与工程版, 2013, 37(6): 1330-1332. ZHANG Yi, GAO Yongqi, NIU Xingjiang.
Simulation Research with an Improved Ant Colony Algotithm[J]. Journal of Wuhan University of Technology: Transportation Science &#x00026; Engineering, 2013, 37(6): 1330-1332.
[本文引用:1]
孙纯哲, 桂贵生, 韩东, 等.
基于蚁群算法的移动机器人路径规划研究与应用[J]. 合肥工业大学: 自然科学版, 2006, 29(10): 1208-1211. SUN Guizhe, GUI Guisheng, HAN Dong, et al.
Algorithm for mobile robot path planning based on the ant colony algorithm and
its application[J]. Journal of Hefei University of Technology: Natural Science Edition, 2006, 29(10): 1208-1211.
[本文引用:1]
万晓凤, 胡伟, 方武义, 等.
基于改进蚁群算法的机器人路径规划研究[J]. WANG Xiaofeng, HU Wei, FANG Wuyi, et al.
Research on path planning of robot based on improved ant colony algorithm[J].
[本文引用:1]
刘道华, 熊炎, 李为华, 等.
蚁群参数自适应调整的优化设计[J]. 计算机应用研究, 2011, 28(3): 905-908. LIU Daohua, XIONG Yan, LI Weihua, et al.
Ant Colony optimization with self-adaptive parameter adjusting[J]. Application Research of Computers, 2011, 28(3): 905-908.
[本文引用:1]
YIN L, YIN Y X, LIN C J.
A new potential field method for mobile robot path planning in the dynamic environments[J].
[本文引用:1]
WANG Y T, LI J J. A route planning optimization model based on improved ant colony algorithm[C]//IEEE. 2009 Eigth IEEE/ACIS International Conference on Computer and
Information Science. ShangHai: IEEE Press, 2009: 82-86.
[本文引用:1]
... 移动机器人路径规划是指移动机器人在有障碍物的环境中,找到一条从起始点到目的点最优的无碰路径[1,2]
... 移动机器人路径规划是指移动机器人在有障碍物的环境中,找到一条从起始点到目的点最优的无碰路径[1,2]
... 近年来,在移动机器人路径规划方法中,国内外专家学者提出了许多仿生智能优化算法[3],如:遗传[4]、人工鱼群[5]、蛙跳[6]、神经网络[7]以及蚁群[8]等算法 ...
... 2 基于改进蚁群算法的路径规化研究表明蚂蚁会在经过的路径上会留下信息素,并且可以在一定范围内感知信息素进而引导自己的运动,因此,蚁群会表现出一种正反馈现象:越多的蚂蚁经过一条路径,就会在这条路径上释放越多的信息素,后面的蚂蚁选择这条路径的概率就越大,蚂蚁之间就是通过这种信息素的交流来选择路径,进而找到食物源[3] ...
... 3 改进信息素更新方式在传统的蚁群算法中,最差蚂蚁的信息素经过正反馈之后可能导致算法搜索陷入局部最优解,为了避免这个问题,论文借用狼群法则对信息素进行更新,在一次循环中,找到经过局部最优的路径和局部最差路径的蚂蚁,分别增加和减少释放信息素浓度的量[3],各条路径按照(6)-(8)式进行信息素浓度更新 ...
潘桂彬, 潘丰, 刘国栋.
基于改进混合蛙跳算法的移动机器人路径规划[J]. PAN Guifeng, PAN Feng, LIU Guodong.
Path planning for mobile robots based on improved shuffled frog leaping algorithm[J].
To solve the problems that the Shuffled Frog Leaping Algorithm (SFLA) path planning is easy to fall into local optima and optimization effect is poor, an improved SFLA was proposed. Euclidean distance and the best frog of the population were added into the original algorithm?s update strategy, and a method to generate a new individual with a adjustable control parameter instead of the original random update operation was proposed. This paper firstly transformed the problem of robot path planning into a minimization one, and then defined the fitness of a frog based on the position of target and obstacles in the environment. The robot selected and reached the position of the globally best frog in each iteration successively to realize the optimal path planning. In the mobile robot?s simulation experiment, compared with other algorithms, the successes? number of the improved algorithm was increased from 82 to 98, and the path planning time was decreased from 9.7s to 5.3s. The experimental results show that the improved algorithm has stronger security and better optimization performance.
School of Internet of Things Engineering, Jiangnan University, Wuxi Jiangsu 214122, China
针对混合蛙跳算法(SFLA)进行路径规划时易陷入局部最优且寻优效果较差的问题，提出一种改进的SFLA。改进算法在原算法的更新策略中引入欧氏距离和种群最优蛙，并提出一种带可调控制参数的产生新个体的方法代替原本的随机更新操作。把路径规划问题转换为最小化问题，基于环境中目标和障碍物的位置定义青蛙的适应度，机器人依次到达每次迭代中最好蛙的位置，从而实现最优路径规划。移动机器人仿真实验中，与其他算法相比，改进后的算法成功次数由82提高到98，规划时间由9.7s减少到5.3s。实验结果表明，改进算法具有较强的安全性和寻优性能。
... 近年来,在移动机器人路径规划方法中,国内外专家学者提出了许多仿生智能优化算法[3],如:遗传[4]、人工鱼群[5]、蛙跳[6]、神经网络[7]以及蚁群[8]等算法 ...
... 近年来,在移动机器人路径规划方法中,国内外专家学者提出了许多仿生智能优化算法[3],如:遗传[4]、人工鱼群[5]、蛙跳[6]、神经网络[7]以及蚁群[8]等算法 ...
聂黎明, 周永权.
基于人工鱼群算法的机器人路径规划[J]. NIE Liming, ZHOU Yongquan.
Path planning of robot based on artificial fish-swarm algorithm[J].
In this paper，the link graph is used to describe the working space of the mobile robot and the Dijkstra algorithm is used to obtain a sub-optimal collision-free path from the start point to the goal point in the graph，then adopt the AFSA（Artificial Fish-Swarm Algorithm） to adjust and optimize the location of the sub-optimal path so as to generate the global optimal path by adjusting the points of the path.A calculation for an example has been done and the computation result shows that this method has some advantages as convergence and computation precision.
College of Mathematics and Computer Science，Guangxi University for Nationalities，Nanning 530006，China
首先采用链接图建立机器人工作空间模型，用Dijkstra算法求得链接图最短路径；然后使用人工鱼群算法对此路径进行优化，最终得到全局最优路径。以一个路径为例，进行了实际编程计算，结果表明，基于人工鱼群算法的机器人路径规划方法，具有较快的收敛性和较高的计算精度。
... 近年来,在移动机器人路径规划方法中,国内外专家学者提出了许多仿生智能优化算法[3],如:遗传[4]、人工鱼群[5]、蛙跳[6]、神经网络[7]以及蚁群[8]等算法 ...
... 近年来,在移动机器人路径规划方法中,国内外专家学者提出了许多仿生智能优化算法[3],如:遗传[4]、人工鱼群[5]、蛙跳[6]、神经网络[7]以及蚁群[8]等算法 ...
柳长安, 鄢小虎, 刘春阳, 等,
基于改进蚁群算法的移动机器人动态路径规划方法[J]. LIU Changan, YAN Xiaohu, LIU Chunyang, et al.
Dynamic Path Planning for Mobile Robot Based on Improved Ant Colony Optimization Algorithm[J].
The dynamic path planning for mobile robot based on improved ant colony optimization algorithm is presented.Firstly,to increase the convergence speed,the heuristic function modified adaptively according to the target point is proposed.To avoid the local optimum,the rule updating the pheromone based on the assignment rule of wolf colony is proposed.Secondly,to optimize the performance of the improved ant colony,the important parameters of the improved ant colony optimization algorithm are optimized by the particle swarm optimization.Finally,the dynamic path planning for mobile robot based on improved ant colony optimization algorithm is implemented and the simulation experiments are finished.From the results,it can see that the dynamic path planning method is viable and efficient.
School of Control and Computer Engineering,North China Electric Power University,Beijing 102206,China
本文提出了基于改进蚁群算法的移动机器人动态路径规划方法.首先针对蚁群算法收敛速度慢,容易陷入局部最优的缺点,提出了根据目标点自适应调整启发函数,提高算法的收敛速度;借鉴狼群分配原则对信息素进行更新,避免搜索陷入局部最优.其次为了优化改进蚁群算法的性能,提出用粒子群算法对改进蚁群算法的重要参数进行优化选择.最后实现了基于改进蚁群算法的移动机器人动态路径规划并完成了仿真实验,实验结果证明了该方法的可行性和有效性.
... 近年来,在移动机器人路径规划方法中,国内外专家学者提出了许多仿生智能优化算法[3],如:遗传[4]、人工鱼群[5]、蛙跳[6]、神经网络[7]以及蚁群[8]等算法 ...
万晓凤, 胡伟, 方武义, 等.
基于改进蚁群算法的机器人路径规划研究[J]. WANG Xiaofeng, HU Wei, FANG Wuyi, et al.
Research on path planning of robot based on improved ant colony algorithm[J].
The basic ant colony algorithm applied to robot path planning in the two-dimensional static environment has problems of long search time, inefficiency and easy to fall into local optimization and so on. It makes improvements on the algorithm for these problems. It uses different expectation mechanism, updates the pheromone by taking evaporation coefficient adaptive approach, and joins the inflection point parameter as one evaluation criteria of the path. Simulation of the two algorithms shows the improved ant colony algorithm is stronger of searching ability and more efficient than the basic ant colony algorithm and gets a shorter path. The results show that the improved algorithm improves the efficiency of the algorithm and inhibits algorithm into local optimum and achieves search of robot&s optimal path. Robot can avoid obstacles to reach the target point safely and quickly.
College of Information Engineering, Nanchang University, Nanchang 330031, China
在二维静态环境下的机器人路径规划中，采用基本蚁群算法寻优存在搜索时间较长、效率较低、容易陷入局部最优等问题。针对这些问题对基本蚁群算法进行改进，改进的蚁群算法使用不同的期望值机制，采用挥发系数自适应方式更新信息激素，并加入拐点参数作为路径的评价标准之一。对这两种算法进行仿真分析，可得改进后的蚁群算法比基本蚁群算法搜索能力更强，算法效率更高，所寻路径更短。结果表明，该改进算法提高了算法效率，抑制了算法陷入局部最优并实现了机器人最优路径搜索，使机器人可以快速地避开障碍物安全到达目标点。
基于改进蚁群算法的移动机器人路径规划
[朱颢东, 孙振, 吴迪, 申圳]}