复杂三维多面体环境中空地协作追逃问题

梁 宵,王宏伦 ,骆海涛

(1.沈阳航空航天大学自动化学院,辽宁沈阳 110136;2.北京航空航天大学自动化科学与电气工程学院,北京 100191;3.中国科学院沈阳自动化研究所,辽宁沈阳 110016)

1 引言

人工智能技术是目前各国学者争相探索的前沿领域,广泛应用于各类智能体.将智能体放置于对抗环境,考量其智能性是一种有效方法(如AlphaGo),因此许多研究围绕着智能体的决策问题展开[1].

空地协作系统是一种新型的多智能体异构系统,利用无人机(unmanned aerial vehicle,UAV)和无人车(unmanned ground vehicle,UGV)各自的感知优势能够完成复杂的协作任务,各国学者均在这方面取得了一系列阶段性的成果.Chaimowicz等人提出了一种抽象模型[2],通过观察全局信息来提供模型状态的估计,实现了空中平台对多辆UGV的控制.Grocholsky等人提出了一种“空中牧羊犬结构”[3],其在城市中部署上百辆UGV,采用UAV控制UGV的分散与聚合以及搜索不同区域.Hager等人针对协同无人救援系统提出了两架UAV导引一辆UGV的协作自主系统(cooperative autonomous system,CAS)[4],各模块通过传感器信息融合进行数据交换,能够较好的避免单一传感器带来的感知误差.Khaleghi等人提出了一种动态数据驱动自适应多尺度仿真(dynamic data driven adaptive multi-scale simulation,DDDAMS)结构,用以处理多智能体的信息交换,从而完成集群运动[5].任务的不同导致这些异构系统的结构各有特点,因此针对追逃问题所描述的对抗环境,需要首先设计合理的系统结构和协作方式,进而考虑如何在复杂对抗环境中体现出协作系统的智能性.

追逃问题属于典型的对抗博弈问题[6].微分对策是经典的解决方案之一,其使用Hamilton–Jacobi–Isaacs(HJI)微分方程对参与者的运动进行统一描述[7].Goode等人利用微分对策使两个智能体获得了较高的避撞成功率[8].Awheda等人提出一种模糊强化学习算法用以解决多追单的问题[9],该算法对“Apollonius circle”定义的抓捕区域进行学习,能够抓捕到速度较快的逃跑者并避免碰撞.基于微分对策的方法将物理约束表达为数学约束,但处理环境约束(特别是复杂环境)却容易捉襟见肘.

警察抓小偷问题是基于图的追逃问题中研究最多的,并且Goldstein等人指出它是一个EXPTIME–complete问题[10],因此不太可能找到一种明显高效的求解算法.Isler等人指出对于分割图中单警察基于行动次序的模型,追逃时间由图的顶点数目决定[11].基于几何环境描述的狮–人博弈也是目前研究的重要分支.Casini等人提出在每次移动时更新计算中心的情况,并给出了博弈时间上界[12].Sato等人通过近似分析,推导出简单链接的几何图形中抓捕时间的上界[13].接着,Bhadauria等人指出3个狮子能够在任何可能有孔的二维多边形环境中抓住人类[14].然而如何使追逃策略适应更加复杂的环境,仍是需要深入研究的问题.

UAV/UGV空地协作系统不同于传统智能体,UAV在空中高速飞行可以侦查广阔的区域,进行空中火力压制;UGV在地面工作,可以和周围环境进行复杂的交互活动,但行进速度较慢.由UAV和UGV组成的空地协作系统,并不是简单地由“单兵”变成“多兵”,这种异构特点将带来独特的协作优势,放置于复杂环境的追逃博弈中,如何使1+1>2?

本文在复杂三维多面体环境中,研究了由UAV和UGV组成的异构智能体的协作追逃问题.在提出的任务背景与协作系统结构下,将三维实时航路规划作为追逃博弈的走法生成器,实现了地形模型的统一.针对非凸三维多面体环境约束和空地协作系统特点,分别分析了追逃双方的最坏情况,并在最坏情况下给出了追逃双方的博弈策略.

