通信距离约束下的无人船集群覆盖搜索方法

尹 洋, 杨全顺, 王 征, 刘 洋

(海军工程大学电气工程学院, 湖北 武汉 430033)

0 引 言

近年来,搭载多种探测设备、通信设备或各型武器的水面无人船(unmanned surface vessel, USV),成为了执行搜索救助、水文勘察、海洋环境检测等任务的重要平台[1]。USV可搭载声纳、光电等传感器来感知环境情况,实现对指定水域的暗礁、海底地形、水下目标等进行探测、识别和定位[2]。单艇的覆盖搜索算法目前已有较多研究。对于形状规则、环境已知的目标水域,USV的覆盖搜索问题可以视作完全遍历路径规划问题[3],可以使用遍历算法进行覆盖搜索[4-5]。对于没有先验知识的未知水域,USV需要实现自主探索并构建环境地图,目前主要方法有边界探索算法[6]及其改进算法[7-10]。

中小型USV的平台载荷有限,存在一定的局限性[11],而以集群的方式执行任务可以功能互补,发挥组织灵活、抗毁重构性强的优势[12],因此集群协同技术成为了当前的研究热点之一。

面对集群协同探测问题,向庭立等[13]使用最小覆盖圆法来确定待探测区域的轨迹点,将区域探索问题转换为集群任务分配问题,进而使用改进灰狼算法求得最优分配。但此方法只能处理边界已知的待探测区域,静态地为集群个体分配搜索任务。高春庆等[14]基于集群规模和初始位置划分搜索任务子区域,将集群协同覆盖问题转换为单遍历路径规划问题,再基于生成树节点交换法优化规划路径。但该方法需要提前给出障碍区域和危险区域,对环境的适应性不高。张耀中等[15]根据异构型集群和多任务区协同侦察的特点构建“资源-需求”矩阵,再基于一致性束算法生成任务分配方案。但其无法处理任务数量的突然增减、任务区移动等突发情况。Wang等[16]基于分布式粒子群算法编码个体信息和任务决策信息,针对不同战术意图分别设计协同算法。但该算法需要根据集群的机动性和通信约束等特点设计专门的适应度函数,扩展性和适应性较低。对于集群通信距离受到限制的情况,张民强等[17]给出了一种分布式的Voronoi区域计算方法,分析了通信和采样周期异步时的信息更新公式。王宁等[18]设计了一种根据有效通信距离自主切换的信息交互机制。符小卫等[19]研究了多种通信约束条件对集群搜索目标任务分配的影响。上述文献均是在已知环境中进行覆盖搜索,对未知环境下的协同搜索研究较少。

针对通信距离受限时,中小型USV集群对未知水域执行覆盖搜索任务的应用场景,本文基于聚类任务划分和竞拍任务分配的思想,推广单艇的边界探索算法,提出一种集群的竞拍协同边界(auction collaborate frontier, AC-Frontier)探索算法,使用改进的聚类算法动态生成边界搜索任务,消除不安全的和无价值的探索任务点,使用分布式竞拍算法进行任务分配,最大化集群搜索效率。设计仿真实验验证该算法在搜索效率上的提升和对不同规模集群的通用性。

1 USV集群覆盖搜索问题描述

考虑USV集群的协同覆盖搜索问题,在没有任何环境先验知识的情况下,USV集群自主分配搜索任务,规划航行路径,在不与障碍物发生碰撞的前提下,尽快地遍历覆盖并构建整个环境地图,完成指定水域的覆盖搜索探测任务。

(1)

式中:mi为USVUi所覆盖搜索的水域。

式(1)表示尽可能地均匀分配搜索水域,且避免重复搜索同一水域,从而在航速一定的情况下,尽快完成覆盖搜索任务。

约束条件为

(2)

式中:(xi,yi)k为Ui在k时刻的坐标;(xb,yb)为障碍物距离Ui最近的坐标点;R为安全避障距离。

约束式(2)表示USV探测距离D远大于转弯半径Rv;任意时刻Ui和障碍物之间需保持安全距离;集群所搜索的水域要覆盖整个指定水域。

