海上动态目标潜在区域博弈预测及搜索方法

杜津铭,吴云华,陈志明,华 冰,许心怡,朱 翼,岳程斐

(1.南京航空航天大学空间光电探测与感知工业和信息化部重点实验室,江苏 南京 210016;2.南京航空航天大学航天学院,江苏 南京 210016;3.哈尔滨工业大学(深圳)空间科学与应用技术研究院,广东 深圳 518055)

0 引 言

船舶一直以来在国民经济和国防事业中发挥着重要作用。根据国家统计局数据,2018年水运货物周转量占全部货物周转量的48.39%;亚丁湾索马里一带海域频繁发生海盗劫持活动,中国海军从2008年底开始在海盗频发区域执行护航、救援等活动。因此,研究海上目标搜索可以获取对方海上力量分布,提前进行战略决策,保障己方海洋权益、远洋贸易、领土安全。

海上移动目标搜索通常利用卫星对目标先进行分析并获得其可能出现区域(潜在区域),再部署相关卫星对这些区域进行搜索。常见的搜索算法有随机搜索、最大概率网格搜索、最大发现概率搜索、最大覆盖搜索、最大信息熵增量搜索等[1]。Ru等[2]根据传感器的检测结果,使用贝叶斯理论更新目标分布概率,采用分布式模型预测控制方法设计搜索策略,提高了搜索效率。Zhen等[3]提出了一种智能自组织算法来解决多无人机的协同搜索任务规划问题。Sara等[4]采用蚁群算法对无人机的搜索路径进行设计,以确保找到移动目标的时间最短。Rihel等[5]使用类似于模型预测控制的方法更新目标分布概率密度,在有界区域中,完成多无人机的目标搜索任务并保证搜索时间最短。Yue等[6]基于改进的多蚁群理论,通过设计目标概率图减小了由动态目标引起的不确定性的影响,完成了未知环境下的目标搜索问题。饶世钧等[7]基于目标先验信息(包括任务特性、海区航行条件、大致航线等)确定多个离散目标分布区,在假设目标服从均匀分布的情况下设计最优搜索策略模型,提高了卫星离散搜索效率。王慧林等[8]利用目标航速和航向先验信息,建立目标运动预测模型并构建其潜在区域,通过遗传算法规划多星组网侦察同一潜在区域,完成对目标的侦测任务。陈杰等[9]采用侦察卫星和地面系统结合的方式获取目标运动信息,通过预测模型进行目标运动预测,最后调用遥感卫星进行目标搜索。高越等[10]结合海上移动目标和光学遥感卫星的特点,建立了目标揭示能力评价模型,完成了多星协同工作规划任务。王瑞安等[11]基于stackelberg均衡策略,结合多步预测思想,实现了无人机和目标都具有远距离探测能力的博弈搜索。

上述算法核心在于目标潜在区域预测与卫星搜索规划。其中预测算法直接决定了需要搜索区域面积和成功率,而规划算法只是在预测的基础上尽可能优化效率。这些算法大多采用均匀分布假设或基于海上动态目标航向和速度等目标先验信息,而海上动态目标航向容易受到局部环境影响,因此预测算法在时间跨度较小时效果较好,在时间跨度较大时存在较大误差。针对上述研究的不足之处,本文提出海上动态目标潜在区域博弈预测及搜索方法。基于已知信息、目标与遥感卫星星座之间的关系建立博弈论模型,以收益为指标设计博弈策略,将目标最优决策作为目标潜在区域预测算法的结果,遥感卫星星座的最优决策作为卫星搜索规划算法的结果。目标最优决策从目标航线的决定因素等方面进行求解,因此相比于基于航速信息的传统算法扩展了预测的时间跨度并提升了整体预测精度。卫星搜索规划作为遥感卫星星座在博弈论模型下的最优决策,能够保证在当前已知信息下的收益最优。本论文的方法可以应用于卫星、飞机等对大型船舶等海上动态目标的预测搜索,对国民经济和国防事业具有重大潜在应用价值。

1 目标搜索博弈论模型