2 协作追逃问题的预备知识

2.1 UAV/UGV空地协作系统与前期工作

UAV/UGV空地协作系统的工作过程如下:UAV在空中飞行,速度较高且视野宽阔;UGV在地面展行驶,速度和视野较小,但能够与环境产生复杂互动.UAV和UGV共享彼此位置、速度和感知等信息,并且能够共享策略.空地协作系统的结构如图1所示.

图1 UAV/UGV空地协作系统Fig.1 UAV/UGV air-ground collaborative system

在前期的工作中,已经实现了该系统的原型机[15],搭建了较为完善的地面站[16],并利用该系统完成了许多复杂的任务,比如:基于Apriltag的实时目标跟踪[17]、复杂背景下的协作跟踪[18]、协作导引降落[19]等.UAV和UGV上均搭载图像、气压、高度和红外等传感器,能够对环境信息和对方运动信息进行感知,采用惯导辅以GPS和视觉等方式完成相对定位,并且地图被认为是已知的,事先存储于机载计算机中.UAV和UGV通过以数传和图传为基础的空地数据链与地面站进行通信.

2.2 不完全信息下的协作追逃问题描述

在第2.1节描述的协作系统框架下,一架UAV(记为P1)和一辆UGV(记为P2)在三维复杂地形环境中对一辆UGV(记为E)展开追逃博弈,且P1,P2和E存在速度关系VP1>VP2=VE.在三维复杂对抗环境中,协作系统既需要与敌对运动目标展开追逃抓捕,又需要考虑实际的三维复杂地形约束与自身的物理约束.另一方面,协作系统内部能够通过信息共享展开合作,在追逃策略中体现出“协作追捕”与“单兵追捕”的区别与优势.E不同于传统的无目的被动抓捕对象(区别于运动目标跟踪),其还能够利用敌对双方的位置以及地形进行逃脱,具备较高智能性.

图2 UAV/UGV协作追逃示意图Fig.2 Pursuit-evasion of UAV/UGV air-ground system

P1和P2在追逃过程中共享E的位置和速度等信息,并且完全已知彼此信息,但不知E的逃跑策略.E的目标是在对抗环境中尽可能提高生存几率并摆脱追击,其已知P1和P2的位置和速度等信息,但不知他们的追击策略.追方和逃方互相不知道彼此的策略,即双方决策信息对称.假设E随时已知P1和P2的位置与速度信息,而P1和P2对躲避在障碍物后E的位置和速度完全未知,因此双方物理信息不对称.此时追方只能在不完全信息下进行决策,而E占据明显优势.由于P1和P2是协作关系,因此E的信息如果被P1获知,P2也会被通知,反之亦然.地形是足够大但有界的,并且对于追逃双方是已知的,追逃双方轮流采取行动.当E到达地图边界认为逃方胜利,当P1或P2在一个计算周期内到达E的位置则认为追方胜利.

这种假设是非常实际且有意义的.在军事方面,对抗的战场一般是公共区域,存在信号的干扰、欺骗或屏蔽.而由于军事力量不同,经常会有一方处于弱势,本文的研究能够有效帮助弱势方完成决策.在民用方面,当警用直升机和警车共同追逐城市环境中的罪犯时,往往可能丢失躲在建筑物后的罪犯,而随着高智商犯罪越来越多,罪犯很可能有周密的计划或更好的装备从而随时了解警察的位置.

