基于改进鸽群优化算法的多无人机目标搜索*

凌文通,倪建军,陈 颜，唐广翼

(河海大学物联网工程学院，江苏 常州 213000)

1 引言

随着计算机、传感器和控制等技术的发展，无人机UAV(Unmanned Aerial Vehicle)在各个领域的应用也更加广泛，例如预防森林火灾、边境侦查和物资运输等。与单无人机相比，多无人机协作[1-3]可以更加高效、快速地完成任务，因此对多无人机协作进行研究具有重要的现实意义。

在多无人机协作中，目标搜索是非常基本和重要的任务之一，为此，已经有许多学者进行了大量的研究工作，如：文献[4]建立了搜索概率环境信息模型，提出了一种新的基于蚁群理论的多UAV协同区域搜索方法。文献[5]建立了多旅行商问题MTSP(Multiple Traveling Salesman Problem)模型，提出了一种聚类算法和遗传算法进行分步组合的优化算法来进行搜索。文献[6]针对动态时敏目标的运动特性，建立了动态时敏目标的运动预测模型，以优化无人机的搜索性能。文献[7]设计了一种基于预测控制思想的多无人机协同区域搜索算法,使多无人机在执行区域搜索任务时同时考虑当前搜索代价和长期搜索代价,提高了多无人机的协同搜索效能。

上述这些研究，大部分是在二维环境中进行的，而无人机工作在三维环境中，这种情况下的协作搜索任务明显复杂很多。因此，近年来很多学者开始针对三维环境中的多无人机协作搜索问题开展研究，如：文献[8]提出了一种基于混沌理论的人工势场算法来解决三维无人机航路规划问题。文献[9]提出了一种基于改进蚁群算法的优化算法用于三维航迹规划。文献[10,11]将鸽群优化算法用于二维环境无人机搜索之中。这些对无人机协作搜索的研究具有重要的理论和实际价值，但是依然存在一些问题需要深入研究，如蚁群算法存在搜索效率低、收敛速度慢等缺点；有的研究只适合单无人机搜索问题等。

针对上述问题，本文研究了在未知三维环境中的多无人机目标搜索问题，并提出一种基于差分进化策略改进的鸽群优化算法来求解多无人机协作目标搜索任务。

2 问题描述

在本文的任务中，目标位置信息未知，环境信息未知，无人机需要在避开障碍的同时搜索到目标。本文将所有的无人机视为质点，忽略大小、形状及通信问题，UAV被标记为Ui，i=1,2,…,N，其中N表示无人机的数量。

假设无人机相互之间通信始终保持良好状况，且通信没有延时，因此无人机之间信息可以相互共享，同时假设目标可以释放信息素[12]，无人机可以检测搜索到目标的信息素，并且可以识别信息素的强弱，定义目标的信息素在环境中的强度如式(1)所示：

(1)

其中,Star表示最大的信息素强度，Rtar表示目标的信息素能够传播的最远距离，ptar和pi分别表示目标ptar和点pi的位置，L(x,y)表示x和y之间的距离。

3 基于改进鸽群优化算法的多无人机目标搜索方法

3.1 基本鸽群优化算法思想

鸽群优化PIO(Pigeon-Inspired Optimization)算法[13,14]相比于人工势场算法、蚁群算法等传统优化算法，具有收敛速度快、搜索效率高等特点，因此，本文使用鸽群优化算法来完成搜索任务。

基本鸽群优化算法是受到鸽子群自主归巢行为启发的新型群体智能算法，鸽群优化算法主要包括2个阶段：

(1)在给定的求解空间内初始化鸽子的位置和速度，分别如式(2)和式(3)所示：

Xi=[xi1,xi2,…,xiD]

(2)

Vi=[vi1,vi2,…,viD]

(3)

其中,i∈{1,2,…,N}表示鸽子编号，N表示鸽子总数，D表示求解问题的维度。鸽子的速度和位置的更新方程如式(4)所示：

(4)

