受限通信范围下海上目标的多无人机协同搜索算法*

王可铮，周兴莲，林梦婷，李 彬

(1.联想集团 方案服务业务集团，四川 成都 610041；2.四川大学 空天科学与工程学院，四川 成都 610000)

0 引 言

多无人机(unmanned aerial vehicles,UAV)协同执行任务能够提升战斗力，在多领域都得到了广泛应用，如协同搜索、探测等[1，2]。协同搜索的关键问题1是如何对不确定的环境进行建模，最常用的方法是基于搜索图的方法，例如基于环境不确定性的认知图[3,4]、信息素图[5]、概率图等[6];关键问题2是如何依据当前对环境和目标的认知做出协同搜索决策,最典型的区域搜索方法有滚动优化算法[7]。

文献[8]采用分散式结构，根据实时通信状态构建不同的小组和环境认知地图，小组内采用集中式算法进行决策。文献[9]考虑通信距离限制情况，建立了UAV通信拓扑结构，超过通信范围且无法间接通信段UAV之间不能协同。文献[10]针对UAV群部分链路不可达问题，根据实时通信状态，建立了局部互通网络，当某一UAV无法与其他UAV进行通信时，将采用单机飞行控制，不再参与协同。

本文以特殊环境下通信受限时海上目标搜索为研究背景，开展基于分布式模型预测控制(distributed model predictive control，DMPC)协同搜索问题研究，旨在生成一条最优的搜索路径。

1 问题描述

1.1 搜索区域环境建模

将海面任务搜索区域Ξ视为平面，并进行如图1(a)所示的栅格化。采用概率图表征目标存在的概率情况。定义在网格c内，目标存在的概率为pc(k)∈[0,1]，pc(0)为先验信息。如图1(b)所示，如果先验已知某个方格里面存在目标的概率比较大时，会将该方格及周围方格的初始存在概率pc(0)设置为逐渐递减形式，随着UAV搜索任务的进行，pc(k)实时变化，为UAV的决策提供实时的环境信息。引入γc,k∈[0,1]变量描述UAVi对网格c的不确定度

图1 搜索区域环境建模

(1)

其中,Kγ>0,|•|为取绝对值。

1.2 UAV模型

假定任务派出n架UAV从指定机场出发对目标区域Ξ展开搜索，在栅格图模型中假设UAV是以一定速度飞行的质点。规定每个单元格最多存在一个目标。在栅格环境中规定UAVi只有8种航向状态，即，D={0,1,2,3,4,5,6,7}，具体如图2所示。由于UAV存在最小转弯半径的物理约束，因此,UAVi在t时刻的某种飞行方向下，下一步的飞行方向只有3种可选，直飞或者左右45°转弯。

图2 航向示意

定义状态变量xi(k)=[δi(k),θi(k)]，其中δi(k)=(xi(k),yi(k))=(n,m)为k时刻UAVi在栅格地图上的位置索引，θi(k)为k时刻UAVi的航向角。UAVi的运动模型如下

(2)

其中,ln[*]为取整函数，搜索过程中UAV以v0保持匀速飞行。

2 受限通信范围下的地图更新策略

2.1 通信拓扑建模

定义表征集群内部通信状态的邻接矩阵F(k)

(3)

式中N为UAV的数量，fij=1为UAVi与UAVj之间能够通信，fij=0为UAVi与UAVj之间超出通信范围无法实现通信。令

2.2 搜索地图更新策略

本文考虑真实的雷达模型如图3所示。O点为UAV所在位置，飞行高度为h，W为UAV在海面上的投影，在方位面的的覆盖角度为2φ，垂直俯仰覆盖角度为α1～α2，盲区半径为r=h×tanα1。UAV搭载的雷达的搜索范围在地面的投影则为ABCD围成的扇形。这样就将三维视场搜索问题转换为二维平面内的覆盖问题，只要海上目标出现在图中的阴影部分，则视为可以搜索到目标。

图3 雷达搜索模型

定义τ=1为事件“网格c中存在目标”，τ=0为事件“网格c中不存在目标”，Ωi,c,k=1为在k时刻UAVi搜索到网格c中存在目标，将目标存在概率地图的更新写为线性更新公式，定义一个新的变量

(4)

因此，概率地图线性更新公式为

Πc,k=Πc,k-1+λc,k

(5)

其中

(6)

式中pd，pf分别为传感器的虚警概率和检测概率，这2个指标描述了传感器的性能。

3 基于分布式模型预测控制的协同搜索算法

3.1 搜索问题建模