定义USVUi搜索路径点的时序集合为Ti={Ti1,Ti2,…,Tis}。随着覆盖搜索任务的进行,USV集群根据覆盖搜索情况,动态决策出一系列目标路径点分配给各艇,Ui执行完毕后,记录到路径点集合Ti中。

在USV航行过程中,由探测距离D可得到探测覆盖的区域,为简化问题,将Ui的航行路径视作覆盖搜索的水域mi,式(2)所描述的优化目标可等价于:

(3)

式中:L(Ti k)为Ui从路径点Ti k-1至Ti k的航程。

式(3)表示在满足覆盖搜索约束的前提下使集群的总航程尽可能短。

本文研究未知环境下覆盖搜索问题,由于没有任何环境信息,无法通过求解路径规划问题得到集群最优航行路径,因此本文将覆盖搜索问题转换为序列决策问题,在每个决策时刻评估挑选局部最优目标路径点,最大化各艇搜索价值的期望,从而减少总航程。定义函数R(Ti k)评估Ui在路径点Ti k完成搜索水域的价值,式(3)可转换为

(4)

式(4)表示集群优化目标为最大化各USV在任意时刻航迹点的搜索价值。

搜索过程中的k时刻,各艇协调分配各自的搜索路径点,使分配后的集群探测收益Jk最大。综合考虑各艇抵达任务点的路程和各个任务点的探测收益等因素,在k时刻由Nt个搜索任务组成的任务集合T={T1,T2,…,TNt},其非对称单分配问题的数学描述为

(5)

式中:A(i)⊆T,为可以分配给Ui的任务集合;xij为决策变量,表示任务Tj是否分配给Ui,是则xij=1,否则xij=0;aij为Ui执行搜索任务Tj的收益。

协同覆盖搜索任务分配问题的约束条件为

Nt≥Nu

(6)

(7)

(8)

式(6)表示搜索任务的数量大于或等于USV数量;式(7)表示每一个任务Tj至多分配给一艘USV;式(8)表示任务分配完成后每艘USV有且只有一个搜索任务。

2 USV集群协同搜索算法设计

2.1 AC-Frontier算法框架

针对通信距离约束下USV集群对未知水域的协同覆盖搜索问题,本文基于层次聚类和拍卖理论提出AC-Frontier协同覆盖搜索算法,推广边界探索算法为集群协同探索算法,算法流程如图1所示。

图1 AC-Frontier算法流程

在k时刻,USV集群根据k-1时刻各艇的探索情况构建地图环境信息,检测已探测水域的边界,然后使用改进的K-mean++算法对边界点进行聚类,对不安全或低收益的目标搜索点重规划,划分出符合要求的任务区间,进而使用竞拍算法为USV分派下一步的搜索任务,将集群协同问题转换为单艇搜索问题,最后各USV自行导航至目标点进行探测并进入k+1时刻。算法迭代运行直至完成指定水域的覆盖搜索。

若某USV完成了k时刻所指派的搜索任务,则其立即进入下一时刻,与相邻的USV交换局部信息并分配新的搜索任务，而不必待机等候整个集群完成k时刻的搜索任务。同时,参与信息交换的USV根据分配结果与自身任务信息进行对照,若发生任务变更事件,则同步进入下一时刻,并更新任务信息,否则继续执行原任务。

2.2 边界检测与提取

本文使用占据网格法对任务水域进行栅格化处理,每个栅格独立地表示自身状态信息:未知栅格、空闲栅格、障碍栅格。栅格在任意时刻的状态信息都为三种状态之一,更新构建地图即更新栅格状态的变化。定义边界栅格为相邻栅格中至少存在一个处于未知状态的栅格。如图2所示,分别以黑色、蓝色、白色表示栅格状态,以黄色表示提取到的边界,红色三角形为USV,绿色圆形为对边界聚类得到的搜索点。

图2 构建地图与栅格信息表示

定义评价函数R(m)=n评估任务水域信息熵,n为水域m包含的未知状态栅格数。提取长度大于阈值的边界点到可访问列表中,作为聚类算法的输入数据。

2.3 改进K-means++聚类划分搜索任务