其中,R表示地图和指南针因子，用来控制鸽子的速度；随机数rand∈[0,1];t=1,2,…,Nc1表示当前迭代次数；Xgbest(t-1)是t-1次迭代所搜索到的全局最优位置，当迭代次数t达到Nc1时，算法第1阶段完成。

(2)此时进入算法第2阶段，鸽子到达目标附近时，PIO算法将切换到地标算子，附近环境的地标信息将提供精确的指导信息。在此阶段，每次迭代时鸽子数量减半且速度不会改变，而位置会更新，如式(5)所示：

(5)

其中,Np表示t-1次迭代减半的鸽子数量；Xc(t)是剩余鸽子的中心位置(作为地标信息)；fitness(·)是每只鸽子的适应度函数，根据求解的最值不同，其定义也不同,如式(6)所示：

(6)

3.2 鸽群优化算法改进

鸽群优化算法虽然搜索效率高、收敛速度快，但是极容易陷入局部最优。差分进化算法[15，16]是一种基于群体差异性的算法，其整体结构类似于遗传算法，它能够使个体在迭代时保留一些其他个体的特性。因此，本文将差分进化算法的特点融入到鸽群优化算法中，以便在快速搜索的过程中保持种群多样性，防止陷入局部最优，提高全局搜索能力。即将式(4)中位置更新公式变更为式(7)：

Xi(t)=Xi(t-1)+α1Vi(t)+α2Ui(t-1)

(7)

其中，α1和α2为调节系数，且α1+α2=1;Ui(t-1)为第t-1次迭代中第i只鸽子的差分进化结果。对Xi(t)进行基因编码操作，然后通过式(8)和式(9)计算Ui(t)：

Vi(t)=Xi(t)+F(Xm(t)-Xn(t))

(8)

(9)

其中，Vi(t)为差分向量;Xij(t)为Xi(t)的第j号基因;Vij(t)为Vi(t)的第j号基因;Uij(t)为Ui(t)的第j号基因;m≠n≠i且m，n都为[1,N]的随机整数;F∈[0,1]为缩放因子，CR∈[0,1]为交叉概率，这种交叉概率可以保证差分进化后的个体包含其他个体的基因，保留种群多样性。

3.3 多无人机目标搜索

无人机在搜索过程中不仅需要搜寻最大信息素，而且应该能够避开障碍物，无人机两两之间互相不能相撞，通过设定安全距离Dsafe，当无人机之间距离大于Dsafe时，令d=0,表示无人机之间互不影响；当无人机之间距离小于Dsafe时，令d=1，从而实现无人机避碰的效果。因此，适应度函数的设计如式(10)所示：

f(Xi(t-1))=

(10)

其中，w1和w2是调节系数，o为障碍物总数，ok为第k个障碍物的位置。无人机利用机载传感器可以进行障碍物探测，这里用函数O(ok,pr)来判断无人机搜索的下一位置pr是否存在障碍，具体定义如式(11)所示：

(11)

由于无人机之间可以共享信息，对于无人机已经搜索过的区域应尽量避免重复搜索，从而可以提高搜索效率，缩短搜索到目标的时间。本文通过将已搜索过的区域进行标记并存储，减小重复搜索的概率。因此，将式(10)进一步改进为式(12)：

f(Xi(t-1))=Itar(Xi(t-1))-

(12)

其中,w3是调节系数，函数G(pr)通过和已标记的区域进行比较，判断无人机搜索的下一位置pr是否已经被其他无人机搜索过,如式(13)所示：

(13)

基于改进鸽群优化算法的多无人机目标搜索方法具体步骤如下所示：

步骤1UAV在环境中飞行，并检测目标信息。

步骤2当UAV检测到目标信息时，使用改进后的鸽群优化算法进行搜索。

步骤3遵循滚动优化的原则，采取算法迭代中选取的最优个体，进行UAV位置的更新。

步骤4判断是否满足最大迭代次数或者UAV找到目标，满足则停止运行，否则返回步骤1。

