分布式多AUV协同搜索方法

高永琪, 马威强, 张林森, 王 鹏, 赵 苗

(海军工程大学兵器工程学院, 湖北 武汉 430033)

0 引 言

自主式水下航行器(autonomous underwater vehicle, AUV)是一种能在水下自主航行的智能化装置,具有成本低、隐蔽性强、活动受限小等优点。当前,AUV的航速、续航力、通信质量、导航和控制能力等都在逐步提高,未来能更多地执行扫雷、攻击、情报搜集、侦察监视等军事任务。单一AUV作业往往会因为故障、外部威胁等导致任务失败,而多AUV协同作业可以通过配合、补位,降低单一AUV失效的影响,从而提高作业效率。

当前,协同作业是AUV研究的一个热点,如协同定位、协同搜索、协同作战等,亦常以AUV集群为对象,开展任务规划、编队控制、路径跟踪、集群稳定性等以协同作业为目的的研究。

AUV还可以与无人水面艇(unmanned surface vehicle,USV)组成异构协同系统发挥更大作用,如海底资源探测。为此,有学者研究了USV对AUV路径的跟踪算法以及异构协同系统的通信与导航。日本已陆续在研制与AUV协同的USV,如日本国家海洋研究所研制的半潜式USV和日本海洋地球科学与技术署的MAINAMI型USV。AUV异构协同也是AUV发展的一个重要方向。

搜索是AUV的核心任务之一,成功搜索到目标是执行相关任务的前提,协同搜索是国内外多智能体协同控制领域的一个研究热点。

常见的协同搜索方法有遍历扫描式搜索、分区域覆盖搜索、概率图引导搜索等。传统遍历式扫描容易因目标运动、传感器失误等原因造成搜索失败,常常要求智能体短时间内迂回,而AUV机动性能差,难以满足要求。

分区域覆盖搜索通过合理分配区域,将多机覆盖搜索问题转化为单机覆盖搜索问题,文献[21-23]所述应用Voronoi图对搜索区域进行分割,该方法被普遍采用,但这种分割复杂,并且带有不确定性,对智能体的自主性要求也较高。

概率图模型可以有效描述任务环境信息,反映任务环境变化。黄杰等人根据环境的先验信息,在原概率图基础上引入标志位,建立基于双属性矩阵的待搜索环境概率模型,提高环境和目标的信息感知准确度,但该方法使用集中式协同结构,需要优化的决策变量往往是高维的,求解难度大,优化时间长。彭辉等人提出一种分布式模型预测控制的多无人机协同搜索模型,采用基于纳什最优和粒子群优化算法进行求解,极大地降低求解维度,但无人机之间需要进行多次信息交换才能实现纳什最优,对通信有很高要求,实际中往往无法满足,具有现实局限性。张哲璇等人提出一种重访机制驱动的协同搜索规划方法,重返可疑区域,降低由传感器性能不足造成误判的影响,但该方法未考虑通信约束,也有现实局限性。

本文针对水下存在通信延时和协同过程中单AUV易失效的问题,提出一种通信实时性需求低、鲁棒性强的协同搜索算法。通过构造人工势场避免AUV碰撞与资源浪费,采用改进后的头脑风暴优化(brain storm optimization, BSO)算法确保多AUV在协同搜索时能在短时间内做出最优决策。

1 问题描述

针对任务区域内存在的个静止目标,如沉底水雷、海底应答器、海底预置武器等,通过某些手段获取目标先验信息(比如分析区域水文信息、地形信息判断这些静态目标更有可能布放在何处等),但这些信息可能存在一定误差,因此需要指派个AUV进入任务区域,利用携带传感器进行具体搜索以获得目标信息。

对任务区域进行栅格化,每个栅格长宽均为一个单位长度,任务区域由×个栅格组成。假设每个栅格内最多只能有一个目标,AUV通过传感器可确认所在栅格有无目标。

目前,大部分AUV搭载有先进的侦察探测装备,如前视声呐、高分辨率侧扫声呐及先进摄像装备等。其中部分国家采用的干涉型合成孔径声呐和立体搜索声呐,具有很高的分辨率,但是这些传感器仍然可能误判,具有一定探测概率和虚警概率。