过多的搜索任务会给任务分配流程带来额外的计算量,考虑到相近的边界点具有相似的收益和成本,可以对检测到的边界点进行合理划分,生成搜索任务。本文借鉴文献[7-9]的方式,使用K-mean聚类算法[20]划分搜索任务点。

但此类算法存在聚簇个数k需要事先给定的固有缺陷。在本文应用中,若k值过大,则计算量较大,且大量搜索任务相似,失去了划分任务的意义;若k值过小,则易出现如图2(a)中无价值的搜索点,即USV受探测距离D的限制,抵达该搜索点后没有探索新水域的效果,和图2(b)中处于未知区域或障碍区域的不安全搜索点,这两种搜索点都需要进行重规划。

基于层次聚类的思想,本文对K-mean++算法做出改进,在初步规划完成后,根据聚类效果决定是否需要进一步细分:首先由集合U的元素数量Nu确定初始聚类中心的数量k,再以轮盘赌算法逐个选出初始点,距离越大的点被选中的概率越大;然后开始对可访问列表中的边界点进行均值聚类,得到k个搜索任务区间;最后对这些任务区间逐个进行评估,若该区间没有一定的价值,或者是不安全的搜索点,则对这个聚类进一步划分,直到得到一组满足要求的搜索任务。改进算法流程如图3所示。

图3 某时刻的边界点聚类生成搜索任务

2.4 集群搜索任务分配

在k时刻获取一组搜索任务后,需综合考虑USV的状态、执行任务的收益和成本,为集群各艇分配搜索任务,消解冲突,使式(5)描述的集群搜索收益最大化。如图4所示,USV集群的控制结构可分为主从式和分布式[21]。图4(a)表示的主从式控制结构需要一个通信中心,记录全局任务信息和各艇状态信息,统一分配搜索任务;图4(b)表示的分布式控制结构则由各艇自行组网,仅与网络内相邻的其他USV交换局部信息。

图4 USV集群控制结构

考虑USV集群在通信距离有限的条件下,采用主从式控制的可扩展性和鲁棒性较弱;此外,集群各艇在执行分配到的搜索任务时,各艇完成指定任务的时间不一定相同,若采取待机等候其余USV搜索完毕统一进行下一轮任务分配的方式,则计算资源开销较大,且覆盖搜索效率低下。因此，本文采用分布式结构进行任务分配。

考虑在实际海域中USV之间能否通信受到可靠通信距离约束的应用背景。本文假设各艇之间通信无延迟,可靠通信距离均为H,处于通信距离内的两艘USV之间才能交换信息,则k时刻能够与Ui进行通信的USV集合Ni定义为

Ni={j∈U,j≠i|‖(xi,yi)k-(xj,yj)k‖≤H}

(9)

若H为无穷大,即在理想情况下集群内各艇无通信约束,则分布式竞拍算法可视为主从式竞拍算法;若H为0,则各艇之间无协作。

现有的任务分配方法可划分为最优化方法、启发式方法和类市场机制方法[22]。最优化方法如整数规划法、约束规划法、穷举法等算法简洁直接,能求出理论最优解,但计算量较大,限制了集群规模的扩展[23];启发式方法如列表算法、进化算法、粒子群算法、模拟退火算法等,通过权衡算法时用时和求解效果来得到近似解,但需要专家根据实际情况对复杂的超参数进行整定,以平衡算法效率和求解效果,难以在工程中应用[24]。同时,使用最优化方法和启发式方法前需要先耗费大量的数据吞吐量和计算量,使集群通过一致性算法实现一致的态势感知。

竞拍算法是一种应用广泛的类市场机制的任务分配方法,其核心思想是各竞拍者对收益最高的拍卖品展开竞价,以出价最高者得到该拍卖品的方式解决各竞拍者之间的分配冲突,使总体收益最大化。本文使用竞拍算法进行搜索任务分配的优点主要体现在:① 竞拍算法可以灵活增减竞标者和拍卖品,适用于本文通信距离约束下,集群网络拓扑动态变化的分布式结构;② 相较于其他分配算法,竞拍算法在处理本文搜索任务数量大于USV数量的非对称分配问题中具备较大优势[25];③ 本文应用分布式竞拍算法时,各艇仅和相邻USV交换局部信息,数据吞吐量小,相较于最优化方法和启发式方法,其计算量受分配问题规模大小的影响较小;④ 竞拍算法不需要USV集群达成一致的态势感知,各艇可仅根据集合Ni获得动态局部搜索信息从而实现协同。

