基于搜索意图交互的无人机集群协同搜索算法

王宁，李哲，*，梁晓龙，侯岳奇，吴傲

（1.空军工程大学 空管领航学院，西安 710051； 2.陕西省电子信息系统综合集成重点实验室，西安 710051）

广域目标搜索是现代作战中的一项重要技术，美军已将无人机（unmanned aerial vehicle，UAV）具备广域目标搜索能力确定为UAV技术的中长期发展目标［1-4］。UAV集群具有卓越的广域搜索能力，能够通过UAV之间的协同合作，实现整体能力涌现，即系统涌现出的能力远超系统内单架UAV能力的总和［5-6］。因此，使用多架UAV组成集群执行目标协同搜索任务得到了日益广泛的关注［7-8］。其中，搜索区域处理与协同搜索策略是UAV集群协同搜索关注的2个主要问题［9］。已有诸多学者对上述问题进行了深入的探索并取得了丰硕成果。

在搜索区域处理方面，提出的主要方法有凸多边形区域分割、凹多边形凸处理、Voronoi图等，主要是将形状复杂的搜索区域分割为特定形状的子任务区域，进而通过UAV集群内部的任务分配提高UAV协同搜索效率。其中，Pehlivanoglu［10］和Guruprasad等［11］提出了使用Voronoi图对搜索区域进行分割的方法，受到了广泛关注，但该方法分割出来的区域具有不确定性［9］，且运算量大，具有一定的局限性。谢朋志和魏晨［12］提出了一种任意搜索区域的等面积单侧区域分割方法，先将任意多边形采用格雷厄姆法拓展为凸多边形，然后进行等面积划分，根据划分区域形状配置UAV起始位置，提高了UAV协同搜索效率；于驷男等［13］根据无人机数量、初始位置将凸多边形搜索区域分割成若干子区域，以UAV总转弯次数作为搜索效率评判标准，提出了一种协同区域分割的有效方法。但上述成果主要应用于静态搜索规划中，无法有效应对搜索过程中UAV故障、火力威胁等突发情况。

在协同搜索策略方面，主要包括滚动时域优化（receding horizon optimization，RHO）［14-17］、动态规划［18］、协同进化算法［19］等方法。其中，文献［15，20-21］提出的动态决策方法较为典型，通过模型预测控制（model predictive control，MPC）方法，使每架UAV根据当前环境信息做出最大收益决策，并通过仿真实验验证了UAV协同搜索过程中动态决策相对预先规划的突出优势。文献［22］提出的分布式模型预测控制（distributed model predictive control，DMPC）框架将集中式多UAV在线优化决策转化为小规模分布式优化决策，是一种有效降低搜索决策问题求解规模的算法，得到了广泛应用。但上述研究主要是针对形状规则的任务区域展开的，仍然存在不足。其中，文献［20-21］未考虑UAV集群协同的通信约束和防相撞约束；文献［7］虽然考虑了集群协同的防相撞问题，但仅通过配置不同高度实现防相撞，并未考虑高度变化对UAV探测范围产生的影响；文献［15，23-24］使用了“粗粒度”的UAV运动模型，降低了决策结果的精细程度且未考虑集群协同搜索时的防相撞及抗毁性问题。

综合国内外研究现状可以看出，UAV集群具备了一定程度的协同搜索能力，但存在以下不足：

1）动态决策搜索方法普遍面向规则的矩形搜索区域，对不规则区域的研究较少。

2）对集群协同搜索过程中的通信问题和避撞问题未予以考虑或过于简化。

3）对UAV集群协同搜索过程中抗毁性的研究较少。

针对上述问题，本文做了以下工作：

1）建立了针对不规则搜索区域的环境地图模型。

2）引入了协同搜索过程中防相撞与通信拓扑条件对UAV集群的约束。

3）在分布式最优决策基础上，引入了滚动优化决策和MPC思想，实现了集群搜索过程中的意图交互，保证了协同搜索任务中UAV集群在未知威胁条件下的可用性。

1 协同搜索任务建模

1.1 任务描述

UAV集群协同搜索任务通常分为区域覆盖任务和目标搜索任务［21-22］。前者是在难以获取任务区域先验信息的条件下，使UAV集群尽快完成最大化覆盖面积的飞行。后者是在已知任务区域内目标位置、数量、重要性等先验信息的条件下，综合考虑飞行代价和任务效率，通过UAV集群实现对区域内所有目标信息的获取。本文针对第1类问题展开研究，UAV集群携带通信设备和光学传感器对未知任务区域展开搜索，如图1所示。

图1 UAV集群协同搜索示意图Fig.1 Schematic diagram of UAV swarm collaborative search