图1 AUV运动方向示意图Fig.1 Schematic of AUV movement directions

但实际上,AUV具有机动约束,存在最大偏航角增量和最小偏航角增量。本文为表征机动约束,限制AUV运动方向为“左航、直航、右航”3种状态,偏航角增量分别用“-1、0、1”表示。+1时刻的偏航角通过取模运算获得,计算公式如下所示:

(1)

式中: Mod(·)为求余运算。

一组偏航角增量可以表征一条搜索路径,如初始偏航角为0,决策偏航角增量为[1,1,-1,1,0,-1]所表示的搜索路径如图2所示。

图2 搜索路径示意图Fig.2 Schematic of search path

2 搜索模型

2.1 目标存在概率图

概率图中栅格(,)的数值表征目标在该栅格可能存在的概率。先验信息中最有可能出现目标的位置为((),()),=1,2,…,。但其周边也可能存在目标,因此以((),())作为峰值中心,利用高斯分布函数表示其附近区域的初始概率,如下所示:

(2)

式中:表示位置((),())的目标存在概率,即高斯分布的峰值;为高斯分布的方差。

当AUV航行至栅格(,)时,目标寻找概率根据贝叶斯准则更新,具体如下。

AUV在第时刻探测到目标,目标寻找概率更新如下：

(3)

式中:为探测概率，表征栅格中有目标且AUV成功探测到目标的概率；为虚警概率，表征栅格中无目标但AUV探测到目标的概率。

AUV在第时刻未探测到目标,目标寻找概率,更新如下所示:

(4)

AUV在搜索过程中,用传感器探测栅格中是否有目标,并及时更新目标存在概率图,当栅格内概率大于阈值时,认为该栅格存在目标,并将该栅格的概率置零,以避免吸引AUV再次前往搜索。

2.2 环境不确定度图

环境不确定度()∈[0,1]表示AUV对栅格(,)中环境信息的掌握情况,其中()=1表示AUV对环境信息完全不确定,()=0表示AUV对环境信息完全确定。初始不确定度根据目标存在概率确定,计算公式如下:

=1-(-ln()-(1-)ln(1-))

(5)

随着AUV对栅格的不断探测,其对栅格环境的掌握愈发清晰,环境不确定度不断变小,具体更新如下:

(6)

式中:∈[0,1]为环境不确定度递减因子。

2.3 协调信息素图

多艘AUV在同一时刻搜索同一栅格,一方面是对资源的浪费,降低了搜索效率;另一方面容易碰撞,破坏了系统结构。本文通过协调信息素图构造人工势场,合理协调AUV集群,避免多艘AUV同时搜索同一栅格。

(7)

栅格的协调信息素越多,说明AUV越有可能与其他AUV发生冲突,前往该栅格会给协同过程带来更大隐患。

3 协同搜索方法

3.1 目标函数

多AUV协同搜索的目的是尽量掌握整个任务区域信息,尽可能发现更多目标。因此，综合考虑目标存在概率收益、环境掌握程度收益和协同代价制定目标函数。

(1) 目标存在概率收益。目标存在概率收益是指按照当前目标存在概率图,AUV依照搜索路径航行,所经过栅格的目标存在概率之和,表征AUV沿着最有可能发现目标的路径航行。

(8)

式中:是指第个AUV按照预测的搜索路径航行所经过栅格的集合。

(2) 环境掌握程度收益。环境掌握程度收益是指按照当前环境不确定图,AUV按照搜索路径航行,所经过栅格的环境不确定度之和,表征AUV沿着环境不确定度最大的路径航行,尽快降低环境不确定度,提高对环境的掌握程度。

(9)

目标存在概率收益与环境掌握程度收益度量标准不一,实际计入目标函数时,需要进行归一化处理。

(10)

基于上述子目标函数,目标函数计算公式如下:

(11)

式中:,,是子目标函数影响系数;为一个充分大的正数。

3.2 分布式协同搜索过程

本文采用滚动优化策略实时产生最优搜索路径,在滚动时域内预测步,但只执行最优决策的第一步;采用分布式结构,将整个AUV系统的全局优化问题转化为各AUV子系统的局部优化问题,减小优化规模、缩短优化时间。