USV集群的任务分配流程由竞拍阶段和共识阶段迭代执行。每艘Ui在分配过程中存储和更新长度为Nt的两个列表Pi和Vi,报价列表Pi存储当前迭代回合各个任务Tj的最高报价,净收益列表Vi存储Ui执行任务Tj净收益的预测值。

竞拍阶段中,Ui首先对可分配任务集合A(i)中任务Tj的收益进行估值。定义式(5)中的收益aij为

aij=γeωR(mij)+(ω-1)P(L(Tij))

(10)

式中:ω∈(0,1)为权重因子;P为Ui执行Tj的成本函数,与路程L(Tij)相关;γ>0为缩放因子。

式(10)定义Ui执行任务Tj的收益与任务水域的信息熵呈正相关,与任务区间到USV的距离呈负相关,相关性由权重因子ω调节。任务收益均为正数,保证所有任务均能参与竞拍。

Ui竞买Tj的净收益为

vij=aij-pj

(11)

式中:pj为报价列表Pi存储任务Tj的最新报价。

(12)

由式(11)和式(12)可知,投标报价与最优净收益和次优净收益的差值有关,报价的增幅为利润空间加上一个大于零的常数ε,使其在下一轮竞价中不再参与此任务的竞拍,而是选择竞拍次优任务。ε保证价格递增,避免算法陷入死循环,其值越大,算法收敛越快,但误差越大。

共识阶段中,Ui与Ni中的相邻USV交换报价列表Pi。若发生冲突,且报价最高,则令xib=1获取此任务;若报价较低,则此轮迭代未能中标此任务,需返回竞拍阶段重新竞拍,并更新报价列表:

(13)

3 仿真验证与分析

3.1 仿真设计与实现

本文使用Unity3D进行仿真实验,搭建所需要的地形要素,模拟舰船航行状态、传感器探测数据,检测舰船碰撞事件等。综合考虑地形复杂度和实验效果,本文选取武汉梁子湖地区面积为64 km2的部分水域作为验证地图,以湖心岛和湖岸陆地作为静态障碍物,湖面为待覆盖检测的区域。如图5所示,以地图中心红色区域为搜索起点,绿色高亮的部分为地形和障碍物,地图中的每一个栅格的初始状态都为未知栅格,等待各USV的抵近探测,检测到的边界点数量为0时视作搜索结束。地图比例尺为1 units:100 m。

图5 算法验证仿真地图搭建

为了检验算法的有效性,本文设计以下几组对比实验。

实验 1集群规模Nu相同的情况下,分别以K-mean++聚类和本文改进聚类方法提取搜索任务点,使用AC-Frontier分布式算法和主从式算法、Near-Frontier算法、Random-Frontier算法[10]进行覆盖搜索。部分实验参数如表1所示。其中， “units”为Unity中的距离单位。

表1 实验参数配置

实验 2集群规模Nu相同的情况下,以实验1参数配置为基础,比较不同的有效通信距离H对分布式AC-Frontier算法搜索效率的影响。

实验 3有效通信距离H相同的情况下,以实验1参数配置为基础,比较集群规模Nu不同时分布式AC-Frontier搜索效率的变化。

3.2 仿真结果分析

实验 1在指定地图下,指定规模的USV集群分别使用4种自主探索算法运行20次,运行结果如图6和表2所示。图6(a)比较了使用K-mean++聚类和使用本文改进聚类方法提取搜索任务时,各算法的覆盖搜索时长;图6(b)比较了各算法使用改进聚类方法完成覆盖搜索任务时集群的航行总路程;表2列出了集群内各艇完成的搜索水域价值R、航程L、价值航程比G=R/L和相应的标准差变异系数CV。

图6 规模相同时不同算法搜索效果对比

表2 集群内各USV的搜索效果

