基于分布式反集群算法的无人水面艇区域覆盖方法

李亚南，黄海滨，庄宇飞，蔡春伟

（哈尔滨工业大学（威海），威海264209）

0 引言

面向无人水面艇（Unmanned Surface Vehicle，USV）的海上无人系统覆盖问题可被广泛应用于搜索营救、区域侦察观测、火力打击、信息采集、巡逻、地形测绘等任务［1］，军用和民用的大量需求使得研究无人系统覆盖问题有着十分重要的意义。

无人系统覆盖问题既要求个体有高度的自主性，又要求个体有很强的协同合作性。自主性要求个体有自主实现环境感知、信息处理、决策和行为的能力；协同的目的是获得有效的、无碰撞的覆盖路径，指示无人系统在给定的时间内覆盖搜索感兴趣的目标，尽可能多地获取任务区域的信息，获取最大收益，降低任务区域信息的不确定性。

对无人系统覆盖任务而言，为避免局部最优、降低优化或控制难度，一种有效的解决思路就是采用多边形分割、模糊C均值聚类、质心Voronoi图划分等方法把任务区域分割为与无人机（Unmanned Aerial Vehicle，UAV）等数量的子区域进行覆盖侦察［2⁃3］。另一种解决思路为编队的方法：系统中所有个体保持相对于领导者的期望距离和方向，通过控制领导者的运动并同时保持编队结构来简化无人系统的覆盖问题［4］。在未知环境下执行覆盖的一种简单方法是完全随机覆盖，个体在保持避障的基础上采用完全随机策略实现任务区域覆盖［5］。就区域覆盖和检测有效性而言，分区及编队这两种方法在已知环境下是一种非常有效的方式。这种优势来自于有效的任务分配，但是不能将其运用到高度动态变化的现实环境中，因其不具备节点故障的鲁棒性及不具备扩展性。与分区及编队这两种方法相比，随机覆盖可以在未知环境中获得使用。然而，随机覆盖不是有效的策略，因为个体可能会重复访问相同的区域而不是探索未访问的区域。为了克服上述缺点，Miao等人［6］提出一种模仿独居动物社会行为的反集群算法，并将其运用到移动监控系统中，通过邻居交流或通过环境进行交流来最大限度地扩大搜索范围并最大限度地减少重叠。仿真结果表明，反集群算法在探测率及探测时间方面均优于随机覆盖。在文献［6］的基础上，Ganganath等人［7］提出了分布式反集群算法并使用信息图来最小化覆盖区域的重叠。

本文采用分布式反集群算法解决了USV对海面区域的区域覆盖问题，通过计算每个个体在每一时刻的最大化收益方向，使得每个个体能够最大化累计覆盖面积及最小化个体之间的重叠覆盖部分。首先建立每个个体的包含覆盖历史的信息图，然后进行反集群算法的避障、去中心化及自私这3个基本属性的数学公式描述，最后进行Matlab仿真，以及进行区域覆盖性能的评估。

1 问题描述

1.1 系统建模

考虑n个USV在R2凸区域移动，将n个USV组成的无人系统定义为Vα={1，2，…，n}。 所有USV均配有取值范围为rs（rs＞0）的传感器，每艘USV都有一个范围为rc的无线通信模块。在实际应用中，rc＞2rs，使得USV能够在感知区域不重叠的情况下相互通信。

采用双积分动态模型描述USV在n维Euclid空间中的运动学模型，如式（1）所示。

其中，xi（t）、vi（t）、ui（t）分别表示第i个 USV在t时刻的位置、速度及控制输入，i=1，2，…，n。

1.2 碰撞规避

定义一个非负成对相斥势能

其中，kp是正常数，z为USV之间或USV与障碍物之间的距离。随着z→0，成对相斥势能φ（z，d）达到它的最大值。随着z→d，成对相斥势能平滑消失到0，在区间 [d，∞)保持在0。随后，使用φ（z，d）来为USV之间实现中心化及为USV与障碍物之间实现避障。

1.3 分布式反集群算法

本文采用文献［7］提出的分布式反集群算法，将分布式反集群算法概述如下。

第i个USV的控制输入由式（3）给出

式中，hi是一个二进制函数，将hi（t）定义为

去中心项的主要目的是使USV彼此保持距离，以避免碰撞，并引导其向着自私的目标前进，这最终有助于在更短的时间内达到整个区域的覆盖范围。其中，dα（0＜dα≤2rs）是USV之间的最小期望距离。

使用式（4）、式（7），以及式（8）中给出的控制输入，可将式（3）重写为

2 计算最大化收益目标

2.1 分布式信息更新

使用这个方法，第i个USV可以跟踪其覆盖历史及与其通信的其他USV的最新信息。除此之外，第i个USV可能间接地访问其非邻居的覆盖历史。

2.2 目标函数

为了最大限度地扩大区域覆盖范围，可引入最大化收益目标，以引导USV转向访问次数较少的区域，向着其最大化收益目标方向前进。

使用信息图，可以有效地确定目标的位置。USV在时刻t（t＞0）的信息图为Ii，引入效益函数λi（x，t）来评价Ii

其中，t-Ii（x）项是距离位置x上一次被访问的时间跨度，其值越大表示越长时间未访问其位置；σ为正常数。函数ηi（x）定义如下

3 区域覆盖评估结果

3.1 仿真参数设置