根据协作追逃问题的描述,协作策略由信息的完备程度以及逃跑概率决定.进一步说,信息的完备程度代表了视觉域的可见性,其根据E相对于P1和P2的状态不同而不同.而逃跑概率则与逃跑路径有关,即与地形中的障碍有关.可见性和逃跑路径相互依存,共同决定了协作策略.那么,本文的追逃问题就可以抽象描述为不完全信息情况下在复杂非凸环境中的协作追逃问题.设E在t时刻的位置为E(t),地图和障碍信息用M表示,则逃跑路径的集合为F(E(t),M),其中第i条逃跑路径为ri.定义E在此时沿ri逃跑的成功率为pE(E(t),t|ri),那么协作追逃问题的决策模型S可由下式描述:

其中符号∝表示决策模型S由右侧的结果决定,并且ri ∈F(E(t),M).

3 基于三维实时航路规划的追逃博弈走法生成器

航路规划是决策的出口与实现手段,将追逃理论与航路规划统筹考虑是决策落地的重要保障.追逃决策需要计算双方所有可能的逃跑路径,因此本节以航路规划算法为基础设计追逃博弈的走法生成器.只有决策算法和航路规划的地形数据能够统一,才能实现这两类研究的无缝衔接(非分层规划[20]).

由于复杂约束的微分对策难以获得解析解,因此本文的追逃策略是建立在多面体环境基础上的.为了实现策略和航路规划的数据统一,应该采用多面体环境下的航路规划方法作为走法生成器(比如基于图形的方法或基于网格的方法).这里,提出一种基于离散网格的改进边界值问题(boundary value problem,BVP)方法作为追逃博弈走法生成器.BVP势场能够避免调和场法的局部极小问题,同时保持了调和场法实时性较好的特点[21].BVP势场属于调和场,其需要建立一个如图3(a)描述的网格地形模型.因此BVP方法的精度受网格密度影响,但并不影响它的有效性.

BVP方法根据势场的梯度下降方向确定最短路径,如图3(b)所示.目标区域被定义为最低势场,边界被定义为最高势场,因此每个网格均有一个梯度大小和方向.注意,图3(b)中的矢量既有方向也有大小,这里只画出了矢量方向.在狄氏边界条件下,每个网格的势场由下式计算:

式中:v表示偏转单位矢量,ε是已知参数.调整这两个参数将人为改变势场从而改进搜索.利用高斯赛德尔(Gauss–Seidel)方法,对BVP方法进行离散化改进,以三维为例,用式(3)完成网格势场动态更新:

中心网格与26个网格相邻(类似魔方中心的部分),因此离散势场的更新与相邻的26个网格有关.式(3)中a为叠加场系数,分别是当前时刻和下一时刻的中心网格势场,第2项是相邻网格的平均势场,第3项是相邻网格的传播场.由于地图有界但较大,因此BVP方法需要改进从而提高收敛速度.单纯增大目标引力场和边界排斥场是不合适的,其会导致势场提前收敛于局部极小.因此借鉴水波纹现象,即波纹的涟漪抵达边界时反向传播的特点,设计了叠加场系数,将障碍物顶点的势场影响纳入考量,如图3(b)中的圆圈箭头.

4 协作追逃博弈策略

追逃问题是博弈论的重要分支,属于人工智能学科极具挑战的研究领域.复杂环境下的追逃问题属于EXPTIME–complete问题,被证明不存在有效的多项式时间求解方法,因此很难找到解析解,只能寻求近似解.传统的追逃问题在无障碍环境中取得了较大突破,而在有障碍地形(非凸环境)中却难以推广.另一方面,随着异构智能体的加入以及规划空间从二维上升到三维,求解非完全信息下的追逃问题变的更为困难.

4.1 逃方策略

逃方策略的总体思想包含以下3点:

1) 向最近的边界移动;

2) 减小被P1或P2发现的概率;

3) 尽可能增大与P1和P2的距离.

第1点是E胜利的条件,第2点和第3点是E生存的条件.E在保证生存的前提下,尽可能争取胜利.在E的策略中,提出一种最坏情况:P1或P2一旦发现E,以后始终可见,即OSU(once-seen-until)条件.