从图6(a)可以看到,面对相同水域环境,使用本文改进聚类方法时,分布式AC-Frontier算法执行遍历覆盖搜索任务的用时比Near-Frontier算法减少30.1%,比Random-Frontier算法减少76.9%,主从式AC-Frontier用时分别减少42.4%和82.8%,这表明搜索过程中USV集群进行了合理的任务分配,优化了搜索效率。主从式掌握更多全局信息,任务分配更合理,所以搜索效率略优于分布式。4种搜索算法使用改进聚类方法时,比使用普通K-mean++算法用时分别减少了39.4%、45.3%、48.8%、44.7%,可见改进聚类方法通过动态重规划,消除了低收益或不安全的搜索任务点,提高了任务点的搜索收益。从图6(b)可以看到,使用本文算法进行协同搜索时集群的航行总路程有明显减少,分布式算法分别为无协同算法的78.7%和22.6%,主从式算法分别为61.5%和17.7%,这说明USV集群通过协同配合,以较少的能耗完成了覆盖搜索任务。

从表2可以看到,使用本文AC-Frontier算法进行协同搜索时,搜索价值E和航程L的变异系数CV较小,说明集群内各艇分配到的搜索任务更为均匀,体现了集群任务分配的作用。各艇收益航程比G较大,说明各艇在单位路程内探索到的未知水域更多,从而使集群最终航行总路程更少,与图6结果分析相同。

实验 2在指定地图下,指定规模的USV集群使用分布式AC-Frontier算法,以不同有效通信距离运行,仿真结果对比如图7所示。其中,H=∞表示使用的是本文主从式算法。

图7 通信距离对分布式算法效率的影响

从图7中可以看到,随着有效通信距离的增大,集群内各艇获得的全局信息越多,集群探索任务的分配结果越好,使得完成覆盖探索的时间更短,分配决策次数也更少,同时误差带较小,说明算法效果更为稳定。通信距离增大到一定程度后,受到仿真环境的限制,算法运行结果趋近于主从式任务分配的搜索算法。通信距离较短时,趋近于无协作的搜索算法,误差带较大,体现出算法效果随机性较大。

实验 3以不同的USV集群规模在相同地图下分别运行,仿真结果如图8所示。

图8 集群规模对算法效率的影响

图8比较了集群规模对搜索用时(红色曲线)和任务分配决策次数(蓝色曲线)的影响。可以看到,随着集群规模的增大,搜索时间和决策次数稳步下降,Nu=6时,相较于Nu=3搜索用时缩短了50%。受限于仿真环境面积大小,继续增大集群规模至过饱和,搜索效率不再有明显提高。这体现了AC-Frontier算法在集群中起到的协同作用,同时说明本算法可以很好地适应不同规模的集群。

Nu=10时,USV集群协同覆盖搜索和地图构建过程如图9所示,黄色栅格为检测到的边界,紫色线条为各USV的航行轨迹。可以看到,USV集群从起始点出发,使用AC-Frontier算法协同配合,动态检测探索边界,自主分配搜索任务,对指定水域完成了遍历覆盖搜索。

图9 AC-Frontier集群协同覆盖搜索过程

4 结 论

针对USV集群覆盖探测指定水域的应用场景,本文基于边界探索算法和拍卖理论,提出一种分布式的集群协同覆盖搜索算法AC-Frontier。该方法提取边界坐标和信息熵,使用改进的K-mean聚类算法划分任务区间,再使用分布式的竞拍算法为集群个体动态分配搜索任务,使集群对指定未知水域进行覆盖探测,并构建环境地图。仿真实验验证表明,集群规模相同时,该算法通过协同配合的方式提高了集群搜索效率,任务用时相较于无协同的Near-Frontier和Random-Frontier算法分别减少30.1%、76.9%,航行总路程缩短21.3%、77.4%,体现了该算法在集群覆盖探测路径规划问题上的有效性;集群规模不同时,搜索效率随着规模的增大而提高,体现了算法对不同规模集群的适用性。下一步将针对异构USV集群执行多任务的问题展开进一步研究,更贴近实际地设计USV集群协同算法。