改进蚁群算法在机器人路径规划中的应用

改进蚁群算法在机器人路径规划中的应用

裴振兵

河南安彩高科股份有限公司 河南省 安阳市 455000

摘 要：本文针对蚁群算法在构造解的过程中,收敛速度慢且容易陷入局部最优,提出了在蚁群搜索路径过程中,自适应调整α(信息素启发式因子),β(期望启发式因子)的值.通过建立α(信息素启发式因子),β(期望启发式因子)的互锁关系,使其达到一种平衡或近似平衡,从而扩大蚁群算法的搜索空间,使蚁群算法跳离局部最优.其次利用栅格法,进行静态已知环境建模,将改进的蚁群算法应用到机器人的路径规划,并完成了仿真实验,实验结果证明了该方法的可行性和有效性.

关 键 词: 改进蚁群算法,移动机器人,路径规划,栅格法

中图分类号：TP 文献标识码：A

1 引 言

路径规划是移动机器人领域中一个重要的研究方向，它是指机器人按照某一性能指标(如行走路线最短，行走时间最短等)在具有障碍物的环境下寻找一条从起始点到目标点无碰撞的最优路径^[1], 蚁群搜索食物的过程与机器人路径规划有着惊人的相似，都是寻找一条从起始点到终点的避障的最优路径，所以将蚁群算法运用到机器人路径规划是合理的。假设信息素挥发因子 的初始值 ，则当蚁群算法求得的最优值在N次循环内没有明显改进时， 按照下式作自适应调整：

(1)

式中 为 的最小值，可以防止 过小降低算法的收敛速度。

本文针对传统蚁群算法在寻优过程中易出现停滞和陷入局部最优的缺陷，提出了一种在蚁群搜索路径过程中自适应调整α(信息素启发式因子),β(期望启发式因子)的值使其达到一种平衡或近似平衡的改进策略，将其运用到移动机器人的路径规划并进行仿真(利用栅格法进行建模)，验证了改进方法的可行性和有效性。

2 基本蚁群算法的数学模型

蚂蚁k(k=1，2,…，m)在运动过程中，根据各条路径上的信息量决定其转移方向。用禁忌表tabu_k(k=1，2，…，m)来记录k当前所走过的城市，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。 表示t时刻蚂蚁k由城市i转移到城市j的状态转移概率^[2]： (3)

式中， 表示t时刻在路径(i,j)上的信息素量;allowed_k={C—tabu_k}表示蚂蚁k下一步允许选择的城市;α为信息启发因子(α反映信息素积累量在指导蚁群搜索中的相对重要)，β为期望启发式因子(β反映了下个目标点的距离在指导蚁群搜索过程中的相对重要)其值越大，则该状态转移概率越接近于贪心规则; 为启发函数，其表达式如下：

(4)

式中，d_ij表示相邻两个城市之间的距离。对蚂蚁k而言，d_ij越小，则 越大， 也就越大。显然，该启发函数表示蚂蚁从城市i转移到城市j的期望程度。对蚂蚁k而言，在每只蚂蚁走完一步或者完成对所有n个城市的遍历后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存入大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。由此，t+n时刻在路径(i,j)上的信息量按如下规则进行调整^[7]:

(5)

(6)

式, 表示信息素挥发系数,则1-ρ表示信息素残留因子，为了防止信息素无限积累, 的取值范围为: ; 表示本次循环中路径(i,j)上的信息素增量，初始时刻 , 表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息量。

其中 按下式进行 (7)

3 蚁群算法的改进

由状态转移概率公式(3)可知，当 时，只是路径信息起作用，算法相当于最短路径寻优，从而有

(8)

当 时，路径信息的启发作用等于0，此时算法相当于盲目地随机搜索从而有

(9)

3.1 动态自适应调整α，β的蚁群算法

根据蚁群算法搜索情况来自适应动态调整信息启发因子α，期望启发式因子β采用关于迭代次数NC的阶梯函数 ， 来代替常数项α，β，按下式进行调整：

(10) (11)

在搜索过程中为了达到一定平衡,式中信息启发因子α,期望启发式因子β是互锁的关系,即α_i+β_i=M(其中M为一定值)。由于α、β值过大或过小,都易使蚁群的搜索过早陷入局部最优^[3]。结合其他改进算法中α、β的取值经验与分析,同时通过仿真实验分析,确定当1≤

