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

刘学芳, 曾国辉, 刘 瑾

(上海工程技术大学 电子电气工程学院,上海 201620)

0 引 言

路径规划是移动机器人研究领域的一个重要技术,是在有障碍物的空间中,按照一定标准规划一条从起点到终点的最优或者近似最优的无碰撞路径[1,2]。机器人的路径规划主要有全局路径规划和局部路径规划[3～7]。

针对机器人路径规划,国内外学者进行了不少研究。文献[8]提出了一种改进的动态局部搜索蚁群优化算法(dynamic local search ant colony optimization algorithm,DLACA),不同路径使用不同信息素更新策略,提高了解的质量。文献[9]提出了根据目标点自适应调整启发函数,借鉴狼群分配机制对信息素进行更新,结合粒子群算法优化蚁群算法参数的改进蚁群算法路径规划，但该方法搜索时间较长,容易陷入局部最优。文献[10]利用粒子群算法个体加权平均值并加入惯性权重提出了一种改进粒子群路径优化算法,但该算法搜索到最优解时迭代次数较多,搜索时间较长。

在解决路径规划上,蚁群算法具有易于与其他算法融合、速度快、精度高、快速找到拟最优解[12]等优点,与其他算法相比具有显著优势,但容易陷入局部最优。人工势场法是一种虚拟力算法[13]，它模仿势力场中引力和斥力对机器人的作用,如将障碍物视为斥力,最终目标点视为引力,建立函数进行机器人路径规划，方法具有计算量小,结构简单,便于控制[14],可以规划出一条平滑的轨迹路线等优点。

将蚁群算法和人工势场法两种方法进行融合,提出一种结合人工势场和蚁群算法的移动机器人路径规划。提高了算法全局搜索能力,加快收敛速度。

1 环境建模

1.1 栅格法

图1 环境模型与人工势场下机器人受力分析

1.2 人工势场法

人工势场法是一种虚拟力方法,其基本思想是将被控对象在环境中的运动虚拟为在受力场中的运动,环境中的障碍物对机器人的运动产生斥力,目标对机器人产生引力,引力和斥力构成的合力控制机器人的运动方向。

假设机器人当前所处位置为P,如图1(b)所示,机器人受到障碍物的排斥力(Frep)和目标的吸引力(Katt),其矢量合力(Ftot)为机器人运动方向

(1)

(2)

Ftot(P)=Fatt(P)+Frep(P)

(3)

(4)

2 传统蚁群算法

(5)

式中α为信息素启发因子,反映了蚂蚁在寻找食物过程中残留在路径上的信息浓度对当前蚂蚁所起的作用,其值越大,表示当前蚂蚁选择此路的可行性越大；β为启发函数因子,表示能见度的重要性。allowedk为蚂蚁k下一步可以选择的路径的数组。τij(t)为节点i和j之间的信息素浓度,ηij(t)为蚂蚁k从节点i到节点j的启发信息

(6)

在搜索的初始阶段,蚁群进行盲目搜索。当所有蚂蚁完成一次寻找食物时,对各路径上的信息素更新

(7)

式中ρ为信息素挥发因子,其数值通常为0<ρ<1,m为蚁群数量,τk为第k只蚂蚁在当前迭代过程中留下的信息素,可表示为

(8)

式中Q为常量,为蚂蚁信息素强度,在一定程度上影响算法收敛速度；Lk为蚂蚁k在本次循环中所走过的路径总长度。

3 改进蚁群算法

3.1 激励函数

为了使机器人更倾向于选择障碍物包含较少的区域,蚂蚁k从i栅格转移到j栅格,定义激励函数

(9)

因此,改进蚁群算法的状态转移概率为

(10)

式中γ为激励函数影响因子。

3.2 信息素的分配机制改进

传统蚁群算法中,当所有蚂蚁走完路程后才再更新信息素。信息素的增加由所有蚂蚁上一轮所走的路径决定。这种信息素更新机制中,所有蚂蚁散发的信息素无论好坏都参与到信息素更新中。实际上,路径较长的蚂蚁所分泌的信息素对蚁群起到误导作用,导致算法收敛速度较慢。

改进的信息素分配机制将增强优秀蚂蚁的影响,降低不好的蚂蚁影响程度。具体思路如下：当所有蚂蚁寻找到食物以后,对所有蚂蚁走过的路径长度按照从小到大的顺序重新排序。对优秀蚂蚁在其所走路径上的信息量更新,对中等路径长度的信息素量减少比例更新,对陷入局部最优解的蚂蚁路径取消更新信息素,并将路径长度设为无穷大,更新方式如下

(11)

(12)

3.3 改进蚁群算法路径规划流程

图2 改进蚁群算法路径规划流程

4 仿真分析

为了验证本文提出改进蚁群算法的有效性和优越性,在Python3.6环境下进行机器人路径规划算法仿真。机器人初始位置为(0,0),目标点位置为(19,19)蚁群算法参数选取：α=1.1,信息素影响因子；β=12,启发式影响因子；γ=0.2,激励函数影响因子；ρ=0.5,信息素蒸发系数；m=20,蚂蚁数量。算法的最大迭代次数设置为100次。仿真结果如图3～图4。

图3和图4为改进蚁群算法和传统蚁群算法仿真路线,以及二种算法最短路径长度与迭代次数变化曲线。本文算法和传统蚁群算法的最短路径长度分别为27.455和34.870,迭代次数分别为45和18。可以看出：本文算法在路径长度和迭代次数上具有明显优势。从图4收敛速度明显加快,搜索全局路径长度明显减少。

图3 二种算法仿真结果

图4 二种算法收敛曲线

5 结 论

本文提出基于人工势场环境下改进蚁群算法用于解决机器人路劲规划问题。利用人工势场建立启发信息强度,可以有效降低蚁群在起始阶段搜索的盲目性和随机性。引入激励函数,有助于增强路径平滑性,降低搜索过程的死锁现象；改进信息素的更新机制,增强了优秀蚂蚁信息素影响程度,降低了路径较长蚂蚁对全局搜索的阻碍。仿真结果表明:本文提出的改进蚁群算法较传统蚁群算法能迅速找到全局最优解,提高了算法全局搜索能力。