MAUV协同搜索多智能目标的路径规划

岳 伟,辛 弘,林 彬,刘中常,李莉莉

(1.大连海事大学船舶电气工程学院,辽宁大连 116026;2.大连海事大学信息科学技术学院,辽宁大连 116026；3.鹏城实验室网络通信研究中心,广东深圳 518052)

1 引言

全球化背景下,监管领海是国家安全和经济发展的重要保障.水下环境不同于陆地,具有信息匮乏和能见度低的特点,近年来,自主水下机器人(autouomous underwater vehicle,AUV)在复杂环境下的定位、隐蔽及跟踪等技术的发展使之能够适配水下任务环境[1-3],吸引了学术界和工业界研究团队的高度关注,并在军事领域得到广泛的应用,美国海军制订的“海军无人潜航器主计划”引领现在和未来的无人自主潜航器发展方向[4].但由于海域环境复杂、任务难度大、不确定性高以及AUV自身能力受限等因素,使得单AUV往往难以满足任务需求,因此,利用MAUV协作完成任务是目前研究的重点方向[5].

水下环境中多自主式水下机器人(multi-autonomous underwater vehicle,MAUV)协同搜索作为MAUV协同任务中的热点,涉及MAUV任务分配和路径规划问题.通常根据搜索任务目的不同将其分为以下几类:对固定区域无特定目标的日常巡逻搜索,对存在危险的特定区域内有目标的警戒搜索,以及对于发现部分目标踪迹区域有目标的应召搜索.在应召搜索任务中,根据目标的行动能力又划分为静态目标搜索和动态目标搜索.静态目标搜索是指目标位移不发生改变,例如:失事飞机的残骸、水下测深、测绘等.文献[6]在概率估计的基础上,建立不同的静态目标数学模型.但在实际任务中,考虑水下复杂环境和智能目标行为决策等诸多因素的影响,目标的位移行动会随时间不断变化,因此针对动态目标搜索的研究具有更普遍的意义.由于动态目标具备智能性、高度机动性,相对于静态目标的搜索任务,动态目标的搜索难度更为复杂,目前对于动态目标搜索问题,大都转化为概率搜索任务[7].如,文献[8]结合蚁群算法开发一种混合元启发式方法对MAUV进行航迹规划.文献[9]结合目标预警位置和地形因素,建立用来描述目标随着时间变化的等概率曲线模型.文献[10]提出了用于搜救的无人水下航行器系统的可行性策略,为AUV应用于搜索救援提供了理论与实际的解决方案.

搜索问题不仅仅是简单地遍历任务区域,考虑目标具有智能决策能力时其行动将具有多种变化,增大预测目标行为的难度.截至目前,对于搜索具有多种决策方案的智能目标,缺乏描述不同决策状态下目标行为的方法,且没有建立相应的目标决策方案转换模型.因此,针对智能目标的决策状态转移影响下的集群协同搜索研究仍旧是一个极具有挑战的难题.

对于决策转移模型的研究,美国麻省理工情感实验室的Picard教授定义了智能体的情感计算[11],并在后续研究中通过多模态技术分析目标情感[12],这对于定性研究智能体的决策模型提供了理论依据.本文在文献[11-12]的基础上,从文献[13]提出的现代化作战中的推演技术出发,针对目标具有智能决策能力的问题,建立基于决策状态转移的目标概率图模型,并提出多狼群算法(improved multi-wolf pack algorithm,IMWPA),用于解决MAUV协同搜索智能目标的路径规划问题,创新点如下:

1)针对在未知水下区域内存在具有智能决策的动态目标,且目标的决策状态可能发生转移.本文设计基于马尔科夫链生成决策状态转移模型,将决策与智能目标的行为相对应,建立了一种新颖的目标概率图模型;同时考虑环境对于传感器的影响,设计新的传感器光线受限的探测概率函数;

2)设计新的实时自适应代价系数,动态调整实时多目标适应值函数,相比于文献[8]中的搜索任务适应值函数的收益或代价权重系数为常量,本文提出的适应值函数更符合搜索任务中的实际需求;

3)提出改进的IMWPA算法,利用人工势场法调整人工狼的奔袭步长,使寻优过程更加灵活;建立新的多狼群框架,增设嚎叫环节用于联络狼群间的信息,防止探索空间的重复;构建人工狼淘汰规则,提出同时依据适应值函数值及其增长量改进狼群淘汰更新策略,防止搜索随机性过大并保证狼群的多样性.