下面根据OSU条件在一个计算周期内描述E的策略.首先,寻找E到每个地图边界点的最短避障路径集合假设第i条路径由有限个航路点组成

接着计算E沿不同路径逃跑的概率,设E在t时刻位置为E(t),其下一时刻的可行路径点为E1(t+1),···,Ek(t+1),其中脚标1,···,k表示t+1时刻的可行路径分支,lj(t+1)表示第j个分支的子树数量.则逃方选择分支Ej(t+1)的概率为

其中j∈{1,···,k}.之后利用直线视野(line-of-sight,LOS)[22]或视觉域(field of view,FOV)[23]计算各航路点被P1或P2发现的概率.

由于P1和P2共享追逃策略,因此认为被P1或P2二者之一发现,E即暴露.特别地,并不是每个航路点代表E行动一步,其与网格密度有关,由于网格尺寸依据一个周期内P1的移动距离建立,则参与者的行动步数关系如表1所示.

表1 E的行动步数与第i条航路的路径点关系Table 1 Relationship between the steps of E and the waypoint of the ith path

接着,根据每个航路点被P1或P2发现的概率,计算每个航路点被P1或P2发现的风险值.对于第i条航路的第j个航路点,如果不被P1和P2发现,该航路点风险值为如果被P1或P2发现,但E在胜利前不被抓捕(需要利用第3节算法推演航路点j之后P1和P2的抓捕情况),风险值为如果被P1或P2发现,且E在胜利前被抓捕,风险值为R_E(i)_M(j)=2,并且根据OSU条件,航路点j之后的所有航路点风险值均设为2.则E所选择的逃跑路径为

这种累加风险值的方法,与文献[24]的分支概率思想类似,但计算更为简便,且不限于速度相等的追逃问题.然而,全概率的计算会导致复杂度增加,为了实现全局最优策略,这种代价无法避免.

4.2 协作追击策略

传统的追逃问题一般采用将逃方驱赶至有界边界的策略,比如狮–人问题[25].但本文的地图是有界且足够大的,传统方法难以确保追方胜利.因此,本节将充分利用协作系统特点(VP1>VP2)设计追方策略.根据E相对于追方的状态有如下3种情况.

4.2.1 情况1: E处于P1或P2的视野范围内

此时以路径最短进行追击,但特别地,P1和P2需尽量保持E始终在视野中.因此,追方策略为:尽可能保证E最大概率位于协作视野中,P1和P2采用下面的算法1 进行抓捕.其是在非完全信息情况下,兼顾障碍分布与最短路径的最优策略.

算法1P1和P2下一时刻的期望位置计算.

1)forP1的所有相邻网格next_P1do

forP2的所有相邻网格next_P2do

假设P1当前的相邻网格为next_P1(i),P2当前的相邻网格为next_P2(j),根据LOS与BVP算法,计算E与不被P1或P2观测到的边界间的最短路径集合

2)forPath_PEdo

针对集合Path_PE中的每条路径,计算E脱离视野所需的步数或周期数(参考第4.1节),并加和作为风险集合

由于P1在三维空间中向前飞行,P2在二维空间中移动(如图4所示),因此P1的相邻网格集合next_P1包含9个元素,P2的相邻网格集合next_P2包含8个元素.算法1并非只以路径最短为目标(不同于传统的航路规划算法),其体现了协作视野的重要性,那么P1在垂向上移动的可能性将增大,这样P1的视野将具备更佳的全局性.

图4 P1和P2的相邻网格Fig.4 Adjacent grid of P1 and P2

4.2.2 情况2: E刚刚消失于P1和P2的视野

图5中,设狮子的初始位置为L0=(L-x0,L_y0),人的初始位置为M0=(M-x0,M_y0).在追逃开始阶段,狮子在直线M0L0上找到一点C(L0在线段M0C上).以C为圆心,CL0为半径做圆(可以有无数个圆),在所有圆中按照图5的情况找到距离坐标原点最近的圆心即为的C位置.追逃过程中,坐标轴即为边界,并且C的位置不变.狮–人问题衍生出了很多重要的研究结论,具体可以参阅文献[26–27].

