基于改进蝙蝠算法机器人避障研究*

黄华东，陈 亮

(1.长沙民政职业技术学院，长沙 410004；2.长沙师范学院，长沙 410004)

0 引言

智能移动机器人广泛地运用于农业生产[1-2]、航天科技[3]、材料加工[4]、医疗救援[5]等领域。自由避障能力是移动机器人最为突出重要的一项能力。这要求智能机器人有对障碍物的自行规避与从起点到终点的路径规划的能力。路径规划问题的实现算法分为传统算法与智能算法，其中传统算法主要有模糊逻辑算法、可视图法、自由空间法、人工势场法等[6]。模糊控制算法求解多维问题难以建立模糊规则库[7]。可视图法实时性能较差，且效率较低[8]。自由空间法处理复杂障碍空间，其复杂度将超出计算能力范围[9]。人工势场法易得局部最优而难以到达终点[10]。随着人工智能的崛起，智能仿生算法被应用于路径规划与优化问题，如粒子群算法(PSO)[11]、人工鱼群算法[12]、蚁群算法[13]等。传统PSO中粒子易陷入不良区域，种群多样性不足，搜索停滞，后期收敛速度较差[14]。基本鱼群算法的历史行为学习度不足，收敛精度低[15]。基本蚁群算法信息浓度低，搜索速度慢[16]。

近年来又出现了一种新型智能优化算法即蝙蝠算法(BA)，是模拟蝙蝠捕食飞行过程的一种仿生智能算法，具有模型简单、算法参数少有并行性强且分布式广的特点[17]。但由于初期搜索范围不够广，收敛过快，精度较低，后期存在较多停留边界的个体，种群多样性差等问题。

因此，本文将其与高斯函数与柯西函数结合，引入高斯柯西变异策略，帮助算法逃离局部极值的同时提高算法精度。另外使用线性渐变法调节响度和脉冲发射率，通过脉冲发射率的大小控制蝙蝠进行全局搜索或局部精确搜索，优化了收敛速度慢的问题。针对存在的个体飞出解空间边界导致收敛速度慢的问题，采用边界再分配机制，减少个体在边界聚集、提高优化效率。

为了规避移动过程转折点多导致的急转急停问题，基于三次样条插值对原规划路径进行处理，使得路径拐点减少，保证运行平顺流畅。经过处理后的路径规避了机器人难以实现的急转急停问题，保证运行过程良好的动力学性能，保护了机器人内部构件不受损坏，具有原生算法路径不可比拟的优势。

1 基本蝙蝠算法

BA算法是模拟蝙蝠飞行时回声定位特点的一种仿生智能算法。通过仿照蝙蝠搜寻猎物，以一定频率和响度的声波，去寻找发现当前最优解。记f(x)为目标函数，每只蝙蝠在算法中都有相应的函数值，代表一个可行解，通过函数值比较判断出最优个体。算法的迭代可分解成4个过程：

(1)随机飞行。

fi=fmin+(fmax-fmin)β

(1)

(2)

(3)

(2)局部搜索。蝙蝠接近全局最优解时,再引入一个取值在0～1的均匀分布数R1，若R1>ri，则开始局部搜索，否则继续全局搜索。通过下式更新位置：

(4)

式中，ε为[-1,1]上的均匀分布随机数；At是第t代所有蝙蝠响度的平均值。

(4)更新参数。接受新解意味着蝙蝠在靠近猎物，响度减小的同时，脉冲发射速率ri不断增加。其更新公式如下：

(5)

(6)

2 改进方向

2.1 高斯柯西变异

单一的高斯变异或柯西变异并不能完美地利用其分布特性。柯西分布两端概率较高，产生广范围随机数，扩大搜索范围，避免个体的聚集导致取得局部极小。

(7)

式中，r∈(0,1)是个随机数，服从均匀分布；t为迭代次数；Tmax是最大迭代次数；C(1,0)是服从标准柯西分布的随机变量。

高斯分布具有中心附近概率较高的特性，适合在最优解附近小步长精细搜索，精确寻找全局最优解。

(8)

式中，R3∈(0,1)是个均匀分布随机数；N(0,1)是服从标准高斯分布的随机变量。

图1 柯西与高斯概率密度

式(7)、式(8)中1-t/Tmax在[0,1]内单调递减，搜索前期阶段t值较小时，1-t/Tmax较大，按式(7)进行柯西扰动，扩大搜索范围。搜索后期阶段，t值增大，1-t/Tmax变小，当其小于随机数R3时，按式(8)进行高斯变异，小步长能对最优解附近实行深度搜寻。两种变异策略交替使用，根据搜索进程自适应调整策略，使得全局搜索与局部搜索得到合理平衡，提高了最优解的搜索精度，同时加快了后期的收敛速度。

2.2 线性渐变算法

(9)

由于两个参数单调递减，故响度最大值Amax即初始响度，一直递减至最小值Amin，脉冲发射率rmax即初始脉冲发射率一直递减至最小值rmin，直到达到最大迭代次数Tmax。

2.3 边界再分配机制

由于蝙蝠算法随机搜索的内生性，个体搜索至边界后聚集不可避免，这将进一步降低多样性。为此本文融合边界再分配机制，将越界个体通过式(10)进行位置随机再分配，而保证个体的速度大小和方向不改变，以此提高个体利用，加快算法后期收敛。位置更新如式(10)所示。