协同搜索问题实际上是一个非线性优化问题,可以通过智能优化算法进行优化。本文采取基于全局最优和差分变异的头脑风暴优化(global-best difference-mutation brain storm optimization, GDBSO)算法优化目标函数,利用其收敛速度快、优化效率高、可靠性较强的优点,快速得到收益最大、代价最小的最优决策,GDBSO算法主要包括以下几个操作步骤。

聚类操作:种群中的个个体通过k-means聚类方法分成类,并定义每一类的最优个体为该类的类中心。

取代操作:聚类后,以取代概率产生随机个体取代某一个类的类中心,防止算法过早地收敛,并有助于算法跳出局部最优。

选择操作:通过4种方法选择待变异个体。

按照轮盘赌概率选中一个类,选择该类的类中心为待变异个体;

按照轮盘赌概率选中一个类,选择该类中随机一个个体为待变异个体;

随机选中两个类,融合两个类的类中心成为待变异个体;

随机选中两个类,在两个类中各随机选出一个个体,融合成为待变异个体。

追随操作:以追随概率使得选择出来的个体追随全局最优个体。

变异操作:以差分概率对待变异个体进行差分变异,否则产生随机新个体作为变异个体。

分布式多AUV协同搜索决策算法步骤如下。

根据先验信息初始化搜索图。

产生第个AUV的初始种群,种群为个个体,每个个体有个自变量,每个自变量的取值范围为-1、0、1。

利用GDBSO算法对步骤2中的种群进行优化,对每一个选择、追随、变异操作产生的个体进行四舍五入取整,若取整后新个体的自变量不符合条件则重新进行选择、追随、变异操作。

将当前最优决策、当前探测情况发送至其他AUV,执行最优决策第一步。

判断是否达到最大搜索步长,是则结束,否则转入步骤6。

接收上一决策时刻其他AUV共享的信息,更新搜索图,转入步骤2。

AUV之间交互的信息包括最优决策与探测情况,最优决策更新环境不确定度和协调信息素,探测情况更新目标存在概率。时刻探测当前栅格,接收到其他AUV在(-1)时刻发出的信息,融合后更新自身搜索图,以此作出决策,并发送最优决策与探测情况。AUV决策的实际依据为上一步的信息,由此允许通信有一定延时。

AUV根据当前时刻各自的搜索图进行优化决策,其中协调信息素来源于上一时刻接受的其他AUV的最优决策,使得AUV避开可能与其他AUV冲突的栅格。

4 仿真研究

首先,为验证本文提出的协同搜索算法的有效性,将GDBSO与BSO分别应用于决策过程,对比搜索结果。其次,改变预测步长、子目标函数影响系数等参数,分析其对搜索过程的影响。最后,分析搜索过程中某AUV失效对整个AUV集群搜索效能的影响。

为减少偶然性对仿真结果的影响,各组仿真均独立运行50次。计算机仿真平台为Matlab 2016a,处理器为Intel(R) Core(TM)i5-6200U CPU@2.30 GHz,RAM4GB,操作系统为windows10-64位。

分布式协同搜索模型参数如表1所示。

表1 分布式协同搜索模型参数

任务区域为20 km×20 km大小的海域,均匀划分为20×20的栅格。根据先验信息,初始目标存在概率分布如图3所示。

图3 初始目标存在概率分布图Fig.3 Probability distribution diagram of initial target existence

4.1 不同算法比较

使用两艘AUV搜索50步,每步决策预测=8步,AUV的出发航向均为0。将子目标函数影响系数设置为=0.4、=0.4、=0.2,GDBSO算法与BSO算法的参数设置参考文献[31],其中,种群数量=30,最大迭代次数=30。

基于GDBSO和BSO决策的分布式多AUV协同搜索路径如图4所示。

图4 基于不同决策的协同搜索路径示意图Fig.4 Schematics diagram of collaborative search paths based on different decision-making

图4中,黑色三角形为AUV出发位置,黑色菱形为实际目标位置,与先验信息中最有可能的位置存在一定差异,红色区域为禁航区域。