本文具体结构如下:第2节为问题描述,将任务区域环境栅格化,制定智能目标模型的转移以及目标概率图的更新规则,并建立受水下环境影响的传感器探测概率模型;第3节结合AUV系统的约束条件,建立MAUV任务评价函数,将其描述为实时适应值函数的形式;第4节设计IMWPA并应用于MAUV搜索系统;第5节建立多个仿真场景,检验IMWPA完成任务的可行性,并将IMWPA与其他搜索方法进行对比,验证了算法的高效性;文章最后给出本文的结论.

2 问题描述

定义的水下任务场景为:预警后消失的多个水下未知智能目标根据自身的决策展开行动.MAUV系统则依据该预警坐标并通过目标的决策状态的转移描述目标行动的变化,在复杂环境下根据决策状态预测未来时刻目标概率分布,并将其作为先验信息,然后利用IMWPA对MAUV搜索过程进行路径优化,期望在水下复杂环境中以最优指标完成搜索任务.

2.1 任务环境建模

针对水下复杂环境进行三维环境建模,考虑水下环境Ω,存在着未知准确数量和位置的智能动态目标.将水下环境Ω栅格化成Lx×Ly×Lz个单位栅格,单位栅格的宽度由AUV的传感器探测宽度Ds决定.将栅格根据坐标(x,y,z)编号为Cellxyz.

MAUV系统采用主-从模式[14],且都安装了水声通信系统和其他通信设备,保证MAUV系统之间的通信[15].主AUV作为通信中继点,在每个决策周期内主AUV都可以实现理想通信,且每隔一段时间主AUV需要浮出水面,通过GPS修正位置误差,以实现高精度的搜索任务;从AUV主要用于搜索,可在一定范围内与主AUV通信,从而实现MAUV搜索信息的一致性.

为避免AUV频繁上浮或下潜,假设MAUV高度坐标为Lz,且能够完全扫描相同(x,y)坐标的栅格,则

其中:Pxyzi表示栅格Cellxyzi目标存在概率表示横纵坐标为(x,y)的栅格集合Cellxy对应目标存在的总概率,在tk时刻平面中Cellxy对应的目标概率为Pxy(tk).

2.2 目标概率模型

考虑任务区域内所有栅格在tk时刻存在两种模式,即,MAUV未正在搜索和正在搜索的栅格,基于此,本节对目标概率图建模如下.

2.2.1 MAUV未搜索时概率图更新模型

1)目标决策状态及其转移模型.

由于预警后消失的目标信息严重不足,仅能根据预警时的部分目标状态信息,预测目标位置.本节建立基于马尔科夫链的决策状态转移模型,设置五元组{D,π,M,S,An}表示n种决策状态集合.π=(π1,π2,···,πn)1×n为初始决策状态分布概率矩阵.M={M1,M2,Mj,···,Mg},j=1,2,···,g表示g种朝向某栅格的位移行为的集合,每种决策状态下可对应多种行为.S={S0,S1}为目标对外界反应集合,其中S0表示目标认为自身安全,对外界不作反应;S1表示目标感知受到外界威胁,将作应急反应.为决策状态转移概率矩阵,表示目标在时间步受到反应为Sl(l=0,1)时决策状态之间的转移概率矩阵.数学描述如下:

本文的决策转移模型是基于马尔科夫链的“无记忆性”的预测模型[16],该模型符合在任务中信息获取不足,环境情况实时变化的特点.即tk+1时刻的决策状态D(tk+1)仅取决于tk时刻决策状态D(tk)和tk时刻目标感知到的外界状态类型Sl.同时,通过引入的决策状态转移矩阵解决动态智能目标的决策在不同情况下变化的建模问题.当目标感知安全后或危险时,会采取不同的决策.

进一步地,可以得出目标在起始时刻t0经过k步后的决策状态转移概率,表示在t0时刻的状态Di在tk时刻转变为Dj的概率.从t0时刻经历k步后的决策状态转移矩阵A(tk)等于这段时间内所有状态转移矩阵连续相乘,即

其中Nl为智能动态目标感知到外界威胁的次数.

从起始时刻t0到tk时刻的决策状态概率分布矩阵表示如下:

目标预警后消失后,定义目标概率计算公式为

其中:t0表示目标消失的时间并将其作为初始时刻,(xT(t0),yT(t0))为目标最后一次出现的栅格坐标.

3)目标概率图更新.

Cellxy对应的行为集合M包括9种位移行为,如图1所示.

图1 朝向Cellxy的智能目标位移Fig.1 Displacement of intelligent target towards toCellxy

智能目标的决策周期为单位时间步,每个周期内Cellxy在MAUV未搜索时目标存在的概率的更新公式如下:

其 中:mij=P(Mj|D=Di)(i=1,2,···,n)(j=1,2,···,9),mij表示在决策状态Di的情况下,目标位于栅格Gj进行位移Mj的概率,并且mij非负,任意决策状态下执行所有位移的概率和为1.

模型搭建。把碳排放作为DEA分析模型的投入要素，假定规模报酬可变，建立投入导向型规模报酬可变(VRS)分析模型，分析在地区生产总值一定的情况下，碳排放、资本和劳动力如何变动，能够实现经济发展的最高效率。

图2 IMWPA结构图Fig.2 Structure of IMWPA

2.2.2 MAUV正在搜索时的概率图更新模型

在任务过程中,AUV的图像识别传感器会受到水下环境的影响光线弱的影响从而降低识别准确率,本小节依据图像传感器接收到的光照反射强度建立传感器探测概率与虚警概率模型,如下所示:

其中Pd∈[0,1]为探测概率,表示栅格真实存在目标,但传感器仅能以Pd的概率检测到目标.ρχ代表传感器检测到的反射光强度;lρχ表示光强度对探测概率的影响系数;反射光强度ρχ1,ρχ2,ρχ3为常数且ρχ1＞ρχ2＞ρχ3,当反射光强度小于ρχ3时,传感器失去探测识别能力.

其中Pf∈[0,1]为虚警率,表示栅格不存在目标,但传感器却以Pf的概率显示检测到目标.该式表明传感器在反射光强度大于ρχ1不会出现虚警情况,反射光强度小于ρχ3时,传感器失去探测识别能力,对于探测结果不予信任.

MAUV传感器系统确定栅格Cellxy存在目标的概率由AUVs,s=(1,2,···,Ns)在检测到Cellxy存在目标事件和该栅格是否实际存在目标事件θxy(tk)共同决定.基于贝叶斯检测规则,设计AUVs对于tk时刻搜索Cellxy的概率更新规则函数如下:

2.2.3 总体目标概率图更新

结合式(6)与式(11)可以构建随着任务时间推移和MAUV探测情况而更新的总体任务区域内的目标概率图,如下所示:

基于此,下一节给出MAUV搜索任务的适应值函数.

3 实时多目标适应值函数

AUV在执行任务时,受到运动特性、机械结构、行动效率等多种条件制约.本章以动态目标搜索任务的实时多目标适应值函数F(tk)描述搜索性能指标,并综合考虑机动性约束Ck,避碰约束Cd,以及危险区约束Cs进行航迹优化.

3.1 约束条件

3.1.1 机动性约束Ck

规定每艘AUV机动性约束为以下形式:

其中:φ(tk)表示tk时刻AUV的实时转向角度,φmax表示AUV的最大转向角度.

3.1.2 避碰约束Cd

规定AUV之间需满足实时避碰约束条件为

其中:dab(tk)表示第a艘AUV和第b艘AUV之间的距离,dmin表示AUV之间的最小安全距离.

3.1.3 危险区约束Cs

为了避免MAUV进入危险区,对危险区约束Cs描述如下:

其中:(xi(tk),yi(tk))为第i艘AUV的实时位置,GD为危险区栅格.

3.2 实时多目标适应值函数设计

考虑在实际任务过程中,总概率会随着MAUV系统探测逐渐下降,最终陷入代价始终超过收益的困境,本文根据实际情况将MAUV系统tk时刻的协同优化问题描述为实时多目标适应值函数

其中:RP(tk)表示概率收益;JO(tk)表示重复路径代价;JE(tk)表示能量损耗代价;JA(tk)表示航迹调整代价;JD(tk)表示进入危险区域的代价;ω(tk)为动态自适应代价权重系数;用每个栅格的平均概率值表示;计算方法如下:

其中∑Pxy(tk)表示对tk时刻任务区域中所有栅格的概率求和.

3.2.1 概率收益RP(tk)

每次探测都会将对应栅格的目标存在概率作为任务区域的探测情况,并将此刻探测的栅格概率作为已确定的探测情况,即MAUV探测的栅格概率值越高,区域内所剩未确定探测情况越少,任务区域的探明情况越明朗.每一时刻MAUV概率收益RP(tk)的计算方式如下所示:

其中kp表示概率收益系数.

3.2.2 路径重复代价JO(tk)

本文引入JO(tk)减少碰撞危险同时增加搜索效率,表示方法如下:

其中:ko表示路径重复代价系数,La表示AUVa搜索路径中覆盖栅格集合,card(·)函数表示集合中相同元素个数.

