0 引言

移动机器人路径规划是机器人领域中一个研究热点, 其目的是在未知或已知的环境中, 按照指定的优化准则(如距离最短, 时间最短, 工作代价最小等)搜索出一条从起始位置到目标位置最优或接近最优的安全无碰撞路径^[1].目前, 国内外学者在移动机器人路径规划方面已经做了大量的研究工作, 其中包括Dijkstra算法^[2]、A*算法和人工势场法^[3]等传统算法, 以及遗传算法^[4]、快速搜索随机树法^[5]、人工神经网络^[6]、粒子群算法^[7]和模糊逻辑控制^[8]等智能优化算法, 每种算法在不同的性能指标下都有自身的优点.

蚁群算法^[9]是一种新型分布式智能仿生类算法, 该算法模拟了自然界中蚂蚁种群的觅食行为特征.蚁群算法具有很强的鲁棒性和适应性, 同时蚁群算法也存在搜索效率低、易出现停滞和局部最优解等缺陷.文献[10]引入障碍物排斥权重和新的启发因子到路径选择概率中, 提高了算法的避障能力和收敛速度.文献[11]利用人工势场法中的势场力重新构造启发信息, 提出改进的势场蚁群算法, 使算法具有良好的收敛性, 但是算法缺乏全局搜索能力, 容易出现停滞.

针对蚁群算法易出现的局部最优和在复杂环境下收敛性差的问题, 本文提出一种改进的势场蚁群算法.该算法利用人工势场法重构启发函数, 避免出现局部最优解; 依据起始点和目标点的位置, 通过初始信息素不均衡分配原则来提高算法收敛速度; 自适应调节信息素挥发系数, 在保证算法收敛速度的同时具有较高的全局搜索能力, 最终使得机器人路径规划向着全局最优的方向不断进化.

1 基本算法描述 1.1 基本蚁群算法

蚁群算法模拟了自然界中蚂蚁种群觅食的行为特征, 蚂蚁在觅食过程中会倾向于选择信息素浓度大的路径, 同时分泌信息素.该过程对应算法中两个关键步骤:概率选择和信息素更新.

1.1.1 概率选择

在t时刻, 蚂蚁k由第i个节点选择下一个节点j是根据初始信息素τ_ij(t)和启发信息η_ij(t)的大小进行判定.蚁群算法采用伪随机比例原则选择下一个节点位置, 即位于节点i的蚂蚁k, 以概率q₀转移到下一个节点j, j为使[τ_ij(t)]^α[η_ij(t)]^β达到最大的节点.蚂蚁的状态转移公式如下:

(1)

否则, 按照下式采用轮盘赌方式选择下一节点:

(2)

(3)

其中: α为信息素启发因子, 表征信息素重要程度的参数, 其值越大, 蚂蚁越倾向于选择信息素浓度大的路径; β为期望启发式因子, 表征启发信息重要程度的参数, 其值越大, 蚂蚁越倾向于选择距离目标点近的节点; d_jg为待选节点j到目标节点g的欧氏距离.

1.1.2 信息素更新

蚂蚁经过的路径会留下一定信息素, 同时随着时间的推移会挥发掉一部分信息素, 这就需要对信息素进行更新.传统的蚁群算法在所有蚂蚁完成一次迭代后, 对信息素通过下式进行全局更新:

(4)

(5)

其中: ρ为全局信息素挥发系数, 通常取ρ < 1, 避免路径上轨迹量的无限累加; Δτ_ij(t, t+1)为蚂蚁在(t, t+1)时刻留在路径(i, j)上的信息素量; Q为信息素强度系数.

1.2 人工势场法

人工势场法基本思想是通过目标位置的引力场和障碍物的斥力场共同作用来搜索出一条无碰撞的最优路径.在虚拟的势场中, 机器人与目标点距离越远, 所受到的势能越大, 与目标点距离越近, 受到的势能越小, 到达目标点时势能为零; 机器人与障碍物距离越近, 斥力越大, 反之则越小.人工势场法的定义如下:

若机器人当前方位为X=(x, y), 目标位置为X_g=(x_g, y_g), 则引力势场函数

(6)

其中: k为大于零的引力场常数, X为机器人位置向量, X_g为目标位置向量.

斥力势场函数定义为

(7)

其中: m为大于零的斥力场常数, ρ为机器人到障碍物的距离, ρ₀为障碍物的最大影响范围.机器人在引力和斥力的共同作用下, 朝目标点移动并最终到达目标点.

2 改进势场蚁群算法 2.1 改进启发信息

传统蚁群算法中各路径初始信息素是相同的, 主要差异在启发信息上.蚁群建立的第1条路径往往偏向于距目标点近的位置, 此时蚁群算法相似于贪婪算法, 有时在特殊环境中未必反映最优路径, 但由于蚁群算法的正反馈性, 从而导致蚁群向着错误的方向搜索.

本文针对这个问题, 采用人工势场法求得的初始路径和机器人与下一个节点之间的距离信息综合改进启发信息, 利用新的转移概率确定下一个节点的选择.在迭代后期, 为避免算法陷入局部最优, 应减小启发信息对蚁群搜索的影响.因此, 新的启发函数引入启发信息递减系数ξ, 启发信息会随着迭代次数的增加所起的作用一直递减.新的启发函数为

(8)

其中: d_ij为节点i到节点j的欧式距离; L_jg为采用人工势场法求得的节点j到目标点g的距离; N_cmax为最大迭代次数; N_c为当前迭代次数; ξ为启发信息递减系数, 且ξ>1.

由于人工势场法模型简单, 实时性强, 将其求得的路径引入蚁群算法的启发函数中, 可有效避免蚁群算法由于启发信息所导致的局部最优问题, 同时提高蚁群算法的搜索效率.

2.2 初始信息素不均衡分配原则

在路径规划初期, 各节点信息素浓度差异较小, 蚁群算法的正反馈作用不明显, 蚁群搜索路径时存在盲目性, 导致算法收敛性差, 且耗时较多.为解决此问题, 本文提出初始信息素不均衡分配原则, 即在起始节点和目标节点之间的所有节点, 规定其初始信息素略大于其他节点, 即

(9)

其中: τ_i∈τ, τ为信息素矩阵; C为大于1的常数; A = {min(g_start, g_end), min(g_start, g_end)+1, …, max(g_start, g_end)}, g_start为起点序号, g_end为目标点序号, 如g_start =1, g_end=30, 则A={1, 2, …, 30}.由零点定理可知, 最优路径往往介于起始点和目标点之间, 因此有利于减少蚁群搜索的盲目性, 缩短路径搜索时间, 而且不会增加算法的复杂性.

2.3 改进信息素更新算法

当蚂蚁k从节点i移动到下一个节点j, 便会进行局部信息素更新.局部信息素更新规则为

(10)

其中: λ为局部信息素挥发系数, 且λ∈(0, 1);τ₀为一个小的正常量; 当τ_ij(t) < τ_min时, 令τ_ij(t)= τ_min; 当τ_ij(t)>τ_max时, 令τ_ij(t)=τ_max^[12], τ_min和τ_max为设定的信息素最小值和最大值, 防止算法由于信息素过多或过少而陷入停滞状态.

当所有蚂蚁完成一次迭代后, 再进行全局信息素更新.在传统蚁群算法中, 完成一次迭代之后, 会根据式(4)进行全局信息素更新.由于任何一次循环中蚂蚁所建立的路径都会对蚁群以后的决策产生影响, 如果所建立路径并非最优, 则以后会对蚂蚁造成误导.因此, 本文在完成一次迭代后, 根据最优最差蚂蚁系统的原理, 找出最优解和最差解, 分别进行全局信息素更新, 对最优解进行增强, 对最差解进行削弱^[13], 最优最差蚂蚁系统使得蚂蚁搜索更集中于到当前循环为止所找到的最好路径的邻域内, 并向着全局最优的方向不断进化.