博弈论[12-13]研究理性决策主体间发生冲突时的决策及其均衡问题,共有3个要素:局中人(所有理性决策主体),策略集合以及收益函数。在海上动态目标搜索过程中,局中人集为

N={遥感卫星星座,目标}

(1)

在t时刻,遥感卫星状态向量为

Xt=[xS(t),yS(t),θS(t)]T∈A1

(2)

式中:xS(t)和yS(t)为遥感卫星在t时刻的星下点位置;θS(t)为遥感卫星星下点轨迹斜率;A1为遥感卫星的状态空间。

在t时刻,海上动态目标的状态向量为

Yt=[xT(t),yT(t)]T∈A2

(3)

式中:xT(t)和yT(t)为目标在t时刻的位置;A2为目标的状态空间。

遥感卫星星座通过目标区域的扫描方向θm(t)和区域位置[xm(t),ym(t)]确定下一时刻遥感卫星,即遥感卫星星座的决策变量为

Ss(t)[θm(t),xm(t),ym(t)]∈B1

(4)

式中:B1为遥感卫星星座的决策空间。

目标通过改变其速度大小vT(t)和运动方向θT(t)决定下一时刻的位置,即目标的决策变量为

ST(t)[vT(t),θT(t)]∈B2

(5)

式中:B2为目标的决策空间。

遥感卫星星座通过(Ss,ST)决策使得捕获目标机率J1最大:

J1(Ss,ST)=max

(6)

目标则通过(Ss,ST)决策使得前往目的地的收益J2最大:

J2(Ss,ST)=max

(7)

对于上述博弈模型,若存在:

(8)

满足

(9)

(10)

2 目标搜索方法

2.1 目标搜索方法及非对称信息假设

如图1为海上动态目标潜在区域博弈预测及搜索方法示意图。在0时刻,目标根据当前任务要求和自身运动参数进行决策,然后按照最优航线航行。对遥感卫星星座,其在t时刻收到对目标进行搜索任务,根据目标过去某时刻(0时刻与t时刻之间)的位置和对目标当前任务与运动参数的估计值,对目标潜在区域预测进行最优决策估计并形成当前时刻下遥感卫星星座的最优决策。

图1 海上动态目标潜在区域博弈预测及搜索方法示意图Fig.1 Schematic diagram of latent area prediction and search method for marine moving targets based on game theory

目标和遥感卫星星座作为博弈模型中的局中人,其信息是不对称的,即两局中人的最优决策建立在非对称信息假设下:

(11)

(12)

虽然目标在0时刻进行决策,遥感卫星星座在t时刻进行决策,但双方的决策都是基于已知信息进行的,在非对称信息假设下,已知信息非时变。即在该假设下,目标和遥感卫星星座从动态博弈变为静态博弈。目标和遥感卫星星座在各自信息下的最优决策构成纳什均衡。

2.2 目标最优航线分析

对目标来说,其收益J2可以表示为

J2=Ge-Gc(Lall)-Gh(tall,Lall)

(13)

式中:Ge为目标抵达目的地可获得的收益,可看作一个常量;Gc(Lall)为目标在行动过程中的成本,为关于总航程Lall的函数,总航程越大成本越高;Gh(tall,Lall)为目标被卫星发现造成的收益损失,为关于航行总时间tall和总航程Lall的函数,目标抵达目的地所消耗的时间越长,总航程越短(即以接近直线的方式前往目的地),被发现的几率越大。

图2为目标可能航线图。A为目标起始点到目的地的最短航线,该决策只考虑Gc的航程成本和Gh中的时间因素,忽略Gh中的航程因素;B为目标到目的地的一条较长的弧线,该决策增大总航程Lall以降低目标被发现几率,但没有考虑Gc的航程成本和Gh中的时间因素。

图2 目标可能航线Fig.2 Possible routes of target

通常情况下,A、B都不是最优决策,但A、B构成了决策空间的边界,最优航线C处于A、B包围的决策空间内,其综合考虑了总航程、时间成本和被发现的损失。

