一种基于目标声信息改进概率图的多UUV 协同搜索方法

杨惠珍 ,周卓彧 ,李 源

(1.西北工业大学 航海学院,陕西 西安,710072;2.水下信息与控制全国重点实验室,陕西 西安,710072)

0 引言

多无人水下航行器(unmanned undersea vehicle,UUV)目标搜索是指多艘装配有声呐传感器的UUV 进入已知范围的海域环境中对若干个未知目标进行搜索,要求UUV 合理分配搜索资源,在线决策出最优的搜索轨迹,尽快搜索到全部目标。多UUV 目标搜索能够扩展单体UUV 的感知范围,通过共享感知信息并利用系统内UUV 资源的冗余性,提高搜索效率,增强系统鲁棒性,在水下资源勘探和目标侦查等领域有着广阔的应用前景,是多UUV 系统的重点研究内容之一。

多UUV 协同目标搜索是一个多目标多约束的优化问题,其研究内容主要包括环境建模和搜索算法设计两方面。

目前,主流搜索环境建模方法基于离散化搜索区域,使用占用图[1]、不确定图[2]及概率图[3]等建立对动态环境的信息描述。文献[4]使用占用图来描述目标的分布情况,根据先验信息对未来时刻目标的位置进行预测,设计占用图更新规则。文献[5]为离散地图中每个栅格赋予一个不确定度值,以描述无人机对该栅格中目标分布的不确定性。文献[6]使用搜索环境中不同区域的权重信息设计动态不确定图,提高了多UUV 对岛礁重点区域的目标搜索效率。文献[7]使用六边形网格离散任务区域并建立概率图,使无人机以相同的代价向不同的相邻单元移动,并基于概率图模型定义了搜索信息增益,有效提高了协同搜索的资源利用率。文献[8]使用目标初始概率分布和目标转移概率对目标位置进行预测,使UUV 编队以较高的成功概率和较短的平均搜索时间实现对马尔可夫运动目标的应召搜索。总得来说,上述环境建模方法将无人机和UUV 等智能体对环境和目标的认知映射到二维离散地图中,随着搜索过程中的感知信息不断更新,如何提高离散地图的信息量和信息可靠性是提高目标搜索效率的重要手段。

在搜索算法设计方面,群智能优化算法被广泛应用于搜索问题[9]。文献[10]提出反信息素改进蚁群优化(ant colony optimization,ACO)算法,并结合参数调节机制提高未知环境目标搜索效率。文献[11]为了解决UUV 在局部极值点附近无法前进的问题,提出了基于ACO 和人工势场法的目标搜索算法,具有较好的快速性。文献[12]提出将机器人系统的协作规则应用到势场函数中,并作为粒子群优化(particle swarm optimization,PSO)的适应度函数应用于未知环境中机器人协作搜索。文献[13]为了克服机器人工作空间的局限性,提出一种基于PSO 的分布式算法,在全局机制下实现整体最优。文献[14]将PSO 结合差分进化(differential evolution,DE)算法提出PSO-DE 算法解决比例积分微分神经网络中权重参数易陷入局部最优的问题。文献[15]结合模拟退火法实现三维环境中最优航迹点的选取。文献[16]结合遗传算法(genetic algorithm,GA)提出PSO-GA 算法实现无人机部署位置的优化。文献[17]针对马尔可夫运动目标的搜索问题,提出一种基于突变遗传算子和突变交叉算子的改进GA 算法,提高了算法的稳定性和UUV 的搜索效率。文献[18]提出一种自适应突变GA 算法,通过最大化探测概率实现UUV 对移动目标的搜索。文献[19]针对城市环境下无人机编队的搜索和跟踪问题,提出改进灰狼算法规划航迹,平衡搜索效率和跟踪的准度。文献[20]提出改进的麻雀算法进行模型求解,提升了多机协同目标搜索的准确率。智能优化算法在求解过程中陷入局部最优解,导致UUV 等智能体聚集在某一区域搜索,降低协同目标搜索准确率,这一现象时有发生,因此,研究和寻找合适的智能优化算法,减少局部最优是研究目标搜索问题的主要方向之一。

综上所述,现有的目标搜索方法在无人机、UUV 等智能体上的应用具有通用性,在传感器全向视域(field of view,FOV)、目标或环境信息部分已知的条件下取得了较好的搜索效果。然而在未知水下环境中,还需要考虑以下限制条件: UUV 探测声呐不是FOV,而是有限视域(扇面);目标先验信息少,甚至没有,且水下目标感知有限,获取的目标信息亦有限。因此,针对水下未知环境中多UUV 目标搜索问题,有必要充分利用目标感知信息,提高离散地图的信息量和可靠性,同时寻找智能优化算法,减少局部最优现象。

