The improved bat algorithm for UV-guided UAV path planning

近年来, 随着无人机(unmanned aerial vehicle, UAV)技术、通信技术以及人工智能技术等前沿科技领域的快速发展，无人机路径规划技术已经在战场、救援、航空测绘、农业植保等方面发挥着显著的作用^[1-3]。植保无人机在农田进行农药喷洒任务时会遇到电线杆、树木、房屋等障碍干扰，存在一定的安全隐患。同时考虑无人机执行作业时一次装载的药物和电池容量有限，很难一次飞行就能完成喷洒作业，需要返回补给点进行补给, 因此, 研究植保无人机在作业中的路径规划问题具有重要意义。

无人机在路径规划时会因为复杂的地形、天气等环境的干扰降低对环境感知能力和对地通信能力，因此需要一种辅助的通信手段引导无人机进行路径规划任务并安全降落。参考文献[4]中采用激光雷达勘测地面实现无人机地形匹配，但激光通信要求收发端严格对准且受天气影响较大。无线紫外光通信通过大气分子和气溶胶粒子的散射进行信号传播^[5-6]，具备全天候工作、非直视通信、抗干扰能力强等优点，可以为复杂环境下无人机通信引导提供可靠保证。参考文献[7]中提出了一种基于无线紫外的适应地面环境导航技术，使得无人机在不同地面环境中安全飞行，为紫外光(ultraviolet，UV)在地面环境中的应用奠定理论和技术基础。参考文献[8]中研究了地面传感器网络的上行链路性能，使得无人机能够定期访问该区域，并通过紫外光信号与地面传感器通信。

按照对周围地形的了解，一般可将其划分为两类：全局路径规划和局部路径规划。所谓的全局路径规划，就是在一个静止的、没有冲突的环境中找到最优的路线^[9-10]; 局部路径规划是当出现动态障碍物和突发情况时能够及时避障从而规划出最优路径^[11-12]。目前，在无人机路径规划领域，国内外学者已经展开了大量的研究。随着仿生智能算法的发展和研究，蚁群算法^[13]、遗传算法^[14]、粒子群优化算法^[15]和蝙蝠算法(bat algorithm，BA)等已被广泛用于航迹规划。其中，蝙蝠算法是一种新颖的启发式智能优化方法，它可以模仿蝙蝠的捕食行为来寻求最优的解决方案，且蝙蝠算法具有参数少、结构简单等优点^[16]。参考文献[17]中将差分进化算法应用于蝙蝠算法，且在此基础上提出了一种新的蝙蝠算法，使其具有更好的遗传多样性，以及更强的全局优化能力。参考文献[18]的作者提出了一种带有逆向学习和正切随机探索机制的蝙蝠算法，并在其中引入了动态扰动系数和正切随机探索机制，以增强算法的全局搜索能力，同时还可以防止算法落入局部最小点。但仅仅考虑了机器人的2维路径规划效果。参考文献[19]中将改进蝙蝠算法运用于人工蜂群算法中，使得无人机在3维环境中规划出长度更短、更安全的避碰路径。

为了更好地解决农业无人机安全且高效的路径规划问题，改善蝙蝠算法易陷入局部最小值、寻优精度不够高、算法收敛速度较慢等缺点，并且使得无人机可以在雨、雾、霾等特殊天气条件下进行有效通信，本文作者将无线紫外信号用作无人机导航信号的指引照明，以克服全球定位系统(global positioning system, GPS)信号的不足，提出了一种改进蝙蝠算法的紫外光引导无人机路径规划方法。首先建立无线紫外光飞行路径引导系统确保无人机对地信息交互能力，然后在蝙蝠算法中引入基于指数递减策略(the improved bat algorithm，IBA) 的动态惯性权重，且在相邻路径点中引入人工势场，避免陷入局部最优。通过在2维环境、突发障碍物干扰环境以及3维复杂环境下对无人机进行的路径规划仿真对比实验分析，可知基于指数递减策略的改进蝙蝠算法(the improved bat algorithm based on exponential decline strategy，EDS-IBA)具备较小的飞行代价和更好的寻优能力。

无线紫外光飞行路径引导系统如图 1所示，主要包括紫外光信号发射模块、大气信道和紫外光信号接收模块。信号发射模块和紫外信标引导装置包含编码子模块、调制子模块、驱动电路和紫外发光二极管(light-emitting diode, LED)装置^[7]。信号接收模块包含光电倍增管(photomultiplier, PTM)、译码子模块、功率测量子模块和运算模块，功率测量子模块中又包含三轴传感器。各子模块通过电信号依次连接和信号传输。UV光信号发射模块安装在地面上的紫外路径引导装置上，紫外光信号接收模块搭载在无人机上。

