基于改进蝙蝠算法的移动机器人路径规划方法研究

倪昌浩，邹 海

（安徽大学 计算机科学与技术学院，合肥 230601）

0 引言

路径规划是移动机器人导航的重要步骤之一，其目的是寻找出一条满足评价标准的无碰撞路径。当前的路径规划方法主要是运用智能优化算法寻找最优路径，如遗传算法[1]、蚁群算法[2]、粒子群算法[3]等，这些算法计算量小，结构简单，但依然存在收敛速度慢、搜索路径时间长等问题。

针对上述问题，学者们也提出了相应的改进策略。文献[4]对粒子群算法惯性权重因子和加速因子进行修改，同时融合鸡群算法对停滞粒子进行扰动，提高路径规划的收敛精度和稳定性。文献[5]将蚁群算法和人工势场法两种方法进行融合，提出一种结合人工势场和蚁群算法的移动机器人路径规划，提高了算法全局搜索能力，加快了收敛速度。文献[6]通过引入莱维飞行，克服粒子群算法的早熟问题，增加了种群多样性，并将改进粒子群算法成功应用于焊接机器人的路径规划问题中。

蝙蝠算法[7]是一种新型的智能优化算法，已经在很多领域得到应用[8,9]。本文为了更好解决移动机器人路径规划问题，提出一种结合黄金正弦和蝙蝠算法的路径规划算法（Golden-Sine Bat Algorithm，GSBA），提升了算法的收敛速度和寻优能力，具有较强的鲁棒性。

1 环境建模

本文研究的是静态环境下移动机器人的路径规划问题，为了让机器人能够识别周围环境，采用导航点模型[10]构建环境模型，如图1所示，图中黑色部分为障碍物，白色部分为可行区域，这种方法可以让移动机器人更好的规避障碍物。障碍物的数学表达式为：

图1 环境建模

其中：（a，b）为障碍物圆心坐标，R为圆的半径。

其中：R（k）为障碍物半径，l（k）为避障约束惩罚函数，D为问题维度，K为障碍物个数，c为安全因子，这里设置c=100。

2 蝙蝠算法

蝙蝠算法是通过研究蝙蝠的一些超声波特征得出的，每个蝙蝠都代表着解空间中的一个可行解，根据适应度函数可以求得每个个体的适应度，记录当前适应度最优蝙蝠，并使用更新公式对个体速度和位置进行调整，同时对最优蝙蝠位置进行局部搜索，通过不断迭代进化，最终收敛至最优解。算法中每只蝙蝠的声波频率fi、速度以及位置更新公式如下：

其中：fi为蝙蝠发出的脉冲频率，频率的最大最小值分别为fmax和fmin，β是[0，1]之间的均匀分布随机数，和分别表示蝙蝠个体i在第t代时的位置和飞行速度，x*代表全局最优位置。

当蝙蝠满足局部搜索的条件时，需对最优个体附近进行随机游走，位置更新公式为：

其中：xold为当前最优个体位置，ε为[-1，1]之间的均匀分布随机数，At为蝙蝠在第t代的平均响度。

在上述位置更新过程中，蝙蝠发现猎物时会减小响度，同时增大脉冲频率，以便更加准确掌握猎物的位置，其更新公式为：

文献[1-2]在处理旋转车轮对轮轨力的响应时，用轮轨力的旋转来代替车轮的旋转。换句话说，作者只是计算了相对地面不旋转的车轮在一个沿车轮滚动圆移动的荷载作用下的响应。由于车轮不旋转，因此车轮的响应可以用车轮的振动模态来叠加，而车轮的振动模态由普通的有限元程序计算出来。这种处理方法考虑了荷载的移动效应，但完全排除了车轮旋转时的离心效应和陀螺效应。

3 融合黄金正弦的蝙蝠算法

3.1 黄金正弦算法

黄金正弦算法（Golden Sine Algorithm，Golden-SA）于2017年提出的新型智能算法[12]，该算法迭代寻优时，依靠正弦函数和单位圆的关系对寻优区域全面搜索，同时引入黄金分割数控制遍历空间，可快速引导个体趋近于最优值，具有收敛速度快、易实现的优点。

Golden-SA算法中个体位置更新公式可表示为：

3.2 种群平均位置

基本蝙蝠算法单纯依靠种群最优个体的引导寻优，如果全局最优值离种群最优值较远，其他蝙蝠个体会受其影响，最终导致算法过早收敛或早熟。本文引入种群平均位置对部分个体进行引导，大大降低算法陷入局部最优的可能性，即速度更新公式为：

其中：mt-1为种群在第t-1代的种群平均位置。

3.3 分阶段局部搜索

基本蝙蝠算法中局部搜索阶段是执行全维搜索策略，这种搜索方式有很强的局部搜索能力，但没有考虑到单个维度值对适应度的影响。单维搜索策略每次只选择一个维度进行更新，可以尽可能广泛地探索，但是搜索效率较低。

