改进蝙蝠算法的无人机路径规划

丁元明,侯孟珂

(1.辽宁省通信网络与信息处理重点实验室,辽宁 大连 116622; 2.大连大学 信息工程学院,辽宁 大连 116622)

0 引言

无人机的路径规划是无人机(unmanned aerial vehicle,UAV)根据飞行任务的要求,在综合考虑各种因素和条件下,找到一条无人机从出发点到目标点的最优飞行轨迹[1]。目前国内对无人机路径规划优化算法设计进行了大量的尝试和突破,但仍存在求解精度和搜索时间难以平衡这一较大的局限性。未来UAV航迹规划的发展趋势应该兼顾计算快、精度高、容错率高等特点。

规划决策可以将无人机路径规划算法分为传统经典算法和现代群智能算法等2类[2]。现代群智能算法成为当前UAV路径规划优化的主要手段[3]。结合约束条件、环境模型、目标函数,再利用群智能算法以及迭代技术求解最优无人机路径。群智能技术已被证实在解决具有挑战性的优化问题方面是非常有效的[4]。最近,受不同动物群体行为的启发,一些基于群智能的算法被开发并在文献中提出,如人工蜂群(artificial bee colony algorithm,ABC)[5]、布谷鸟搜索(cuckoo search,CS)[6]、萤火虫算法(firefly algorithm,FA)[7]、粒子群算法(particle swarm optimization,PSO)、蝙蝠算法(firefly algorithm,BA)等。这些群智能算法正在不断地在无人机路径规划中得到应用。PSO在无人机路径规划中因搜索效率高而得到广泛应用,但算法结构缺陷,容易陷入局部极值问题[8-12]。文献[8]提出了改变粒子群拓扑结构的改进PSO结构的算法。大量的粒子和更加复杂的拓扑结构也使得搜索时间的增加,求解速度变慢。文献[9]提出了一种通过动态分治策略和A*算法改进的PSO优化算法。但算法复杂度变高,求解速度变慢,求解精度和速度难以平衡。文献[10]为了提高PSO的收敛速度和寻优能力,在粒子种群个体中引入了质心的概念,并通过柯西变异运算对粒子进行但算法加重了粒子种群个体的信息负载,算法冗杂。文献[11]是将PSO和细菌觅食(bacterial foraging algorithm,BFO)算法进行结合,再引入迁徙算子,会在粒子群陷入局部最优时使得算法有跳出局部最优的能力,增大了算法结构复杂度,求解速度变慢。文献[12]针对PSO解决维数递增问题,提出了一种结合模糊C均值( fuzzy c-means algorithm,FCM)算法的改进粒子群算法。但是改进之后的算法依然容易陷入局部极值。PSO兼容性强、执行效率高等优点被广泛应用与UAV航迹规划上,但传统PSO存在容易过早收敛和容易陷入局部极值的问题。

2010年Yang教授提出了新的群智能启发式算法,即蝙蝠算法(BA)[13]。BA在迭代搜寻最优解过程中,在最优解周围通过随机飞行产生局部最优解,加强局部搜索,可以极大程度地避免算法陷入局部极值[14]。但由于BA算法在局部搜索上精细搜索,因此求解速度较慢,没有平衡求解速度和求解精度。文献[15]提出一种基于差分进化的蝙蝠算法(DEBA)。通过应用这些策略,蝙蝠种群的种群信息得到了充分的利用,探索能力得到了相对提高。经过策略改进之后的DEBA搜索无人机航迹规划路径的成功率有所降低,求解速度会有所变慢。文献[16]提出了一种将差分进化中的变异引入BA的混合元启发式算法,并利用BA来挖掘种群信息,变异之后的算法仍然没有提高求解速度。

1 飞行空间模型与目标函数

为了测试算法的可靠性,健壮性,需要建立起模拟真实环境中的飞行空间模型。保证UAV安全、有效到达目标点,需要实现在飞行长度约束、飞行高度约束、威胁区距离约束、山地环境约束条件下,无碰撞安全的到达目标点位。将搭建飞行空间模型和目标函数数学模型模型。

1.1 飞行空间模型

在全局空间模型中,山地地图是空间建模的重要部分,采用文献[17]中的山地建模方式,如图1所示。

图1 山地仿真地图

由于在实际飞行过程中,环境是变化的,该山地模型中的山峰随机产生,增加了环境随机性,对路径规划算法的健壮性、普适性有更加严格的要求。其数学模型为:

(1)

式(1)中:(xi,yi)为第i个山峰的中心坐标;n为随机生成山峰的个数;hi为地形参数,控制第i座山峰的高度;xsi、ysi分别为随机生成的第i个山峰沿着x轴方向和y轴方向的山峰坡度。并对山体的表面进行了平滑处理。