3.2.3 能量损耗代价JE(tk)

本文引入JE(tk)描述AUV执行任务中的能量损耗.如下所示:

其中:Jk(tk)为动力电池电量损耗代价,Jf(tk)表示控制电池电量损耗代价.

3.2.4 航迹调整代价JA(tk)

本文引入JA(tk)描述航迹平滑度,表达方式如下:

其中ka为航迹调整代价系数.

3.2.5 危险航迹代价JD(tk)

MAUV与危险区较近的航迹以JD(tk)描述,如下所示:

其中:kD为MAUV危险代价系数,ND为危险区域个数,rid表示第AUVi与危险区d的距离,r0和rs为危险判定距离的下界和上界.

4 IMWPA

由于狼群在解空间搜索的行动中体现出的智能性,与MAUV协同搜索行为相似,如表1所示.同时,WPA作为搜索中常用的启发式算法,适用于搜索智能目标[17].因此,本文提出一种IMWPA来对MAUV航迹规划问题进行求解.

表1 狼群行为与MAUV协同搜索相似点Table 1 Wolf behavior and MAUV collaborative search relation

4.1 基于人工势场法改进步长

步长因子决定了搜索的精细程度,由于步长因子固定,在行动中存在步长跨度过大越过最优解,或者步长跨度过小耗费算力的情况.IMWPA采用人工势场法对解空间中的人工狼的步长进行调整,设计步长因子如下:

其中:S0表示人工狼步长因子基础值;λ表示势场影响因子;Ui(I)表示第I次迭代时i狼所处位置的势场函数,设计如下:

其中ζ表示引力增益,设计为

其中:ki表示头狼引力系数表示第I代人工狼i当选头狼次数,Dw代表算法探索空间的维数.

其中:µ表示斥力增益表示第I次迭代时i狼所处位置与其最近普通狼之间的距离,大于此距离将不会产生斥力.

IMWPA通过人工势场法设置步长因子使得势场函数值与步长因子负相关、与步长正相关,利用不断学习探索过程中较好的头狼的探索规律,从而防止寻优过程越过最优解的同时,改善寻优搜索精细度.

4.2 嚎叫环节

嚎叫环节的执行步骤如下:

1)子狼群WPξ接收其他子狼群的头狼信息;

2)子狼群WPξ内部判断此刻的最优解对应的头狼是否满足全局性要求.即,若此头狼h与其他狼群的头狼探索范围发生重复,则根据式(28)对该函数值进行惩罚;

3)比较气味浓度得出新的头狼,转到步骤4;

4)判断此头狼是否满足约束条件:若不满足约束条件,删除此头狼信息,选择次优解,转回步骤2;若满足约束条件,转到步骤5;

5)WPξ通过嚎叫将此头狼h信息发布.

其中kz∈[0,1]代表探索空间重复惩罚系数.

IMWPA作为多狼群算法,通过嚎叫环节实现狼群之间的信息共享,预防探索空间的重复,改善算法全局性探索能力.

4.3 狼群更新

传统狼群搜索的淘汰更新只根据气味浓度大小采取末位淘汰机制,由于淘汰的数目大小会影响算法效果,IMWPA针对每次迭代时人工狼气味浓度的数值和速率两方面,拟定同时满足这两项条件将被淘汰:

1)数值角度:气味浓度数值处于较小的R匹,R∈[(NW-Snum-1)/2γ,(NW-Snum-1)/γ],γ为群体更新比例因子;

IMWPA通过健全淘汰更新机制,防止因淘汰数目过多导致算法趋于随机搜索的同时,保证了狼群个体的多样性.

4.4 基于IMWPA的MAUV搜索路径规划

基于IMWPA的MAUV搜索路径规划伪代码如表2所示.

表2 基于IMWPA的MAUV搜索路径规划伪代码Table 2 Pseudocode for MAUV search path planning based on IMWPA

5 仿真

为了验证IMWPA的可靠性及优越性,本节在MATLAB中建立了基于智能决策目标概率图的MAUV协同搜索动态目标的仿真环境.任务区域面积为40 km×40 km,AUV的有效探测半径Ds=500 m,将任务区域均分成40×40个单位栅格,任务区域内共设置10个动态目标.MAUV的实时变量为速率和转向角,其中速率最大值vmax=2km/h,转向角最大值φmax=45°,从任务区域的边界出发进入任务区域,AUV之间的最小距离dmin=1km,由于能耗和时间因素设定MAUV执行任务的最大时间步数stepmax=200.IMWPA算法参数设置如表3所示.

