基于蚁群算法路径规划的收敛性分析.pdf

《基于蚁群算法路径规划的收敛性分析.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、机械设计与制造第8期l64MachineryDesign&Manufacture2010年8月文章编号：1001—3997(2010)08—0164—02基于蚁群算法路径规划的收敛性分析半刘军刘广瑞(郑州大学机械工程学院，郑州450001)PathplanningofmobilerobotbasedonimprovedantcolonyalgorithmLIUJun，LIUGuang-rui(SchoolofMechanicalEngineeringZhengzhouUniversity，Zhengzhou450001，

2、China)中图分类号：TH16，TP24文献标识码：A1引言短路径到达已知的目标位置。设机器人在二维平面上的凸多边形有限区域内运动。该区域移动机器人的路径规划是按照某一J生能指标搜索一条从起内分布着有限个不同大小的障碍物。在该区域内建立直角坐标点到目标点的最优或次最优的无碰撞路径。机器人路径规划的研系。假设机器人以一定的步长R运动，则轴和Y轴分别以R为究始于70年代，目前国内外对这一问题的研究仍然十分活跃。根单位来划分栅格。栅格大小以机器人能在其内自由运动为限，每据环境信息掌握程度，路径规划可分为：环境信息完全已知的全

3、局路径规划；环境信息不完全或未知的局部路径规划。行的栅格数=一；每列的栅格数N,=y~／R。如果区域为不规则形状，则可在边界处补以障碍栅格，将其补为正方形或者长方受自然界中真实蚁群集体行为的启发，意大利学者Dorigo于形。其中障碍物占一个或多个栅格，若不满一个栅格，以一个栅格1991年首次系统地提出了一种基于蚂蚁种群的新型优化算法一蚁计算。每个栅格都有对应的坐标和序列号，而且序列号与坐标之群算法(ACO)，目前人们对蚁群算法的研究已经由当初单一的旅行商问题(travelingsalesmanproblem，P)领域渗透

4、到了多个应用领间一一对应，图给出了栅格坐标与序列号之间关系的示意图。2_2栅格标识可采用下述两种方法域，由解决一维静态优化问题发展到解决多维动态组合优化问题，(1)直角坐标法。如图1所示，以栅格阵左上角为坐标原点，由离散域范围内的研究逐渐拓展到了连续域范围内的研究。针对基水平向右为轴正方向，竖直向下为确正方向，每一栅格区间对本蚁群算法存在收敛速度慢，计算周期长，易死锁等问题，本文在算应坐标轴上的一个单位长度。任一栅格均可用直角坐标(，’，)唯法上进行了改进，通过多次仿真试验证明，改进后的算法增加了新路径的生成甚陉和提高了

5、路径生成速度，从而能够陕速得到较优解。一标识。0123456782蚁群算法的基本原理0~2314臁151617182．1环境建模为实现预定的路径规划算法，在建模时作如下假设：(1)机器人工作空间为二维结构化空间记为RS，并且障碍物位置、大小已知，且在机器人运动过程中，障碍物的位置、大小均不发生变化。(2)机器人的运动空间中分布着有限个已知的大小不同的障碍物，障碍物可以由多个栅格描述，忽略障碍物的高度信息。路径规划的目的是使机器人能够由起始位置出发安全避碰地沿一条最图1栅格坐标与序号的关系★来稿日期：2009—10—09★

6、基金项目：公益性行业(农业)科研专项(nyhyzx07-O05—25)第8期刘军等：基于蚁群算法路径规划的收敛性分析165(2)序号法。如图1所示，按从左到右，从上到下的顺序，从栅ATi=∑△格阵左上角第一个栅格开始，给每一个栅格一个序号n(从1开=1始计)，则序号n与栅格块一一对应。△：{【ijptimalP砒h(5)3改进算法的算法描述0else机器人路径规划的蚁群算法可简单描述为：将m只蚂蚁放式中：Q一常系数；Il—路程的长度；—全局信息挥发系数。如果：岛，根据禁忌表中生成的路径一分两种情况：若在出发点，每只蚂蚁以

7、当前节点为中心，按拟定的策略选择下一个节点，按信息素更新策略更新路径的信息素。当第一只蚂一为蚁群生成的第一条路径时，将三一置人存储当前最优路径的矩阵LOPT[-k1中，得到一，再对一按(4)进行信息素更新。若蚁k到达目标节点，意味着k到达目标点用时最少，所以在本轮寻优中k得到的路径为最优，故对k所得路径进行全局信息一不是蚁群生成的第一条路径时，此时若lL—l

8、为O)。若为目标继续寻优。若蚂蚁得到新的路径，则将新路径与当前最优不成立，n直接加1。最后，清空k的禁忌表tabuk，并更新g，置路径进行比较，若新路径优于当前最优路径则用新路径更新当前最优路径，并对新的当前最优路径进行全局信息更新进行比较若g：=g鲁，岛昌∈({ge咖，或＆}一{1g：})。o(5)令循环次数N=N