无人机在飞行过程中 需要依据山势保持安全距离,即提升安全高度h。由于飞行燃油、飞机性能的限制,UAV不能无限制的升高,因此0

H(x,y)=z(x,y)+h

(2)

式(2)中,H(x,y)为飞行的安全高度,与山体有一定距离,实现安全飞行。并且h

1.2 目标函数

UAV飞行路径是指在约束条件下生成最优飞行路线,其目标是在合理的时间、成本内找到UAV的最优飞行路线。在飞行过程中,要考虑飞行成本。飞行成本主要分为3个部分:飞行路径长度成本、威胁区成本和飞行高度成本。总成本函数用W表示。最小成本函数Wmin可以表示为

Vmin=k1VL+k2VT+k3JH

(3)

式(3)中:VL为飞行路径长度成本;VT为威胁区成本;VH为飞行高度成本;k1、k2、k3为比重权值,0

飞行路径长度成本为

(4)

式(4)中:VL为飞行路径长度成本,总飞行路径的长度被分成n段路径轨迹段;lij为轨迹段的长度所花费的成本。

威胁代价VT为

(5)

式(5)中:tk为威胁因素,也是威胁源和无人机节点之间威胁级别的度量;Nt为威胁源总数UAV坐标为(x,y,z),威胁源中心的坐标为(xk,yk,zk)。

飞行高度代价JH为

(6)

式(6)中:H为无人机飞行安全回路的高度,无人机的飞行高度不应超过该高度;W0为无人机在一定高度下的能源成本;h为无人机的当前高度。

2 改进蝙蝠算法

2.1 经典算法

2.1.1经典粒子群算法

PSO是一种基于种群的智能随机算法,PSO模拟种群行为在搜索空间中进行全局搜索和局部开发,并根据目标函数得出当前搜索周期内的全局最优gbest和个体最优pbest;并根据前一代的gbest、pbest决定下一代粒子,最终得出最优解。粒子的速度和位置更新公式为

(7)

式(7)中:k为粒子迭代次数;w为惯性权重;c1为局部速度参数;c2为全局速度参数;r1和r2为0～1的随机值的数。

2.1.2基本蝙蝠算法

蝙蝠算法(BA)的灵感来自于自然界中的蝙蝠,是通过模拟蝙蝠回声定位抽象出的群智能算法。算法利用与飞行相关的变量代替蝙蝠避障飞行中的回声频率,并根据声波频率和当前全局最优解更新迭代下一代的速度与位置,最终得出最优解。模拟蝙蝠回声频率的参数迭代公式为

fi=fmin+(fmax-fmin)×β

(8)

式(8)中:β为一随机值,且满足β∈[0,1];fi为蝙蝠发出的声波频率;fmax为频率最大值;fmin为频率最小值。可以看出fi会在fmax到fmin的范围内取值,随机跳动,以保证了飞行搜索的随机性。

1) 在随机飞行搜索过程中,蝙蝠个体在时间节点t处的位置和速度的更新公式为

(9)

(10)

2) 在局部搜索阶段,若蝙蝠在全局最优解处时,蝙蝠个体根据响度A更新位置。

xnew=xold+εAk

(11)

3) 参数更新。接受新解,则代表着更进一步靠近最优解,则降低响度,并不断增加回声发射速率ri,其更新公式为

(12)

(13)

2.2 改进蝙蝠算法

本文中改进蝙蝠算法(PSOBA)保留了蝙蝠算法的全局搜索和局部搜索的搜索过程。但PSOBA算法允许在全局搜索过程加入种群个体最优的因素。传统BA算法回声频率fi是对全局最优解的调整,其本质还是趋向于对全局最优解的搜索,降低了搜索的随机性,容易使算法过早收敛,导致求解的精度有所损失。

1) 在全局随机搜索过程中,PSOBA引入个体最优的概念,本质上扩大了搜索的范围,如图2所示。当种群进行迭代时,x*以及回声频率f都是指向全局最优,从而导致原BA搜索前期收缩快。加入个体最优,分担了快速靠近全局最优的比重,增加了路径搜索的广度。但前一代的个体最优搜索方向与搜索的目标方向是相同的,对算法的搜索效率不会有太大的损失。

图2 PSOBA搜素示意图

在PSO中有明确的全局最优和个体最优的定义。由PSO中个体最优的定义出发改进BA,则PSOBA在随机全局搜索的速度与位置迭代模型为

(14)