在本次迭代中选出最优蚂蚁路径和最差蚂蚁路径, 对最优蚂蚁按式(4)执行全局更新规则, 对于最差蚂蚁, 则按下式进行全局信息素更新:

(11)

其中: ε为该算法引入的一个参数; L_worst为当前迭代中最差蚂蚁的路径长度, L_best为当前迭代中最优蚂蚁的路径长度.

最优最差蚂蚁系统在信息素更新上加大了蚁群算法的收敛性, 但是由于正反馈性导致算法易陷入局部最优解, 降低了算法的全局搜索能力.通过减小ρ可以提高算法的全局搜索能力, 但会降低算法收敛速度, 因此本文提出自适应调节信息素挥发系数ρ来克服上述缺陷, 通过自适应地调节信息素挥发系数, 可以在保证收敛速度的条件下提高解的全局性.

设定一个迭代阈值R, 当未到达阈值R时, 信息素挥发系数ρ随迭代次数增加而递减, 到达阈值R后取ρ₀, 再进行递减, 即

(12)

其中: γ为算法引入的一个参数, 取小于1的正数; ρ₀为信息素初值, 本文取ρ₀=1;N_c为当前迭代次数; R为迭代阈值.

2.4 改进算法具体步骤

图 1所示为改进的势场蚁群算法流程, 具体步骤描述如下.

Step 1:初始化参数.选择起始位置S、目标位置G、迭代计数器N_c=0, 设置最大迭代次数N_cmax, 对蚂蚁数量m、信息素启发因子α、期望启发式因子β、启发信息递减系数ξ等其他参数初始化.

Step 2:初始信息素分配.按照式(9), 根据起始点位置S和目标点位置G进行信息素的不均衡分配.

Step 3:蚂蚁路径选择.将m只蚂蚁放到起始点, 并将起始点S加入禁忌表中.采用人工势场法计算当前待选节点j到目标点距离L_jg, 代入式(8)得到启发信息的值, 再依据式(1)和(2)寻找下一个可行节点j, 并将选取的节点j加入禁忌表中.如此循环直到蚂蚁到达目标点.

Step 4:信息素局部更新.蚂蚁每建立一条路径便按式(10)进行局部信息素更新, 同时保证信息素浓度τ_ij(t)∈[τ_min, τ_max].

Step 5:信息素全局更新.等所有蚂蚁完成一次迭代后, 找出本次迭代中的最优蚂蚁和最差蚂蚁, 同时通过当前迭代次数是否到达设置的迭代阈值R, 按照式(12)确定全局信息素挥发系数.对最优蚂蚁所走过的路径按照式(4)和(5)进行信息素更新; 对最差蚂蚁所走路径按照式(11)进行更新, 同时保证信息素浓度τ_ij(t)∈[τ_min, τ_max].

Step 6:结束搜索.判断迭代是否到达最大迭代次数, 若达到最大迭代次数, 则输出最优路径长度; 否则, 清空禁忌表, 令N_c=N_c+1, 转Step3依次循环执行, 直到满足循环次数N_c=N_cmax, 输出最优路径长度, 算法结束.

3 实验研究与仿真分析

将本文改进势场蚁群算法应用于机器人路径规划问题求解, 为验证本文算法的可行性和有效性, 进行大量仿真实验, 并通过与基本蚁群算法和文献[10]中提出的改进蚁群算法相比较, 验证本文算法的优越性.算法运行环境为: Windows7 64 bit; Matlab R2014a;处理器Intel(R) Core(TM) i5-5200U;主频2.2 GHz; 内存8 GB.

3.1 地图建模

机器人工作环境建模是实现路径规划的首要条件, 通过提取到的有用信息, 分析得到机器人可以理解的环境地图, 使机器人能够在该环境中进行路径规划.目前常用的环境建模方法有可视图法、拓扑图法、栅格法和链接图法等^[14].其中栅格法在机器人路径规划应用中最为广泛.本文研究的移动机器人运动空间为二维空间, 选取栅格法建立移动机器人环境模型.