图5 狮–人问题Fig.5 Lion and men problem

本文的地图是有界足够大的,并且地图中存在较多供逃方躲藏的障碍,而追方只具备LOS视野并非全局视野,因此本文的逃方将拥有更加有利的条件,而追方的追击环境更加严苛.因此“协作堵截”策略充分发挥了空地协作系统特点,帮助追方应对这种挑战.

类似第4.1节逃方策略的讨论,对追方同样提出一种最坏情况:一旦P1和P2丢失E的位置,E以后始终不可见,即OLU(once-lose-until)条件.则“协作堵截”策略为:在OLU条件下,利用的空地协作特点,P2将E消失的位置作为子目标点进行直线追击(图6),而P1根据E逃跑的趋势,将E未来可能出现的位置作为子目标点进行堵截(图7).

图6 丢失目标时P2的二维追击情况(矩形为例)Fig.6 2D pursuit of P2 when the evader is lost

图6中,设E(t)为E的当前时刻位置,E(t+1)为E的下一时刻位置,P2(t)为P2的当前时刻位置,O1为矩形障碍,Vinvisible为不可见点.当E由E(t)行进至E(t+1)时,其相对于P2的状态由可见变为不可见.造成遮挡的O1的顶点S即为子目标点,根据文献[24],其具有如下性质:

性质1如果P2与E因多边形遮挡而不可见,则P2与E之间的最短路径是一条多边形路径,多边形的顶点是该路径中的一点.

由性质1,子目标点必在P2和E之间的最短路径上,其作用是对E进行驱赶和逼迫,使追逃态势向追方有利的方向发展.对于P1的三维堵截情况,根据之前的工作[28–29]计算子目标点.图7以长方体为例,介绍了三维子目标点的计算方法.

图7 丢失目标时P1的三维堵截情况(长方体为例)Fig.7 3D pursuit of P1 when the evader is lost

图7中,设E(t)为E当前时刻位置,E(t+1)为E下一时刻位置,P1(t)为P1当前时刻位置,O1为长方体障碍,Vinvisible为不可见点.记直线P1(t)E(t+1)与O1的交点靠近E(t+1)一侧的为D,D到其所在平面各边中最近的一条垂足为A,其所在边为FG.平面E(t)P1(t)E(t+1)与FG交点为B.当E由E(t)行进至E时,其相对于P1的状态由可见变为不可见.则存在如下定理.

定理1对于任意的B位置,图7中有

证以FG为轴旋转平面AE(t+1)B,直至与AP1(t)B成为同一平面E(t+1)BP1(t).此时点P1(t),A和E(t+1)在一条直线P1(t)E(t+1)上.在三角形E(t+1)BP1(t)中,有

由于B点是任意的,因此式(6)始终成立. 证毕.

由于本文假设如果E对于P1不可见,则P1丢失E的位置,因此实际上E(t+1)对于P1是不可知的,即A点无法得到.在“协作堵截”策略中,当丢失E位置时,P1将E未来可能出现的位置作为子目标点进行堵截,即图7中的S1和S2.因为平面E(t)P1(t)E(t+1)先与边HI相交,因此P1先以S1为子目标点,如果仍未发现E再以S2为子目标点.S1,S2和B均是障碍O1某一竖边上的点,并均在平面E(t)P1(t)E(t+1)内.以S1为例给出计算通式.

在三维空间中,设HI所在的直线方程为

其中:(x1,y1,z1)是点H的坐标,(x2,y2,z2)是点I的坐标.用中间变量l重写方程(7)为

那么,方程(7)可以变形为

设P1(t),E(t)和Vinvisible所确定的平面方程为