所需覆盖的区域为400m×400m正方形区域，半径为30m的圆形障碍物位于（90m，250m）处，边长为70m的方形障碍物左下角坐标位于（270m，50m）。将所需覆盖区域离散为1m×1m的单元格，USV在整个仿真过程中都保持在给定的区域内。为便于比较，默认在所有仿真中，下面的参数是固定的：rc=600m、dα=1.9rs、kp=25、ks=0.1、kv=0.3、σ=0.2、ε1=0.04，以及ε2=0.01，以下给出了几组不同的仿真结果。

3.2 仿真结果分析

3.2.1 性能指标分析

首先，分析在反集群算法控制下的系统采用不同数量USV在给定区域内实现100%覆盖所需的平均时间，USV 的数量为n（n∈［4，12］），rs=50m。仿真结果如图1所示。从仿真结果可以看出，完全覆盖所花费的平均时间随着USV数量的增加而呈指数衰减。因此，稍微增加网络规模，便可以大大提高覆盖时间性能。然而，随着网络规模的增大，增益减少，基础设施成本增加。因此，应慎重决定规模以达到良好的投资回报效果。

图1 在分布式反集群算法控制下实现100%覆盖率所需平均时间与USV数量的函数关系Fig.1 Relationship between the number of USV and the average time required to achieve 100%coverage under the control of distributed antiflocking algorithm

其次，分析分布式反集群算法对系统瞬时面积覆盖的影响。瞬时区域覆盖的定义为：所有USV在t时刻所覆盖的区域占总区域的百分比［8］。仿真结果如图2所示。根据给出的结果，由于反群集算法的中心化项，因此系统的瞬时面积覆盖率随USV数量的增加而线性增加。

图2 分布式反集群算法控制的USV的瞬时覆盖面积与USV数量的函数关系Fig.2 Relationship between the number of USV and the instantaneous area coverage of USV under the control of distributed antiflocking algorithm

再次，仿真比较了在分布式反集群算法和随机搜索模型［9］控制下的累积面积覆盖性能。分别采用5个USV进行仿真，仿真结果如图3所示。累积覆盖率的定义为：在 [0，t)时间间隔内，USV累计覆盖面积占总区域面积的百分比［8］。根据图3给出的仿真结果，随着时间的推移，这两种算法控制下的累计覆盖率不断增长。与执行随机搜索算法相比，分布式反集群算法控制下的覆盖给定区域所需的时间更短。因此，该算法可以提高能量利用率。虽然反集群算法的目的是以更小数量的个体提供更好的动态覆盖性能，但分布式反集群算法也可用于大规模无人系统。

图3 由两种不同算法控制的USV的平均累积面积覆盖率与时间函数关系Fig.3 Relationship between the average cumulative area coverage of USV and the time under the control of two different algorithms

最后，验证反集群算法在应用过程中的避障能力。如图4所示，采用8个USV进行仿真，传感器探测范围为rs（rs=50m），8个USV从给定区域内的随机位置启动。在图4的左侧图中，圆圈和六角星分别表示USV和目标，弯曲轨迹代表了USV的移动路径历史，黑色长方形和圆形表示障碍物。图4右侧图表示USV在t时刻所覆盖的区域占总区域的比例。

图4 避障能力验证Fig.4 Illustration of obstacle avoidance capability

随着时间的推移，USV根据式（11）中给出的控制输入在给定区域内移动，在17.9s时已完成85%的区域覆盖。在仿真过程中，没有检测到USV和障碍物之间及USV与USV之间的碰撞，证明了分布式反集群算法的避障能力。

3.2.2 某个USV故障的情况

假设某个USV出现故障，采用8个USV进行仿真，传感器探测范围为rs（rs=50m），设置USV初始位置及初始速度方向与图4仿真中相同，仿真结果如图5所示。

图5 模拟某个USV故障的情况Fig.5 Simulation in failure of a UAV

从提取的样本中可以看出，USV一直在不断地探索区域，同时最小化其感知覆盖的重叠。当覆盖率为70%时，第8个USV（如左图中玫红色的标记USV及其路径所示）发生故障。由于USV轨迹是根据最新的信息动态获取的，因此，这使得其可以在某些个体失效的情况下无缝工作，该算法可以很容易地适应环境的变化。当t=41.2s时，达到100%的覆盖率。

3.2.3 USV传感器探测范围存在差异的情况

考虑到不同USV所携带的传感器探测范围的不同会导致区域覆盖效率变化，仿真模拟了USV传感器探测范围不同的情况。采用8个USV进行仿真，采用携带3种传感器探测范围的USV（rs=50m、rs=30m、rs=20m）共同进行区域覆盖，设置USV初始位置及初始速度方向与图4仿真中相同，仿真结果如图6所示。

图6 模拟USV传感器探测范围差异情况Fig.6 Simulation the difference of detecting range of different USV sensors

从提取的样本中可以看出，在t=0s初始时刻，由于部分USV所携带的传感器探测范围小于等于50m（rs≤50m），故其初始覆盖率相较于图4而言明显减小，完成100%覆盖率所需时间更长。从仿真结果来看，不同的探测范围并不影响其避障及去中心化能力，并且最终仍能够实现100%的区域覆盖。因此，分布式反集群算法同样适用于USV传感器探测范围存在差异的情况。

4 结论

本文采用分布式反集群算法，在障碍物密集的环境中实现了有效的动态覆盖。由于该算法具有完全分布式、智能化的控制机制，与随机运动模型相比，具有更好的可扩展性、自适应性及鲁棒性。该算法基于相邻个体间局部交互的自组织行为，使得无人系统更容易适应动态环境。在今后的工作中，需要进一步考虑洋流、旋涡及风力等的干扰作用，使该算法更适用于实际系统。此外，需进一步将算法中的避障机制推广到更复杂的场景中，如凹形动态障碍及动态障碍物等。