基于博弈策略的双无人机冲突解脱方法

2023-01-12 00:30吴学礼董虎翼阚海龙

河北科技大学学报 2022年6期

吴学礼，董虎翼，阚海龙，甄然

(1.河北科技大学电气工程学院，河北石家庄 050018；2.河北省生产过程自动化工程技术研究中心，河北石家庄 050018)

冲突解脱方法分为离散型和连续型2种解脱方法[1]。离散型解脱方法将解脱过程按等时间或等距离划分，将整体航迹离散成多段航迹，多段最优达到整体最优，以智能算法为代表；连续型解脱方法可用速度障碍法、最优控制等方法计算出无威胁航线，通过调整航向、调整速度和调整高度3种解脱策略完成冲突解脱[2]。

离散化方法，如采用智能算法[3-8]进行路径规划，规划出的路径存在无人机机动次数较多的问题，且为全局规划算法，求解计算量大，不适合实时规划。连续型方法，如速度障碍法[9-12]，通过调整无人机的相对速度使其与保护区相切或相离，即可求解出相应的解脱速度，消除潜在威胁，其缺点在于面对多机冲突解脱时无法求出最优解。人工势场法[13-14]，障碍物周围为斥力场，目标地点周围为引力场，通过引力与斥力的相互作用使无人机沿无冲突的航迹飞行，但人工势场法会使无人机出现不符合转角约束或速度约束的解。也有诸多学者采用其他方法对解脱方法有新的见解。文献[15]提出了一种考虑风力预测不确定性影响的飞行器冲突探测与解脱方法，将风分量作为随机变量，最接近距离和冲突概率作为发生飞行冲突的指标，考虑了合作型和非合作型解脱的情况。文献[16]针对多机飞行冲突问题，提出了一种深度强化学习算法，建立了基于马尔可夫决策过程的多机飞行冲突问题模型，采用独立深度Q网络算法对模型进行求解。文献[17]将解脱时产生的额外飞行距离作为代价函数，针对该问题提出双层优化策略,以航向解脱策略为基础，先利用随机并行梯度下降法搜索初始解,再用序列二次规划求得最优解，最后采用蒙特卡洛法对算法进行可靠性评价。以上研究都是基于单机解脱的研究或没有考虑合作解脱。

为了节省空域资源，需要两无人机或是多无人机共同完成冲突解脱，多方参与涉及到各方的利益分配问题，基于博弈论的方法可使各方的利益达到最优。文献[18]将合作博弈概念用在冲突解脱过程中，利用最优化理论将联盟福利最优解作为博弈双方最优解脱策略，实现了支付代价最小前提下的实时冲突解脱。文献[19]提出了博弈中的效用函数，构建了合作博弈冲突解脱模型，提出以联盟福利最优解均衡各参与人效益，并仿真模拟了多架无人机冲突的情形，取得了较好效果。文献[20]为解决冲突解脱过程中个体支付成本不公平的问题，提出基于合作博弈“核仁解”概念的多机冲突解脱算法，再提出基于人工势场法-蚁群法的冲突解脱混合求解策略。文献[21]同样提出了基于“核仁解”的无人机协作冲突解脱算法，构建冲突解脱“分支”模型并设计额外支付成本矩阵,最后改进遗传算法进行仿真。

本文针对文献[9]依据速度障碍法建立了冲突探测模型，利用几何关系推导出单无人机解脱所需改变的速度或航向角的情况，利用无人机运动学方程建立冲突探测模型，得到最小距离的时间公式，将最小距离视为安全距离，由此反解出所改变的速度或航向角。与文献[9]相比，本方法省去了利用几何关系一一推导所需改变的速度或航向角值。关于冲突解脱方法的改进以博弈论中的鹰鸽博弈为模型，在双方信息不完全的情况下，采用贝叶斯博弈分析鹰鸽博弈模型，基于各种策略的收益列出双方期望效用函数，通过分析期望效用决定博弈双方采用何种解脱策略，而不是针对单机解脱的纯策略进行研究。

1 冲突模型建立

1.1 规定假设

为了便于分析与计算，对模型进行一些假设与规定，使问题简化：

1)规定两无人机在解脱初期时飞行状态均不发生改变，做匀速飞行。根据外推法可以推测出何时、何位置发生飞行冲突；

2)为便于分析，使无人机都处于同一高度飞行，将三维问题降维压缩到二维平面；

图1 无人机安全区域示意图 Fig.1 Schematic diagram of UAV safety area

3)依据国际民航组织(ICAO)和空域安全专家组(SASP)的相关规定，基于雷达服务下的最小安全间隔为5 nmile(约9.26 km)；