由式(14)可以得出,速度迭代加入了个体最优的因素,使得种群搜索的方向不再单一指向全局最优,种群整体的搜索范围覆盖更广。继而在无人机飞行过程中获取更多信息,从而进行有效飞行。

2) 在局部搜索阶段,PSOBA也引入了取值在0～1的均匀分布数R1,若R1>r1,则开始局部搜索,否则继续全局随机搜索。并且PSOBA算法对xnew的更新进行重定义为

(15)

式(15)中:R2为0～1服从均匀分布的随机数;k为当前迭代次数;K为最大迭代数;C(-1,0)是服从标准柯西分布的随机数,范围为-1到0;N(0,1)是服从高斯分布的随机数,范围为0到1。

2.3 最优成功率策略动态调整惯性权值

OS-PSOBA算法虽然在全局随机搜索过程中加入了个体最优的变量,增加了路径搜索的广度和随机性,但降低了上一代种群速度对当前种群速度影响的比重,没有动态继承上一代种群的优势。若上一代种群搜索结果较好,但没有继承或延伸优势,就会延长搜索时间;降低了PSOBA的搜索精度。若上一代种群搜索结果很差,在搜索前期个体最优和全局最优的比重较小,则迭代种群也会继承上一代种群的劣势。因此,将惯性权值引入到PSOBA的速度迭代更新中,并利用最优成功率策略对其自适应动态调整,即OS-PSOBA。

首先在式(14)中引入惯性权值,有

(16)

式(16)中:w为加入的惯性权值。

进而,将最优成功率策略用于动态调节惯性权值w,这使得惯性权重与种群的最佳成功率相关。最优成功率策略动态调节的自适应惯性权重为

(17)

(18)

(19)

OS-PSOBA通过最优成功率策略动态的调整w,使得种群按照k-1代的搜索结果进行收敛搜索,或是靠近全局最优和个体最优进行发散搜索,并在搜索过程中维持种群搜索的多样性,整个搜索路径的过程形成一个外部稳定,核心自适应动态调整的整体。

2.4 改进蝙蝠算法的无人机路径规划流程

本文中提出 OS-PSOBA流程如图3所示。

图3 PSOBA算法流程图

OS-PSOBA算法具体步骤描述如下。

步骤1初始化种群,包括种群个体规模N,最大迭代数k,局部加速因子c1和全局加速因子c2,回声频率f的最大值与最小值以及惯性权值w。

步骤2根据目标函数,即式(3)计算种群各个个体的适应度。

步骤3按照个体适应度进行对比,找出个体最优解pbest以及全局最优解gbest。

步骤4判断最优解的随机数R1是否大于脉冲发射频率r。若R1>r,则将在最优解附近随机飞行;若R1

步骤6按照式(16)对种群个体的速度和位置进行迭代更新。

步骤7如未达到结束条件(通常为足够好的适应值或达到一个预设的最大迭代数),则返回步骤2,直至达到结束条件,找出最优路径。

3 模拟实验与讨论

为了验证OS-PSOBA的可行性和有效性,在i7-7700HQ CPU和8 G内存的计算机上,利用Matlab进行算法的仿真实验。在二维、三维空间环境中,且在多种约束下对PSOBA算法进行仿真实验,最后设置PSO、BA、OS-PSOBA的对比仿真实验。

3.1 二维空间下的仿真实验

为了快速了解OS-PSOBA的性能,先对OS-PSOBA进行简单二维环境下的无碰撞、避障仿真实验。实验中设置威胁区,并利用二维环境下的B样条曲线进行平滑处理,从而得到UAV飞行路径轨迹。二维环境下的实验参数如表1所示。

表1 PSOBA算法参数

二维空间仿真中,起始坐标为(0,100),目标点位(400,450)。设置7个威胁区域,其中心坐标分别为(250,150)、(100,100)、(300,350)、(50,300)、(400,100)、(170,300)、(156,207)、威胁半径为60、65、70、50、60、30、20。二维空间下仿真结果如图4所示。

图4 二维空间下UAV路径规划

图4中平滑曲线为无人机路径轨迹,圆圈为仿真模拟的威胁区域和障碍区域。轨迹与威胁区无交叉、重叠点,二维环境下可以完成避障,躲避威胁区的任务目标。且在躲避后可以回归原定规划路线。得到路线尽可能短、平滑、无突变,符合路径规划要求。并且成功到达目标点。

3.2 三维空间下的仿真实验

3.2.1随机变换三维空间下仿真实验