Figure 1.  Wireless UV light flight path guidance system

如图 2所示, 信标引导装置为紫外光半球形多输入多输出(multiple-input multiple-output, MIMO)结构，顶部全向接收，该结构在经纬线交点处安装紫外LED。每个LED都有不同的身份编号(identification, ID)，ID编号中的前者代表经线号，后者代表纬线号，每一个LED点亮后, LED即以某种编码方式发出含有自己ID的消息^[7]。当LED经纬编号一定时，固定高度上LED发射紫外光锥位置随之确定，并向LED输入相应位置地形信息，无人机便可根据收到的紫外光得到相应的地形信息。

Figure 2.  Hemispherical UV LEDs^[7]

该系统运用在农业无人机等特殊场合，图 3所示为飞行区域1/4范围内的紫外飞行引导装置示意图。紫外光LEDs发出的紫外光呈半球形覆盖在飞行区域上空，无人机在上空飞行时会经过由紫外LEDs发出的紫外势场，紫外势场包含有该区域对应的地形和其它障碍物干扰信息，搭载到无人机上的紫外接收模块接收到携带信息的紫外光，根据地形和障碍物干扰信息调整自身飞行状态，从而引导无人机安全飞行和降落。

Figure 3.  Schematic diagram of UV-guided UAV

蝙蝠算法是利用群体智能思想实现的一种启发式搜索算法，可有效地搜索全局最优解^[20]。蝙蝠个体通过改变声波的频率、响度和脉冲发射率来搜索最优解。该算法本质上是优化和搜索过程中的迭代过程，用更好的可行解替换不合适的可行解^[21]。

对于虚拟蝙蝠个体在多维搜索空间t时刻下，第i个蝙蝠发声频率f_i、速率v_i和位置x_i的更新公式为：

对于发声频率的更新中，β是一个服从均匀分布的随机变量，满足β∈[0, 1]；f_max与f_min为初始发声频率的最大值与最小值；x^*是当前全局最优解的位置，蝙蝠个体根据自身上一时刻所处的位置与全局最优解x^*的接近程度来衡量其向最优解运动的加速度；而下一时刻的运动速度还受到上一时刻速度的影响。

上面介绍了蝙蝠种群在解空间中全局搜索时遵循的迭代机制，全局最优解周围的蝙蝠利用随机游走法生成局部新解：

式中，ε∈[－1，1]是一个随机数；A_t=〈A_i，t〉是所有蝙蝠在t时刻的平均响度。

t时刻蝙蝠个体发声响度随频率变化更新计算公式如下:

式中，r_t=〈r_{i, t}〉是所有蝙蝠在t时刻的平均发声频率；α与γ均是常量，通常取α=γ=0.9。可以看出，当蝙蝠向最优解无限逼近时，蝙蝠的发声响度会逐渐降低，直到到达最优解时停止发声，而发声频率则随着时间推移不断接近初始脉冲发声频率r_{i, 0}。

对于群智能算法中的全局搜索和局部搜索，对它的权衡直接影响到搜索效率和寻优精度^[22]。本文中引入基于指数递减策略的动态惯性权重ω_t来改写速度更新公式：

式中，ω_max、ω_min分别代表惯性权重ω的最大值和最小值；C_now代表当前迭代次数，C_max代表最大迭代次数。

改进后的速度个体速度更新公式如下：

惯性权重随迭代次数的变化曲线如图 4所示。在初期惯性权重较高，加速了算法全局搜索能力的提高，而在后期惯性权重则逐步降低，使得算法快速进入局部寻优和精确搜索中，保证了寻找最优解。

Figure 4.  Change curve of inertia weight with the number of iterations

由于障碍物环境下无人机飞行路径点会出现引力场和斥力场合力为零的情况，此时无人机在路径规划过程中会容易陷入局部最优解，从而在当前点发生震荡现象，影响无人机飞行安全^[23]。本文中设置相邻两个路径节点上的引力场和斥力场，保证无人机路径尽量平滑且避免陷入局部最优。

对改进蝙蝠算法中路径点x_{i, t}的上一路径点x_{i－1, t}和下一路径点x_{i+1, t}分别设置引力场F_{i－1, t}、F_{i+1, t}，这两个引力场只对相邻的两个路径点产生作用。图 5是相邻路径节点的人工势场示意图。图中，将障碍物统一用实心圆表示，x_{i, t}所受的合力方向指向障碍物，因此更新后的下一代蝙蝠的路径点运动方向为x_{i, t}的合力方向，以此达到缩短路径长度的效果。

Figure 5.  Schematic diagram of potential field of adjacent path nodes

当前路径点的上一路径点和下一路径点的引力场设置如下。

上一路径点x_{i－1, t}的引力场为：

