基于蝙蝠算法-人工势场的机器人路径规划研究

（上海理工大学，上海 200093）

0 引言

近年来智能机器人领域发展飞速，移动机器人在各个领域中都得到了广泛的应用和发展，如智能仓储、货物码垛、无人机侦查、未知环境探索、深海探索、机械加工等，例如，焊接机器人利用粒子群算法实现焊接过程中避障的路径规划[1]；矿山救援机器人利用改进遗传算法实现在矿山救援任务中的路径规划问题[2]。在考虑到环境的复杂，障碍物交错，机器人自主寻找出一条安全、可靠的最短路径是机器人研究中的关键技术。工程中，最短路径可以节约机器人运动过程的时间成本，提高工作效率；路径减少锐角转向，可减少机器人运动过程中不必要的损耗，减少后期维护成本。国内外学者对机器人路径规划问题做了大量的工作并取得不少成果并运用到了各个领域中。A*算法、传统人工势场、强化学习方法、深度学习方法[3～5]等是较常用的路径规划算法，这些算法或多或少存在着难以满足实际要求的问题。如A*算法复杂度较大，内存占用量大，不适用于追求灵活运动的小型系统的机器人的路径规划中。基本人工势场法在迭代过程中容易陷入局部最优解，产生路径震荡[4]。近年来，机器人路径规划研究逐渐向仿生智能算法转移，对于机器人路径规划问题上，仿生智能算法更具有先天优势。如蚁群算法、人工鱼群算法、遗传算法、粒子群算法[6,7]等。粒子群算法容易陷入局部最优解，蚁群算法搜索迭代时间长，容易停滞等缺点。因此研究对环境适应性强、算法步骤简单、求解速度快和路径最短成为研究者们追求的目标。

1 基本算法

1.1 蝙蝠算法

蝙蝠的生物学机理较简单，集群生活，通过声波回声定位和搜索猎物，搜索猎物时发射低频脉冲。剑桥学者Yang于2010年，根据模拟蝙蝠回声定位的仿生学机理提出了蝙蝠算法[3]。蝙蝠全局搜索猎物时，发射低频脉冲，声波响度大，能量损耗小，传播距离长，能快速锁定猎物大致方位。当声波传递到猎物后，蝙蝠接收回传声波信号，结束全局搜索。此时开始局部搜索，并发射高频脉冲。高频脉冲的特点是，声波响度小，声波间距小，传播距离短，能量损耗大。声波间距小，对于猎物的形状大小能精确检测。蝙蝠利用随机飞行策略将猎物距离告知其他蝙蝠，同时更新位置和速度。目前蝙蝠算法已经在电力系统广域协调控制[6]、AGV物料配送调度[8]、车辆调度路径[10]等领域得到了实际的应用。

基本的蝙蝠算法中，蝙蝠群体中单一个体被视为单一的粒子，粒子无质量和体积，仅代表空间中的每一个目标函数的一个可行解，通过比较目标函数值的大小，即可判断蝙蝠位置是否处于最优位置。蝙蝠飞行过程中不断更新自身位置和速度，因此在机器人路径规划的求解过程中可以利用蝙蝠飞行、捕捉猎物的一系列行为进行类比。蝙蝠算法的仿生思路为：蝙蝠开始搜索猎物时发出声波响度大，脉冲频率低的声波，为了能在一个较大空间中寻找全局最优；在发现猎物后，降低声波响度，提高脉冲频率，为了能在局部空间精确寻找定位猎物。

在此，由于蝙蝠发出的声波是间断的，脉冲频率是指单位时间内声波的频数，而不指声波震动的频率，声波频率取决于蝙蝠种类。

蝙蝠算法规则为：蝙蝠在d维空间中寻找猎物，即适应度函数的最优解。假设在t时刻，第i只蝙蝠位置为，其速度为，当前最优位置为x*，更新位置和速度公式如下：

其中，fi为第i只蝙蝠发出的搜索声波频率，fmax为蝙蝠搜索声波的最大频率，fmin为蝙蝠搜索声波的最小频率，因此fi∈[fmin，fmax]。

当蝙蝠发现猎物，通过改变声波响度和脉冲速率使全局搜索策略转变为局部搜索策略。减小声波响度，增大脉冲速率，进行局部搜索，遵循以下公式：