图3为t时刻的目标位置。Ltotal为目标起始点与目的地之间的距离;L(t)为目标与目标起始点之间的曲线长度,即目标从目标起始点到当前位置的航行路程;Ltd为目标与目的地之间的曲线长度,即目标从当前位置到目的地的航行路程;Lbias为目标偏离目的地与目标起始点连线的距离,即目标与最短航线的最小距离。分析式(13),目标的收益J2和目标的总航程Lall以及航行总时间tall有关。其中总航程Lall为

Lall=L(t)+Ltd

(14)

图3 t时刻的目标位置Fig.3 Position of target at time t

2.3 遥感星座最优搜索策略

假设Ssat为遥感卫星成像区域面积,在t时刻,目标的概率分布为p(x,y,t),则遥感卫星发现目标的期望为

(15)

在真实环境下,遥感卫星星座的已知信息包括目标的航速范围、目标在过去某时刻t0的位置,而目标决策函数中的参数无法完全掌握。因此,假设总航程Lall为

Lall=Ltotal+Ladd

(16)

式中:Ltotal为t0时刻目标位置与目的地之间的距离;Ladd为相对于最短航程所增加的航程,可表示为

Ladd=kadd·Ltotal

(17)

目标从t0时刻到t时刻的航行路程L(t)为

(18)

Lall≥Dist(p0,pt)+Dist(p0,pd)

(19)

式中:函数Dist(pi,pj)表示点pi和pj的距离。

根据式(16)和式(17),kadd满足:

(20)

(21)

(22)

绘制目标概率分布图[14-16]以避免式中的积分运算。假设Lallmax=1.8Ltotal,即3σdis=0.8,μv=40 km/h,3σv=15 km/h,目标在t0=0 h时的经纬度坐标为[9.5°,165°],目的地经纬度坐标为[27.5°,125.4°]。图4为t=24 h时,整个区域的概率密度分布图,图5为t=48 h时,整个区域的概率密度分布图。图4和图5中的三角形为起点,六角形为目的地。分析两张图可以发现,随着时间的推移,目标出现在起点和目的地之间的概率增大,目标潜在区域的面积也不断增大。

图4 概率密度分布图(t=24 h)Fig.4 Probability density distribution map (t=24 h)

图5 概率密度分布图(t=48 h)Fig.5 Probability density distribution map (t=48 h)

在实际应用中,海上目标航行的影响因素还包括天气、洋流等。洋流主要随季节变化,而天气相对来说更具突变性,对海上航行的影响更大,因此下面对天气干扰进行讨论。天气对海上动态目标的影响主要可分为两种情况:① 不威胁航行安全的普通天气,主要干扰海上目标的航速;② 热带气旋等威胁海上航行安全的恶劣天气,将对海上目标的航线规划产生直接影响。对第一种情况,根据气象局发布的预报信息,调整式中μv和σv(海上目标航速相关参数)以降低天气对船速的干扰。对第二种情况,影响的具体表现为海上目标的航线在进行规划时将避免经过恶劣天气影响区域,即将直接影响海上目标概率分布区域。根据天气对航线的影响程度,划分恶劣天气影响区域(简称天气区域),该区域是海上目标航行禁区。根据第2.2节的分析,海上目标最优航线为折线,因此通过从目的地和目标起始点对天气区域作切线,划分出3块受天气影响的区域,结果如图6所示。

图6 恶劣天气影响区域划分Fig.6 Regional division affected by severe weather

对于图6中区域1,天气主要影响海上目标的未来航线,而对当前时刻的概率分布影响较小,可以忽略其影响。对于区域3,海上目标进入该区域的航线必将经过天气区域,因此在区域3中,海上目标分布概率为0。对于区域2,天气区域将影响经过该区域的航线,即降低该区域分布概率。该区域内点(x,y)的概率密度p(x,y,t)变为

(23)

假设天气区域为圆形,圆心为[28°,160°],半径为500 km。图7为t=48 h时刻,天气影响下的海上目标概率分布图。

图7 天气影响下的概率密度分布图(t=48 h)Fig.7 Probability density distribution map under the influence of weather (t=48 h)