下一路径点x_{i+1, t}的引力场为：

式中，x_i，t为t时刻第i个路径点的当前位置，k_g为大于零的引力场常数。

为保证无人机在障碍物环境下稳定飞行的同时寻找最优路径，本文作者在无线紫外光引导通信的基础上, 通过代价函数与代价函数的适应度值来判断路径优劣与所提算法的性能好坏。无人机路径规划过程中的代价函数分别由规划路径的长度代价、干扰产生的干扰代价、无人机与目标点产生的通信代价三部分组成。

对于规划路径的长度代价定义为：

式中，d_ab表示分段路径的长度，n表示飞行路径的分段数量。

对于障碍物对无人机所产生的干扰代价定义为：

式中，N是干扰的数量，(x, y)表示无人机当前位置坐标，(x_k, y_k)表示干扰的中心点坐标，r_k表示障碍物的干扰半径。

对于无人机与目标点产生的通信代价定义为：

式中，(x_f, y_f)表示目标点的坐标，n表示到n个路径点处进行了n次通信。

适应度函数往往可以用来衡量算法收敛速度和性能，对比适应度函数值能判断出路径的优劣程度，故本文中路径规划适应度函数可表示为:

式中，k₁、k₂均为常数，且0≤k₁≤1，0≤k₂≤1。

综合以上3点的改进，本文作者所提出的无线紫外光协作的EDS-IBA路径规划算法流程图如图 6所示。

Figure 6.  Algorithm flowchart

为验证本文作者提出的算法在无人机2维空间和3维空间路径规划问题上的有效性和可用性，将改进算法EDS-IBA与BA、基于差分进化算法的改进蝙蝠算法(improved bat algorithm based on differential evolution algorithm, DEA-IBA)进行仿真对比。为保证数据客观一致，本文中所用算法运行环境和编程平台保持统一。

在2维环境下，3种算法参数均保持一致。仿真地图大小为120 m×120 m，种群规模M=60，初始发声响度A₀=0.25，初始脉冲发声频率r₀=0.5，最大迭代次数C_max=100, 无人机起点坐标为(0, 0)，目标点坐标为(100, 100)。分别在简单干扰环境和突发干扰环境下进行路径规划的对比实验。简单环境下设置6个障碍物，分别为1、2、3、5、6、7，复杂环境下设置8个障碍物，突发障碍物为4和8。具体干扰中心和干扰半径设置如表 1所示。

从图 7、图 8可以看出, 3种算法从同一起点到达同一目标点进行路径规划的过程中，本文中所提算法均能绕开干扰安全到达目标点。相较于其它两种算法规划出的路径最短，其原因是将动态惯性权重指数递减策略引入蝙蝠速度更新中，用合理均衡全局搜索与局部搜索速度，以提高算法搜索精度与寻优能力，路径点中引入的势场函数也使得路径转折时更加平滑。

Figure 7.  Path planning renderings of three algorithm in simple environment

Figure 8.  Path planning renderings of three algorithms in burst interference environment

图 9展示了3种算法重复运行30次的路径长度的分布图。可以看出, BA规划出的路径长度波动范围最大，在[157, 206] m之间；DEA-IBA路径长度波动在[154, 196] m之间，相较BA有略微减小，但相较于本文中所提算法EDS-IBA路径波动范围在[145, 151]m也有很大的涨幅。结合表 2简单环境下3种算法的路径长度对比情况可以看出，本文中所提算法的最短路径、最长路径和平均路径均优于其它两种算法，且平均路径相较于DEA-IBA缩短了10.7%，相较于BA缩短了16.3%。因此，在路径规划的长度和算法稳定性分析上，本文中所提算法EDS均优于其它两种算法。

Figure 9.  Path length distribution of 30 times of three algorithms in simple environment

目标函数的适应度值是衡量算法性能的标准之一，如图 10所示的简单环境下目标函数适应度值收敛曲线，本文中所提算法EDS-IBA从一开始迭代便逐渐收敛，当迭代次数为30~40之间时逐渐趋于稳定，而DEA-IBA、BA算法分别从第7次、第26次开始收敛，体现了本文中算法的收敛速度均优于其它两种算法。BA、DEA-IBA、EDS-IBA 3种算法目标函数的适应度值分别227.3、145.3和90.24，本文中的EDS-IBA算法适应度值最小，表明同一环境中无人机路径规划成本最低，以确保算法最优时无人机能耗最低。

Figure 10.  Convergence curve of objective function fitness value in simple environment