表3 IMWPA仿真参数表Table 3 IMWPA simulation parameter table

5.1 场景1:无危险区下的动态智能目标搜索

在本场景中,已知目标决策状态及其位移转移概率,设定智能目标具有4种决策状态以及9种位移行为.

最后一次预警时的目标位置作为初始条件,将预警丢失的目标视作全部搜索任务目标,如图4(a)所示.通过式(5)计算在最后一次预警时间步tk=20后的多目标概率分布图作为MAUV先验信息,此时MAUV开始执行任务,此时多目标概率图如图3(b)所示.

图3 无危险区场景下的先验信息Fig.3 Prior information without danger

多目标概率图根据式(12)进行更新,并且MAUV的搜索路径通过IMWPA进行设计.在任务结束时,得到MAUV搜索路径如图4(a)所示,以及多目标概率图模型如图4(b)所示.

图4 无危险区的任务执行结果Fig.4 Task execution results without danger area

任务时间内采取IMWPA、狼群算法、并行搜索以及随机搜索几种不同方法在动态目标任务中的路径图,分别如图5(a)-(d)所示.

从图5中可对比看出,IMWAP方法下的MAUV轨迹相比WPA覆盖范围更广,航迹平滑度更高,全局性更好.对比并行搜索和随机搜索,IMWPA发挥了启发式算法能够根据适应值函数进行航迹规划的优点.

图5 不同方法下的MAUV搜索路径图Fig.5 MAUV search path graph in different method

任务执行过程中的搜索概率收益、适应值函数值和搜索目标数对比,如图6(a)-(c)所示.

图6 无危险场景的搜索指标对比Fig.6 Comparison of search indexes for no risk scenes

从图6(a)中可以看出,由于在任务前期阶段(时间步)IMWPA与WPA的搜索概率收益相差无几.而对比另两种搜索方法则有较大领先.随着任务到达中后期(时间步),IMWPA算法的搜索过程中探测的栅格概率逐渐与其他方法拉开差距.从概率收益的上升幅度可以看出,在AUV执行任务期间,任务区域由最开始的完全未知情况(10个目标的未确定的概率为10)到接近完全探明任务区域(未确定的概率仅为0.574).在图6(b)的实时多目标适应值函数对比中,IMWPA的函数值在任务全程相较于WPA都有领先.在图6(c)的搜索目标数对比图中,在时间步到达200时IMWPA能够平均搜索到9个以上的目标.综合图6的3幅图,表明IMWPA有效且高效地完成搜索任务,在任务过程中始终执行算法最优的航迹规划路线.

5.2 场景2:有危险区下的动态智能目标搜索

本节仿真环境的初始条件在场景1的基础上增加设置针对MAUV的危险区,其余参数设置不变.先验多目标概率图仍然如图3(b)所示.在任务过程中,采用IMWPA的MAUV搜索情况如图7所示,方框中的区域为危险区.

图7 有危险区的任务执行结果Fig.7 Task execution results with danger area

从图7(a)中可以看出,AUV在执行任务的过程中能够有效避免进入危险区域.

本部分将对本文提出的算法IMWPA与狼群、粒子群和蚁群算法进行对比分析.首先,给出任务过程中的实时适应值函数对应的4个代价指标的平均值,如表4所示,从中可以看出IMWPA算法在减少重复路径和能量损耗方面性能要弱于粒子群和蚁群算法,但在航迹调整和躲避危险区域方面具有较好的性能,且从图8(a)可以进一步看出本文IMWPA发现目标的概率为8.323,该指标相比于狼群、粒子群和蚁群算法得到大幅度的提高.同时图8(b)给出的实时多目标的适应值函数,也可以看出IMWPA在多目标的优化上要好于其余3种启发式算法.

表4 200决策周期内JO,JE,JA和JD的平均值Table 4 Average value ofJO,JE,JAandJDwithin 200 decision cycles

图8 有危险场景的搜索指标对比Fig.8 Comparison of search indexes for dangerous scenes

6 结论

本文建立了智能目标概率图模型,并设计IMWPA解决MAUV协同搜索路径规划问题.根据马尔科夫链构造智能目标决策状态转移模型,将目标决策与目标位移行为进行关联,建立目标概率图.在搜索过程中,设计能够针对不同光线反射强度采取不同的探测概率和虚警率的传感器探测概率函数.提出了基于人工势场法改进了步长的灵活度、增设多狼群间的信息交互环节以及完善狼群更新淘汰机制.最后通过多组对比仿真验证本文算法的有效性和实用性.