基于改进鲸鱼优化算法的多无人机围捕

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

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

0 引 言

随着计算机、传感器、控制等各方面技术的发展，无人机技术在各个方面的应用也越来越广泛。因为无人机的速度、机动性的优势[1]，无人机所发挥的作用也会越来越大。相比较于单无人机，多无人机执行任务能力更强，效率更高[2-3]。而多无人机对目标进行围捕是其中重要且典型的任务之一。

为了解决这个任务，已经有许多学者做了广泛的研究。文献[4]提出了一种多层环状攻击围捕模型，并依据能量均衡原则，对系统能量进行消耗平衡。文献[5]提出了一种基于博弈论及Q学习的多Agent协作追捕算法。文献[6]通过优化机器人的速度和方向以达到快速围捕任务。Dutta[7]介绍了Kamimura和Ohira以及Angelani的多目标离散化围捕模型,但初始化时随机分布、无障碍物、无对抗、路径特殊，不需要形成一定的队形。文献[8]针对有障碍的复杂环境下围捕问题，改进了粒子群算法，使得围捕者能够在规避障碍物的情况下实现对目标的围捕。文献[9]通过改进传统的人工势场方法，解决了“目标不可到达”和“死锁”问题从而完成任务。文献[10]把动物学行为引入无人机群，使用基于势点的策略完成任务。

在实时围捕任务中，仍有一些问题需要解决，如人工势场、粒子群算法搜索效率慢等。大部分的算法直接使用路径规划[11-13]方法围捕目标，而使用预测的方法能够实现拦截式围捕，具有先验性，减小航行距离，能够更快地完成围捕任务。针对上述问题，本文将改进的鲸鱼优化算法用于无人机围捕任务，提出一种基于动态预测围捕点的多无人机围捕算法。

1 问题描述

在本文任务中，将所有的无人机视为质点，忽略大小、形状及通讯问题，UAV被标记为Ui，i=1,2,…,N,其中N是无人机的数量；T表示移动目标，目标运动轨迹未知。

围捕过程描述如下：无人机探测范围大于目标，并且可以实时感知目标的位置信息，无人机相互之间信息共享，若无人机在目标周围均匀分布且到目标的距离小于规定距离时，即可以认定围捕成功。

2 动态围捕点预测和分配

2.1 动态围捕点

因为本文假设目标轨迹是未知的，没有大量数据进行模拟预测[14-15]，可以认为目标未来短期时间内的运动轨迹与其之前一段时间内的运动状态有关，而与更久远之前的运动状态无关。通过采样当前位置及之前k个位置信息，通过多项式拟合法拟合出目标运动轨迹方程，在较短时间内可以认为目标会沿着拟合运动轨迹运动。根据所需求预测的步数在轨迹上确定目标点，然后发送给无人机。预测步数越大，围捕效果越好；预测步数越小，准确度越高，同时因为本文地图是连续的，所以本文将预测步数设置如下：

(1)

其中，s为预测步数，s1为常数，t为迭代次数，tmax为最大迭代次数。预测目标点确立之后，在其周围产生动态围捕点。随着目标的不断移动，预测信息不断进行更新，动态围捕点也不断更新，实现动态预测。

无人机沿着动态围捕点向着目标进行围捕，因为离目标的距离不同，为避免有无人机提前进入目标勘测范围，导致目标逃逸增加任务难度，所以设立安全域的范围[16]，当所有无人机未到达期望围捕点之前，安全域禁止进入，其定义为：

(2)

其中，Dsafe(E)为安全域，(x,y)为安全域中任一点，(xm,ym)为目标点位置，f为目标探测距离。

期望围捕点在安全域边界产生，以目标运动反方向与安全域交点为起点，均匀产生n个点作为围捕点，n的个数等同于围捕无人机的个数。如图1所示。

图1 围捕点的分配

图1中V为目标运动方向，因此围捕点的坐标表示为：