这里需要再次强调的是，蝙蝠的搜索声波频率f和蝙蝠脉冲速率r是有非常大的区别。f指的是蝙蝠搜索时发出的一小段声波的频率，取值取决于需要解决的实际问题；r指的是蝙蝠每秒发出声波的数量，局部搜索时，r将逐渐增大，直至找到最优解，取值等于最大值。

1.2 人工势场法

人工势场法是通过设定终点坐标为引力势场，设定障碍物为斥力势场，寻找躲避障碍物无碰撞的最优路径。随着机器人运动过程中逐渐靠近障碍物，机器人和障碍物的距离越近，斥力越大，反之越小；机器人躲避障碍物后逐渐靠近终点，机器人和终点的距离越近，引力越小，反之越大。基本人工势场法算法定义如下：

引力势场函数Ugra：

其中机器人当前位置为X=（x，y），终点位置为Xg=（xg，yg），k为大于零的任意引力场常数。

斥力势场函数Urep：

其中m为大于零的任意斥力场常数，ρ为机器人到障碍物的距离，ρ0为障碍物的最大影响半径。在引力势场和斥力势场的共同作用下，机器人受斥力和引力，朝合力最大的方向运动最终到达终点。

1.3 三次样条插值

三次样条插值用于平滑机器人路径，从起点到终点上给定区间[a，b]上分割成n个插值点满足：

若满足以下条件，则在[a，b]上的一个函数S（x）就称为三次样条插值函数。

1）每个区间（xi，xi+1）（i=1，2，3，…，n）中，都有三次多项式函数：

2）S（x）、S'（x）和S''（x）在[a，b]上连续，且满足

插值条件：

连续性条件：

其中满足插值条件的方程个数共有n+1个，满足连续性条件的方程个数共有3n-3个，因此共可建立4n-2方程，加上边界条件后共有4n个方程，因此可求解出分段函数S（x）。

2 基于人工势场的蝙蝠算法（BA-APF）

和其他路径规划的群集智能算法相似，蝙蝠算法在寻优的过程中，存在种群多样性和算法深度挖掘能力之间存在矛盾，两者难以兼顾。对于路径规划算法的改进目标都是针对保证种群多样性和算法的快速收敛性，同时避免局部最优。本文对蝙蝠路径节点进行势场化处理，引入扰动系数g改进ri脉冲速率，提高算法的挖掘深度能力。对相邻两个路径节点[15]加入引力势场。建立基于人工势场的蝙蝠算法（Bat Algorithm-Artificial Potential Field，BA-APF）模型。对算法迭代Tmax次，最后求得最优解。

2.1 动态扰动系数

当蝙蝠发现猎物，即将接近全局最优解时，基本蝙蝠算法将在最优个体附近开始局部搜索策略。此时生成均匀分布的随机数P作为判断阈值[16]，当P>r时，使用局部策略，否则重复全局搜索。因此，基本蝙蝠算法中蝙蝠是否进入局部搜索，完全取决于r值的取值。若r值的大小在算法前期一直保持一个较小的值，则可以增大算法进入局部搜索策略概率，较有效防止算法局部最优，同时满足蝙蝠算法要求。

其中，t是当前迭代次数，Tmax是最大迭代次数。g值随着迭代次数的增加而自适应的增大，在算法前期扰动影响较小，在算法中后期仍然保持在一个相对较小的范围中，例如，时，，引入扰动系数后的是基本蝙蝠算法中的0.7倍。改进蝙蝠脉冲速率r 后，BA-APF 算法保证扰动系数g 满足1≥g>0，每次迭代过程都能保证系数的取值相比基本蝙蝠算法所获得的取值更小，并能满足基本蝙蝠算法脉冲速率的取值条件：保持增大到设定值。

2.2 基于人工势场的改进

在机器人路径规划过程中，基本人工势场仅仅对障碍物和终点设置斥力场和引力场[17]。然而，当机器人所处的某点的引力势场和斥力势场大小相等方向相反时，基本人工势场法容易发生锁死，无法求解；当陷入障碍物斥力场范围叠加时，机器人路径容易发生震荡。

为同时保证BA-APF算法过程中路径尽可能平滑，在BA-APF算法中引入人工势场，设置相邻两个路径节点势场。

具体方法如下：

1）按式(6)对目标点设置引力势场。

2）按式(7)对障碍物中心设置斥力势场，影响半径为障碍物半径。

3）路径势场化，方法如下：

图1 路径节点势场化示意

