基于规则的无人机集群区域协同搜索算法

The Regional Collaboration Search Algorithm of UAV Swarm Based on Rules

摘要: 区域搜索是无人机集群非常重要的一个应用方向，而科学合理的控制算法是提高集群执行任务效率的最有效途径。现有的规划控制算法存在非自主、规模小、计算复杂等不足之处，本文针对大规模无人机集群对不确定区域执行搜索任务，基于Boids动力学模型提出了一种基于规则的区域协同搜索算法，该算法具有自主性好、鲁棒、计算简单以及在理论上能以概率1实现搜索区域全覆盖等优点，并且通过仿真验证了该算法的有效性。

Abstract: Regional search is a very important application direction for UAV swarms, and adopting scientific and reasonable control algorithm is the most effective way to improve the efficiency of swarms executing tasks. The existing planning control algorithms are involuntary, small-scale, and computationally complex. This paper proposes a rule-based regional collaboration search algorithm, based on the kinetic model—Boids, for large-scale UAV swarms to perform search tasks on uncertain regions. The search algorithm has the advantages of good autonomy, robustness, simple calculation and theoretical full coverage of the search area with probability 1. The effectiveness of the algorithm is verified by simulation.

1. 引言

相对有人机，无人机具有无人员伤亡、成本低、适应复杂环境作业等诸多优越性能，更适合执行4D (Dull, Dirty, Dangerous and Deep)任务 [1]，而相对于单个无人机，多无人机集群则更加灵活，容错性也更好，能满足多种任务的需要，其中区域协同搜索是其中一种重要的任务类型，比如人员搜救、情报侦察和森林救火等。该类型的任务主要有两个方面研究侧重：一是以较小的搜索代价对特定区域内可能存在的目标进行搜索；二是合理地控制多个无人机，使得区域搜索覆盖率最大，本文的研究属于第二种。

由于无人机集群具有非常广泛的应用前景，区域搜索问题也引起了许多学者的关注。文献 [2] 对多UAV协同区域覆盖进行了研究，将求解问题分为任务区域分配和完全覆盖路径规划两个子问题，给出了在特定多边形区域下，最小代价的搜索模式和搜索路径；文献 [3] 提出了一种基于模型预测控制理论和遗传算法的多UAV协同搜索算法，旨在降低环境的不确定度；文献 [4] 针对降低环境不确定度的问题，基于搜索概率图，提出了一种协同进化算法，对多UAV协同搜索路径进行规划；文献 [5] 提出了一种分布式概率图更新模型和多主体协同控制方法，能够对多个移动地面目标进行有效地协作搜索；文献 [6] 在UAV动力约束的基础上，针对常用搜索样式“Z”字形和内螺旋的缺陷，对常用的区域搜索算法进行了改进；文献 [7] 提出了一种基于预测控制思想的多无人机协同区域搜索算法，研究各种通信约束对多无人机协同区域搜索效能的影响。但是这些研究可能存在以下局限：1) 无人机数量较少，对每一架无人机，都使用设计的代价函数进行路径规划。当无人机增多时，可能会使得计算量非常大。2) 将搜索区域离散化，无人机的运动是从一个网格跳跃到另一个网格，覆盖率的计算也是基于网格的，可能与实际情况不符。3) 搜索区域较小，比如文献 [4] 和 [7] 仿真采用的网格分别为 $30\times 30$ 和 $40\times 40$，当搜索区域增大，其算法的计算量和有效性可能并不一定很好。4) 部分算法要求无人机具有额外的储存能力。比如文献 [7] 对搜索区域建立了搜索概率图，这增加了每一架无人机额外的硬件负担，并且概率图的时刻更新也加大了无人机之间的通信负载。