构建三维空间模型,利用随机生成山峰,得到不同的三维山地空间。按照OS-PSOBA算法进行山地环境下的UAV路径规划,起始坐标为(1,1,1),终点为(100,100,80),仿真结果如图5所示。图5(a)、图5(b)分别为同一山地环境下的正视图和俯视图,图5(c)、图5(d)也是同一山地环境下的正视图和俯视图,图5(a)与图5(c)是不同山地环境下的路径规划仿真结果。红色曲线为无人机路径规划轨迹,轨迹平滑、无突变,符合无人机飞行转角约束。并且从起始点成功到达目标点位,没有与山地交叉点位,无山体碰撞。飞行轨迹与山峰保持安全距离的同时,不会越过山峰,飞行成本更低,航迹更加隐蔽。

图5 随机三维环境下仿真

3.2.2复杂三维空间下避障仿真实验

构建更加复杂的三维空间,增加山地的崎岖程度,并且在山地中增加威胁区,威胁区在三维空间中建模为半球状,威胁区在此表示为(x,y,z,r)。r代表威胁半径。2个威胁区坐标分别为(230,190,350,50)(207.1,333.3,389.9,30)、(410,330,349.2,50)。UAV飞行起始点坐标为(15.15,30.3,349.9),目标点坐标为(449.5,459.6,422)。仿真结果如图6所示,黑色曲线为UAV飞行轨迹,黑色半球状为威胁辐射区。无人机可以在进行山地无碰撞飞行的同时,避开威胁辐射区,从起始点成功到达目标点。

图6 复杂三维环境下避障仿真实验

3.3 三维环境下对比实验

为了验证OS-PSOBA的实际优越性进行对比仿真实验。算法与BA和PSO算法进行对比仿真实验。构建三维空间环境模型。为了保证对比实验的公平性,只改变路径规划算法这一差异,设置迭代次数相同、种群数目相同、实验仿真环境一致,具体参数如表2所示。

表2 对比实验参数设置

对比实验进行5次,以避免偶然性对实验结果产生影响。每次将对比实验结果的路径长短、路径搜索时间、目标函数收敛情况和任务成功率作为比较参数。对比实验认为路径中无碰撞、无断点,轨迹平滑,且从目标点成功到达目标点即为成功,运行结果如图7所示。

图7 三维空间下算法路径对比图

图7(a)、图7(b)、图7(c)为5组对比试验的一组仿真结果。通过对比实验可以得出3种算法都可以得出平滑的UAV航迹,并且完成飞行任务,3种算法都具有一定的鲁棒性。但OS-PSOBA(黑色曲线)相比于PSO(红色曲线)、BA(蓝色曲线)可以看出,可以得到最短的UAV飞行轨迹。在相同UAV的条件下,OS-PSOBA可以更快地完成飞行任务,故OS-PSOBA搜索精度得到提升。

图8为3种算法在相同实验环境下5组对比仿真实验的UAV飞行路径长度。由图8可以明显看出,OS-PSOBA所搜索到的路径长度短于其余2种算法的路径长度,则表明OS-PSOBA求解精度要高于BA和PSO。求解精度越高,才能在避开飞行障碍,符合飞行和环境约束条件下,飞行路径更短。进而路径长度结果证明OS-PSOBA在UAV路径搜索可以提高搜索精度。

图8 算法路径长度统计图

表3中数据分别是3种算法在5组对比实验中的路径搜索时间。可以明显的得出,OS-PSOBA使用的时间要要少于PSO和BA的路径搜索时间。仅由搜索时间可得,OS-PSOBA平均搜索时间比BA提升约9%,相对于PSO搜索时间提升了约18%。因此,利用OS-PSOBA进行无人机路径规划可以提高搜索速率。

目标函数值收敛曲线比较图如图9所示。OS-PSOBA算法得到的飞行成本目标函数曲线一直处于PSO、BA算法函数曲线之下,证明OS-PSOBA算法可以降低飞行成本。由于飞行成本大多是由飞行距离和飞行高度决定,侧面证明OS-PSOBA算法所搜寻路径,距离短、精度高。

图9 目标函数值收敛曲线比较图

4 结论

改进之后的蝙蝠算法OS-PSOBA可以有效地解决无人机路径规划搜索中,搜索精度和搜索速度难以平衡的问题。结论如下:

1) 在全局随机搜索中,加入个体最优因素,避免了搜索过早收敛,增加了路径搜索的广度,提高了算法的精度。

2) 在局部搜索过程中,路径搜索依靠于高斯分布和柯西分布,集中逼近最优解,减少了搜索次数,提高了搜索速度和搜索精度。

3) 在此基础上,通过最优成功率策略调节,避免了不必要的迭代搜索,使得搜索速度和精度再次提升。实验仿真证明,OP-PSOBA算法可以使无人机路径规划搜索精度和搜索速度双提升。