针对此,文中提出了一种新的含目标声学探测信息的概率图模型及其更新方法,有利于UUV 充分利用声呐探测的目标信息规划搜索路径,解决因为感知信息利用不足导致的目标遗漏问题;同时,文中将线性种群规模减小算法(linear population size reduction,LPSR)与基于成功历史的自适应微分进化(success-history based adaptive differential evolution,SHADE)和广泛学习机制(comprehensive learning mechanism,CLM)相结合 的LPSRSHADE-CLM 算法的突变策略引入PSO 算法,提出了一种具有学习机制和自适应参数调节机制的PSO-LPSR-SHADE-CLM 优化算法。通过生成自适应调整参数的突变粒子,增加粒子多样性,在多UUV 目标搜索应用中,减少了局部最优,提高搜索效率。

1 多UUV 协同目标搜索问题建模

假设在未知无障碍的有界区域中,处于固定深度的N艘同构UUV 对处于同一水平面的若干个非合作目标执行搜索任务。每艘UUV 安装有主动声呐感知目标信息,根据感知的目标信息在线规划搜索路径,在规定的任务时间内以最优效能搜索到更多的目标。该问题可以描述成一个目标优化问题,涉及的关键要素包括: 搜索区域、UUV运动学及UUV 探测能力等。

首先使用栅格化模型描述搜索区域的环境模型。将任务区域 Ω均匀划分为rrows×ccols栅格,每个栅格使用Mmn唯一表示,则离散区域的集合表示为

UUV 水平面运动如图1 所示。t时刻第i个UUVi的质心在水平面中的坐标为µi(t)=[xi(t),yi(t)]T,UUVi的航向角为ψi(t),航向角增量为ri(t),航行速度为v,通常v的大小不变,仅改变方向。

图1 UUV 水平面运动坐标系Fig.1 Motion coordinate system of UUV

离散状态空间中UUV 运动学模型为

式中,ri(t)为t时刻 UUVi的航向角增量,是 UUVi的控制输入,须满足UUV 的航向角变化有限的运动学特性约束,即ri(t)∈[-rmax,rmax]。

UUV 声学探测通常包括主动探测和被动探测,其探测性能主要由探测扇面 (R,ε)来描述,其中R为声呐作用距离,ε为扇面角。假设目标的坐标为(xT,yT),目标与 UUVi之间的距离为Rv,角度为α,则目标落在UUV 探测扇面内的数学描述为

因此,UUV 目标搜索问题可以用集合{UUVs,Map,J,U}表示。其中: UUVs为UUV 群体集合;Map为搜索环境;J为系统的效能函数;U为系统控制输入量集合。目标搜索问题可以描述成如下优化问题

即在UUV 运动约束条件下,寻找使性能指标最优的UUV 航向角控制输入序列。

2 基于目标声场信息的概率图模型

概率图是UUV 自身所维护的一种内部数据结构,反映了UUV 对当前不确定环境的认知程度。传统概率图(traditional probability map,TPM)由目标存在概率和环境确定度组成[3],即

式中:pmn(t)是在t时刻栅格Mmn对应的目标存在概率,描述了栅格Mmn中存在目标的可能性;qmn(t)是t时刻栅格Mmn的环境确定度,描述了UUV 对栅格Mmn处环境信息的掌握程度。

由文献[3]中对TPM 的定义可知,pmn(t)∈[0,1],pmn(t)=0表示UUV 认为在t时刻栅格Mmn不会出现目标,pmn(t)=1表示该时刻UUV 认为栅格Mmn中存在目标。qmn(t)∈[0,1],qmn(t)=0表示UUV 对栅格Mmn处信息一无所知,qmn(t)=1表示该时刻UUV 完全掌握了栅格Mmn的信息。

文中在TPM 的基础上引入占用信息和目标声信息,提出改进概率图模型(improved probability map,IPM),即

式中:omn(t)是UUV 的占用信息,用来描述栅格Mmn被UUV 的占用情况;Wmn(t)是栅格Mmn处的目标声信息,用来反映UUV-目标几何距离的远近。