α≤9,1≤β≤9更有利于整个改进算法动态调整。刚开始信息素浓度差别不大，主打各个节点之间的距离,这样有利于提高路径搜索速度,即信息启发因子α（1≤α₁＜5）先取较小值,相对应的期望启发式因子β（5＜β₁≤9）取较大值^[9];随着迭代次数增加,各条路径的信息素也得到了积累,此时选择主打信息素浓度进行全局搜索,即信息启发因子α（5＜α₂≤9）先取较大值,相对应的期望启发式因子β（1≤β₂＜5）取较小值;随着迭代次数的继续增加,为了防止由于信息素积累的正反馈机制作用,陷入局部最优,进而改为主打各个节点距离,即信息启发因子α（1＜α₃≤5）先取较小值,相对应的期望启发式因子β（5≤β₃＜9）取较大值。

4 仿真实验及其分析

为了进一步验证改进蚁群算法的可行性，将本文所提出的动态自适应调整α，β的蚁群算法（其中1≤α≤9，1≤β≤9）运用到移动机器人路径规划。

本文仿真实验中重要参数设置如表1所示：

表1 参数设置说明

Tab. 1 Parameters setup instructions

5.1环境描述

为了便于蚁群算法的搜索到最优路径，本文采用栅格法进行静态已知环境建模^[4]。设机器人的工作空间为二维平面上的有限区域AS，起始点B和目标点E.本文路径规划的优化准则为路径最短，即寻找一条从B到E避开障碍物的最短路径。工作空间AS由400个1×1大小的方格组成，AS的规模为20行×20列。对于位于节点(i,j)的蚂蚁(其中(1≤i≤20; 1≤j≤20)),下次可能目标节点(u,v)即:(i-1,j),(i-1,j+1),(i-1,j-1),(i+1,j),(i+1,j+1),(i+1,j-1),(i,j+1),(i,j-1),代表着蚂蚁每次只能按“左”, “左上”, “左下”, “右”, “右上”, “右下”, “上”, “下”八个方向进行移动。最短路径问题的目标函数可表示为:

(12)

其中:( , )为路径点坐标，n为路径点数目， 为路径长度。

按从左到右﹑从上到下的顺序对栅格进行编号(1～400) ，同时设机器人工作空间由M行N列栅格组成其中每个栅格是边长为1的正方形小格^[5]，将障碍物地图用一个二维数组矩阵map(M,N)表示为^[16]:

(13)

5.2 仿真及应用

图5 收敛曲线（最小路径长度）

Fig.5 Convergence curve (minimum path length)

图6机器人避障最优路线

Fig.6 Robot obstacle avoidance optimal route

图7机器人避障最优路线

Fig.7 Robot obstacle avoidance optimal route

图8机器人避障最优路线

Fig.8 Robot obstacle avoidance optimal route

图5，图6分别是采用本文动态自适应调整α，β的蚁群算法经过300次迭代后所收敛到的最短避障路径长度及所对应的最短路线。图7，图8分别是动态自适应调整信息素的蚁群算法、自适应调整信息素挥发因子的蚁群算法经过300次迭代后所收敛到的最短避障路线。具体仿真实验统计结果如表3所示：

表3仿真数据

Tab. 3 Simulation data

由表3可见，本文所提出的改进蚁群算法能有效地应用于移动机器人的路径规划，且与其他改进算法相比找到的机器人避障最优路线的路径最短，进一步验证了动态自适应调整α，β的蚁群算法可行性和有效性。

6 总结

本文在传统蚁群算法的基础上，提出了一种动态自适应调整α，β的改进蚁群算法，在一定程度上提高了搜索速度，有效的弥补了传统蚁群算法容易陷入局部最优的劣势，通过与其他改进策略的对比彰显了本文改进算法在逃离局部最优的优势，但也暴露了有些地方的不足(如搜索时间没有得到明显的改善)。通过仿真实验进一步证明了动态自适应调整α，β的蚁群算法的可行性和有效性．

参考文献(References):

[1] 庄慧忠.机器人路径规划及相关算法研究[J].科技通报,2004,(3):210-215.(Zhuang huizhong.

[2] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. Processings of the 1st European Conference on Artificial Life[C],1991,134-142.

[3] 王颖,谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报,2002,14(1):31-33.

[4] 覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制,2001,31(3):198-201.

[5] 黄国锐,曹先彬,王煦法.基于信息素扩散的蚁群算法[J].电子学报,2004,32(5):865-868.