其中AA,BB,CC和DD是已知系数,联立方程(9)和方程(10)解得中间变量

将式(8)中的l代入式(6)就能计算出交点S1的坐标(子目标点).之前的工作包含多种二维和三维复杂几何体,其中三维几何体包括:长方体、球体、圆锥、圆柱等,仿照上述的过程能够计算出子目标点.可以证明,上述子目标点的计算方法均是具备最短路径特点的,具体可以参考文献[28].

4.2.3 情况3: E的信息对于P1和P2完全未知

P1和P2进行协作搜索.计算各自在下一时刻的视野覆盖面积,使P1和P2在下一时刻所观察的协作视野最大.其追逃策略为:执行情况3的协作搜索算法直至发现E(转化为情况1)或追逃过程结束.

根据文献[30]的结论,在非完整信息情况下很难找到最优解,因此协作搜索的目标是减少感知重叠,扩大视野面积.并且文献[31]指出,对于藏匿在障碍后的逃跑者的搜索策略存在条件是:搜索算法必须是完备算法.因此协作搜索可以采用最大–最小算法.

4.2.4 补充说明

1) 地图有界足够大的假设是为了有足够的步数推演追逃过程.由于追方在不完全信息下进行决策,如果地图很小,逃方非常容易获得博弈胜利.

2) 对于P1和P2,全局最坏情况是:P1和P2不知道E的位置.因此,追方的总体策略是尽可能将情况3转换为情况2,然后在情况2的OLU条件下尽可能将情况2转换为情况1完成追逃.

5 仿真验证与分析讨论

5.1 三维多面体环境中的协作追逃仿真

在1000×1000×6的三维地形中对本文的方法进行验证,地形中一共有27个障碍,其中长方体障碍19个,圆柱障碍4个,圆锥障碍4个,P1起始点为(50, 50, 1),P2起始点为(370, 150, 0),E起始点为(450,370,0),速度关系为P2和E每个计算周期移动一个栅格.图8(a)为复杂三维多面体环境中的UAV/UGV协作追逃仿真结果,图8(b)为其俯视图.追逃过程被划分为6个阶段进行分解说明.

图8 复杂三维多面体环境中的UAV/UGV协作追逃Fig.8 Collaborative pursuit-evasion of UAV/UGV system in a complex 3D polyhedral map

阶段1图8(b)中,E对于P1和P2均不可见,则P1和P2向协作视野最大的方向分头搜捕.E已知P1和P2的位置,为减小在P1和P2中视野暴露的概率,其选择向地图的东北方向移动,并且寻找位于(400,450)的长方体障碍作为掩体进行躲藏.

阶段2图8(b)中,E仍 对于P1和P2均不 可 见,因此保持原协作搜索策略,向协作视野最大的方向移动.E已经完成了寻找掩体的躲避,并结合P1和P2的移动方向,继续向边界(胜利条件)移动.

阶段3与阶段2相似,E仍然对于P1和P2均不可见.但由于P1的速度高于P2和E,因此在图8(b)中P1已经几乎完成了地图的搜索.E被发现的危险逐渐增加,因此图8(b)中E在保持继续向边界移动的同时,选择位于(500,550)的长方体障碍作为第2个掩体进行躲藏.

阶段4图8(b)中,E在向第3个掩体(650,650)移动过程中(同时第3个掩体也更靠近边界,即E的胜利条件),被P2发现并与P1共享.接着,P1和P2改变了追捕策略(由第4.2节的情况3转为情况1),此时图8(b)中P1和P2同时向着E进行追击.

阶段5图8(b)中,E绕过第3个掩体(650,650),脱离了P1和P2的视野,并继续向边界移动.此时由于P1和P2丢了E的位置,则追捕策略转为情况2的“协作堵截”.图8(b)中P2向着E消失的方向移动,P1向着E可能出现的位置移动.