路径节点的设置方法如下：

3 适应度函数的构建

机器人路径规划需要避免与障碍物碰撞、寻求路径最短和避免出现急转。为保证路径有效、最优以及机器人运动稳定性，BA-APF算法重复迭代t次，每一只蝙蝠代表一条机器人路径均要求通过适应度对比计算来判断路径优劣。BA-APF算法需要求满足上述条件，路径规划的适应度函数构造如下：

其中，式(18)中，L为机器人路径总长度；（xm，ym）为机器人路径节点坐标；式(19)中，η和σ是初值为0的避障标志变量和转向标志变量；μ为增大系数，仅用于增大标志变量对适应度值的影响，故取值大于1即可，为使增大效果更为直观取值100。当η和σ为0时，不对适应度值产生影响；当η和σ不为0时，增大适应度值。

为了保证机器人路径尽量避免产生锐角路径，减小失控可能，利用式(20)三角形三边关系对路径节点的坐标进行约束。

推导如下：

转向标志变量σ计算方法如下：

通过式(21)判断相邻的路径节点连线的夹角是否小于90°，若小于90°有σ=σ+1；否则σ=σ。

对σ进行迭代，若路径规划过程中σ值恒为初值0，则机器人路径不存在小于等于90的度转向角，反之机器人转向角过小，机器人运动稳定性和可控性降低。

计算机器人当前路径节点与障碍物的距离dk来确定机器人路径是否穿过障碍物（如图1所示），若穿过障碍物则发生碰撞，路径无效，避障标志变量η>0。

η计算流程如下：

步骤1：按式(22)计算机器人路径节点与所有障碍物的距离。式中，dk为机器人运动路径节点距离障碍物的距离；（xobsk，yobsk）为障碍物轮廓圆圆心。

步骤2：按式(23)产生一个大于0集合θk。式中robs为障碍物轮廓圆半径。

步骤3：若集合θk中元素平均值mean（θk）>0，η迭代加1，依据式(24)；否则η保留上一代的值。若迭代过程中η的值始终等于初值0，说明规划的路径均躲避了障碍物，反之路径不满足约束条件。

4 算法步骤

步骤1：初始化蝙蝠种群数量npop、蝙蝠声波响度A、速度vx，vy、声波频率最大值fmax最小值fmin、蝙蝠个体个数d和人工势场斥力系数m、引力系数kx、算法迭代次数t、最大迭代次数Tmax、障碍区个数nobs以及障碍位置坐标

步骤2：初始化蝙蝠坐标位置：

其中xi，yi分别为第i只蝙蝠的横坐标和纵坐标，每只蝙蝠包含d个路径节点，对蝙蝠路径节点x1和路径节点xd分别赋值起点xs和终点xT。初始化人工势场法的斥力系数kc和引力系数kx，障碍物吸引半径dx和排斥半径dc，对障碍物中心设置斥力势场和引力势场。

步骤3：将蝙蝠坐标代入式(22)、式(23)求出只蝙蝠的dk和θk，再利用式(21)、式(24)求出标志变量η和σ，最后代入式(18)路径L长度以及适应度函数的值，并提取最佳蝙蝠的位置坐标。

步骤4：将步骤3中的最佳蝙蝠的位置坐标（路径节点）势场化，加入引力场式(16)、式(17)。利用三次样条插值法求解出S（x）分段函数，将离散的路径节点平滑连接，获得连续平滑的路径。

步骤5：将蝙蝠坐标代入式(1)～式(3)进行位置更新，若阈值P>r，则进入局部搜索策略，利用式(4)、式(14)、式(15)更新声波响度和脉冲速率，更新所有蝙蝠位置坐标和速度；否则直接重复步骤3）。

步骤6：t=Tmax是否成立，是进入步骤7）；否则重复步骤3）。

步骤7：输出路径结果。

步骤8：结束。

5 实验与结果分析

为了验证本文算法在机器人路径规划问题的可行性和有效性，在路径最短、路径无锐角路线、无碰撞的前提下，在相同仿真实验环境、迭代次数、种群规模条件下，对比BA-APF、粒子群算法、基本蝙蝠算法。

5.1 实验参数设置与软件