2016年投入使用的GF-4卫星可见光红外波段的分辨率优于50 m,单景成像幅宽优于500 km×500 km。欧洲空客公司提出的GO3S卫星星下点空间分辨率为3 m,成像幅宽为100 km。GEO SAR卫星通常能够达到幅宽400 km之上[17],如Madsen等[18]研发的系统能够提供10 m空间分辨率、600 km幅宽的条形观测带,Braun等[19]提出的系统空间分辨率为20 m、总幅宽为1 800 km[20]。因单颗卫星的覆盖范围、载荷观测能力等有限,难以满足对全空域、全时域的信息获取需求,需要将多星构成一个遥感星座。同时由于卫星轨道限制,对海上动态目标的观测属于间歇式事件[10],通常情况下无法在单次成像就完成对所有目标潜在区域的探测,因此考虑通过多次成像完成对可能区域的探测。

假设Δtsat为遥感卫星星座访问指定地区的时间间隔,Wsat和Lsat为遥感图像的宽和长,nsat为成像次数。图8为第1次和第2次成像的成像区域示意图。对于第i次成像,其成像区域的目标概率分布p(x,y,t)将会变为0或1,0为未发现目标,1为发现目标,提前结束后续成像过程。对于第i+1次成像来说,成像区域可以和第i次成像的成像区域合并,将合并后的大区域作为第i+1次的成像区域。

需要注意的是,由于两次成像之间有时间间隔Δtsat,如果目标在第i次成像时位于成像区域边缘,则在下一次成像前,目标将会进入第i次成像区域。因此，对于第i+1次成像,在合并上一次成像区域前,需要将上一次的成像区域向内收缩VmaxΔtsat,Vmax为目标的最大速度。

图8 成像区域Fig.8 Imaging area

对于第i次成像,Ssat(i)为成像区域面积,t为成像时刻,p(x,y,t)为目标在t时刻的概率分布。遥感卫星星座的收益J1可以表示为

G2(Ssat(i))-G3(i,Δtsat)

(24)

式中:第1项为卫星发现目标的期望,其中kcost-pro为调节系数,其值越大代表发现目标的重要性更高,值越小代表更看重为发现目标所付出的成本;第2项G2(Ssat(i))为到第i次成像为止遥感卫星拍摄并处理图像的成本;第3项G3(i,Δtsat)为到第i次成像为止拍摄图像所花费的时间成本。

3 数学仿真与分析

为了验证海上动态目标潜在区域博弈预测及搜索方法的有效性,对基于航速信息的传统算法、仅基于海上动态目标分布概率的搜索算法和本文提出的潜在区域博弈预测及搜索算法进行仿真研究。

3.1 仿真参数

设置海上动态目标目的地经纬度坐标为[27.5°,125.4°],起始点(目标在t0=0 h时的坐标)为[9.5°,165°]。假设Lallmax=1.8Ltotal,即3σdis=0.8,μv=40 km/h,3σv=15 km/h,遥感卫星星座的成像幅宽Wsat=600 km,遥感卫星星座访问指定地区所需时间(相邻两次成像时间间隔)Δtsat=30 min。

图9为针对图5的概率密度分布设计的最优决策成像区域。图9中的三角形为起始点,六角形为目的地。虚线圈出了概率密度大于一定阈值(最大值的2%)的区域,为最优决策所要求的有效成像区域,该区域下发现目标的数学期望超过97.62%。实线矩形框对应第i次成像区域,即第i次进行目标搜索的区域。通过调整成像区域的位置和成像顺序,可以使得发现目标的期望概率和预计搜索次数最优。

图9 最优决策成像区域Fig.9 Imaging area of optimal

选用基于航速信息的传统算法和仅基于海上动态目标分布概率的搜索算法作为对照组。图10和图11分别为两种算法的成像区域,图中实线矩形框对应第i次成像区域,三角形为起始点,六角形为目的地。图10为传统算法的成像区域,该算法基于航速信息,单次搜索区域为沿目标在t0=0 h时的坐标与目的地连线的垂线方向的条形扫描带,从海上动态目标可能到达的离目的地最近的位置开始,向目标t0=0 h时的坐标进行多次搜索。图11为仅基于海上动态目标分布概率的搜索算法的成像区域,该算法单次搜索区域与传统算法类似,但是根据海上动态目标分布概率密度对每次搜索的扫描带长度进行调整,从目标t0=0 h时的坐标开始向目的地进行多次扫描。