4)无人机的保护区域可以确定为以无人机质心为中心的圆柱，在二维平面下忽略高度，安全区域为以无人机质心为中心，半径R=5 nmile的圆，如图1所示。

1.2 冲突模型

假设本机与入侵机的初始位置分别为A(X1,Y1)、B(X2,Y2)；速度分别为V1，V2；航向角分别为α，β。由此可以列出本机与入侵机关于时间的运动方程：

本机：

(1)

入侵机：

(2)

由式(1)和式(2)可以得到本机与入侵机关于时间的距离函数D(t)：

(3)

为计算方便，将式(3)平方后展开，展开后为关于时间t的一元二次函数，配方后得到式(4)：

(4)

当

(5)

D2(t)有最小值：

(6)

(7)

在飞行初期依据此公式可以判断何时发生飞行冲突，当两无人机的距离D

(8)

依据此公式也可判断无人机何时完成冲突解脱，当执行解脱策略后，将该时刻的位置作为初始位置，当Dmin=R时冲突解脱结束。最小距离与两无人机的速度V1，V2，航向角α，β有关。当执行其中一种解脱策略时，必定有相应的速度值或航向角值使Dmin=R，通过相应的解脱策略改变至对应的速度或航向角，那么在经过时间t后，会出现两机距离Dmin=R，进而实现冲突解脱。

求解速度值或航向角值的方法公式比较繁琐，尤其是求解航向角时涉及三角函数，所以直接求解较为麻烦。用麻雀搜索算法来计算速度或航向角的变化值，设置算法的目标函数F为两无人机的距离公式D：

D=(X1+V1cosα·t-X2-V2cosβ·t)2+(Y1+V1sinα·t-Y2-V2sinβ·t)2。

(9)

首先算法初始化输入大量随机的速度值或航向角值，然后由式(5)计算出两无人机达到最小距离的时间，再代入距离函数中求得目标函数值F：

(10)

当两无人机相对距离D

2 双机解脱方法

2.1 鹰鸽博弈

鹰鸽博弈是博弈论模型中的一种，用来描述大自然中鹰和鸽子的生存与进化。鹰作为一种天性凶猛的物种，鸽子作为一种天性温顺的物种。当鹰与鹰发现食物时会相互竞争，会出现你死我活争抢的场景；当鸽子与鸽子发现食物时会相互分享，会出现谋求和平的场景；当鹰与鸽子相遇时会出现鸽子逃走、鹰占据食物的场景。

表1 鹰鸽博弈收益矩阵Tab.1 Income matrix of eagle pigeon game

针对上述现象，基于博弈论的知识将上述现象的收益进行整理与分类。假设得到的收益为v，鸽子与鸽子之间相互分享，各自收益为v/2；鹰与鹰之间相互竞争会平分利益，但竞争也会带来c/2的损失，所以各自的收益为(v-c)/2；鸽子与鹰的相遇使得鹰的收益为v,鸽子收益为0。表1为收益矩阵。

鹰鸽博弈模型存在纯策略均衡与混合策略均衡。纯策略为完全偏向一种策略，即100%的选择其中一种策略；混合策略则是参与人以某种概率随机选择不同策略，由于混合策略伴随的是支付的不确定性，因此参与人关心的是其期望收益。

2.2 基于鹰鸽策略的贝叶斯纳什均衡

在博弈过程中己方只知道自己采取的策略，对于对手采取的策略不得而知，在对方信息不完全的情况下，利用静态贝叶斯博弈来分析博弈参与者的期望收益。令G为贝叶斯博弈：

G={N,{Ai}{Θi}{ui},p}，

(11)

式中：N是玩家集；{Ai}是策略集，表示博弈双方可采取每种策略组成的集合；{Θi}是状态集，表示每一方所拥有的“私有信息”；{ui}表示效用；p为状态集下的联合分布率。

鹰鸽策略下的贝叶斯博弈，其中N={N1,N2}；A={A1={鹰，鸽}；A2={鹰，鸽}}；Θ={Θ1={A1=鹰，A2=鹰，鸽；A1=鸽，A2=鹰，鸽}；Θ2={A2=鹰，A1=鹰，鸽；A2=鸽，A1=鹰，鸽}}。

依据贝叶斯纳什均衡的概念，在不完全信息静态博弈中，博弈双方行动同时发生，没有哪一方能够有机会观察其他方的选择。在给定其他博弈方的策略条件下，每个博弈方的最优策略依赖于自己的类型。如果每个博弈方不知道其他博弈方实际选择什么策略，但是，只要知道其他博弈方有关类型的概率分布，就能够正确地预测其他博弈方的选择与其各自的有关类型之间的关系。因此，该博弈方选择的依据就是在给定自己的类型，以及其他博弈方的类型与策略选择之间关系的条件下，使得自己的期望收益最大化。