分布式模型预测控制方法需要考虑相邻智能体之间的信息交互，以实现UAV之间的协同。因此，UAVi决策搜索轨迹时，需要考虑相邻UAVj的状态信息序列以及控制量序列。

3.1.1 搜索性能指标

1)环境搜索收益

(7)

其中，Φl(c)为UAVi在网格c处，传感器的探测靶面。

2)任务执行代价

(8)

V(i,l,k)=Vs(i,l,k)-VD(i,l,k)

(9)

3.1.2 约 束

1)机间协同约束:为避免UAV集群发生碰撞，需要考虑UAV之间的安全约束

dij≥dmin

(10)

2)转弯半径约束:由于UAV存在转弯半径物理约束，每个时刻UAV的航向只能选择直飞或者左右45°转弯

θi(k)∈{-45°,0,45°}

(11)

3.2 基于模型预测控制的分布式算法

考虑UAV间的相互通信，将集中式优化决策问题分解为各个子系统的局部优化问题，进行分布式求解，分布式模型预测控制包括预测、滚动优化和执行3个关键步骤[11]。

3.2.1 预 测

3.2.2 滚动优化

分布式决策过程中每架UAV的优化目标只需要关注自身的搜索收益和航路代价，因此在分布式框架下，优化问题可构造为

s.t.xi(k+q+1|k)=fi(xi(k+q|k),ui(k+q|k)),

xi(k+q|k)∈Ξ,θi(k+q|k)∈Θ，

dij≥dmin,q=1,2,…,T;i=1,2,…,N

(12)

由于耦合约束和耦合目标函数的存在，导致上述优化问题难以求解。因此，本文采用冻结策略[12]将上述问题进行解耦。即每个采样时刻都只有一架UAV会求解优化问题(式(12))，更新控制序列，其他UAV将利用最新求解的控制序列进行控制。具体而言，在UAVi进行优化更新时，其他UAV的状态及控制量采用上一更新时刻的预测序列，因此当前优化问题只包含与子系统i有关的优化变量。“冻结”策略原理示意如图4所示。

图4 冻结策略下系统更新示意

其中,r=[x(k),x(k+1|k),…,x(k+T|k),…,u(k+T|k)],UAV将自身预测的状态量以及控制量序列传输给邻域内的UAV。当fij(k)=0时，UAVi采取上一时刻获取到的最新邻居信息对下一时刻UAVj的状态进行预测。

3.2.3 执 行

在以冻结策略进行的滚动优化机制基础之上，每架UAV会执行上一个最新的控制序列中对应时刻的控制量。

4 仿真结果

矩形格子大小设置为200 m×200 m，搜索任务区域为100×100个网格，面向速度为30节的海上动态目标，使用5架UAV执行搜索任务。传感器的虚警概率pf为0.3，检测概率pd为0.9，探测范围为1.2 km，盲区半径为400 m。敌方目标t1和t2的初始位置分别为[10,50]和[55,70]，考虑低动态目标，目标做匀速运动。设置UAV搜索到2个目标后就停止搜索。在目标周围存在区域，半径为：考虑2个半径为1 km的区域，及参数Kγ设置为1。UAV初始时刻在地图边缘呈一字队形。图5(a)为初始化地图，其中，★代表目标初始位置，底部扇形为雷达探测器的探测靶面，灰色阴影部分为威胁区域。

图5 搜索地图及搜索轨迹

如图5(b)所示，使用DMPC算法在72 s时，搜索到目标t1，108 s时搜索到目标t2。图5(c)为平行搜索法下的搜索轨迹，47 s时探测到目标t1，132 s时搜索到目标t2。虽然平行搜索算法先行搜索到目标t1，但所有目标搜索到的总时间更长，且每个阶段的搜索区域覆盖率都比DMPC算法下的搜索结果低。

表1所示，DMPC在108 s时间内的覆盖率为42.10 %，而平行搜索算法在132 s的搜索任务执行下只实现了39.92 %的覆盖率。随着搜索任务的进行，由表2可以看出:在统计的多个时间段里DMPC算法的覆盖率都是高于平行搜索算法。

表1 搜索到目标的时间及覆盖率对比

表2 覆盖率随时间的变化 %

5 结 论

本文研究了通信受限条件下UAV群协同搜索问题，利用模型预测控制的滚动时域优化特点，针对海上舰船目标搜索任务提出了一种多UAV分布式协同搜索算法。与传统平行搜索算法相比，该算法能够实现避障，并以更高的效率实现目标搜索任务。除了通信范围受限问题，在实际的环境中，通信延时、数据包丢失等更复杂的情况将在未来的工作中进一步的研究。