Research on robot path planning based on bat
algorithm and artificial potential field
李昶威，甘 屹，孙福佳，张鹏举
LI Chang-wei, GAN Yi, SUN Fu-jia, ZHANG Peng-ju
（上海理工大学，上海 200093）
摘 要：为优化机器人路径规划全局最优问题，将人工势场法思想融入到蝙蝠算法中，建立基于人工势
场蝙蝠算法（Bat Algorithm-Artificial Potential Field，BA-APF）：在蝙蝠算法的脉冲速率中引入动态扰
动系数g，加强算法的局部搜索能力，在蝙蝠位置更新公式中加入引力势场系数，以加快算法收敛速度；在目标终点加入引力系数，障碍物加入斥力系数，以保证路径躲避障碍并到达终点。BA-APF首先随机生成初始蝙蝠种坐标，以路径最短、避开障碍物和危险区域，避免路径出现锐角转角为约束条件，在满足约束条件前提下构建合理的适应度函数。然后，BA-APF随机生成初始蝙蝠种坐标，将初代蝙蝠坐标带入势场化蝙蝠算法，通过对比适应度值求出初代最佳蝙蝠个体。若满足局部搜索条件，则更新脉冲速率和声波响度并开始局部搜索策略，否则重复对蝙蝠位置和速度进行更新迭代，在优化后的路径和原最优路径进行适应度值中取其优值，并对路径进行三次样条插值使路径平滑衔接。最后，在随机障碍环境下，分别对BA-APF、粒子算法、基本蝙蝠算法进行路径规划实验对比。结果表明，BA-APF在求解最优解以及算法迭代速度上，均优于对比算法。
关键词：路径规划；人工势场法；蝙蝠算法；三次样条插值中图分类号：TP391.9 文献标识码：A 文章编号：1009-0134(2021)02-0076-06
收稿日期：2019-09-03
基金项目：国家自然科学基金项目（51375314）
作者简介：李昶威（1994 -），男，广东人，硕士，研究方向为智能制造。0 引言
近年来智能机器人领域发展飞速，移动机器人在各个领域中都得到了广泛的应用和发展，如智能仓储、货物码垛、无人机侦查、未知环境探索、深海探索、机械加工等，例如，焊接机器人利用粒子算法实现焊接过程中避障的路径规划[1]
；矿山救援机器人利用改进遗传算法实现在矿山救援任务中的路径规划问题[2]。在考虑到环境的复杂，障碍物交错，机器人自主寻出一条安全、可靠的最短路径是机器人研究中的关键技术。工程中，最短路径可以节约机器人运动过程的时间成本，提高工作效率；路径减少锐角转向，可减少机器人运动过程中不必要的损耗，减少后期维护成本。国内外学者对机器人路径规划问题做了大量的工作并取得不少成果
并运用到了各个领域中。A*算法、传统人工势场、强化学习方法、深度学习方法[3～5]等是较常用的路径规划算法，这些算法或多或少存在着难以满足实际要求的问题。如A*算法复杂度较大，内存占用量大，不适用于追求灵活运动的小型系统的机器人的路径规划中。基本人工势场法在迭代过程中容易陷入局部最优解，产生路径震荡[4]。近年来，机器人路径规划研究逐渐向仿生智能算法转移，对于机器人路径规划问题上，仿生智能算法更具有先天优势。如蚁算法、人工鱼算法、遗传算法、粒子算法[6,7]等。粒子算法容易陷入局部最优解，蚁算法搜索迭代时间长，容易停滞等缺点。因此研究对环境适应性强、算法步骤简单、求解速度快和路径最短成为研究者们追求的目标。
1 基本算法
1.1 蝙蝠算法
蝙蝠的生物学机理较简单，集生活，通过声波回声定位和搜索猎物，搜索猎物时发射低频脉冲。剑桥学者Yang 于2010年，根据模拟蝙蝠回声定位的仿生学机理提出了蝙蝠算法[3]。蝙蝠全局搜索猎物时，发射低频脉冲，声波响度大，能量损耗小，传播距离长，能快速锁定猎物大致方位。当声波传递到猎物后，蝙蝠接收回传声波信号，结束全局搜索。此时开始局部搜索，并发射高频脉冲。高频脉冲的特点是，声波响度小，声波间距小，传播距离短，能量损耗大。声波间距小，对于猎物的形状大小能精确检测。蝙蝠利用随机飞行策略将猎物距离告知其他蝙蝠，同时更新位置和速度。目前蝙蝠算法已经在电力系统广域协调控制[6]
、AGV 物料配送调度[8]
、车辆调度路径[10]等领域得到了实际的应用。
基本的蝙蝠算法中，蝙蝠体中单一个体被视为单一的粒子，粒子无质量和体积，仅代表空间中的每一个目标函数的一个可行解，通过比较目标函数值的大小，即可判断蝙蝠位置是否处于最优位置。蝙
蝠飞行过程中不断更新自身位置和速度，因此在机器人路径规划的求解过程中可以利用蝙蝠飞行、捕捉猎物的一系列行为进行类比。蝙蝠算法的仿生思路为：蝙蝠开始搜索猎物时发出声波响度大，脉冲频率低的声波，为了能在一个较大空间中寻全局最优；在发现猎物后，降低声波响度，提高脉冲频率，为了能在局部空间精确寻定位猎物。
在此，由于蝙蝠发出的声波是间断的，脉冲频率是指单位时间内声波的频数，而不指声波震动的频率，声波频率取决于蝙蝠种类。
蝙蝠算法规则为：蝙蝠在d 维空间中寻猎物，即适应度函数的最优解。假设在t 时刻，第i 只蝙蝠位置为x t i ，其速度为v t i ，当前最优位置为x *，更新位置和速度公式如下：
(1) (2)
(3)
其中，f i 为第i 只蝙蝠发出的搜索声波频率，f max 为蝙蝠搜索声波的最大频率，f min 为蝙蝠搜索声波的最小频率，因此f i ∈[f min ，f max ]。
当蝙蝠发现猎物，通过改变声波响度和脉冲速率使全局搜索策略转变为局部搜索策略。减小声波响度，增大脉冲速率，进行局部搜索，遵循以下公式：
t i
t i
A A
⋅=+α1
(4)
(5)
其中，A t i 为第i 只蝙蝠在t 时刻的声波响度，A i t+1为第i 只蝙蝠在t+1时刻的声波响度；任意值α∈（0，1），为声波响度衰减系数；任意值γ>0，为脉冲速率增强系数；r i t+1为第i 只蝙蝠在t+1时刻的脉冲速率，r 0i 为第i 只蝙蝠在初始时刻的脉冲速率。其中迭代次数逐渐趋向于无穷时，A t i 趋于0，蝙蝠发射频率r i t 趋于初始脉冲速率。
这里需要再次强调的是，蝙蝠的搜索声波频率f 和蝙蝠脉冲速率r 是有非常大的区别。f 指的是蝙蝠搜索时发出的一小段声波的频率，取值取决于需要解决的实际问题；r 指的是蝙蝠每秒发出声波的数量，局部搜索时，r 将逐渐增大，直至到最优解，取值等于最大值。1.2 人工势场法
人工势场法是通过设定终点坐标为引力势场，设定障碍物为斥力势场，寻躲避障碍物无碰撞的最优路径。随着机器人运动过程中逐渐靠近障碍物，机器人和障碍物的距离越近，斥力越大，反之越小；机器人躲避障碍物后逐渐靠近终点，机器人和终点的距离越近，引力越小，反之越大。基本人工势场法算法定义如下：
引力势场函数U gra ：
(6)
其中机器人当前位置为X=（x ，y ），终点位置为X g =（x g ，y g ），k 为大于零的任意引力场常数。
斥力势场函数U rep ：
(7)三爪卡盘结构
其中m 为大于零的任意斥力场常数，ρ为机器人到
障碍物的距离，0ρ为障碍物的最大影响半径。在引力势场和斥力势场的共同作用下，机器人受斥力和引力，朝合力最大的方向运动最终到达终点。1.3 三次样条插值
三次样条插值用于平滑机器人路径，从起点到终点上给定区间[a ，b]上分割成n 个插值点满足：
b x x x x x a T n S =<<<<<= (21)
(8)
若满足以下条件，则在[a ，b]上的一个函数S （x ）就称为三次样条插值函数。
1）每个区间（x i ，x i+1）（i=1，2，3，…，n ）中，都有三次多项式函数：
32)()()()(i i i i i i i x x d x x c x x b a x S −+−+−+=
(9)
2）S（x）、S'（x）和S''（x）在[a，b]上连续，且满足
插值条件：
(10)
连续性条件：
(11)
(12)
(13)
其中满足插值条件的方程个数共有n+1个，满足连续性条件的方程个数共有3n-3个，因此共可建立4n-2方程，加上边界条件后共有4n个方程，因此可求解出分段函数S（x）。
2 基于人工势场的蝙蝠算法（BA-APF）
和其他路径规划的集智能算法相似，蝙蝠算法在寻优的过程中，存在种多样性和算法深度挖掘能力之间存在矛盾，两者难以兼顾。对于路径规划算法的改进目标都是针对保证种多样性和算法的快速收敛性，同时避免局部最优。本文对蝙蝠路径节点进行势场化处理，引入扰动系数g改进r
i
脉冲速率，提高算法的挖掘深度能力。对相邻两个路径节点[15]加入引力势场。建立基于人工势场的蝙蝠算法（Bat Algorithm-Artificial Potential Field，BA-APF）模型。对算法迭代Tmax次，最后求得最优解。
2.1 动态扰动系数
当蝙蝠发现猎物，即将接近全局最优解时，基本蝙蝠算法将在最优个体附近开始局部搜索策略。此时生成均匀分布的随机数P作为判断阈值[16]，当P>r时，使用局部策略，否则重复全局搜索。因此，基本蝙蝠算法中蝙蝠是否进入局部搜索，完全取决于r值的取值。若r值的大小在算法前期一直保持一个较小的值，则可以增大算法进入局部搜索策略概率，较有效防止算法局部最优，同时满足蝙蝠算法要求。
BA-APF首先通过式(14)对蝙蝠脉冲速率r0i加入余弦
扰动系数，改进基本蝙蝠算法中的脉冲速率r0
i
的取值方式，具体如式(15)所示：
(14)
(15)
其中，t是当前迭代次数，T
max
是最大迭代次数。g 值随着迭代次数的增加而自适应的增大，在算法前期扰短信认证
动影响较小，在算法中后期仍然保持r t
i 在一个相对较小
的范围中，例如，max
2
1T
电容式触摸屏结构
t=时，7.0
)
4
cos(=
−
=π
g，引入
扰动系数后的r t
i
是基本蝙蝠算法中r t
i
的0.7倍。改进蝙蝠
脉冲速率r后，B A-A P F算法保证扰动系数g满足
1≥g>0，每次迭代过程都能保证r t i系数的取值相比基本
蝙蝠算法所获得的取值更小，并能满足基本蝙蝠算法脉
冲速率r t
i
的取值条件：r t
i
保持增大到设定值r0
i
。
2.2 基于人工势场的改进
在机器人路径规划过程中，基本人工势场仅仅对障
碍物和终点设置斥力场和引力场[17]。然而，当机器人所
处的某点的引力势场和斥力势场大小相等方向相反时，
基本人工势场法容易发生锁死，无法求解；当陷入障碍
物斥力场范围叠加时，机器人路径容易发生震荡。
为同时保证BA-APF算法过程中路径尽可能平滑，
在BA-APF算法中引入人工势场，设置相邻两个路径节
点势场。
具体方法如下：
1）按式(6)对目标点设置引力势场。
2）按式(7)对障碍物中心设置斥力势场，影响半径
为障碍物半径。
3）路径势场化，方法如下：
对蝙蝠算法计算过程中的路径节点x t
i-1
和x t
i-1
（t >1）
peepm
设置引力场，该引力场仅对相邻的两个点产生作用。则
x t i所受的合力方向指向障碍物，使得更新后的下一代蝙
蝠路径节点将向合力方向运动，以获得更短的路径。如
图1
所示。
图1 路径节点势场化示意
路径节点的设置方法如下：
对x t
i-1
设置引力场：
(16)
对x t
i+1
设置引力场：
(17)
X t i 为第t 代的路径节点坐标，算法计算中X t i 产生的引力场仅对相邻的两个路径节点有效。
3 适应度函数的构建
机器人路径规划需要避免与障碍物碰撞、寻求路径最短和避免出现急转。为保证路径有效、最优以及机器人运动稳定性，BA-APF 算法重复迭代t 次，每一只蝙蝠代表一条机器人路径均要求通过适应度对比计算来判断路径优劣。BA-APF 算法需要求满足上述条件，路径规划的适应度函数构造如下： ∑=++−+−=n
j m m m m y y x x L 12
12
1)()(
(18)
)1(µσηµ+⋅+⋅=L z
(19)
其中，式(18)中，L 为机器人路径总长度；（x m ，y m ）为机器人路径节点坐标；式(19)中，η和σ是初值为0的避障标志变量和转向标志变量；μ为增大系数，仅用于增大标志变量对适应度值的影响，故取值大于1即可，为使增大效果更为直观取值100。当η和σ为0时，不对适应度值产生影响；当η和σ不为0时，增大适应度值。
为了保证机器人路径尽量避免产生锐角路径，减小失控可能，利用式(20)三角形三边关系对路径节点的坐标进行约束。
222cos 2c ab b a =++ϕ
(20)
推导如下：
当路径角度2
π
ϕ>时，满足约束条件，故有
2
22c b a >+。
转向标志变量σ计算方法如下：
通过式(21)判断相邻的路径节点连线的夹角是否小于90°，若小于90°有σ=σ+1；否则σ=σ。
2
2112112212
12
2121])()[(])()[(])()[(−+−+++−−−+−>−+−+−+−m m m m m m m m m m m m y y x x y y x x y y x x (21)
对σ进行迭代，若路径规划过程中σ值恒为初值0，则机器人路径不存在小于等于90的度转向角，反之机器人转向角过小，机器人运动稳定性和可控性降低。
计算机器人当前路径节点与障碍物的距离d k 来确定机器人路径是否穿过障碍物（如图1所示），若穿过障碍物则发生碰撞，路径无效，避障标志变量η>0。
η计算流程如下：
步骤1：按式(22)计算机器人路径节点与所有障碍物的距离。式中，d k 为机器人运动路径节点距离障碍物的距离；（xobs k ，yobs k ）为障碍物轮廓圆圆心。
2121)()(k m k m k yobs y xobs x d −+−=++
(22)
步骤2：按式(23)产生一个大于0集合θk 。式中robs 为障碍物轮廓圆半径。
−=0,1robs d MAX k k θ
(23)
步骤3：若集合θk 中元素平均值mean （θk ）>0，η迭代加1，依据式(24)；否则η保留上一代的值。若迭代过程中η的值始终等于初值0，说明规划的路径均躲避
了障碍物，反之路径不满足约束条件。
1+=ηη (24)
4 算法步骤
步骤1：初始化蝙蝠种数量npop 、蝙蝠声波响度A 、速度v x ，v y 、声波频率最大值f max 最小值f min 、蝙蝠个体个数d 和人工势场斥力系数m 、引力系数k x 、算法迭代次数t 、最大迭代次数T max 、障碍区个数nobs 以及障碍位置坐标
步骤2：初始化蝙蝠坐标位置： T T d m S
i x x x x x x ）
（1
<−=
远程定向强声扩音系统
T T d m S
i y y y y y y ）
（1
<−=其中x i ，y i 分别为第i 只蝙蝠的横坐标和纵坐标，每只蝙蝠包含d 个路径节点，对蝙蝠路径节点x 1和路径节点x d 分别赋值起点x s 和终点x T 。初始化人工势场法的斥力系数k c 和引力系数k x ，障碍物吸引半径d x 和排斥半径d c ，对障碍物中心设置斥力势场和引力势场。
步骤3：将蝙蝠坐标代入式(22)、式(23)求出只蝙蝠的d k 和θk ，再利用式(21)、式(24)求出标志变量η和σ，最后代入式(18)路径L 长度以及适应度函数的值，并提取最佳蝙蝠的位置坐标。
步骤4：将步骤3中的最佳蝙蝠的位置坐标（路径节点）势场化，加入引力场式(16)、式(17)。利用三次样条插值法求解出S （x ）分段函数，将离散的路径节点平滑连接，获得连续平滑的路径。
光通维持率步骤5：将蝙蝠坐标代入式(1)～式(3)进行位置更新，若阈值P>r ，则进入局部搜索策略，利用式(4)、式(14)、式(15)更新声波响度和脉冲速率，更新所有蝙蝠位置坐标和速度；否则直接重复步骤3）。
步骤6：t=T max 是否成立，是进入步骤7）；否则重复步骤3）。
步骤7：输出路径结果。步骤8：结束。
5 实验与结果分析
为了验证本文算法在机器人路径规划问题的可行性和有效性，在路径最短、路径无锐角路线、无碰撞的前提下，在相同仿真实验环境、迭代次数、种规模条件下，对比BA-APF 、粒子算法、基本蝙蝠算法。5.1 实验参数设置与软件
仿真实验采用操作系统为W i n d o w s 10，编程环境为M A T L A B R 2016a 。路径规划环境尺寸为2000mm ×2000mm 、种规模npop=100、最大迭代次数t=100、路径节点（维度）个数d=20，三种算法上诉取值均保证一致；其中基本蝙蝠算法与势场化蝙蝠算法中的蝙蝠声波响度A 0=0.25、r 0=0.5、速度v x =0.5，v y =0.5、声波波长根据环境和障碍物大小确定，最后利用波长取值范围，可计算得出声波频率的取值范围（f max ，f min ）=（7000，600）。在PSO 算法中，个体经验C 1和体经验C 2对结果有重要的影响，参考同类型实验后，本文选用C 1=C 2=1.5。5.2 路径规划结果分析
仿真实验分别在单位面积下障碍物密度为N 1个/m 2
和N 2个/m 2（N 1<5，N 2>5）的环境下进行。障碍物数量、位置和半径均随机产生。机器人从S 点出发到达T 点，其中黑圆为障碍物的轮廓圆，障碍圆心设置斥力势场，终点设置引力场，所获路径
结果如图3
所示。
图2 算法路径规划对比
表1 障碍物环境在N 1个/m 2
环境下四种算法路径长度对比算法最优解最差解平均解BA 271.05322.43296.81PSO 310.26345.62320.63BA-APF
261.59
301.59
285.46
通过图2、表1实验数据可得出结论。障碍物密度在N 1个/m 2的环境的路径规划中，势场化蝙蝠算法（BA-APF ）无论在最优解还是平均解中，所获机器人路径的
长度、平滑程度或转向角度均优于另外两种算法。机器人路径均满足约束条件，故路径有效。BA-APF 路径规划中，存在人工势场的调整和干预，在躲避第二个障碍物时，路径明显优于基本蝙蝠算法和粒子算法，障碍物中心设置了斥力势场，由于路径节点势场化的调整，路径并没有因此刻意躲避障碍物造成过度转向。势场化蝙蝠算法的路径更为平稳，波动也较小。
障碍物密度在N 2个/m 2的环境的路径规划中，障碍物数量、位置和半径随机产生。路径结果如图3、图4
所示。
图3
十位数量级障碍环境下三种算法路径规划对比
图4 三种算法迭代曲线对比图
表2 十位数量级障碍物环境下四种算法路径长度对比算法
最优解最差解平均解BA 326.68379.35340.68PSO
365.38398.71375.45BA-APF
312.97
365.86
337.52
通过图3、和表1可知，障碍物密度在N 2个/m 2的环境的路径规划中，算法在路径长度、收敛速度方面均优于对比算法。
如图4所示，对比其他算法BA-APF 收敛速度最快，算法第40代时收敛，并求出最优解。得益于算法中加入动态扰动系数g ，扰动系数影响了蝙蝠脉冲速率，增大蝙蝠算法进入局部搜索策略次数，相比较BA 算法的盲
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议