(3)

(4)

2.2 围捕点分配

围捕点确定之后，需要将围捕点分配给各个无人机[17-19]。最常用的方法是贪婪算法，但是该方法容易出现死锁问题，本文采取的是基于距离的双向协商法。该方法首先利用基于距离最近原则的贪婪算法，通过计算机器人与围捕点的距离，对围捕点进行预分配，然后双向协商进行再分配。这种双向协商方法计算简单，效率很高，算法具体过程如下：

1)初始化无人机和期望围捕点位置，设U为无人机的集合，U={U1,U2,…,Un}，M为期望围捕点的集合，M={m1,m2,…,mn}。

2)计算无人机Ui到各个围捕点mj的距离Dij；其中：

3)对于无人机Ui,i=1,2,…,n，计算Dij,j=1,2,…,n的最小值，将对应距离最小的围捕点mj分配给无人机Ui，令mj=mj+1。

4)mj的值有3种情况：

①mj=0，则该点未进行分配。

②mj=1，则该点匹配成功，记录下匹配成功的围捕点mj和无人机Ui，并将其分别从集合U和集合M中移除，令n=n-1。

③mj>1，则将围捕点mj分配给距离最远的无人机Ui，并将其分别从集合U和集合M中移除，令n=n-1。

5)若n=0，则表明所有的围捕点都分配成功，否则跳往步骤1继续。

3 鲸鱼优化算法及改进

3.1 鲸鱼优化算法

鲸鱼优化算法[20](Whale Optimization Algorithm， WOA)是澳大利亚学者Mirjalili等根据座头鲸的狩猎方式提出的一种新的群智能优化算法。鲸鱼在大海中随机游走寻找猎物，使用一种泡网觅食法的狩猎方式，先深入水底收缩包围猎物，而后螺旋上升在靠近海面的地方捕食猎物。鲸鱼优化算法数学模型主要包括3个部分：游走搜索猎物、收缩包围猎物和螺旋捕食猎物。

1)搜索阶段。

WOA在寻优过程中，通过参数A的改变来控制搜索策略。当|A|>1时，WOA进行全局寻优，随机选择一个作为参考个体，新个体然后按以下公式进行更新：

D=|C·Xrand-X|

(5)

X(t+1)=Xrand-A·D

(6)

其中，X表示当前鲸鱼位置，D表示包围步长，Xrand为种群中随机选取鲸鱼的位置，t为当前计算次数，A表示生成个体离参考个体远近程度，A和C的定义如式(8)和式(9)所示：

a=2-2t/tmax

(7)

A=2·a·r-a

(8)

C=2·r

(9)

其中，r是在[0,1]范围内的随机数。

2)包围阶段。

包围阶段时，鲸鱼个体不再随机更新位置，选择当前最优位置作为目标，从而使种群获得最优解。收缩包围猎物的位置更新公式为：

Dbest=|C·X(t)best-X(t)|

(10)

X(t+1)=X(t)best-A·Dbest

(11)

3)捕食阶段。

鲸鱼通过一种螺旋式游走的方式形成气泡网进行捕食，其具体更新为：

X(t+1)=Dbest·ebt·cos(2πl)+X(t)best

(12)

其中，b为控制螺旋线形状的常数，l为[0,1]的随机变量。鲸鱼的捕猎行为和螺旋收缩是同时进行的，假设两者概率均为50%，具体数学模型为：

(13)

3.2 改进的鲸鱼优化算法

WOA相比其它算法，具有结构简单、自身参数少以及寻优能力强的特点，在许多工程领域已经得到应用，但与其它智能优化算法类似，容易陷入局部最优，导致早熟。因此需要提升算法的全局搜索能力[21-23]，本文提出一种自适应权重方法。在算法包围阶段，迭代完成之后，保留最优的3个个体X1(t),X2(t),X3(t)，最优个体按照式(14)进行计算：