1.2 任务区域建模

图2为不规则任务区域Ω示意图。首先，任选4个可行顶点构造尺寸为Lx×Ly的外接矩形。然后，将此矩形区域按照固定间隔Δd栅格化为M×N的环境地图。最后，建立笛卡儿坐标系，分别用横向坐标x和纵向坐标y来描述环境地图中的每个栅格：

图2 任务区域栅格化Fig.2 Rasterized task area

式中： 表示向上取整。

该环境地图中任意栅格的位置可以表示为

进一步定义k时刻环境地图中栅格（i，j）的状态：

式中：Ωc（k）为k时刻已搜索栅格；Ωnc（k）为k时刻未搜索栅格；I为非任务区域。从而可以得到k时刻的环境地图矩阵GM×N（k）为

1.3 UAV系统模型

UAV在携带光学传感器执行搜索任务时，为保证成像尺寸的一致性，一般不进行高度调整，而是通过调整偏航角完成避障、航线修正等动作。由于只关注UAV的运动轨迹，为简化分析，将UAV视为二维空间中匀速运动的质点［14-15］，其离散状态空间方程为

式中：（xi（k），yi（k））为k时刻集群中UAVi在环境地图中的位置；ψi为UAVi的航向角；控制变量ui为偏航角，满足ui∈［-umax，umax］，umax为受机动性能限制下的最大转弯角；v0为UAV平飞速度；Δt为决策步长。

记k时刻UAVi的状态变量pi（k）为

则k+1时刻UAVi的状态变量为

式中：f（·）为状态转移函数，由式（5）确定；ui（k）为该UAV在k时刻的控制变量。

进而有UAVi在k+j时刻的状态变量预测量为

式中：NUAV为UAV集群规模；T为预测周期。

在给定T步预测输入后，可以根据式（7）预测出未来T步以内的UAV航路，如图3所示。

图3 UAV i航路预测图Fig.3 UAV i route forecast chart

2 环境地图更新与融合

2.1 UAV探测矩阵

考虑到CCD、CMOS等光学传感器的成像范围一般为矩形，先将UAV传感器探测模型简化为以UAV质点为中心的W×H矩形区域。然后，将该矩形区域栅格化为P×Q个栅格，如图4所示。

图4 UAV探测区域栅格化Fig.4 Rasterized UAV detection area

进而可以确定UAV探测矩阵ΓP×Q的行数P和列数Q为

式中：W和H分别为传感器有效探测区域的宽度和长度；Δd为环境地图中栅格的尺寸大小；为向下取整函数。

结合式（3）定义ΓP×Q中的值全为-1，得到最终的UAV探测矩阵为

2.2 环境地图更新算子

借鉴文献［21］中使用Hadamard积进行环境地图矩阵更新的思想，定义UAV探测矩阵与环境子矩阵之间的信息更新算子“◦”：

其物理含义为：当UAV探测未知栅格后，该算子可将环境地图矩阵中该栅格状态由-1变为+1，即由未知转变为已知；当UAV探测非任务区域时，环境信息矩阵中相应栅格的状态仍为0，即环境地图不进行更新；当UAV探测已探测栅格后，环境地图矩阵中仍将该栅格状态标记为+1。

其数学运算式为

将UAV探测矩阵与环境地图矩阵中的相应环境子矩阵进行信息更新运算，即可实现环境地图矩阵的更新，如图5所示。

图5 环境地图矩阵更新流程Fig.5 Update process of environment map matrix

2.3 环境地图融合算子

通过定义环境地图更新算子，每架UAV在搜索过程中可根据自身决策量更新环境地图。但要获取集群协同搜索过程中不断更新的全局环境信息，还需对每架UAV更新的环境地图进行整合。文献［14］提出了广播式通信条件下的地图信息融合方法，通过获取每架UAV的实时决策量集中更新环境地图，实现了集群协同搜索过程中的环境地图融合，但该方法对通信条件要求高且运算量较大。因此，本文提出一种分布式环境地图融合方法，每架UAV仅根据自身状态更新环境地图矩阵。然后，通过环境地图融合算子对其他UAV的环境地图矩阵进行环境信息融合，能够减少每架UAV进行环境地图更新所需的运算量。

设k时刻UAV通过自身状态更新所获得的环境地图矩阵为Gi（k），此时可接受其他UAV的环境地图矩阵为Gj≠i（k），定义环境地图矩阵中元素融合运算为

式中：“⊙”为环境信息融合算子，运算结果如表1所示。

表1 环境地图融合算子运算规则Table 1 Environmental map fusion operator operation rules