X*=Lb+λ(Ub-Lb)

(10)

式中，λ∈[0,1]是一个随机变量，是位置随机分配因子；Lb代表空间边界的下界；Ub代表空间边界的上界。

2.4 三次样条插值法的路径平滑

本文路径规划地图采用栅格地图表示，因此会在转弯处产生明显拐点。为了让移动机器人减少实际轮子的轴磨损和能耗，应保证规划出的路径具有平滑性。

三次样条插值具有一阶和二阶导数的收敛性，三次函数的最高项系数为0时三次样条插值曲线仍为曲线，插值效果更好。另外三次样条插值与高阶插值相比具有计算简单稳定性好的优点。因此本文使用三次样条插值形成平滑路径。

取区间[a,b]分成n个区间[(x0,x1),(x1,x2),…,(xn-1,xn)]，三次样条方程满足以下条件：

在任意的[(xi-1,xi)]上，S(x)=Si(x)都是一个三次方程：

Si(x)=ai+bi(x-xi)+ci(x-xi)2+di(x-xi)3

(11)

S(x)在区间[a,b]中是连续的：

S(x0)=y0,…,S(xn+1)=yn+1

(12)

S-=S+(xi),i=1,2,…,n

(13)

S′(x)在区间[a,b]中是连续的：

(14)

S′′(x)在区间[a,b]中是连续的：

(15)

在本文中三次样条函数用于在起点控制点和目标点的路径上进行插值可以将移动机器人的路径分割为一系列连接路径点的线段从而获得了通过连接所有插值点而形成的完整路径。

2.5 算法实现流程

本文算法的实现具体流程如下：

(1)建立地图环境，确定起终点和最大迭代次数初始化蝙蝠位置、速度、频率、脉冲发射频率、响度，种群规模等参数；

(2)计算蝙蝠种群的适应度，记录最优个体x*；

(3)按照式(2)、式(3)更新蝙蝠位置和速度，越界个体按式(10)进行处理，产生新个体xnew；

(4)生成随机数R1，若R1>ri，则根据式(7)、式(8)选择变异机制，并将变异个体赋值给xnew；

(6)比较所有蝙蝠的适应度，找到当前最优解x*；

(7)重复(3)和(6)，直到达到最大迭代次数；

(8)得到平滑前的最佳路径；

(9)通过三次样条插值法得到平滑路径。

3 仿真及分析

3.1 地图环境生成

本文将栅格图作为机器人建模环境。栅格地图形如棋盘，将障碍物通过膨胀法或腐蚀法进行栅格化，暗色部分表示个体不可通过，白色部分表示可自由通过。机器人在传统栅格图移动有8个方向可供选择，如图2所示。

图2 移动方向

机器人栅格环境模型如图3所示。以左下角第一个栅格的中心点坐标(0.5,0.5)为原点，根据栅格图中每个栅格的行列次序，依据从下至上，从左到右原则依次递增。如栅格地图规格为j行k列，栅格号为G，栅格粒径为1，则栅格中心坐标可表示为：

图3 栅格图

(16)

式中，x、y分别为中心点的横、纵坐标；mod为取余操作；int表示求整。

3.2 参数设置

基于MATLAB2016a平台搭建20×20栅格地图环境，设置起点为(0.5,0.5)，终点为(19.5,19.5)。其余主要参数设置如表1所示。

表1 本文用到的基本参数

3.3 实例仿真分析

基于相同环境且根据上节设置的参数值，分别利用本文算法和基本蝙蝠算法进行路径规划，基本蝙蝠算法仿真图如图4所示，改进蝙蝠算法未平滑仿真图如图5所示，改进蝙蝠算法平滑化仿真图如图6所示，各项指标对比如表2所示。

图4 基本蝙蝠算法仿真图

图5 改进蝙蝠算法未平滑仿真图 图6 改进蝙蝠算法平滑化仿真图

表2 指标对比

从图4、图5可以看出，相比于基本蝙蝠算法，本文算法规划出的路径长度更短，拐点数更少，并且路径的平滑性更好。图6相比于使用三次样条插值法前的图5则几乎没有拐点，路径非常平滑对机器人的性能损耗较小。另外，本文算法收敛效果优于基本蝙蝠算法。因此在对机器人进行路径规划时，本文算法能够更好的适应机器人实际运行环境，高效完成相应任务，对机器人的工作更加有利。

4 结论

本文以线性渐变方式调节响度和脉冲发射率，通过脉冲发射率的大小控制蝙蝠进行全局搜索或局部精确搜索，优化了收敛速度慢的问题。在局部寻优阶段融合高斯柯西变异策略，前期利用柯西函数两翼高概率特性产生广泛围随机数，扩大算法搜索范围，后期利用高斯函数中间概率高，两端概率低的特性进行精准定位。同时采用边界再分配机制，优化了蝙蝠在边界聚集，带来的种群多样性不足问题，提高收敛效率。最后，利用三次样条插值法将拐点平滑，形成一条光滑曲线。仿真表明，改进后的蝙蝠算法相较于基本蝙蝠算法，规划路径更短，拐点数更少，运行时间短，迭代次数少，对机器人工作运行更为有利。