《基于栅格模型机器人路径规划的改进蚁群算法》由会员分享，可在线阅读，更多相关《基于栅格模型机器人路径规划的改进蚁群算法（4页珍藏版）》请在金锄头文库上搜索。
1、第 卷第 期 计算机应用与软件 年 月 基于栅格模型机器人路径规划的改进蚁群算法王沛栋 冯祖洪（ 北方民族大学计算机科学与工程学院 宁夏 银川 ）收稿日期： 。宁夏自然科学基金项目（ ） 。王沛栋，硕士生， 主研领域： 人工智能， 计算机网络。摘 要 提出了一种静态环境下机器人路径规划的改进蚁群算法。该算法使用栅格法对机器人的工作空间进行建模， 通过模拟蚂蚁的觅食行为， 采用折返的迭代方式对目标进行搜索； 在搜索过程中， 以移动方向一定范围内最大信息素和目标引导函数作为启发式因子； 此外， 根据蚁群算法处理本问题时信息素散播的特点， 重构了信息素的更新策略和散播方式。仿真试验结果表明， 改进措
2、施使最优路径的寻找快速而高效， 即使在障碍物非常复杂的环境下， 算法也能迅速地规划出一条最优路径。关键词 机器人 蚁群算法 路径规划 （ ， ， ， ， ） ， ， ， 引 言机器人路径规划是机器人学研究领域中的一个重要部分，其任务是在具有障碍物的环境内， 按照一定的评价标准（ 工作代价最小、 行走路线最短等） 寻找一条从起始状态（ 包括位置和姿态） 到目标状态（ 位置和姿态） 与障碍物无碰的最短路径。栅格法是对平面移动机器人运动环境的一个抽象模型。它把机器人的工作空间分割成规则而均匀的栅格， 每个栅格可为两种状态， 它们表示该栅格处是否存在障碍， 没有障碍的栅格称为自由栅格， 否则为障碍栅格
3、。在机器人移动的过程中， 栅格的尺寸和位置不变， 并且栅格的尺寸通常与机器人的移动步长及机器人的尺寸一致。栅格法直观且建模比较容易， 因此得到了广泛的应用。基于栅格模型求解有许多方法， 例如： 随机树算法、 遗传算法、 神经网络等。这些方法几乎都存在搜索空间大、算法复杂、 效率不高等问题， 特别是当障碍物的数目增加或地形障碍物趋于复杂时， 这些路径规划算法的复杂度将会大大增加。文献 提出了一种基于栅格法的机器人路径规划的蚁群算法， 该算法通过使用点到目标点的距离和栅格使用的次数作为启发式信息， 增强了搜索的指导性， 但是由于路径上的信息素变化较慢， 使蚂蚁在路径选择时的目的性不突出， 所以收敛
4、时间较长。文献 使用一种快速随机树算法来解决该问题， 它以机器人的起始点作为根节点， 向目标点方向进行延伸， 每次选取距离目标点最近的叶子节点进行扩展。这种方法简单、 收敛速度快。但是它缺乏对整体环境的搜索， 而且扩展原则单一， 容易使算法陷入“ 死锁” 状态。本文提出一种基于栅格模型的改进蚁群优化算法， 通过模拟蚂蚁的觅食行为， 采用折返的迭代方式对目标进行搜索， 在搜索过程中， 以移动方向上一定范围内最大信息素和目标引导函数作为启发式因子， 此外， 利用蚁群算法处理本问题时信息素散播的特点， 重构了信息素的更新策略和散播方式。试验结果表明， 本文提出的算法与其它优化算法相比，在解的质量和收
5、敛速度上都显示出了良好的性能。 问题描述及数学模型基于栅格模型的机器人路径问题可以表示为一个约束优化问题， 它可简单地描述如下：在一平面栅格图中， 存在栅格和一机器人。栅格分为两种，障碍栅格和自由栅格。机器人具有一定的感知和记忆能力， 能够感知当前位置邻接范围内的栅格信息。给定起始栅格和目标栅格， 要求机器人从起始栅格出发， 在整个栅格图未知的条件 计算机应用与软件 年下， 绕过障碍栅格， 找出一条通往目标栅格的最短路径。假设栅格图有 行 列。初始栅格为（ ， ） ， 目标栅格 为（ ， ） 。用 表示图中栅格的集合； 表示栅格 （ ， ） 的信息； 表示当机器人处于栅格（ ， ） 时， 下一
6、步可选 择栅格的集合； （ ） （ ， ） 表示从栅格（ ， ） 出发， 经第 步后所能选择的栅格； 表示问题所有可行解的集合； 表示问题的最优解， 则机器人路径问题即如下的优化问题： ， （ ） （ ） （ ） （ ， ） ， （ ） （ ， ） ， ， （ ） （ ， ） （ ） （ ， ） 且 （ ） （ ， ）（ ， ） ， ， ， ， （ ） （ ， ） ， （ ） 栅格（ ， ）为障碍栅格， （ ， ） 栅格（ ， ）为自由栅格， （ ， ）（ ）设（ ， ） （ ） （ ， ） （ ） （ ， ）（ ， ） ， （ ， ） 且 （ ） （ ， ） ， （ ， ） ， （ ， ）
7、， （ ， ） （ ， ） （ ） 算法设计 算法改进及说明 新的迭代方式蚁群算法求解其它问题时， 每次迭代所有蚂蚁都会得到问题的解（ 无论优劣） 。求解机器人路径规划问题时， 由于蚂蚁对路径选择不同， 所以每次迭代所有蚂蚁不可能同时到达目标点。如果每次迭代要求所有的蚂蚁都到达目标点后再开始新一轮的迭代， 那会浪费大量的时间， 不利于最优解快速收敛； 如果每次迭代只要一只（ 或一些） 蚂蚁到达目标点， 就停止其他蚂蚁的搜索， 这样不利于对新路径的探索。受真实蚂蚁觅食行为的启发，本文算法采用一种折返的迭代方式， 它将迭代分别应用于每只蚂蚁身上。一只蚂蚁从起始点出发， 到达目标点后， 再从目标点返
8、回， 当回到起始点时， 就完成一次迭代， 迭代计数器加 。这种方式使蚂蚁从两个方向对最优路径进行搜索， 能够充分发挥每只蚂蚁的搜索能力， 增加了搜索的多样性， 加快了寻优的速度。 信息素更新和散播策略针对问题和迭代方式的特点， 算法从三个方面对信息素进行改进：（ ）算法使用两种信息素对蚂蚁进行引导， 一种是关于目标点的信息素； 另一种是关于起始点的信息素， 它们分别引导蚂蚁向目标点和起始点运动。（ ）蚁群算法求解栅格模型机器人路径规划问题时， 由于路径长度是以走过的栅格来计算的， 所以从同一点出发的蚂蚁每行走一步所释放的信息素是等量的（ ， 是蚂蚁目前已行走的距离） ， 并且会随着探索的深入而逐渐减小， 经过同一栅格的蚂蚁， 行走的路径越短， 所释放的信息素越大。利用这个特点， 信息素更新采用一种比较更新的方式， 假设某一栅格（ ， ）在 时刻有 只蚂蚁经过， 那么它 时刻的信息素应为公式（ ） 所示： （ ） （ ） （ ） （ ） （ ）（