计算期望收益使用的是期望效应函数。该理论阐述的是随机变量X所属集合X={Xi,i∈N+}，其随机变量的概率分布为

P(X=Xi)=Pi,i=1,2,…,n。

(12)

确定的选择Xi的效用为u(Xi)，那么该随机变量的效用表示为

(13)

式中：E[u(X)]为离散型随机变量X的期望效用；U(X)为期望效用函数。

在鹰鸽博弈中，博弈双方都会采取鹰策略或是鸽策略其中一种,但一方无法完全确认是哪一种策略。假设在鹰鸽博弈模型中，博弈方1选择鹰的概率为p，选择鸽子的概率为(1-p)；博弈方2选择鹰的概率为q，选择鸽子的概率为(1-q)。

根据表1的收益矩阵可以列出博弈双方的期望效用函数：

(14)

为了求出基于鹰鸽策略的贝叶斯纳什均衡解，令博弈双方的期望效用函数的偏导数为0，得到：

(15)

解得

(16)

对于博弈1方来说的最优条件是博弈2方以v/c的概率选择鹰策略，以(1-v/c)的概率选择鸽策略；同理，对于博弈方2来说最优条件是博弈方1以v/c的概率选择鹰策略，以(1-v/c)的概率选择鸽策略。

此博弈的混合策略纳什均衡解为

(17)

由于鹰鸽博弈归根结底是因为竞争来获取收益，所以获得收益要小于竞争带来的损失，因此v

2.3 鹰鸽博弈在解脱策略中的应用

表2 解脱策略收益矩阵Tab.2 Income matrix of relief strategy

将此模型应用到冲突解脱策略中，将调速策略和航向策略表示为模型中的鹰和鸽子。由于调速策略操作方便，没有多余路程的消耗，收益较大，因此将鹰比作调速策略；航向策略需要改变航向，产生额外的飞行路程，将鸽子比作航向策略。将对应策略替换为鹰鸽博弈收益矩阵中的各项，详细数据见表2。

1/3作为该模型的纳什均衡解，将概率区间[0，1]改为3个正整数(0，1，2)，从3个数中随机选取1个数，当取值为0时表示概率值的取值在[0，1/3)；取值为1时表示概率值为1/3；取值为2时表示概率值的区间为(1/3，1]。该值表示本机选择调速策略的概率，如果小于1/3本机选择航向解脱策略，反之选择速度解脱策略。

依据解脱策略收益矩阵计算博弈双方的期望效用可以得到：

1) 当本机选择调速策略的概率小于p*，即p<1/3，入侵机选择的最优解脱策略为调速策略；

2) 当本机选择调速策略的概率大于p*，即p>1/3，入侵机选择的最优解脱策略为航向策略；

3) 当本机选择调速策略的概率等于p*，即p=1/3，入侵机选择二者之一无任何差异。

3 航迹恢复

冲突解脱策略完成后，为节省无人机燃料的消耗、减少航迹的偏离，需要解脱完成后执行恢复策略。执行完调速策略后，各无人机分别将速度恢复至初始速度大小；执行完航向策略后，各无人机分别改变航向角至初始航线，之后继续朝向目标点飞行。在初步仿真完成后发现，如若立即执行航迹恢复策略会出现两机距离仍在减小的情况，因此对2种解脱策略出现该情况进行了分析与解决。

3.1 调速策略恢复

将无人机视为质点，通过式(5)求出的达到安全距离的时间是第1次本机与入侵机安全距离为相切状态的时间。虽为相切状态，但此时恢复速度距离仍会减小，因此两无人机仍需继续按当前速度飞行一段距离，这一段距离是由无人机的初始速度V计算而得。

图2 调速策略恢复示意图 Fig.2 Schematic diagram of speed regulation strategy recovery

假设本机、入侵机改变速度后，当两机距离为R时的位置记为A(x1,y1)、B(x2,y2)，速度为V1′，V2′，两机从A，B点按原速度V1，V2飞行，由式(5)计算出两机距离为安全距离R的时间t1，经过时间t1后两无人机的位置记为A′(x1′,y1′)和B′(x2′,y2′)，此时两机为初始速度下的相切状态，如图2所示。

以本机为例，本机仍需飞行的距离|AA′|，计算方法如下：

(18)

当无人机继续飞行此段距离或在此之后恢复至初始速度，不会出现距离逐渐减小的情况。