GDBSO和BSO均有能力在50步内成功寻得所有目标,并且避开禁航区与避免AUV同时搜索同一栅格,可见本文提出的分布式协同搜索方法具有可行性。

GDBSO和BSO各独立仿真50次,统计结果如表2所示。

表2 不同算法搜索效果比较

GDBSO与BSO相比,寻得目标数量更多、每步决策时间更短,可见GDBSO在决策方面更有优势。

4.2 参数影响分析

设定预测周期=8,取不同的子目标函数影响系数进行仿真,各组均独立仿真50次,结果如表3所示。

表3 子目标函数影响系数的影响

结果表明,搜索结果与子目标函数影响系数的取值息息相关。目标存在概率收益权重不断增大,环境掌握程度收益权重不断减小,寻得目标数量逐渐增大后减小,可见这两个权重处于某种平衡时能使算法有更好的搜索效果。当=04、=04、=0.2时,寻得目标数最多为8.80,说明目标存在概率收益权重等于环境掌握程度收益权重时,目标函数引导AUV决策的效果为佳。

设定子目标函数影响系数为=04、=04、=02,取不同预测周期,各组均独立仿真50次,结果如图5所示。

图5 不同预测周期的影响Fig.5 Impact of different forecast periods

由图5(a)可见,预测周期过长或过短都使得搜索效果变差,当预测周期=8时,搜索效果最佳。预测周期过短,AUV没有充分利用搜索图信息,不能作出对未来更有利的决策。预测周期变长,优化规模变大,算法求解难度增大,更容易陷入局部最优,导致搜索效果差强人意。由图5(b)可见,预测周期越长,每步决策时间越长,但预测周期取6～10时均小于1 s,满足协同搜索实时性要求。综上所述,建议设定预测周期=8,既有较好搜索效果,又满足较短决策时间。

4.3 AUV数量变化

为分析AUV数量对搜索效果的影响,分别指派2～7艘AUV执行协同搜索任务,每组仿真均独立运行50次,统计寻得目标数量如图6所示。

图6 AUV数量变化的影响Fig.6 Impact of number changes of AUVs

当AUV数量少于5艘时,寻得目标数量随AUV数量增大而增大,大于5艘后,寻得目标数量基本不变。在任务区域与搜索步长不变的条件下,AUV数量达到一定值后,数量增长对搜索效果基本无帮助。AUV数量为6艘时的搜索示意图如图7所示,在搜索后期,出现栅格被反复搜索的情况,造成资源浪费。因此要根据实际情况,指派合适数量的AUV,提高搜索效率,同时避免资源浪费。

图7 6艘AUV搜索结果示意图Fig.7 Schematic diagram of search result for six AUVs

由于海洋水下环境复杂,AUV编队在执行任务过程中容易发生部分AUV失效,为此,指派4艘AUV组成AUV集群执行协同搜索任务,各AUV搜索50步,假设在20步时有1艘AUV失效。独立运行仿真50次,结果如图8所示。

图8 单AUV失效时搜索结果示意图Fig.8 Schematic diagram of search results in case of single AUV failure

由图6可知,单AUV未失效时4艘AUV寻得目标数量占实际总目标数量的95.4%,而由图8所示,单AUV在途中失效时该比例为94.8%,仅比未失效低0.6%。可见,协同搜索方法鲁棒性较好,AUV集群并未因个别AUV失效而导致整体搜索效果大幅度下降。

5 结 论

本文针对水下协同搜索中通信延时、单AUV作业过程中失效的问题,提出一种具有较强实时性和鲁棒性的分布式协同搜索方法,用于对任务海域的静态目标完成协同搜索。该方法利用上一步搜索图信息进行决策,减弱通信实时性需求,通过协调信息素避免AUV碰撞与资源浪费,使用GDBSO优化目标函数,确保AUV短时间内获得最优决策。仿真结果表明，单个AUV在协同搜索过程中失效对整体搜索效果影响很小,验证了方法的鲁棒性。但本文研究的搜索目标是静态的,实际任务中还有动态目标,协同搜索静态和动态目标是下一步研究方向。