针对现有算法存在的以上不足，本文做了一些探索，提出了一种基于局部规则的集群区域协同搜索算法。该算法借鉴了自然界自组织生物群体的运动规则，设计了离心、无序、分离、惯性和随机等六个规则及相应的搜索算法，使无人机能够迅速有效地扩散到目标搜索区域，并且对于搜索过的区域，未来某个时刻可进行重复搜索。该算法在理论上能以概率1对目标区域实现全覆盖，并且具有计算简单、鲁棒等特点，适用于环境规划复杂、无人机数量规模大、搜索区域宽广的任务场景。本文通过仿真对提出的算法的有效性进行了验证。

2. 集群协同搜索问题建模

2.1. 问题描述

假设存在一块 $l\times l$ 的矩形目标区域，区域中可能存在火灾点或者受难人员，但其具体位置信息未知。现在使用无人机集群对该区域进行搜索，要求尽量提高覆盖率从而减小环境信息的不确定度。

考虑到现实环境和硬件制约，无人机的运动需遵循以下规则：

1) 运动具有连续性。

2) 无人机的通信距离有限。

3) 个体之间存在最小距离。

从物理学的角度，规则1) 是集群必须遵守的物理学原理，因为无人机不可能从区域的一端跳跃到另一端，它需要一个持续的运动过程。其中规则2) 考虑的是无人机的通信约束，现实生活中的无人机，由于硬件成本以及通信技术的限制，无人机的通信距离不可能无限远。规则3) 也非常有必要，为了保证无人机集群能够顺利地执行任务，个体之间的距离不能超过阈值，不然就可能发生碰撞而撞毁。

在遵循这些规则的前提下，如何使集群高效地完成搜索任务，本文对此进行了探究。

2.2. 集群控制算法

无人机集群对不确定区域执行搜索任务，其行为过程类似于蚁群等生物群体在未知环境中寻找食物，应当具有一定的自主性和鲁棒性。如果将每一架无人机都类比为生物个体，则可将无人机集群看作是一类特殊的生物群体。

描述生物群体的运动，1987年Reynolds [8] 提出了一个经典的Boids模型，它遵循以下三个规则，如图1所示。

1) 集聚。

2) 对齐。

3) 分离。

Figure 1. Boids model rules: Cohesion, Alignment, Separation

图1. Boids模型聚集、对齐、分离规则

其中：规则1) 描述的是群体中的个体都有着向自身邻域中心运动的趋势，这是因为处于集群边缘的个体往往受到外界更大的威胁，向邻域中心运动可以减小这种威胁。规则2) 描述的是个体的速度方向会趋向于邻域中个体的平均速度方向，这能保证自身与群体的协同性，使自己不跑出所在的群体。规则3) 保证了个体的自身安全，使个体远离较近的其他个体。

然而对于执行搜索任务的无人机集群而言，直接应用这些规则并不合适。因为商业应用的无人机一般不存在威胁，并且如果考虑威胁可以使用很多其他比“聚集”更有效的技术手段来应对，而且为了保证覆盖率，无人机并不需要向着同一方向运动。

经过分析，本文将区域协同搜索的无人机集群的运动规则改进如下：

1) 离心。个体具有远离邻域中心的运动趋势。

2) 无序。无人机个体具有使速度方向各异的趋势。

3) 分离。无人机之间存在最小距离。

4) 惯性。无人机具有保持上一时刻速度方向不变的趋势。

5) 随机。无人机在每个时刻有个随机运动的趋势。

6) 反向。当无人机飞出目标搜索区域时，其反向飞行。

基于Boids模型改进和增加的这些规则，都是根据任务特性以及科学的逻辑来制定的，可以让集群充分散布到目标区域，从而提高集群的覆盖率，减小区域的不确定度。其中：规则1) 的目的是让无人机个体向着无人机数量较少的地方运动；规则2) 让无人机的运动方向各异，从而提高搜索效率；规则3)是为了保证无人机自身的安全；规则4) 是使无人机具有向前运动的趋势，防止无人机在短时间内对搜索过的区域进行重复搜索；规则5) 让无人机具有一个随机运动的趋势，使得无人机集群在理论上能以概率1对目标区域实现全覆盖；规则6) 保证无人机不会飞出目标区域。