(14)

因为适应度值是反应个体优劣的重要指标，所以将适应度值作为求取权重的判断依据，w1的计算方法为：

(15)

其中，J1、J2、J3分别代表X1、X2、X3的适应度值，w2,w3由同样计算方式所得。通过保留多个最优个体从而提升全局搜索能力，克服算法容易陷入局部最优的缺点。

在捕食阶段，鲸鱼以螺旋式方式对自身位置进行更新，其中公式(13)的b为控制螺旋形状的参数，一般设为常数，这种前进方式比较单一。为了使鲸鱼能够以更多的方式捕获目标，将参数b设计为随迭代次数而不断进行改变的变量，参数b的具体设置为：

(16)

b随着迭代的次数不断增加而改变，螺旋线形状由大到小也在发生改变，在算法初期，能够扩大搜索空间；在算法的后期，能够提高局部寻优精度，加快搜索速率，改善算法性能。改进后整个算法步骤如下：

步骤1 初始化无人机以及目标位置。

步骤2 根据目标信息，动态预测目标将要出现的位置，以此位置建立目标安全域和期望围捕点。

步骤3 根据双向协商法将期望围捕点分配给各个无人机。

步骤4 无人机使用改进后的鲸鱼群算法朝着期望围捕点前进。

步骤5 当无人机都达到任务点后停止，否则返回步骤2继续。

4 仿真实验

4.1 简单环境实验

在实验过程中，为验证所提出算法的有效性，首先在二维环境中进行了无障碍和有障碍的实验。实验过程中，目标进行不规则的平滑曲线运动。实验结果如图2所示。

在这部分实验中，无人机初始位置分别为(0,0)，(90,10)，(10,50)，其中图2(a)和图2(c)是原始算法结果，图2(b)和图2(d)为改进后算法所得到结果，从2幅对比图中可以明显看出改进后的算法优于原始算法，行进路线更为平滑，减小了无人机转弯损耗。在面对障碍物时，也能更好地躲避障碍物，围捕效果明显优于原始算法。

(a) 原始算法

(b) 改进算法

(c) 原始算法

(d) 改进算法

4.2 中等环境实验

无人机实际工作环境为三维环境，为了使实验更加接近真实环境，并测试所提出算法的性能，设计了如下实验，建立了三维环境模型。如图3所示，将无人机数量设为5，其初始位置分别为(10,10,8)，(30,40,65)，(80,35,40)，(15,85,60)，(80,95,50)，目标点位置为(50,50,10)。目标是运动的，三维空间中存在障碍物。通过多幅图来展现无人机目标围捕过程，图3(a)为初始位置，图3(b)和图3(c)是无人机进行围捕的路径过程，从图中可以看出无人机在三维环境中也可以成功完成目标围捕任务。

(a) 初始位置

(b) 围捕过程1

(c) 围捕过程2

(d) 最终结果

4.3 复杂环境实验

针对实际环境中可能出现更加复杂的情况，比如出现动态障碍物等，设计了如下实验。在这次实验中，存在着空中移动障碍物。图4显示整个团队围捕过程，即使在复杂的实验环境下，无人机仍可以安全完成围捕任务。

(a) 初始位置

(b) 围捕过程1

(c) 围捕过程2

(d) 最终结果

为了验证算法的有效性，以中等环境为实验背景，将蚁群算法和原始算法以及改进后的算法进行了比较，实验结果如表1所示。

表1 实验对比结果

5 结束语

本文研究了未知运动目标轨迹下的无人机围捕问题，通过预测目标短期内可能出现的位置，采用双向协商法对预测围捕点进行分配，最后通过改进的鲸鱼优化算法，实现了目标围捕任务。为了验证本文算法的有效性，分别在二维以及三维环境下进行了多次实验，验证了算法的优越性。在下一步工作中，将寻找更好的预测与更简洁的分配方法，提升算法的性能。