仿真实验采用操作系统为Windows10，编程环境为MATLAB R2016a。路径规划环境尺寸为2000mm×2000mm、种群规模npop=100、最大迭代次数t=100、路径节点（维度）个数d=20，三种算法上诉取值均保证一致；其中基本蝙蝠算法与势场化蝙蝠算法中的蝙蝠声波响度A0=0.25、r0=0.5、速度vx=0.5，vy=0.5、声波波长根据环境和障碍物大小确定，最后利用波长取值范围，可计算得出声波频率的取值范围（fmax，fmin）=（7000，600）。在PSO算法中，个体经验C1和群体经验C2对结果有重要的影响，参考同类型实验后，本文选用C1=C2=1.5。

5.2 路径规划结果分析

仿真实验分别在单位面积下障碍物密度为N1个/m2和N2个/m2（N1<5，N2>5）的环境下进行。障碍物数量、位置和半径均随机产生。机器人从S点出发到达T点，其中黑色圆为障碍物的轮廓圆，障碍圆心设置斥力势场，终点设置引力场，所获路径结果如图3所示。

图2 算法路径规划对比

表1 障碍物环境在N1个/m2环境下四种算法路径长度对比

通过图2、表1实验数据可得出结论。障碍物密度在N1个/m2的环境的路径规划中，势场化蝙蝠算法（BAAPF）无论在最优解还是平均解中，所获机器人路径的长度、平滑程度或转向角度均优于另外两种算法。机器人路径均满足约束条件，故路径有效。BA-APF路径规划中，存在人工势场的调整和干预，在躲避第二个障碍物时，路径明显优于基本蝙蝠算法和粒子群算法，障碍物中心设置了斥力势场，由于路径节点势场化的调整，路径并没有因此刻意躲避障碍物造成过度转向。势场化蝙蝠算法的路径更为平稳，波动也较小。

障碍物密度在N2个/m2的环境的路径规划中，障碍物数量、位置和半径随机产生。路径结果如图3、图4所示。

图3 十位数量级障碍环境下三种算法路径规划对比

图4 三种算法迭代曲线对比图

表2 十位数量级障碍物环境下四种算法路径长度对比

通过图3、和表1可知，障碍物密度在N2个/m2的环境的路径规划中，算法在路径长度、收敛速度方面均优于对比算法。

如图4所示，对比其他算法BA-APF收敛速度最快，算法第40代时收敛，并求出最优解。得益于算法中加入动态扰动系数g，扰动系数影响了蝙蝠脉冲速率，增大蝙蝠算法进入局部搜索策略次数，相比较BA算法的盲目搜索重复全局搜索策略，改进后的BA-APF算法提升了早期的收敛速度，一定程度的减小了算法迭代次数。

最后验证BA-APF算法在Maklink图论环境下基于Dijkstra算法下使用BA-APF算法二次规划路径。（Maklink图论广泛运用于机器人、飞行航线、船舶航道等问题的路径规划研究和工程中。Dijkstra算法基本思想是按照路径长度增加顺序叠加寻找最短路径，是Makink图论的底层计算算法）。

图5 Maklink图论实现

如图5所示，BA-APF算法在Dijkstra算法规划出的黄色轨迹的基础上二次规划出红色路径。路径成功躲避障碍物，并以最短路径抵达目标。由此可以看出，在Maklink图论中，基于Dijkstra算法下使用BA-APF算法二次规划路径，BA-APF算法也能有效的规划出合理的运动路径。BA-APF算法仍具有一定局限性，BA-APF算法适用于已知环境的路径规划，并规划出适合的路径。但在未知环境中，BA-APF算法需要提前输入未知环境地图的相关参数，或利用SLAM算法完成对实时场景的地图构建后，再利用BA-APF算法完成路径规划并反馈至机器人端完成对未知环境的路径规划。

6 结语

本文利用势场化蝙蝠算法求解机器人路径规划问题的最优解，规划最优路径。利用动态扰动系数g对蝙蝠算法的脉冲速率r进行改进，增加算法进入局部搜缩策略次数，提升算法的挖掘能力，并一定程度减小算法盲目随机搜索，保证了算法较快速收敛。加入人工势场思想策略，对蝙蝠算法中位置路径节点进行势场化处理，路径节点之间转角进一步减小，同时对障碍物添加斥力势场的基础上加入应力势场影响机器人路径。最后，利用插值法平滑曲线，多次迭代求得算法最优解。建立了在多种环境下机器人路径规划的可行性方案。实验结果表明，基于势场化蝙蝠算法的路径规划求解性能优于对比算法。