与文献［14，21］提出的环境信息融合方法相比，通过环境地图融合算子进行环境融合时，不需要根据其他UAV预测控制量更新环境地图，只需根据自身预测控制量更新环境地图矩阵。然后，通过环境地图融合算子与获得的其他UAV环境地图矩阵进行融合计算，即可得到实时环境地图矩阵。

此外，在文献［14-15］中，当k时刻某架UAV通信中断，后续决策就会一直缺失k时刻该UAV的决策信息。而通过意图交互方法决策时，每架UAV始终获取其他UAV的最新环境信息矩阵，即使某架UAV通信中断一定时间，一旦通信恢复就能够恢复该UAV历史决策信息，使后续决策不受通信中断的影响。

3 搜索回报函数与意图交互策略

3.1 搜索回报函数

通过搜索回报函数实现UAV搜索过程中的路径决策是UAV集群协同搜索的关键［7］。针对无先验条件下的协同搜索问题，主要考虑了以下约束条件：

1）集群中每架UAV飞行时倾向于选择覆盖率增量最高的方向。首先，计算k时刻区域覆盖率为

式中：1gij（k）为随机变量，当gij（k）＞0时其值为1，反之为0。

则k～k+1时刻的覆盖率增量为

2）定义集群中每架UAV之间的安全距离为ds，记第i架UAV与集群中第j架UAV之间的距离为dij（k）：

约束条件有

则集群防相撞的约束函数为

3）为使协同搜索过程中UAV尽可能多地获取其他UAV的搜索意图，增加通信约束条件：

式中：dc为UAV的机间通信距离。

4）作为UAV的主要控制变量，偏航角的调整往往会带来较大的能量与时间损耗。因此，增加偏航角调整约束条件，偏航角调整的约束函数为

5）受任务区域边界限制，需要在UAV选择路径时增加强约束条件，使其不能越出任务区域边界。文献［21］所采用的势函数方法会使所有UAV倾向于飞向任务区域中心，最终影响搜索效率并带来相撞风险。借鉴文献［25］中地理围栏的思想，设计了约束函数式（21），UAV搜索视野中无效区域一旦超过三分之一，回报函数会迅速下降。因此，k时刻UAV边界约束条件为

综上所述，可以进一步定义搜索过程中每架UAV选择路径时的回报函数为

式中：ωt为平衡每个约束条件的取值。

3.2 基于MPC和PSO的意图交互决策

在UAV集群协同搜索过程中，本文引入了滚动时域控制中的滚动优化决策思想（rolling horizon optimization decision，RHOD）。首先，在栅格化搜索区域和确立搜索回报函数的基础上，集群中每架UAV依次采用MPC方法［21］进行最优控制输入预测，并根据输入预测更新环境地图。此时每架UAV所做出的决策都是建立在得知前一架UAV决策基础上进行的，从而实现了UAV协同搜索过程中的意图交互决策。

针对大规模的UAV集群，本文提出了基于DMPC的分布式意图交互决策。首先，集群中每架UAV根据当前环境信息同时做出预测决策，并根据预测决策量更新环境地图矩阵，生成预测环境地图矩阵。然后，将该预测环境地图矩阵向集群中其他UAV广播，每架UAV将从集群其他成员处获取的预测环境地图矩阵融合成决策环境信息矩阵（见图6），并在此基础上做出自身决策，从而实现UAV集群规模较大时的协同搜索决策。

图6 决策环境信息矩阵产生流程Fig.6 Decision environment information matrix generation process

对于集群UAVi，其搜索过程中的MPC决策流程如图7所示。

图7 UAV集群环境地图矩阵更新流程Fig.7 UAV swarm enviornment map update process

综上所述，可将集群搜索意图交互决策流程分为3步：

步骤1 意图产生。

UAVi基于自身环境地图矩阵Gi（k）和自身状态pi（k）对累积搜索回报函数进行优化求解，此时不考虑其他UAV的运动情况。其H步累积回报函数下的分布式模型预测控制结构可以表示为

步骤2 意图交互与融合。

对于小规模UAV集群的区域协同搜索，采用基于RHO的集中式意图交互策略，如图8所示。其实质是一种顺序决策，中央节点先根据初始环境地图矩阵和UAV1初始位置，通过搜索回报函数求出决策控制量u1（0），并在此基础上更新中央环境地图矩阵G（0）。集群其他成员在中央环境地图矩阵的基础上，依次在前一架UAV决策意图上进行决策，直至所有UAV完成一轮决策。在协同搜索过程中，这种决策方式要求中央节点始终能与所有UAV保持通信，是一种“星形”通信拓扑结构，且运算量会随着集群规模的增加迅速增长［22］，因此，仅适用于小规模UAV集群。