假设第i架无人机在t时刻的速度和位置分别为 $v_i^t$ 和 $x_i^t$，根据以上运动规则，则有：

$\{\begin{array}{l}{v}_i^{t+1}=v_i^t+c_1{a}_1+c_2{a}_2+c_3{a}_3+c_4{a}_4+c_5{a}_5\\ x_i^{t+1}=x_i^t+v_i^{t+1}\end{array}$ (1)

式中 $a_1~a_5$ 分别表示规则1)~5)产生的加速度， $c_1~c_5$ 是权重，表示各个规则对无人机的速度的影响程度。对于无人机个体i，其速度和位置更新的具体算法如表1：

Table 1. The UAV swarms’ speed and position updating algorithm

表1. 无人机集群速度和位置更新算法

算法中r表示无人机的通信距离， ${\bar{x}}_i^t$ 和 ${\bar{v}}_i^t$ 分别表示处于通信范围内无人机个体(不包含自身)的平均位置和速度，具体计算见公式(3)和公式(4)； $r_c$ 为距离阈值，当无人机之间的距离小于 $r_c$，则会相互分离，m为 $r_c$ 范围内的其他无人机数量， $\bar{s}$ 为搜索区域的几何中心。

$k=Neigh\left(x_i^t,r\right)$ (2)

${\bar{x}}_i^t=\{\begin{array}{l}{x}_i^{t}k=0\\ \frac{1}{k}{\displaystyle \underset{j=1}{\overset{k}{\sum }}{x}_j^t}k\ne 0\end{array}$ (3)

${\bar{v}}_i^t=\{\begin{array}{l}{v}_i^{t}k=0\\ \frac{1}{k}{\displaystyle \underset{j=1}{\overset{k}{\sum }}{v}_j^t}k\ne 0\end{array}$ (4)

式中 $Neigh\left(x_i^t,r\right)$ 是一个邻域函数，表示无人机 $x_i^t$ 周围半径r范围内的其他无人机数量。

2.3. 搜索效率评估

评估构建的协同搜索算法优劣，覆盖率是一个非常合适的指标 [7] [9] [10]，其具体含义是无人机侦察覆盖的总面积与目标区域面积之比。其主要有以下几种类型：

1) 瞬时覆盖率

$C_t=\frac{{\displaystyle \underset{i=1,\cdots ,n}{\cup }{S}_i^t}}{S}$ (5)

表示某个时刻无人机总的覆盖面积与目标区域面积之比，可以体现该时刻无人机在空间上的分布情况。其中 $S_i^t$ 为t时刻第i架无人机覆盖面积，S为目标区域的总面积。适合用来评估对每个时间点都有要求的任务，比如监视动物群，要求每个时刻处于无人机集群视野范围之内动物的数量不能少于90%。

2) 持续覆盖率

$C_{con}=\frac{{\displaystyle \underset{t=0,\cdots ,T}{\cap }\left({\displaystyle \underset{i=1,\cdots ,n}{\cup }{S}_i^t}\right)}}{S}$ (6)

表示整个任务执行时间内都处于无人机覆盖范围内的区域面积与总的目标区域面积之比。适合于评估某些特殊任务，比如对重要目标的监视，要求目标时刻处于监视之下。

3) 总覆盖率

$C_{total}=\frac{{\displaystyle \underset{t=0,\cdots ,T}{\cup }\left({\displaystyle \underset{i=1,\cdots ,n}{\cup }{S}_i^t}\right)}}{S}$ (7)

表示整个时间段内，无人机总的覆盖面积与目标区域面积的比值。适用于实时性要求不高的任务，比如土地测绘、喷洒农药等，只要求无人机对每一个地区经过一次。