在突发干扰出现的情况下，结合图 11突发干扰环境下3种算法运行30次路径长度分布和表 3突发干扰环境下3种算法路径长度对比情况，可以看出, 本文中所提算法的最短路径、最长路径、平均路径同样优于其它两种算法。相较于简单干扰环境下的30次路径长度的分布图，本文中算法的平均路径长度虽然有略微增加，但整体的路径长度分布跨度没有较为明显的变化；而其它两种算法的最短路径和平均路径均有较大的涨幅，且路径长度分布跨度也有较为明显的变化。说明即使有突发情况时，本文中所提算法的寻优能力和算法稳定性也有明显优势。

Figure 11.  Path length distribution of 30 times of three algorithms in burst interference environment

图 12所示为有突发干扰下3种算法目标函数的适应度值对比情况。BA、DEA-IBA、EDS-IBA 3种算法分别在第56、46、21次迭代时开始收敛，其中本文中所提算法EDS-IBA在之后的迭代过程中目标函数的适应度值也有一定减小，且收敛时目标函数适应度值分别为240、201.3、113.3，本文中算法相较于DEA-IBA、BA适应度值分别降低了56%、63.1%。因此本文中算法收敛速度更快、路径规划代价最低、算法性能更好。

Figure 12.  Convergence curve of objective function fitness value in burst interference environment

在100 m×100 m×1100 m的3维空间中，3种算法参数均保持一致。种群规模M=60，初始发声响度A₀=0.25，初始脉冲发声频率r₀=0.5，最大迭代次数C_max=100, 无人机起点坐标为(0, 0, 0)，目标点坐标为(100, 100，0)。利用数字高程地图来模拟无人机空中飞行障碍物空间，且将随机4个圆柱作为干扰，具体干扰参数设置如表 4所示。

无人机在3维空间中的路径规划效果更能体现算法的准确性和实用性，如图 13a、图 13b所示, 为不同角度的3维路径规划效果。在地形障碍和圆柱形干扰存在的3维地形空间中，本文作者所提EDS-IBA算法能够规划出一条从起点到目标点能够避免碰撞且长度较短的路径。与此同时飞行高度也决定了无人机的飞行能耗，如图 13b所示。本文中算法最大飞行高度为460 m，而DEA-IBA、BA算法的最大飞行高度分别达到了536.8 m和465.9 m，因此, 本文中算法在3维空间中路径规划效果更好、能耗更小。

Figure 13.  Path planning renderings from different angles of in 3-D complex environment

图 14展示了无人机采用3种算法在3维干扰空间中重复运行30次的路径长度的分布。结合表 5中路径长度对比情况可以看出, BA规划出的路径长度波动范围最大，在[1312.716, 1637.542] m之间；DEA-IBA路径长度波动在[981.2152, 1253.042] m之间，相较BA有略微减小，但相较于本文中所提算法EDS-IBA路径波动范围在[864.2076, 959.9741]m也有很大的涨幅。此外，本文中所提算法的最短路径、最长路径和平均路径均优于其它两种算法，且平均路径相较于DEA-IBA缩短了13.7%，相较于BA缩短了36.2%。因此，无论是在路径规划的长度和算法稳定性分析上，本文中所提算法均优于其它两种算法。

Figure 14.  Path length distribution of 30 times of three algorithms in 3-D complex environment

3维空间中3种算法目标函数的适应度值收敛情况如图 15所示。BA、DEA-IBA、EDS-IBA 3种算法分别在第25、22、10次迭代时开始收敛，本文中所提算法从开始迭代到收敛后的适应度值均小于其它两种算法，且收敛时的适应度值分别为1033、934.6、910.1，因此本文中算法不但收敛速度更快，路径规划代价也最低，综上所述, 本文中所提EDS-IBA的算法性能更好。

Figure 15.  Convergence curve of objective function fitness value in 3-D complex environment

通过建立无线紫外光飞行引导系统，利用安装在无人机飞行终点的紫外路径引导装置和无人机上搭载的紫外接收模块来进行地形和障碍物位置等信息的实时交互，从而协作无人机调整自身飞行状态并安全降落；其次，为了提高收敛速度与寻优精度，在指数递减策略基础上引入动态惯性权重，重写蝙蝠算法速度更新公式；此外，在路径点中引入人工势场来保证路径规划避免陷入局部最优；最后，通过引入干扰代价和紫外光通信代价来保证飞行环境的多样性及真实性。将无人机分别置于2维简单环境、突发干扰环境和3维复杂干扰环境中进行路径规划对比仿真实验，结果表明，不论从路径规划长度还是算法稳定性分析，本文中所提EDS-IBA算法均优于DEA-IBA和BA两种算法，验证了改进后算法在障碍物及特殊天气干扰环境下无人机路径规划的可行性和优越性。因此，本文中算法在不同环境下的仿真结果对无人机路径规划的实际应用和开发具有一定的现实意义，未来工作将继续优化算法性能，并将其算法运用于多无人机及路径规划问题中。