阶段6E在到达边界之前被P1抓捕.图8(b)中,P2由于速度较慢此时刚刚绕过位于(650,650)的障碍.P1在绕过(650,650)的障碍之后发现了E,而E正准备将位于(750,850)的障碍作为第4个掩体,但由于E与P1距离较近,其没有足够的时间完成摆脱,因此最终追方获得胜利.

5.2 对比仿真验证

目前的追逃研究大多在开放的凸环境[32],非凸环境较少.为了验证本文算法性能,选择文献[24]的算法进行了对比仿真,其研究了一种基于可视性的追逃问题,提出了多边形环境中的随机追逃策略,能够利用子目标点完成多步追逃.为了阐述简便,在后续分析中将本文的算法简称“方法1”,将文献[24]的算法简称“方法2”,针对图8所示地形进行对比仿真(只显示俯视图),如图9所示.

图8–9中,相同线型所代表的意义一致,是用方法1计算得到的路径,整个追逃的过程同样被划分为几个阶段进行分解说明.在图9中,阶段1–3使用的是方法1,阶段4–6使用的是方法2.这是因为方法2 在丢失目标后采用的是随机搜索策略,其虽然保证了算法的完备性,但却由于缺少启发信息,使得E在复杂地形中极容易逃脱.本文的方法1在丢失目标后将转入第4.2.3节的情况3,采用协作视野最大化的搜索策略,提高了搜索效率.因此,为保证追逃过程的连续性,只在阶段4–6使用方法2.方法2没有给出逃方策略,因此E的策略仍使用本文第4.1节的算法.阶段1–3的结果与第5.1节一致,不再赘述,下面从阶段4开始进行对比分析.

图9 对比仿真结果Fig.9 Comparison of simulation results

阶段4E向位于(650,650)的第3个掩体躲藏过程中被P2发现并通知了P1.方法1和方法2在E位置已知的情况下均采用直线追击,因此图8(b)和图9中P1和P2同时向E的方向进行追击.

阶段5E绕过位于(650,650)的第3个掩体并脱离了P1和P2视野.此时由于P1和P2丢失了E的位置,方法1和方法2采用了不同策略:图8(b)中方法1的追捕策略由第4.2节的情况3转为情况2,P2向E消失的方向追击,P1向E可能出现的位置堵截,展开合围;图9中方法2的P1和P2同时将E消失的位置作为子目标进行追击.

阶段6E再次被追方发现.针对方法1和方法2不同的追方策略,本文E的路线也有所改变.对于图8(b)中的方法1,由于P1和P2采用了“协作堵截”策略,追方的包夹使得E只能继续向地图的东北方向移动,其逃跑空间进一步被压缩,最后追方获胜.图9的方法2中,由于P1和P2均处于E的同侧,因此其利用了位于(650,650)的障碍进行掩护,通过绕圈的方式尝试对追方进行摆脱,但由于P1速度较快使得E摆脱失败,最终追方获得胜利.然而,随着E的速度逐渐提高,实验结果表明:在图9的地图中使用方法2时,当逃方速度到达临界速度1.2VE=后,逃方是可以获胜的.因此方法1的鲁棒性更好,能够在P1和E的速度较为接近时,仍然保证追方具有较高的胜率.

表2从视野覆盖程度和路径长度方面对比了方法1–2.由于阶段1–3均使用了本文的方法1,因此表2只列出了阶段4–6的对比内容.表2中的视野覆盖程度是当前阶段下的平均视野覆盖面积,追方与E的距离采用区间表示,区间的上下限分别是追方在当前阶段下与E的最大和最小距离.

对于表2中方法1的P1,在阶段4–5,其在获知E的位置后,追逃策略由情况3转为情况2,因此迅速缩小了与E的距离.但在阶段6,由于需要对位于(650,650)的障碍进行避障,因此存在短时间内与E距离增大的情况.在视野覆盖程度方面,方法1的P1在阶段6进入空白地带的直线追击,因此阶段6的视野范围大于阶段4–5.