借鉴文献[1]中关于占用图的定义,使用UUV当前的视域范围对占用信息omn(t)进行定义。假设UUV 视域范围内栅格均视为完全占用,则omn(t)∈{0,1},omn(t)=0 表示栅格Mmn不属于任一UUV 的FOV 范围,omn(t)=1表示栅格Mmn正在被FOV 占据。为了利用有限的声呐感知信息,使用主动声呐方程结合声波的传播特性对目标声信息Wmn(t)进行定义。为了消除量纲的影响,解决IPM 各元素之间的可比性问题,对Wmn(t)进行归一化处理,处理后得Wmn(t)∈[0,1],Wmn(t)=0表示声呐未接收到目标回波信息,或传播损失过大导致回波强度低于声呐的检测阈值,Wmn(t)=1表示声呐接收到强度大且明确的目标回波信息。

基于上述定义,为IPM 中各元素建立初始化及更新规则。

2.1 目标存在概率

UUVs对任务区域的目标信息事先完全未知时,栅格Mmn处存在目标与不存在目标的可能性相等,此时初始化pmn(0)为

UUVs在搜索过程共享和维护pmn(t),反映了UUV 群体对目标分布信息的认知情况。由于pmn(t)跟随声呐探测信息进行动态更新,考虑UUVs声呐探测的不确定性建立更新规则。

首先,使用检测概率PD和虚警概率PF描述声呐性能,有

式中:pmn(t)表示t时刻栅格Mmn处目标存在的先验概率;Xmn表示事件“栅格Mmn中存在目标”;PD表示事件“栅格Mmn中存在目标的条件下,U UVs的声呐检测到Mmn中存在目标”的发生概率,即声呐的检测概率;Zmn表示事件“声呐检测到栅格Mmn中存在目标”;PF表示事件“栅格Mmn中不存在目标,但UUVs的传感器却检测到Mmn中存在目标”的发生概率,即声呐的虚警概率。

目标存在概率的更新机理[21]为: 已知t时刻栅格Mmn处目标存在概率pmn(t),由t+1时刻声呐探测结果Zmn确定后验概率pmn(t+1)。令t时刻的UUVs传感器视场范围内栅格的动态集合为FOV′,YFOV′表示事件“ UUVs在 FOV′内发现目标”,由Bayes 理论可得更新公式(11)和(12),同时综合式(8)～式(12)和全概率公式,IPM 的目标存在概率更新公式如式(13)所示

2.2 目标声场信息

由于UUV 系统对目标分布情况预先未知,初始化目标声场信息

在声呐探测过程中,声波的传播损失TL作为度量声源到接收机之间声强衰减大小的一个物理量,其大小反映了UUV-目标几何距离的远近。检测阈值DT作为可接受传播损失的指标,其大小反映了声呐设备的信号处理能力。通过设置合理的DT并与TL比较,UUV 能够在噪声环境下对当前UUV-目标相对方向和几何距离的远近进行合理判断。因此,使用检测阈值DT和传播损失TL对Wmn(t)进行更新。

检测阈值DT根据主动声呐方程(15)进行设定且各UUV 设定相同

式中:S L为目标声源级;NL为环境噪声级;DI为发射指向性系数;TS为目标强度;TL为单程传播损失,随UUV-目标的距离变化而变化。

对于主动声呐,声波的双程传播损失为2TL,2TL通过测量声呐视域范围内不同方向的回波信号声强度的衰减进行确定。为更好地区分不同方向的回波信息,令 FOV′内同一回波方向上的栅格具有相同的双程传播损失,则t时刻 FOV′内各栅格包含的双程传播损失信息记为2TLmn(t)。为了消除量纲的影响,对 2TLmn(t)进行归一化处理,即

当 2TLmn(t)过大时,表示该方向不存在目标或UUV-目标距离过远;2TLmn(t)足够小时表示声呐接收到强度大且明确的目标回波信息。文中以DT/2、DT作为判断的分段点,使用归一化后的双程传播损失定义目标声场信息更新公式为

2.3 UUV 占用信息

由于任务区域中占用信息仅和当前UUV 声呐视域内的栅格集合有直接关系,因此占用信息的初始化和更新均与其余时刻无关。令 FOVt表示t时刻UUV 的视野范围,占用信息的初始化和更新公式相同,即

2.4 环境确定度

假设UUV 能完全掌握其视域范围内栅格的信息,则UUV 系统初始视域范围内的栅格环境确定度最大,其余栅格信息视为完全未知,环境确定度最小。则初始化环境确定度为

在搜索过程中,UUV 系统完全掌握的环境信息跟随omn(t) 改变,对omn(t)=1的栅格更新确定度为1,对于未被FOV 所占据的栅格,UUV 丢失了是否存在目标的信息,但考虑到目标以连续轨迹移动,栅格内的声信息仍具有一定可靠性,为减少目标遗漏和误判现象,将目标声信息Wmn(t)引入qmn(t)的更新公式中,越靠近目标的区域,单位时间内确定度下降越慢,从而利于引导UUV 对可能存在目标的区域进行重访[22]。令动态更新因子λ∈[-1,0],定义更新公式为