覆盖率的计算是比较复杂的，特别是当无人机数量非常多的时候，这涉及计算每一个无人机的覆盖面积，然后求和并减去重复的覆盖面积，计算量往往很庞大。为了克服这个问题，文献 [11] 提出了一种空间分布熵的方法来衡量无人机在空间分布上的性能，可以极大地简化计算量。其具体思想是，将目标区域用Voronoi图划分，然后统计每个子区域上的无人机数目，最后通过公式 $H=-{\displaystyle \underset{i=1}{\overset{n}{\sum }}{p}_i\ln \left(p_i\right)}$ 计算熵。但是该方法也有局限，Voronoi图的划分具有一定的主观性，划分结果不同，最终的熵也会不同。并且它不能体现子区域上无人机数量一样，但分布不一样时，无人机集群性能的差别。随着计算机硬件以及软件的发展，很多计算问题已经变得相对简单，借助图像处理技术，本文选取总覆盖作为集群区域协同搜索的评估指标。

3. 仿真分析

假设目标搜索区域为 $800\times 800$ 的矩形，现在使用50架小型的无人机对该区域进行搜索。无人机集群的相关参数设置如表2：

Table 2. Simulation parameter setting

表2. 仿真参数设置

假设无人机集群中每一架无人机都不受其他无人机影响，并且每个时刻其速度有一个向左或者向右随机偏转(偏转角小于等于 $\pi /4$ )，而当无人机飞出目标区域之后，其速度会反向以保证无人机始终处于搜索区域内，本文称这种搜索算法为随机搜索算法。下图是本文构建的协同搜索算法和随机搜索算法总覆盖率的对比。

Figure 2. Comparison of coverage between rule-based collaborative search and random search

图2. 基于规则的协同搜索与随机搜索的覆盖率对比

图2显示，随着时间推移，基于规则的协同搜索算法和随机搜索算法的覆盖率都增加，但是本文构建的算法覆盖率增加更快，并且最后接近于1，这是因为只要时间足够长，随机规则就可以使无人机集群对目标区域实行全覆盖，而离心、无序和分离等规则加速了这一过程。相对而言，随机搜索算法的覆盖率虽然也增加，但增加较为缓慢，这说明本文构建的协同搜索算法确定能提高集群的搜索效率。

经分析，这是由于离心、无序、分离等规则会加快无人机的扩散，使无人机更快飞向未曾搜索过的区域。其搜索过程详细对比如图3和图4所示，图3为集群中两架无人机分别在基于规则的协同搜索算法和随机搜索算法控制下的路径对比，图4为在时间步T分别为250、500、1000时两种算法控制下无人机集群的分布对比。

Figure 3. Comparison of single UAV path between rule-based collaborative search and random search

图3. 基于规则的协同搜索与随机搜索单个无人机路径对比

(a) T = 250 (b) T = 500 (c) T = 1000

Figure 4. Comparison of UAV distribution at different times between rule-based collaborative search and random search

图4. 不同时刻基于规则的协同搜索与随机搜索无人机分布对比

图3中，B-UAV表示基于规则的协同搜索算法无人机路径，R-UAV表示随机搜索算法无人机路径。图3显示，基于规则的协同搜索算法，无人机运动更远，运动的区域更大，并且具有一定回旋，在一定程度上能对经过的区域进行重复搜索。图4中，箭头的位置表示无人机位置，箭头的方向表示当前时刻无人机的速度方向，从T = 250、500、1000时间步，两种算法下无人机的分布显示，基于规则的协同搜索算法扩散更快，搜索区域也更大。

综上，本文提出的基于规则的协同搜索算法，能够有效地提高无人机的搜索效率。

4. 结论

基于描述自然界生物群体运动的经典模型——Boids模型，本文改进和增加相关局部规则，提出了一种基于规则的协同搜索算法，该算法通过离心、无序、分离、惯性、随机等规则作用于无人机个体，使无人机集群能够高效地散布于搜索区域。并且通过仿真，本文验证了该算法的有效性。通过比较发现，随机搜索算法控制下的无人机集群，无人机扩散较慢，搜索效率明显低于本文提出的基于规则的协同搜索算法。而基于多个局部规则运动的无人机则能够较为迅速地飞到较远的地方，对未知区域进行搜索，从而迅速提高覆盖率。