对于表2中方法1的P2,由于在阶段4其发现了E的位置,因此追逃策略由搜索转变为直线追击.在阶段4–5,P2与E的距离逐渐缩小.位于(650,650)的障碍对P2的追击路线造成了影响,并且E开始向位于(750,850)的障碍移动,因此阶段6中P2与E的距离存在增大的现象.在视野覆盖程度方面,方法1的P2在阶段5进入到两个障碍的间隙,因此阶段5的视野范围比阶段4和阶段6小.

表2 方法1与方法2的对比Table 2 Comparison of Method 1 and Method 2

对于表2中方法2的P1,在阶段4–5,其在获知E的位置后,直接向E的位置移动,迅速缩小了与E的距离,并且在阶段6中围绕位于(650,650)的障碍对E进行追击,距离进一步缩短.在视野覆盖程度方面,方法2的P1在阶段4–5经过的区域相对空旷,因此其视野范围在阶段4–5相较于方法1大,而方法2的P1在阶段6始终围绕位于(650,650)的障碍进行追击,因此其视野在阶段6比方法1小.

对于表2中方法2的P2,其在阶段6的视野范围比方法1大.在与E的距离方面,方法2的P2在阶段5–6比方法1小,这是由于两种方法中E的逃跑方向不同所导致.

5.3 追逃结果的影响因素分析

追逃结果除了与第5.2节分析的速度有关,还与追逃双方的初始位置有关,这一点在经过蒙特卡洛仿真后得到验证:针对图8–9所示地形,假设使用两种方法时追方胜利的次数与E的初始距离关系均服从正态分布且相互独立,均值为µ1=µ2=0而标准差σ1和σ2未知,随机选取1000组P1,P2和E的初始位置,进行蒙特卡洛仿真后得到方法1与方法2的标准差关系为σ1=1.38σ2,即在不同初始位置时,使用方法1的追方胜率更高.

从第5.1节和第5.2节的仿真结果可以看出,追逃双方处于零和博弈状态,那么该问题的鞍点解必存在.根据博弈的显示原理和贝叶斯均衡,非完全信息下需要通过博弈机制的设计使代理人如实暴露自己的类型,从而计算策略表达式并得到一阶鞍点解.根据第2.2 节的分析,实际情况下追逃双方处于战斗对立阵营,彼此不会知悉作战策略,即对手的支付函数(或代价)无法假设.因此,即使鞍点解存在,本文所述的追逃博弈仍然较难找到这种均衡.

可以预见的是,复杂非凸环境中的追逃结果与多种影响因素有关,包括追逃双方的速度、初始位置以及障碍的形状与分布等,这是值得进一步深入研究和讨论的问题.

6 结论与未来工作

区别于传统追逃问题,本文的追逃地形是有界足够大的,并且包含多种障碍.针对逃方能够利用障碍进行躲避的特点,在最坏情况下设计了逃方策略.为了充分发挥追方空地协作的优势,利用LOS和BVP算法,根据逃方状态分析了3种情况下的追击策略:

1) 当逃方处于追方视野范围内,追方采用最优协作视野下的追逃算法;

2) 当逃方刚刚消失于追方视野范围时,结合狮–人问题,提出了追方的“协作堵截”策略,并计算了子目标点;

3) 当逃方完全消失于追方视野时,追方采用协作搜索策略.

由于追逃地形是非凸且足够大的,因此本文策略不保证追方一定能够胜利,但在文中假设的最坏情况下是最优的,追逃双方的胜利条件与多种影响因素有关,还需进一步分析.目前,利用前期搭建的UAV/UGV空地协作系统,已经完成了大量的室内室外实验,其中包括室内地面追逃实验(图10).

图10 室内环境中两台UGV之间的追逃实验Fig.10 Indoor pursuit-evasion experiment of two UGVs