栅格大小一般设定为移动机器人的步长.为确保移动机器人在运动中的安全性, 障碍栅格进行膨胀处理, 即障碍物以机器人尺寸大小的一半进行膨胀, 未占满一个栅格的按一个栅格进行处理.规定机器人在进行路径搜索时按照八叉树形式进行搜索.假设栅格规模为N_x列N_y行, 即一个二维数组矩阵map(N_y, N_x).其中:第i个栅格的位置坐标为(x_i, y_i); 栅格序号与坐标映射关系如下:

(13)

R_a为一个单元栅格的边长, mod为取余函数, ceil为向上取整函数.

3.2 主要参数优化

由于到目前为止还没有研究出蚁群算法模型的数学分析方法使之能够在每种情况下都能生成最优的参数设置, 一般通过经验选择参数.本文在参数变化范围内设置不同的参数组合, 通过统计实验结果的优劣, 选取最优参数组合.

每个参数设置一组值, 同时其他参数不变, 并且为了避免偶然情况将每个参数设置进行10次仿真, 对算法结果求均值进行对比.测试参数为α∈{0, 0.5, 1, 5}, β∈{0, 1, 5, 8, 10}, ξ∈{0, 1, 5, 10, 100}, λ∈{0, 0.5, 0.8, 1}, ε∈{0, 0.5, 0.8, 1}, Q∈{1, 10, 100}.参数默认值设为α=1, β=5, ξ=5, λ=0.5, ε=0.5, Q=1.每次实验只改变一个参数, 如当计算α=0的仿真结果时, 其他各参数皆取默认值, 以此类推.经过多次仿真实验, 由表 1参数优化结果中可以得出本文算法的主要参数有如下特征:α的最优值在1附近, β的最优值介于5~10之间, ξ的最优值在5附近, λ的最优值在0.8附近, ε在0.5附近最优, Q的取值对算法结果影响不大, 本文取Q=1.

3.3 10×10仿真环境

10×10的仿真环境由于其特殊的栅格信息, 基本的蚁群很难找到最优路径, 而本文算法很快便可找到一条最优路线.本次实验各相关参数取值为N_cmax=50, M=50, α=1, β=8, ξ=5, λ=0.8, ε=0.5, Q=1. 图 2为蚁群算法和本文改进的势场蚁群算法规划的路径结果.

由图 2可以看出, 蚁群算法并未搜索到最优路径, 而是收敛到一条较长路径, 这是因为受启发信息的影响, 蚂蚁在第1次搜索路径时偏向于离目标点较近的栅格, 加上正反馈作用, 以后的蚁群也会趋于选择此条路径, 并最终收敛到这条路径.改进后的势场蚁群算法采用势场法规划的路径和下一个栅格的位置信息作为参数, 引进新的启发信息避免了这种问题, 并提高了算法的收敛速度.由表 2可看出, 蚁群算法迭代16次后收敛于非最优路径, 而本文算法只用了8次迭代即收敛到最优路径, 且减少了算法的运行时间.

3.4 30×30仿真环境

为了对比在复杂环境下改进势场蚁群算法与其他算法的差异, 本文设置30×30的仿真环境, 分别采用本文算法、蚁群算法和文献[10]提出的改进算法进行路径规划仿真实验. 3种仿真算法的结果如图 3所示, 粗实线为本文改进的势场蚁群算法规划的路径, 细实线为蚁群算法规划的路径, 点画线为文献[10]提出的改进算法规划的路径.

由图 3可以看出, 在复杂环境下, 本文改进算法搜索到的路径相比于其他两种算法搜索到的路径较优, 且收敛速度较快.由表 3可以看出, 蚁群算法用了30次迭代收敛到49.694, 文献[10]算法用了21次迭代收敛到47.936, 本文改进的势场蚁群算法只用了13次迭代便收敛于最优路径45.108.在算法运行时间上, 文献[10]算法稍微优于本文改进算法, 但从算法结果上看, 本文改进算法在运行时间上可稍作舍弃, 以赢得较快的收敛速度和较优的路径长度.