3 协同目标搜索算法

3.1 效能函数

为使多UUV 系统在规定任务时间内以最优效能搜索到更多的目标,需要考虑以下效能指标:

1) 优先搜索目标存在概率较高的区域;

2) 优先搜索环境确定度较低的区域(包括未被探测和因为长时间未被探测而需要重访的区域);

3) 优先搜索声场强度较大的区域。

将这3 个指标加权求和,得

式中: ω1,ω2,ω3分别为3 种指标所占的权重,满足约束ω1+ω2+ω3=1;JF为目标发现收益;JE为环境搜索收益;JL为声场信息收益。

式(21)中的第1 项将UUV 在执行任务过程中发现目标的可能性累加,引导UUV 向概率高的栅格航行;第2 项使用栅格的动态集合和动态更新的确定度,保证对确定度较低栅格的回访率;第3 项中,使用声场信息收益表示对于声场强大的区域应当优先搜索。因此,该目标函数综合了协同搜索效率和声呐探测结果,通过优化可以获得最佳的航向角输入集合。

3.2 基于PSO-LPSR-SHADE-CLM 的搜索算法

文中将LPSR-SHADE-CLM 算法的突变策略[23]引入PSO 算法,通过生成自适应调整参数的突变粒子,增加粒子多样性,减少局部最优。参数的自适应控制可以从历史决策中学习成功经验,完成最优决策的选取。

文献[23]中突变粒子v的生成公式为

式中:Fw、F为突变因子;pg为群体极值;µpb,g是当前种群中最佳适应度位置;µpr1,g、µpr2,g是从当前种群中随机选择的位置。

LPSR-SHADE-CLM 算法中突变因子F、Fw的自适应控制的步骤如下[23]。

1) 初始化当前迭代次数g、当前进化数量n;设置算法相关参数: 最大迭代次数Gmax、最大进化数量nmax、正弦率f1、f2、成功率s1=0.5、s2=0.5。

2) 设置生成突变因子F的函数候选池f1、f2,其中f1为自适应正弦递减函数,f2为自适应正弦递增函数,记为

3) 根据当前进化次数n和nmax,在函数候选池中进行选择。若n≤0.2×nmax,使用随机数在函数候选池中选择生成F的函数

4) 若 0.2×nmax≤n<0.5×nmax,令c1和c2分别是使用f1、f2进行参数生成的次数。ki为使用fi进行参数生成时产生更优秀的个体次数。分别更新f1、f2的成功率s1、s2,使用奖励机制在函数候选池中选择生成F的函数

5) 若n≥0.5×nmax,令uF为在过去迭代过程中参数F的历史值中随机选择的一个值,使用柯西分布生成

6) 根据突变因子F设计Fw如下

7) 进入下一次迭代,重复步骤3)～6)。

可以看出,通过式(22)中的µpb,g、µpr1,g和 µpr2,g,自适应控制策略在粒子更新公式中使用次优位置、随机位置,避免了算法的早熟收敛。式(26)～(27)通过对历史信息中成功样本的学习,自适应选择突变因子的生成函数,有利于生成优秀个体。由式(29)可知,在算法运行初期,为了增强算法的全局搜索能力和种群的多样性,将F设置为一个大值、Fw设置为一个小值。在算法运行后期,为了加快算法的收敛速度,将F设置为一个小值。该方法不受函数约束条件的连续性、可导性限制,避免了过早收敛和参数敏感性高等问题,有利于提高求解效率。

将式(22)引入PSO 算法粒子更新公式,PSOLPSR-SHADE-CLM 融合算法的粒子更新如下

式中:w为惯性权重;c1,c2为常值学习因子;S(∗)=[cos(∗) sin(∗)]T为式(2)UUV 运动学模型中关于三角函数关系的函数。

PSO-LPSR-SHADE-CLM 融合算法的流程框图如图2 所示。

图2 PSO-LSHADE-CLM 算法流程框图Fig.2 Flow chart of PSO-LSHADE-CLM algorithm

4 仿真与分析

为了验证文中所提出的基于声场信息的IPM以及PSO-LPSR-SHADE-CLM 混合算法的有效性,基于Matlab GUI 开发多UUV 协同目标搜索仿真软件。主要功能为选择UUV 参数(包含UUV 的初始位置和移动方向)、目标参数(包含目标的初始位置及是否移动)、搜索方法的选择、显示搜索轨迹及显示搜索结果。软件界面如图3 所示。

