基于改进蚁群算法的移动机器人路径规划

2010—08 29(8) 岳 工 自动 化 Ordnance Industry Automation ·69· doi：10．3969~．issn．1006—1576．2010．08．022 基于改进蚁群算法的移动机器人路径规划 温如春 ，汤青波，杨国亮 (江西理工大学 机电学 院，江西 赣州 341000) 摘要：针对移动机器人路径规划中传统蚁群算法容易出现停滞现象、收敛较慢的问题进行研究。采用局部更新 规则和自适应，构建了移动机器人在迷宫中的动态路径规划模型。通过计算机仿真和电脑鼠机器人实际行走实 验表明，在场地复杂的情况下，该算法可以有效地规划出全局最优路径，加快规划速度，满足实际应用需要。 关键词：蚁群算法；路径规划；移动机器人；迷宫 中图分类号 ：TP302；TP242 文献标识码 ：A M obile Robot’S Path Planning Based on Improved Ant Colony Algorithm Wen Ruchun，Tang Qingbo，Yang Guoliang (School of Mechanical& Engineering，Jiangxi University of Science&Technology，Ganzhou 341000，China) Abstract：Aiming at the problem that the traditional ant colony algorithm for mobile robot path planning easier to stagnation behavior and slower convergence．Local update rule and self-adaptive method construction of dynamic path planning of mobile robot in the maze model are made．Computer simulation and micro·mouse walking robot actual experiments show that the optimal path planning algorithms can effectively work under any complicated situation． Keywords：ant colony algorithm；path planning；mobile robot；maze O 引言 IEEE 国际电工和 电子工程学会 电脑 鼠走迷宫 竞赛⋯的 目的是制作一个微型机器人，使电脑 鼠【1】 能在最短的时间内穿越迷宫到达终点。在 20世纪 90年代，意大利学者 M．Dorigo等人通过模拟 自然 界蚂蚁寻径的行为，提出了一种全新的模拟进化算 法【2 】一人工蚁群算法。该算法具有并行计算、鲁棒 性等特点。但传统蚁群算法也存在易出现停滞现象、 收敛缓慢等缺陷，故对其进行改进，提出一种适用 于栅格式路径规划问题的新型启发式算法。 l 移动机器人动态路径规划算法 栅格法l4j是对平面移动机器人运动路径规划的 一 个抽象模型，是 目前研究最广泛的路径规划方法 之一。栅格法由M．B．Metea提出，用于解决分等级 地形的自动化路径规划问题。为了实现机器人的动 态路径规划，模型首先是要机器人从给定栅格图的 起点，绕过障碍，找出通往终点的路线：要求极小 化该条路线所经过的栅格数。 2 改进蚁群算法原理在迷宫问题中的实现 2．1 迷宫最短路径 路径规划的任务是为机器人规划一条从起始点 到 目标点的无碰撞路径。一般来讲，路径规划方法 大致可分为传统方法和智能方法 2类。传统方法有 可视图法、栅格法、人工势场法等【5】，这些算法在 搜索效率及路径优化方面有待改善。智能路径规划 方法包括遗传算法、模糊方法和蚁群算法等【5】。智 能算法可提高移动机器人路径规划的避障精度，加 快规划速度。从减少算法时空消耗的角度出发，作 者引入蚁群系统的思想求解栅格式路径规划问题。 迷宫由 256个 18 cm×18 cm大小的方格组成， 迷宫的规模为 l6行×16列。在迷宫区域内，对位 于节点(f，．，)的蚂蚁 (其中(1 f≤16；1≤J≤16))，下 次的可能目标是节点 ， )：即(f一1， )、(f，_『+1)、 ( +1，J)和( ， 一1)，代表着蚂蚁每次只能按图1的 “向左 ”，“向上”，“向右”和 “向下”4个方向移 动。迷宫最短路径问题的目标函数可表示为： l=旦 r—————————：——————————一 L 4(xf一 f一1) +(yf—Yf一1) (1) i=2 其中：( ，yf)为路径点坐标信息，n 为路径点 数目，L为路径长度。 图1 位于节点( ， )的蚂蚁四方位移动图 收稿日期：2010—02—18；修回日期：2010—04—16 基金项目：2009年度江西省教育厅科技项目立项资助 (项 目批准号：GJJ09253) 作者简介：温如春 (1972一)，女，副教授，从事嵌入式系统与智能控制方面的研究。 ·70· 兵工 自动化 第 29卷 2．2 蚁群算法模型 设 m为蚁群中蚂蚁的数量。在栅格地图初始化 时，赋予每个节点相等 的信息素 =C (C为常 数)，以尽量扩大蚂蚁最初的搜索范围。每只蚂蚁在 运动时，根据各条路径上的信息量决定转移方向。 例如，对位于节点(f，．，)处的蚂蚁k，选择下一 个可行节点( ，1，)，构造决断概率函数如式 (2)。 r a ／ a ． ： { ( ) 咄 可行节点 (2) 【 0 ；其它 其中， 为在t时刻蚂蚁由位置(i，J)转移 到 ， )的转移概率； 为信息素的重要程度，且 >0；allowed 为蚂蚁 k当前可到达的点集，其 元素为allowed(i，．7)中的点除去蚂蚁 k已走过的 点； 为点(f，．7)与点 ，V)之间的。信息素，随 着算法的运行将会逐渐改变。 2．3 改进蚁群算法在迷宫可行解中的构造 为使每只蚂蚁能以尽可能高的概率生成可行 解，采用两组数量相等的蚁群分别从迷宫的起点和 终点同时出发，每只蚂蚁按式 (2)确定的概率在迷 宫中漫游。为避免生成无效路径，为蚂蚁 k分配一 张禁忌表，记录蚂蚁k当前走过的路径点集 ，以避 免选择已经走过的点。在移动过程，对任意一只蚂 蚁定义 3种生命周期：1)蚂蚁走进死角，除非沿原 路返回一步或多步，不能再朝前移动，否则将该蚂 蚁从系统中删除：2)蚂蚁到达另一组蚁群的出发 点，此时该蚂蚁走过的路径为一条可行路径：3)蚂 蚁碰到另一组的某只蚂蚁。如果这 2只蚂蚁所经过 的点没有重复 (相遇点除外 )，则将 2只蚂蚁所经过 的路径相连以构成迷宫的一条可行路径。因此，从 蚁群的产生到生命周期的结束，会有部分蚂蚁找到 问题的可行解，但可行解的数量小于蚁群数的一半。 2．4 信息素的更新 随着时间的推移，前一代蚂蚁留下的信息素逐 渐消失。经过Ⅳ个时段，蚂蚁完成一次搜索，当蚂 蚁由节点( ， )转移到节点 ， )时，信息素根据式 (3)进行调整。 f _， (g+1)=(1一p)xr,j_÷ (f)+ rfJ-÷ (f)P∈(0，1) J (3) fAr = 其中， 为调节信息素挥发速度的参数；g为 蚂蚁繁殖的代数： 是蚂蚁在本次循环中留在节 点( ，7)上的信息量；m为蚂蚁的数量。 依据比赛规则，机器人寻找的是耗时最少的最 优路径而不是最短路径。但是在算法中并不适于直 接考虑 “转弯”事件，因此作者采用将转弯耗费的 事件折算到路程上，最终表现在路径的信息素上。 当k只蚂蚁完成一条搜索路径时，按照局部更新规 则对信息素进行更新，更新模块如式 (4)。 △ ：{Q／( + ∑ m)；蚂蚁在行进的路径上 【 u ；其它 (4) 其中：Q为常量； 为第k只蚂蚁在本次循环 中搜索到的路径长度 ；K1(K1 O)为其权重系数； 表示在这条路径上的转弯次数。 由于迷宫环境复杂，问题规模 比较大。信息量 挥发系数 过大，算法的全局搜索能力会降低；但 P过小，将会降低算法的收敛速度。算法改进的方 面是：设 初始值为 1；当算法求得的最优值在 N 次循环内没有明显改进时， 改变为 (P的最 小值)，用于防止P过小而降低算法的收敛速度。 ，’ 一 J0．95p如果0．95p P i (5) 【P 其它 3 结束语 机器人实际行走试验表明：当它遇到障碍时， 能在不到 0．5 S的时间内迅速规划出新的路径。新算 法解决了蚂蚁在搜索过程中过早陷入局部最优解的 问题，扩大了蚂蚁的搜索空间，提高避障精度，满 足了实际应用的需要 。 参考文献： 『11 http：／／www．eece．maine．edu／sc20O6／2006MicromouseRules pdf 【2】Dorigo M，Caro G．D．Ant Colony Optimization：a New Meta．heuristic[C1．Proceeding of the 1999 Congress on EvOlutionarv Computation。1999：1470—1477． r31 Dorigo M， Manieazo V， A Colorni． Atit System： Optimization by a Colony of Cooperating Agents．IEEE Trans on Systems， M an， and Cybernetics—Part B： Cybernetics，1996，26(1)：1—23． 【4】YinYee M，Jaco V．A grid—based proposal for efficient global localization of mobile robots[C1．U．K． Cambridge，CB2 1PZ，ICASSP，2005(5)：217—220． [5】梁毓明，徐立鸿．移动机器人路径规划技术的研究现状 与发展趋势[J】．机电一体化，2009(3)：35-38．