图8 集中式意图交互Fig.8 Centralized intention interaction

图9 分布式意图交互Fig.9 Distributed intention interaction

步骤3 集群分布式决策。

式中：“*”为计算出的最优控制决策；u为无人机可以采取的决策量；u*为无人机的最优决策量。

意图交互决策算法伪代码如下：

4 仿真分析

为验证本文算法的有效性，分别对无人机集群搜索进行分布式决策仿真和意图交互决策仿真。仿真条件为i5-9300H，主频2.40 GHz，16 GB内存，仿真中所用算法参数如表2所示。

表2 算法参数Table 2 Algorithm parameters

4.1 小规模集群协同搜索仿真

设定任务区域为不规则多连通域，如图10所示。任务区域外接矩形边界为800 m×600 m。在外接矩形中，用黑色表示任务区域，用灰色表示非任务区域。其中，非任务区域可根据任务区域边界、敌方火力范围和外部障碍物位置等信息进行设置。设定UAV飞行高度为8 m，光学传感器成像范围为20 m×16 m，4架UAV从任务区域不同位置进入，进入点坐标分别为（100，0）、（300，0）、（500，0）、（700，0），单位均为米/m。UAV均以10 m/s速度匀速飞行，最大转弯角为90°，仿真步长Δt=1 s，预测步长为1 s，仿真时间为600 s。

图10 三种搜索算法仿真结果Fig.10 Simulation results of three search algorithms

分别运用无意图交互的个体最优决策、分布式意图交互决策和集中式意图交互决策进行对比仿真。仿真结果如图10所示。

从仿真结果可以看出，UAV集群在对不规则任务区域协同搜索过程中，有效避开了非任务区域。从图10（a）中可以看出，在满足通信、防相撞约束的条件下，缺少意图交互的UAV集群在决策时会产生大量的重复搜索，导致整体搜索效率下降。图10（b）中，集群中每架UAV在获得其他UAV决策意图后，会做出尽量避免与其他UAV搜索区域重复的决策，使集群的整体搜索效率明显提高。图10（c）中，每架UAV根据自身编号在获取前一架UAV决策的基础上进行决策，从而获得更接近当前全局最优解的决策。从图11中可以看出，相较个体最优决策，通过意图交互能够有效提高集群的协同搜索效率。

图11 三种搜索算法覆盖率变化曲线Fig.11 Coverage change curves of three search algorithms

4.2 大规模集群协同搜索仿真

集中式意图交互决策虽然能够得到全局最优决策序列，但是其求解过程是在中央节点上进行的，随着UAV数量增加，其求解时间会迅速增大，进而导致无法在线实时决策［14，22］。而分布式意图交互决策能够适用于较大规模的UAV集群协同搜索决策，以包含10架UAV的集群为例进行仿真，结果如图12所示。

设定不规则任务区域外接矩形边界为800 m×600 m，集群中10架UAV的初始位置和航向随机分布，机间安全距离为20 m，仿真时间为360 s。设定UAV2、UAV3、UAV7、UAV8分别于100 s、120 s、330 s、300 s处被击毁，仿真结果如图12所示，可以看出在4架UAV被击毁的条件下，UAV集群仍然有效地完成了协同搜索任务。从图13中可以看出，在集群协同搜索过程中，机间距离始终大于所设定的机间安全距离20 m，满足了集群的防相撞要求。从图14可以看出，在集群中部分UAV被击毁的时刻，搜索覆盖率受到一定影响，但仍然能有效增长，最终完成协同搜索任务。

图12 10架UAV集群协同搜索仿真结果Fig.12 Collaborative search simulation results for swarm with 10 UAVs

图13 集群中机间最小距离曲线Fig.13 Curve of minimum distance between UAVs of swarm

图14 覆盖率变化曲线Fig.14 Change curve of coverage

5 结 论

1）算法在实验仿真条件下实现了较高的区域覆盖率，对比了个体最优决策与协同决策的搜索效率，体现了意图交互策略在UAV集群搜索任务中的优势。

2）采用了DMPC框架，使无人机决策过程中能够考虑长期收益并具有较快的决策速度，避免了集中式意图交互决策中较大的运算量。

3）利用环境地图更新算子和环境地图融合算子实现了环境地图的分布式更新与快速共享。

4）以区域覆盖率为引导，在通信、防相撞等关键约束的条件下，通过实验仿真验证了算法对大规模集群执行搜索任务时的可行性。

算法实现了无人机集群在火力威胁场景下的有效覆盖搜索，但针对集中式协同搜索和分布式协同搜索算法复杂度的对比分析，还有待进一步更深入的研究。