针对全维操作的不足，本文使用单维和全维互补的方式对最优蝙蝠进行搜索，即在前迭代中执行单维更新策略，后迭代中执行全维搜索，如式(15)所示：

其中：T为总迭代次数，d为[1，D]间的随机整数。

3.4 删除操作

为了减少路径的冗余节点本文还增加了删除操作，如图2所示。

图2 删除操作

图2(a)中，机器人的路径为1→2→3，连接路径节点1和3，若1→3为无碰撞的安全路径，可删除路径节点2。

从起始节点开始依次对后面的路径节点进行连接，如果存在无碰撞路径，则将中间节点删除，如果不存在则对下一个节点依次搜索，直到到达终点，操作结束后重新计算路径的适应度。这种方法有效减少了路径的冗余度，也会让路径在平滑性上有较好的表现。

3.5 融合黄金正弦的蝙蝠算法

针对蝙蝠算法易陷入局部最优、多样性差等问题，本文提出了融合黄金正弦的蝙蝠算法（Golden-Sine Bat Algorithm，GSBA）。该算法按照不同的适应度把蝙蝠分为两个子种群，对于适应度较优的精英蝙蝠使用黄金正弦更新位置，使个体可以充分吸收最优个体的信息，达到快速收敛的目的，同时使用种群平均位置对另外的蝙蝠个体引导，以保证种群的多样性，防止搜索路径陷入局部最优。这里黄金正弦的位置更新方式可以用下式表示：

其中：x*为全局最优位置。

在蝙蝠算法局部搜索阶段，分阶段使用单维和全维操作对最优蝙蝠局部区域进行搜索，实现单维和全维操作优势互补。最后删除最优解的冗余节点，使路径更为简洁。

图3为算法流程图，移动机器人路径规划步骤如下：

图3 算法流程图

1）对工作环境进行建模，参数初始化，设置机器人起始点S和目的点E，根据环境确定路径数量N、问题维度D、最大迭代次数T，同时初始化蝙蝠位置xi、速度vi、声波响度、初始脉冲发射率；

2）计算每只蝙蝠所搜索路径的适应度，记录全局最优路径x*，根据式(14)计算种群平均位置；

迭代次数t=t+1，计算位置更新后各路径的适应度值，并更新全局最优路径x*，若t达到最大迭代次数，对最优路径进行删除操作，输出结果，否则跳转到步骤3）。

4 仿真分析

为了验证改进算法的性能，利用MATLAB软件进行路径规划仿真实验，对本文改进算法、原始蝙蝠算法、传统粒子群算法和黄金正弦算法在同样的环境下进行路径规划，共进行两组实验。实验中，机器人起点为S（0，0），终点为E（100，100），具体参数选取如下：种群规模N=100，问题维度D=30，迭代次数T=100，最大脉冲频率fmax=2.0，最小脉冲频率fmin=0.0，初始脉冲发射率r0=0.5，响度最大值A0=0.9，响度、脉冲的调节参数α=γ=0.9，PSO算法中学习因子c1=c2=2.0。

图4为各个算法在地图一下规划结果，从图4(a)中可以看出四种算法都可以规划出一条有效路径，但是本文算法的路径平滑度明显优于其他算法。PSO、BA、Golden-SA和GSBA在地图一中得到的路径最短长度分别为158.89、150.98、165.76和143.75，结合图4(b)可以看出，改进算法的规划路径明显短于对比算法，且有很好的执行效率，改进算法迭代次数到达26次时路径长度趋于稳定，同时在寻优后期依然可以使路径质量有所提升，而BA和PSO算法分别在42和30次迭代后，规划路径长度开始平稳减小，Golden-SA算法在68次迭代后，结果才趋于稳定。

图4 地图一下路径规划结果

地图二规划结果如图5所示，相对于地图一，地图二环境略微复杂，从图5(a)、图5(b)中可以看出GSBA算法依然可以寻找到一条较优路径，而其他对比算法规划的路径存在较高冗余度，PSO、BA、Golden-SA和GSBA在地图二中得到的路径最短长度分别为164.09、160.98、211.19和146.64，GSBA算法的规划路径长度依然有明显的优势。综上可得：本文改进算法提高了寻优收敛速度的同时，也使该算法规划路径的质量得到很大提高，验证了改进算法在路径规划中的有效性。

图5 地图二下路径规划结果

5 结语

为了解决传统算法在进行机器人路径规划时出现的搜索精度低、易陷入局部最优等问题，本文研究了蝙蝠算法在机器人路径规划中的应用，同时提出了一种改进的路径规划算法，通过引入黄金正弦算法和种群平均位置，优化个体位置更新方式，保持种群多样性的同时提高了算法的收敛速度，利用单维和全维相结合的局部搜索，使最优位置的局部区域得到充分探索，再对节点进行删除操作，进一步简化了路径。仿真结果表明：本文提出的算法具有较高的搜索效率和精度，能使移动机器人快速找到最优路径，有效解决了此类路径规划问题。