图10 基于航速信息的传统算法的成像区域Fig.10 Imaging area of traditional algorithm based on navigational speed information

图11 仅基于海上动态目标分布概率的搜索算法的成像区域Fig.11 Imaging area of search algorithm based only on distribution probability of the marine moving target

3.2 仿真结果与分析

分析表1实验结果可知,传统算法仅基于海上动态目标的最大航速估计值,从目标可能达到的离目的地最近的位置开始搜索,因此在目标的航线近似于起始点到目的地的直线(对应第2组仿真参数,即表1第3行)和目标在过去一段时间的平均航速较大(对应第4组仿真参数,即表1第5行)这两种情形下,算法对目标的捕获率较高,而在其他情形下算法的捕获率较低。

分析表2实验结果,搜索算法仅基于海上动态目标分布概率,未考虑搜索顺序的影响。算法在面对推理参数与实际参数不一致的情形时,对目标的捕获率整体较好,仅在目标在过去一段时间的平均航速较大(对应第4组仿真参数,即表2第5行)这一情形下捕获率较低,这是由于航速较大时目标的实际可能分布区域大于理论区域,因此搜索区域的期望预期低于理论计算值。

分析表3实验结果,潜在区域博弈预测及搜索算法综合考虑海上动态目标分布概率与卫星星座搜索路径,算法在面对推理参数与实际参数不一致的情形时,对目标的捕获率整体依旧较好,仿真结果基本符合理论计算结果。

表1 基于航速信息的传统算法Table 1 Traditional algorithm based on navigational speed information

表2 仅基于海上动态目标分布概率的搜索算法Table 2 Search algorithm based only on distribution probability of the marine moving target

表3 潜在区域博弈预测及搜索算法Table 3 Latent area prediction and search algorithm based on game theory

对比分析表1,表2和表3的实验结果,传统算法所需信息较少(仅需要海上动态目标的最大航速估计值),但是对目标的捕获率随着真实情况的不同,波动较大,整体捕获率较低;相对于传统算法,仅基于海上动态目标分布概率的搜索算法引入了更多目标的信息,搜索区域更具针对性,因此算法的整体捕获率更高;潜在区域博弈预测及搜索算法综合考虑了海上动态目标分布概率与搜索成本,对搜索路径进行了优化,在保证了较高目标捕获率的同时,平均成像次数和平均搜索面积较前两种算法大幅下降。

4 结 论

针对海上动态目标搜索定位问题,根据目标已知的历史位置及可能的目的地,本文给出了一种目标潜在区域博弈预测及搜索方法。通过对海上动态目标和遥感卫星星座之间的态势进行分析,在非对称信息假设下,将两者的博弈关系从动态博弈转化为静态博弈。以收益设计博弈策略,将目标潜在区域预测和卫星搜索规划转化为纳什均衡下最优策略求解。对3种搜索算法进行仿真校验。

结果表明,该算法在保证了较高目标捕获率的同时,资源消耗量(成像次数与成像面积)较小。相比基于航速信息的传统算法,该算法引入了目的地信息,能够良好应用于时间跨度(海上目标的已知轨迹点对应时刻和开始搜索时刻之差)较大的情形,预测算法的结果作为搜索算法的输入,预测时间跨度和预测准确性影响搜索算法的效率。预测时间跨度越大,目标潜在区域也越大,即需要进行搜索的区域也越大。从算法的应用角度定义预测时间跨度的阈值:完成目标搜索的时刻必须早于目标抵达目的地的时刻,即预测时间跨度与目标潜在区域搜索的时长之和必须小于目标到达目的地的预计时长。相比仅基于目标分布概率的搜索算法,该算法通过设计遥感卫星星座的收益函数,能够在低搜索成本(低目标捕获率)和高目标捕获率(高搜索成本)等不同任务场景之间灵活切换。需要指出的是,该方法不仅能够应用于遥感卫星星座对海上动态目标的搜索,同样也适用于无人机或机器人对移动目标的搜索应用需求。