基于角色切换策略的多无人机协同区域搜索

2021-06-09朱黔许诺黄蓓李强周锐

北京航空航天大学学报 2021年5期

朱黔，许诺，黄蓓，李强，周锐

(1.中国运载火箭技术研究院战术武器事业部，北京100076； 2.北京航空航天大学航空科学与工程学院，北京100083；3.北京航空航天大学自动化科学与电气工程学院，北京100083）

区域搜索是情报侦察的重要手段，比较单架无人机，多无人机协同搜索能够尽可能覆盖任务区域并提高搜索效率，获取更为准确的目标信息。

针对多无人机协同区域搜索问题，目前国内外的研究主要分为2个方向：①以传统的搜索论为基础，主要针对静态目标的搜索，以最大化目标发现概率为目标，设定能够完全覆盖任务区域的固定搜索航线，如Zomboni搜索、Spiral搜索等；②考虑目标搜索的动态过程，根据传感器获取的探测信息，通过在线规划实现无人机运动控制，主要基于不同的搜索图，如概率图［1-3］、信息素图［4-5］、收益图［6-7］等。

针对多无人机协同区域搜索，通常将待搜索区域划分成大小相等的若干网格，以目标在网格内的存在概率及无人机对网格状态的确定程度来描述待搜索的目标信息。目前，多无人机协同区域搜索问题已经取得了很多丰硕成果，但是考虑远程指挥控制和实时态势感知，存在地面站需要实时数据回传的研究刚刚起步，而这却广泛存在于灾难救援、区域监视、远程感知等［8-11］。

在多无人机协同区域搜索过程中，随着搜索任务的展开，各无人机对不同区域进行搜索，由于通信范围有限，网络拓扑结构会不断发生变化，相应地，无人机在网络中的重要程度和对协同搜索任务的作用也随之动态变化。考虑无人机有限的通信能力，实时搜索信息需通过多跳网络回传给地面站，以实现远程指挥控制和态势感知。因此，本文充分考虑搜索区域完全覆盖和通信拓扑动态变化，建立准确有效的无人机节点重要性评估方法并设计合理的任务分配机制，对实现协同区域搜索任务与网络连通性的动态平衡具有重要的研究意义。

1 多无人机协同区域搜索问题建模

1.1 无人机运动学模型

假设所有无人机都在同一高度并忽略风干扰，仅考虑二维平面上的控制律设计，对应的无人机运动学模型如下：

式中：x=(x，y，ψ，v，ω）T为无人机状态向量，(x，y）为惯性坐标系下的位置，ψ、v、ω分别为无人机的航向角、速度、偏航角速度；(τv，τω）为时间常数，用于表征执行器时延；u=(uv，uω）T为无人机控制向量，uv为速度控制命令，uω为偏航角速度控制指令，需要满足如下约束［12-13］：

其中：无人机的巡航速度为v0，速度和偏航角速度的最大变化范围分别为vmax和ωmax。

1.2 概率传感器模型

在协同区域搜索过程中，通常采用简单的传感器模型，如探测圆［6-7］，而实际应用中部分传感器可能存在视线角约束，并且二值覆盖函数很难有效表示探测能力。文献［14］基于真实传感器，考虑探测距离、角度、可视性等要素，提出概率传感器模型。将其引入多机协同区域搜索中，采用覆盖概率作为评价指标，用于表征概率传感器对各个网格的探测能力差异，相应的覆盖概率函数由距离、方位角、俯仰角及可视性函数构成。

式中：si=(pi，θi，ξi）为四元组，表示第i架无人机传感器配置信息，由位置pi、方位角θi及俯仰角ξi构成；q为待搜索区域网格中心点的位置坐标。本文不考虑传感器视线遮挡，则覆盖概率函数可改为如下形式：

相应地，距离、方位角及俯仰角函数表示如下：

式中：γi=∠p(q-pi）-θi；ζi=∠t(q-pi）-ξi；参数t、β用于调整S函数的宽度和边界斜率，对应调整这2个参数即可改变概率传感器探测能力。

1.3 多无人机协同区域搜索模型

假设待搜索区域Ω为一个LX×LY的二维矩形平面，其被均匀分成NX×NY个网格，为简便计算，每个网格都用对应的中心点位置坐标进行表示。选取NU架同构无人机执行协同区域搜索任务，其对应集合为U=｛U1，U2，…，UNU｝。假设有NT个目标随机分布在该未知区域，相应的，其对应的集合可表示为T=｛T1，T2，…，TNT｝，为不失一般性，目标的分布概率均满足正态分布。

在协同搜索过程中，无人机能够对其概率传感器所覆盖的网格进行独立探测，并且通信范围内的无人机彼此能够交换探测信息。以覆盖概率作为网格探测程度的评价指标，设定固定的覆盖阈值ps，当该网格的覆盖概率超过固定阈值时，则认为当前网格能够被无人机有效探测，反之不能。定义为无人机m通过单次探测能够发现目标j∈T的概率，在tk时刻无人机m对网格q探测的次数记为lm(q，tk）。因此，截止到tk时刻，无人机m对网格q在各时间点的探测次数可表示为hm(q，tk）=｛lm(q，t1），lm(q，t2），…，lm(q，tk）｝。如式(8）所示，截止到tk时刻无人机m对网格q的总探测次数即为各个时间点的探测次数之和［6］。

考虑通信时延，各架无人机需要保存接收到所有无人机的最新探测信息。在tk时刻，无人机m接收到无人机n对于网格q的总探测次数可表示为hm，n(q，tk-τn，m），τn，m为随机有界的通信时延。而无人机m获得所有无人机的总探测次数信息可表示如下：

在tk时刻，依据接收到的最新探测信息，计算目标j在网格q中的发现概率如下：

如果无人机m对网格q执行一次新的探测，则无人机m对于网格q的总探测次数将变为(q，tk）=Lm(q，tk）+1。因此，当无人机m对网格q执行一次新的探测，目标j在网格q中的发现概率估计值可计算如下：

式(10）表示tk时刻目标j在网格q中的发现概率，而式(11）则表示无人机m对网格q执行一次新的探测后，目标j在网格q中的发现概率估计值。由此可估算出，当无人机m对网格q执行一次新的探测，其对在网格q内的目标j的发现概率增量可计算如下：

假设目标j在网格q内的先验概率为pj(q），因先验信息一致，对所有无人机有(q）=pj(q），因此可估算出无人机m对网格q执行一次新的探测对应的搜索收益增加值为

如式(14）所示，截止到tk时刻，整个机群的协同搜索收益可定义为目标存在先验概率与发现概率的乘积。

由式(11）～式(14）可以看出，整个搜索过程中，无人机间仅需要共享对每个网格的总探测次数。在每个探测周期内，各架无人机依据邻居无人机共享信息对所存储的各无人机总探测次数进行更新，对应更新原则如下：

当无人机m对网格q执行一次新的探测，其增加的搜索收益主要由目标存在概率、历史搜索信息及通信时延共同决定。对应的，总的搜索收益增加值可用如下公式进行估算：

若只考虑无人机单步运动规划，则可通过式(17）计算得到无人机m的最优控制输入：

1.4 图论基础知识

针对多无人机协同区域搜索，在保持通信网络拓扑连通的前提下，需要在短时间内最大化搜索收益。利用无向图表示地面站和无人机共同构成的拓扑网络，定义其为G=(V，E），V为n个顶点集合，E为节点边集。设Ni为节点vi的邻居集合，则整个连通图的邻接矩阵可表示如下：

整个连通图的拉普拉斯矩阵表示如下：

定义λi(L）为拉普拉斯矩阵的第i小特征值，满足0=λ1(L）≤λ2(L）≤…≤λn(L）。其中，λ2(L）为拉普拉斯矩阵的第二小特征值，也称作费德勒值，其表示网络拓扑的几何连通性。而无向图是否连通的充分必要条件［15］可以表示如下：

2 无人机角色切换策略

在协同区域搜索任务中，随着搜索范围的逐渐扩大，无人机群逐渐远离地面站的通信覆盖范围，为保证实时信息能够及时回传给地面站，考虑有限通信能力需要部分无人机充当中继无人机提供通信服务，确保整个搜索任务的顺利执行。

考虑存在地面站的多无人机协同区域搜索，由于无人机平台的通信能力有限，为实现远程指挥控制和实时态势感知，如图1所示，需要在地面站和远端搜索无人机间建立可靠的通信连接。

图1 存在地面站的多无人机协同区域搜索Fig.1 Multi-UAV cooperative surveillance with ground station

结合区域搜索任务特点，本文参考文献［16］提出了3种不同的无人机任务角色，用于实现协同搜索收益和网络连通性保持之间的平衡与折中。3种无人机角色分别为中继无人机、关节无人机、搜索无人机，相应的角色功能和任务目标如表1所示，具体各个角色之间的切换关系如图2所示。

表1 协同区域搜索任务中无人机角色信息Table 1 UAV roles in cooperative sur veillance

图2 协同区域搜索任务中无人机角色切换关系Fig.2 Role switch relationship among UAVs in cooperative surveillance

2.1 无人机节点重要性评估要素

在协同搜索过程中，整个通信拓扑可以视为一个复杂网络，而各架无人机可以视为复杂网络中的节点。节点重要性评估［17］是复杂网络的一个重要研究内容，目前国内外学者针对节点重要性评估提出了很多描述重要性的要素，如度中心性、介数中心性、接近中心性、特征向量中心性等［18-21］。然而针对存在地面站的多无人机协同区域搜索，为保持通信拓扑连接和协同区域搜索任务的动态平衡，显然越靠近地面站的无人机节点的重要程度越高，反之亦然。因此，现有描述节点重要性的要素并不能直接应用，需要提炼出能够准确反映无人机节点重要性差异的评价要素。

首先，频繁的角色切换不利于任务的连续性，需要设置不同的重要程度表征任务角色。其次，参照图论中最短路径，当前无人机到地面站的最小跳数通道可以最大限度降低探测信息传输时延并提高信息传输的可靠性［22］；类比图论中通过某一固定节点的全部最短路径，当前无人机在所有无人机与地面站最小跳数通道上的比值能够表征当前无人机对其他无人机通信的影响程度。针对某些特定场景，以上3个要素不足以完全区分无人机的重点程度，将当前无人机距离地面站实际距离作为补充要素用于描述节点的重要程度。

式中：i∈U为无人机序号；式(19）表示各个搜索任务角色(RV）对应的价值，考虑搜索信息的实时回传，认为网络连通性最为重要，设定各个角色价值关系为：中继无人机＞关节无人机＞搜索无人机；式(20）表示当前无人机与地面站通信所需的最小跳数(MH），chani表示无人机i与地面站间的通信通道，L(chani）表示通道chani的跳数值，而Ωi为无人机i与地面站之间所有的通信信道集合；式(21）代表无人机i的最短路径通过比(RMH），Lji为无人机j与地面站之间具有最小跳数且经过无人机i的通道数量，Lj为无人机j与地面站间具有最小跳数的通道数量；式(22）表示无人机i与地面站间的实际距离(AD），(xb，yb）为地面站的点位坐标。

2.2 基于改进逼近理想解排序法的节点重要性评估

逼近理想解排序法是一种基于多属性决策问题中的理想解和负理想解，对多属性决策问题的供选方案进行排序的方法。基于2.1节描述的4种无人机节点重要性评估要素，可以构建无人机节点的属性矩阵如下：

需要强调的是，最小跳数和真实距离值越小，其节点重要性越高。因此，需要进行取反处理，随后代入属性矩阵，完成后续运算。式中，xij为第i架无人机的第j个属性值，并对属性矩阵标准化，具体计算公式如下：

考虑评估要素作用差异，采用方根法计算权向量为ωV=(0.520 5，0.201，0.201，0.077 5）。对应的加权标准化矩阵为

依据加权标准化矩阵，可以计算得出对应的理想解和负理想解。

式中：A*和A-分别为理想解和负理想解。

目标i与理想解和负理想解之间的距离可以用式(25）进行计算：

为增加距离公式的区分度，将相对熵［23-24］代入式(25），可获得改进距离计算公式：

可计算出各节点距离理想解的接近度：

接近度作为无人机节点重要性评估的最终评估指标，显然，若C*i越大，对应节点重要性越高，反之亦然，即=0对应最不重要的节点，=1对应最重要的节点。因此接近度越大，节点重要性越高，而对接近度进行排序，即可确定NU个备选方案的最优排序。

2.3 无人机协同区域搜索角色切换策略

依据改进的逼近理想解排序法，可以获得无人机节点重要程度序列VSeq。依据无人机节点重要程度序列，提出协同区域搜索角色切换策略实现网络连通性和协同搜索收益的平衡。

协同搜索任务中，设当前所需中继无人机数目为NR，其最大值为NU-2。为简化计算，假设同一时刻只对最远端中继无人机的角色进行调整，即增加或减少中继无人机，从而实现对搜索区域的动态调整。定义序列VSeq中第n重要的无人机为nth无人机，其与无人机的ID并不一一对应，定义nth无人机节点为Vn，用V*n表示无人机的信息集，包含任务角色，当前位置，重要程度最高的前继、后继无人机节点序号，盘旋点位置，依次表示为｛R，Pos，P，S，PC｝，其中盘旋点是固定翼无人机充当中继时的盘旋圆圆心。

无人机角色切换由2个阶段构成：角色分配和角色调整。在角色分配阶段，需要先对无人机节点重要性进行评估，获得重要程度序列VSeq。1st～无人机被指定为中继无人机，第(NR+1）th无人机作为关节无人机连接中继无人机和搜索无人机群，而剩余的无人机则作为搜索无人机继续执行搜索任务。由于在协同区域搜索任务中为扩大搜索范围，在通信保持的前提下显然增补中继无人机比移除中继无人机更重要，在角色调整阶段，依据搜索无人机群、关节无人机及第个中继无人机彼此位置关系，优先考虑增补中继无人机。完成无人机角色调整。

如图3所示，rcomm为无人机通信距离。设定2个距离阈值用于判断无人机彼此的位置关系，其中rstr为搜索无人机远离时需要增补中继无人机的距离阈值，rrts则对应需要移除中继无人机时的距离阈值，而zbuffer=｛x：rrts≤x-xu≤rstr｝作为角色切换缓冲区，能够防止无人机角色频繁切换。

图3 角色调整阶段无人机相对位置关系Fig.3 Geometry relationship among different UAVs in role conversion stage

首先考虑搜索无人机群是否远离关节无人机。如果没有搜索无人机在关节无人机(NR+1）th的圆域z1=｛x：x-xu≤rstr｝中，则表明搜索无人机群正在远离中继无人机，网络拓扑可能出现中断。因此，关节无人机需要切换为中继无人机防止通信中断，通过增加中继无人机来扩展通信范围，选取(NR+2）th无人机作为新的关节无人机。

如果没有增补中继无人机，则应该考虑是否需要移除中继无人机。如果在第架中继无人机，即距离地面站最远端的中继无人机的圆区域z2=｛x：x-xu≤rrts｝中存在至少一架无人机，则表示第架无人机附近存在其他无人机，其没有必要继续充当中继无人机。此时需要调整中继无人机的数目为(NR-1），而第个无人机切换为新的关节无人机，原先的关节无人机变为搜索无人机，用于扩大区域搜索范围。

考虑无人机最小转弯半径约束，为保持网络连通性，固定翼无人机需要在指定的盘旋点附近进行盘旋确保通信连接。本文不考虑地面障碍物遮挡的影响，因此中继无人机的盘旋点可按照等间隔分布在地面站和搜索无人机群的质心之间，相邻盘旋点的间隔设定为rstr。相应地，定义和分别代表第nth无人机的圆区域z1、z2内无人机数量，相应的角色切换策略伪代码如下。

输出：所有无人机的角色VRi和盘旋点，i=1，2，…，NU。

//角色分配阶段

1.计算RV、MH、RMH、AD值(见式(19）～式(22））。

2.计算无人机节点重要程度序列VSeq(见式(23）～式(27））。

//角色调整阶段

6.else

9.endif

10.endif

11.计算盘旋点VPCi，i=1，2，…，NR。

3 基于角色的无人机运动规划

在协同区域搜索任务中，考虑无人机运动学、通信保持及机间防撞等约束，基于邻居信息和当前无人机任务角色，通过分布式滚动时域优化［25］实现每架无人机在线运动规划。依据式(1），无人机运动学模型的离散形式可表示如下：

式中：xk为无人机的状态向量；uk为控制输入；TS为计算步长。假设规划时域长度为N，相应地，滚动时域控制序列为uk=［，，…，-1］。依据协同区域搜索任务角色设置，各架无人机的优化指标存在一定的差异。对于搜索无人机和关节无人机，其优化目标是最大化协同区域搜索收益值，对应的目标函数可以表示如下：

对于中继无人机，其首要任务是在指定位置附近进行盘旋确保网络通信连通。相应地，优化目标函数可以表示如下：

考虑通信保持和机间防撞约束，在滚动时域优化过程中设计惩罚函数用来表征可能导致碰撞或网络中断的无人机运动规划结果，相应的惩罚函数可以表示如下：

考虑通信保持、无人机运动学及机间防撞等约束，对于所有无人机m∈U，在每个预测时刻，即对于∀i=1，2，…，N，应满足如下约束：

将惩罚函数(31）代入到各无人机的目标函数中，相应的改进目标函数如下：

在每一个采样时刻，结合局部信息及当前无人机任务角色，通过分布式滚动时域控制优化每架无人机的最优控制序列。

4 仿真结果与分析

4.1 基于角色切换策略的多无人机协同区域搜索仿真分析

对基于角色切换策略的多无人机协同区域搜索方法进行仿真验证，指派8架同构无人机对一个5 000 m×5 000 m的矩形区域进行协同搜索，目标搜索信息通过机间数据链实时回传至地面站用于战场态势感知。假设区域内随机分布着10个未知目标，满足以目标所在位置为中心，均值为0，标准差为250 m的正态分布。整个区域均分为50×50个等面积网格，任一无人机m∈U通过一次探测对于在网格q内目标j∈T的发现概率为=0.5。设定多无人机协同区域搜索的仿真步数为400，采样时间为0.5 s，滚动时域优化的时域长度为4。性能参数v0、vmax、ωmax、rcomm、rsafe分别为80 m/s、20 m/s、0.8 rad/s、1 000 m、50 m。在角色切换策略中，切换为中继无人机的阈值距离为rstr=700 m，而切换为搜索无人机的阈值距离为rrts=400 m。为确保通信连接，搜索无人机和中继无人机的通信惩罚距离分别设置为900 m、650 m，而机间防撞惩罚距离设置为200 m。

图4为各架无人机的搜索轨迹，图中颜色较深的网格区域代表目标存在区域。初始时刻各架无人机以200 m的等间隔从未知区域下方开始进行搜索，由搜索轨迹可以看出，随着搜索任务的进行，机群对所有的潜在目标都进行探测搜索，各架无人机通过合理有效的角色切换，尽可能扩大搜索区域范围，这也体现出基于角色切换策略的多机协同区域搜索的可行性和有效性。

图4 多无人机协同区域搜索轨迹Fig.4 Multi-UAV cooperative surveillance trajectories

由图5的协同搜索收益曲线可以看出，随着搜索范围的扩大，发现目标数量和协同搜索收益都逐渐增加。但由于目标随机分布，以及机群需要与地面站保持通信连接，致使不同时段内获得的协同搜索收益存在差异。但随着搜索任务的执行，所有潜在目标均被发现，这也反映出角色切换策略在协同区域搜索任务中的可行性和有效性。

图5 多无人机协同区域搜索收益Fig.5 Payoff in multi-UAV cooperative surveillance

由图6可以看出，λ2＞0始终满足，这表明在整个搜索过程中，随着无人机的相对运动和角色切换，通信拓扑始终保持动态连接以适应搜索任务的需求。在任务初始阶段，λ2值较大，这是由于多架无人机从距离地面站较近的初始位置出发，网络连通度较高。随着无人机逐渐远离地面站，部分无人机切换为中继无人机，搜索范围扩展的同时网络连通度逐渐下降，λ2值逐渐减小。

图6 拉普拉斯矩阵第二小特征值Fig.6 The second smallest eigenvalue of Laplacian matrices

图7为协同区域搜索任务中不同时刻对应的各无人机拓扑连通。在任务初始阶段，多架无人机处于地面站通信范围内，此时所有无人机均为搜索无人机。随着搜索范围的逐渐扩大，为确保通信连接，部分无人机需要切换角色变为中继无人机，在地面站和搜索无人机群之间建立动态通信连接。在tk=30 s时，无人机节点重要性序列为VSeq=｛3，2，1，6，5，4，7，8｝，所需的中继无人机数目为NR=2。基于角色切换策略，无人机3、2被指派为中继无人机，而无人机1作为关节无人机连接搜索无人机群6、5、4、7、8和中继无人机2。较比tk=20 s，随着搜索无人机群逐渐远离地面站，无人机2已由关节无人机切换为中继无人机，在确保通信的前提下，使得搜索区域范围得以扩大。由tk=75 s和tk=160 s的瞬时拓扑可以看出，在每个采样时刻，地面站依据各架无人机的瞬时信息，计算出各架无人机的重要程度，并为其分配不同的任务角色，随着角色的有序切换，实现协同区域搜索任务和网络拓扑连通性的平衡。

图7 多无人机协同区域搜索中无人机角色切换Fig.7 UAV role switch in multi-UAV cooperative surveillance

图8反映了区域搜索过程中各架无人机间的距离信息。其中，图8(a）中的红色实线表示为保持必要通信连接，各架无人机与其最小邻居无人机集合间的最大机间距离，而蓝色虚线则代表整个无人机编队内最近2架无人机间的相对距离。图8(a）中，上下2条虚线分别为无人机有效通信距离和最小安全距离，可以看出整个搜索过程中，2条机间距离曲线都在指定区间内且具有一定安全阈值，这也体现出在滚动时域优化中引入惩罚函数对通信保持和机间防撞的有效性。

图8 相对距离曲线Fig.8 Relative distance curves

4.2 传感器探测能力对多无人机协同区域搜索的影响

通过调整距离、方位角和俯仰角参数体现概率传感器探测能力差异，针对每种探测能力均重复10次仿真，对应的平均协同搜索收益曲线如图9所示。考虑不同探测能力、协同搜索收益随任务进行而快速增加，这表明角色切换策略对扩大搜索范围的有效性，通过曲线对比可以看出，传感器性能提升有助于协同搜索收益的增加。然而，仅单方面提升传感器性能并不能确保协同搜索收益一直保持快速增加，这主要受限于无人机的有限机动能力，如最大飞行速度。

图9 不同传感器能力下的协同搜索收益Fig.9 Cooperative search payoff under different sensor capacities

考虑常用的评价指标，如发现目标数目、网格探测比例等，搭载不同传感器的协同搜索对比结果如表2所示，其中平均最小完成任务时间是指所有潜在目标均被发现所需要的时间。可以看出，传感器性能改善能有效提高协同搜索收益，但随着传感器能力提高，协同搜索收益增长率会逐渐下降，而这与之前分析结果一致。

表2 不同传感器能力下的多无人机协同区域搜索结果Table 2 Multi-UAV cooperative surveillance results under different sensor capacities

4.3 搜索策略对多无人机协同区域搜索的影响

显然，不同的搜索策略会对协同搜索产生不同影响。采用Zamboni策略［26］与将角色切换策略进行对比，其是一种通过预先规划指定搜索路径的确定性策略。此外，不考虑地面站和角色切换策略，设计仅考虑搜索机群的拓扑连通性和搜索收益最大化的简单策略。

针对不同策略均进行10次重复仿真，仿真结果如图10所示。比较Zamboni和搜索收益最大化策略，角色切换策略能够获得最大协同搜索收益，Zamboni策略因预先规划路径确保能够覆盖整个区域，但受到随机目标分布影响，其最后完成搜索任务。作为一种简单搜索策略，搜索收益最大化策略不考虑与地面站保持通信，能够最先完成搜索任务，但其与Zamboni策略一样不能始终保持与地面站的通信连接，而角色切换策略在保持通信连通的前提下，能够在较短时间内完成搜索任务，这也体现出基于角色切换策略的多无人机协同区域搜索方法的可行性和有效性。