为进一步验证本文改进算法具有较优的全局搜索性, 分别在相同环境下对蚁群算法和本文算法所有蚂蚁走过的路径进行仿真分析, 图 4(a)为蚁群算法所有蚂蚁走过的路径, 图 4(b)为本文改进算法所有蚂蚁走过的路径.

由图 4可以看出, 本文改进势场蚁群算法中蚂蚁所走路径比蚁群算法具有较高的全局性, 这样也更有利于算法找到最优路径.

3.5 算法复杂度及实用性分析

蚁群算法的复杂度分析主要研究蚁群算法在求解问题时所需各种资源的量, 其主要考虑的是设计可用于估计、定界蚁群算法求解某类问题时所需要的和仅需要的计算资源量.一般包括时间复杂度分析和空间复杂度分析^[15].

通常将算法执行基本操作的次数定义为算法的时间复杂度.在蚁群算法中, 设n为所求解问题的规模, m为蚂蚁数目, 循环变量为N_c, 最大循环次数为N_cmax, 则针对蚁群算法的时间复杂度可表示为

(14)

其中O表示数量级的概念.在本文中时间复杂度可理解为执行算法编译运行的时间, 由大量实验仿真和算法对比可以看出, 本文改进算法拥有较高的执行效率.

蚁群算法的空间复杂度可定义为算法执行时间内所占用的存储单元.本文改进算法中数据主要实现两方面功能:一是问题的描述; 二是实现算法功能的辅助数据.针对蚁群算法的空间复杂度计算公式为

(15)

在实际应用中, 机器人工作环境信息使用数据文件存储, 用到的存储单元不超过数兆, 在数据存储上非常简单.如机器人工作在50 m×50 m的环境中, 机器人步长为0.5 m, 则共有100行, 每行有100个栅格, 用0和1表示栅格属性, 每行约用100个字节, 全局环境信息共用约100 kB, 对于目前存储技术并无压力.所以本文改进蚁群算法拥有较低的复杂度, 易于程序移植和后期在线路径规划.

本文改进势场蚁群算法主要用在移动机器人全局静态路径规划中, 若在考虑实时规划时(如移动机器人在按原规划路径行进中)遇到动态障碍物或其他原因无法继续行进, 则根据指令转移到新的目标地点或重新规划一条可行的路径继续前行, 只需将机器人当前位置作为起点, 新的目标点取代之前的终点信息, 即可用本文改进的算法实时地规划出一条路径.在遇到动态障碍物时, 通过传感器得到机器人与障碍物之间的距离信息和障碍物的速度信息, 从而确定障碍物运动范围, 将该范围内栅格环境数值设置为1, 机器人进行实时规划, 得到一条避开动态障碍物的最优路径.

4 结论

本文在全局静态环境下, 基于栅格法对移动机器人工作空间进行建模, 针对基本蚁群算法在机器人路径规划中出现的不足, 提出了一种改进的势场蚁群算法.

1) 该算法利用人工势场法求得的初始路径和机器人与下一个节点之间的距离信息对启发函数进行改进, 新的启发信息能够有效避免算法在特殊环境中陷入局部最优, 且由于人工势场法的先验路径作为启发信息的参数, 使得算法的收敛速度得以提高.

2) 依据起始栅格和目标栅格的位置信息, 提出了信息素不均衡分配原则, 能有效避免蚁群搜索初期的盲目性, 提高算法的搜索效率.

3) 自适应调节信息素挥发系数, 在保证收敛速度的条件下提高了算法的全局搜索能力.

通过对算法的复杂度和实用性分析, 以及在特殊环境和复杂环境下的仿真结果可表明, 本文改进的势场蚁群算法能够更有效地规划出最优路径.本文是在全局静态环境下展开的研究, 后续研究将结合动态避障, 进一步提高算法路径规划的能力.