图3 多UUV 系统目标搜索仿真界面Fig.3 Simulation interface of multi-UUV target search

仿真实验中,设置矩形搜索区域的大小为20 km×20 km,在该区域中投放4 艘UUV 执行搜索任务,UUV 参数如表1 所示,声呐参数如表2所示。

表1 UUV 初始状态及参数表Table 1 Initial states and parameters of UUVs

表2 声呐参数表Table 2 Parameters of sonar

滚动优化的时间窗T=3,每隔1 0 s进行一次决策。每决策一次作为一个仿真时间节点,限制搜索最大时间为1 000 个时间节点,算法参数如表3所示。

基于上述仿真软件以及参数,设置2 种任务场景。

场景1: 搜索区域中存在1 个动态目标,该目标以位置坐标 (18 km,4 km)为起点,沿正弦轨迹往返运动。采用PSO-LSHADE-CLM 算法,分别使用TPM 和IPM 模型进行搜索。

对比图4、图5 各UUV 的搜索轨迹可知,采用TPM,图4 中 UUV1、UUV2(见图中数字标记)轨迹始终没有导向目标,UUV3在搜索前期同样出现盲目搜索现象,降低了搜索效率。采用IPM 模型,在相同时间内,图5 中全部UUV 均导向了目标可能存在的方位,增大了搜索到目标的概率,加快了搜索速度。图中: 黑色方块为移动目标;黑色实线为移动目标的运动轨迹;其余4 种颜色的线条分别为4 艘UUV 的搜索轨迹;扇形区域为搭载声呐的探测范围;k为当前时间节点。

图4 TPM 搜索轨迹(第800 步时)Fig.4 Search trajectories of TPM at step 800

图5 IPM 搜索轨迹(第800 步时)Fig.5 Search trajectories of IPM at step 800

场景2: 搜索区域中存在2 个动态目标,目标1 以位置坐标 (8 km,8 km)为圆心,1.5 km为半径做匀速圆周运动,目标2 以坐标 (18 km,4 km)为起点,沿正弦轨迹往返运动。采用IPM 模型,分别使用PSO、PSO-LPSR-SHADE-CLM 算法进行搜索。其余设置和场景1 一致。

对比图6、图7 各UUV 的搜索轨迹可知,采用PSO 算法,图6 中出现了很明显的局部最优现象: UUV2、UUV4对同一区域在短时间内进行了重复搜索,降低了搜索效率。这是由于PSO 算法在算法运行过程中,粒子多样性迅速消失,在2 艘UUV 同时面对具有高目标函数值的区域时,无法通过引入突变粒子实现新区域的选择。采用PSOLPSR-SHADE-CLM 算法,图7 中 UUV3、UUV4较好地避免了对目标2 的重复搜索,UUV3改变航向前往新区域进行搜索,表明引入学习机制和突变粒子的改进算法提高了求解效率。

图6 PSO 搜索轨迹(第600 步时)Fig.6 Search trajectories of PSO at step 600

图7 PSO-LPSR-SHADE-CLM 搜索轨迹(第600 步时)Fig.7 Search trajectories of PSO-LPSR-SHADE-CLM at step 600

为进一步验证改进概率图IPM、PSO-LSHADECLM 算法的有效性,分别改变移动目标数量及投放的UUV 数量进行搜索,完成蒙特卡洛实验100 次。表4 对比了IPM+改进算法、IPM+传统算法及TPM+改进算法3 种组合条件下搜索到的平均目标数目,可以看出,IPM 与PSO-LPSR-SHADECLM 组合算法发现的目标数量最多。

表4 不同组合算法搜索到的目标数量Table 4 Number of searched targets by different combination algorithms

5 结束语

文中对未知环境同构多UUV 系统的目标搜索问题展开研究,针对感知信息利用不足带来的盲目搜索及局部最优难题,提出了一种基于目标声信息的IPM 模型,充分利用声呐探测的目标信息,提高了UUV 对动态环境的认知;提出了一种基于学习机制和自适应参数调节的PSO-LPSRSHADE-CLM 优化算法,增加了粒子多样性,减少了局部最优,得到了UUV 最优路径可行解。仿真结果表明,文中所提出的搜索方法在相同搜索周期的约束下发现目标的数量更多、速度更快。后续将对该多UUV 目标搜索系统引入通信距离约束,开展分布式目标搜索方法的研究,以便更好地满足实际系统的需求。