3.2 航向策略恢复

图3 航向策略恢复示意图 Fig.3 Schematic diagram of heading strategy recovery

式(5)求出达到安全距离的时间是第1次两机为相切状态的时间，因此需要按当前航向继续飞行一段距离。用相对速度法的思想进行分析，设VR为两机的相对速度，VR=V2-V1，执行航向策略后视入侵机为静止，新的航向角为α，本机向入侵机的方向飞行，当本机与入侵机的安全范围(圆心记为O)为相切状态时(切点记为P)，此时两机距离为R，两机继续沿当前航向飞行，当本机的位置在圆外一点(记为A″)且从该点引的2条切线其中一条为第1次本机与入侵机安全范围为相切状态时的切线，由切线长定理可知，2条切线长度相等(第2条切线与远航路交于A′)且2个切点(另一个切点记为P′)关于A″O对称，如图3所示。

则本机仍需飞行的距离记为|PA″|，计算方法如下：

|PA″|=R·tanα，

(19)

式中α为相对速度下的航向角，因此在计算飞行该段距离的时间时也应使用相对速度VR计算。

针对上述2种恢复策略，双机解脱时2架无人机都需执行对应的恢复策略，然而2种恢复策略下的飞行距离不同导致恢复时间不同，2种方法计算的位置均为2架无人机之间为安全距离的位置，在此位置或之后恢复航迹均不会出现距离减小的情况，计算出采取恢复策略的时间后，以恢复策略时间长的时间为基准。

4 算例分析

仿真运行环境为MATLAB R2016b。仿真选用的无人机类型是由中国研制的高空高速长航时察打一体的无人机WJ-700“猎鹰”，该无人机航时可达20 h，航程超过10 000 km，最大速度可达700 km/h(194 m/s)，飞行高度可在12 000 m以上。

图4所示为冲突场景的3种类型。其中交叉冲突因为航路交叉角的情况分为2种类型。

图4 飞行冲突类型Fig.4 Flight conflict types

表3 两无人机初始状态Tab.3 Initial states of two UAVs

为了验证本文方法的有效性，将上述3种冲突场景进行仿真模拟。表3给出了各个场景下2架无人机的起始位置、速度及航向角。设置无人机飞行高度在10 000 m，飞行空域范围为100 km×100 km，无人机安全区域半径R=9.26 km，执行解脱策略的位置为2倍的安全区域半径，速度变化范围V∈[0.5V，194 m/s]，航向角变化范围Δθ∈[-π/2，π/2]。

以下3种冲突场景，每一种场景都会试验2.3节中结论的1种。

场景1为两机对向冲突的场景(见图5—图7)。该场景下不会出现两机都执行调速策略的情况，2架无人机均执行航向解脱策略。本机的航向角变化为22°—-8°—52°—22°，入侵机航向角变化为158°—167°—150°—158°。2架无人机航向角的变化均在约束范围内。

图5 冲突解脱过程示意图(场景1)Fig.5 Process of conflict resolution (scene 1)

图6 解脱前后距离变化(场景1)Fig.6 Distance change before and after conflict resolution (scene 1)

图7 航向角变化(场景1)Fig.7 Change of heading angle (scene 1)

场景2为两机交叉冲突的场景(见图8—图10)。本机与入侵机的初始航向角分别为22°和59°，可以计算出此时2条初始航路的斜率分别为0.40和-1.67，由此得出2条航路的一次函数，由2个函数的交点计算出航路交叉点为(50,50) km。根据两机的起始点与航路交叉点，使用向量法求夹角的方法可以求出航路交叉角。求得航路交叉角为80.84°，此时交叉冲突为锐角。

图8 冲突解脱过程示意图(场景2)Fig.8 Process of conflict resolution (scene 2)

图9 解脱前后距离变化(场景2)Fig.9 Distance change before and after conflict resolution (scene 2)

图10 速度与航向角变化(场景2)Fig.10 Change of speed and heading angle (scene 2)

经过双方博弈后，本机选择航向解脱策略，入侵机选择调速策略。本机航向角变化为22°—13°—31°—22°，入侵机速度由100 m/s变为57 m/s。2架无人机航向角及速度的变化均在约束范围内。

场景3同样为两机交叉冲突场景(见图11—图13)。用上段提出的方法可以求出该航路交叉角为103.20°，此时交叉冲突为钝角。双方博弈后本机选择速度解脱策略，入侵机选择航向策略。本机速度由90 m/s变为144 m/s，入侵机航向角变化为129°—98°—158°。2架无人机航向角及速度的变化均在约束范围内。