实现基于改进鸽群优化算法的多无人机目标搜索方法的伪代码如下所示：

(1)初始化：Ui,i=1,2,…,N;Tj,j=1,2,…,M;//初始化无人机和目标位置

(2)计算：Itar,f(Ui),载入环境信息O;/*Itar为信息素强度，f(Ui)为标志位*/

(3)搜索过程：

fori=1..N

iff(Ui)==1

break;

else

Xi=rand(Xmin,Xmax);

Vi=rand(Vmin,Vmax);

location=g(Xi,Vi);//使用改进后的算法计算

Ui=Ui+location;//无人机进行位置更新

endif

endfor

(4)结束条件：

ifi≥NorItar==Star

f(Ui)=1;

endif

4 仿真实验与结果分析

在UAV搜索过程中，目标状态可能出现2种不同情况：第1种目标是静止的，第2种目标是随机运动的。针对2种不同情况本文分别进行了多次实验。为了简化实验，本文中不考虑噪声的影响，将所有UAV和目标视为质点，与此同时适当扩大了障碍，以抵消忽略UAV实际形状和尺寸所带来的影响。

Figure 1 Experimental results of static targets

Figure 2 Experimental results of dynamic targets

4.1 静态目标的实验结果

在这部分实验中目标处于静止状态，基于改进鸽群优化算法的搜索过程如图1所示。图1a显示了UAV的初始位置分别为(65,10,60)，(10,10,60)，(40,90,60)和(90,80,60)，目标的位置分别为(10,40,5)和(90,80,5)，图1b和图1c为无人机搜索过程中的运动轨迹，从图中可以看出，无人机可以避开障碍并朝着散发最大信息素的地方移动，最终发现目标。实验次数都为20次，根据实验结果对实验数据进行了计算，静态实验中无人机搜索到目标的平均步长为61，平均时间为25.13 s。

4.2 动态目标的实验结果

在这部分实验中，目标能够在路面上随机运动，无人机的速度必须大于目标随机运动的速度，否则无人机将无法搜索到目标。所有目标初始位置与静态实验中的相同，最终实验结果如图2所示。

从图2结果可以看出，即使目标处于运动状态，本文所提出的方法仍然能够避开障碍并最终完成目标搜索任务。实验结果平均步长为69，平均时间为35.25 s。

4.3 复杂环境实验结果

实际环境中，情况可能更加复杂(如山地环境等)，因此为了更进一步验证本文所提方法的有效性，设计了复杂环境实验。如图3a所示，在这部分实验中除了地面存在山脉等复杂地形，空中还分布着静态障碍物(如其他飞行器等)。图3显示了无人机的整个搜索过程。实验结果表明，本文方法是有效可行的，在较为复杂的实验环境中，无人机仍然可以安全且平稳地搜索到目标。实验平均步长78.8，平均时间为42.15 s。

Figure 3 Experimental results in complex environment

Figure 4 Results of contrast experiment

4.4 对比实验结果鸽群优化

为了更进一步探讨所提算法的有效性，在复杂的实验环境中，将改进后的鸽群优化算法与未改进的鸽群优化算法以及蚁群算法进行比较，实验结果对比图如图4所示。

为了防止一次实验带来的偶然性，所有算法均运行了20次，实验结果如表1所示。从表1中可以看出，鸽群优化算法比蚁群算法搜索效果要好，改进后的鸽群优化算法在3种算法中表现最优。

Table 1 Comparison of experimental results

5 结束语

本文研究了三维未知环境中的多无人机目标搜索问题，使用鸽群优化算法求解问题，由于鸽群优化算法容易陷入局部最优，本文提出了基于差分进化策略的鸽群优化算法。为了验证所提出的基于改进鸽群优化算法的多无人机目标搜索方法的有效性，设计并进行了多次仿真实验，实验结果表明该方法能够有效完成搜索目标任务。在将来的工作中，将进一步优化方法的性能，并开展实际多无人机协作目标搜索实验，验证方法的实际工作性能。