飞行冲突网络演化博弈中牵制机制的研究

蒋旭瑞，吴明功，温祥西，涂从良

（空军工程大学空管领航学院，西安 710051）

0 引言

随着我国航空运输业的高速发展，有限的空域资源越来越难以满足人们日益增长的飞行需求。当前，空中交通流量持续增加，无人机集群广泛应用，探索出一种高效的飞行器自组织解脱方法尤为重要。博弈论作为解决冲突、优化资源配置的经典数学模型，在飞行器冲突解脱领域引起了人们的广泛关注。朱衍波等人开创性地使用合作式博弈论分析了双机飞行器冲突解脱合作方式与解脱代价[1]，Hill和Archibald等人使用满意博弈论来分析飞行器冲突的状态可达性[2]，杜文博等人首次将飞行器冲突解脱问题抽象为网络演化博弈动力学模型，系统地研究了网络结构、学习策略、博弈模型等因素对解脱效果的影响[3]，为网络演化博弈解决飞行器集群冲突做了大量基础性工作。他们的研究中，将飞行器视为节点，有探测关系的飞行器之间构建连边，建立起飞行器冲突的无向网络。但飞行器冲突解脱网络不同于一般复杂网络中相邻节点间相互影响，飞行器探测半径的异质化使飞行器不一定互为邻居，若按照无向网络来构建冲突解脱模型不能真实地反映网络结构，在演化博弈中忽视了博弈收益对策略影响的单向传递特性。因此，这里构建了飞行器冲突场景的有向网络模型：飞行器间的探测是单向的，只有一个节点能够探测到另一个节点，才存在单向连边。

此外，人们发现在演化博弈的规则下，当背叛诱惑值较大时，合作效果不理想。为了解决这一问题，杜文博等人采用牵制机制来提高合作频率，即在初始化时有选择地挑出部分“关键”节点赋予合作策略。主要包括两种方式：随即牵制机制和特定牵制机制。随机牵制机制（randomly pinning scheme）[4]，是在初始化时随机选择若干节点赋予合作策略达到提高合作频率的目的。这种方法挑选节点盲目，缺乏针对性，需要选择相当数量的节点才能达到提高合作频率的目的。特定牵制机制（specifically pinning scheme）[5]，在无向网络中选择度大的节点施加牵制。这种方法考虑了节点度大的节点邻居数目多，获得收益和较大，这些Hub节点抵御背叛侵蚀的能力强，将合作频率维持在较高水平，但没有从传播合作策略的动态角度考虑。这两种方法丢失了部分重要邻居的信息，提升合作频率的程度有限。

基于以上分析，结合有向网络的特点，提出了两种牵制机制：基于总度的牵制机制和基于聚类系数的牵制机制。基于总度的牵制机制是在构建的有向网络中，选择总度大的节点赋予合作策略，从合作策略的维持与传播两个方面提高网络合作频率；基于聚类系数的牵制机制选择有向网络聚类系数大的节点赋予合作策略，使合作者聚集成簇出现。希望通过以上方法，提高网络合作频率，防止背叛策略的Hub节点使邻居节点纷纷陷入背叛，避免大规模飞行冲突的发生。

1 模型的建立与分析

1.1 飞行器冲突的有向网络构建

在飞行器分布比较均匀的网络中，网络结构主要由探测半径的异质化程度决定。当空域中飞行器探测半径相同时，可以把飞行器的冲突场景构建为无向网络。但是，当探测半径异质化程度较高时，飞行器之间探测获得的信息不对等，将飞行器冲突场景构建为无向网络已不再适用。把飞行器视为节点，有从飞行器出发指向被探测飞行器的单向连边，形成有向网络。由于仅仅研究有向网络的静态特征，并不涉及求解最小生成树等问题，将双向的连边简化为两条相反方向的有向边，形成环边。

图1 局部飞行器冲突解脱中构成的有向网络

如图1所示，飞行器A、B、C、D被视为节点，因探测能力有限网络不是全连通的，仅有存在探测关系的飞行器之间存在单向连边。飞行器A探测能力较强，B和C均在其探测范围内，有从A出发指向B和C的连边。而B和C探测能力有限，未发现空域中飞行器A，故不存在从B和C到A的连边，B、C和A之间单向连通。其探测关系的邻接矩阵可以简单表示为：

该邻接矩阵是非对称的，意味着探测关系也是非对称的。所有能探测到i的飞行器都属于i的入邻集，在i探测范围内的飞行器属于i的出邻集。

1.2 网络演化博弈模型在飞行冲突中的建模

在实际飞行中，当飞行员在短时间内预测到冲突可能发生时，是否进行避让操作的策略选择与囚徒困境博弈模型有很大的相似之处：

两架飞行器A和B都探测到短时间内可能发生飞行冲突，飞行员可以选择是否进行避让操作（合作C或背叛D）。当飞行器A选择避让（合作），而飞行器B保持原航向飞行（背叛），B在未付出任何代价的前提下安全通过，获得最大收益T；而A因做出机动动作，不仅付出时间和油耗成本，安全性也大大降低，获得最小收益S。当飞行器A、B均选择避让时，各自只需机动较小角度，付出相当的较小机动成本，均获得收益R；如果两飞行器均选择不进行避让操作，A和B虽然不需要支出额外成本，但在很大程度上可能造成飞行冲突或危险接近，均获得较小收益P。以上的收益满足条件：T＞R＞P＞S且2R＞T+S。可以看出，双方均选择进行避让操作，对飞行安全而言是最优的。其收益矩阵可表示为：

这是建立在双机冲突基础上的经典囚徒困境博弈模型，无法在实际网络中动态演化，合作现象也很不稳定。Nowak和May在经典的囚徒困境博弈模型的基础上进行了探索研究，提出了空间博弈，使得囚徒困境博弈能够在网络上实现，并根据规则自行演化。在飞行器冲突场景中，演化博弈建模中主要有以下几个步骤：

1）飞行器冲突构建的有向网络中，每一个节点代表一个决策者。初始化时，将合作C（或背叛D）策略随机地赋予每一个决策者，简化参数T=b，R=1，P=S=0。其收益矩阵可以表示为：

2）一轮演化开始，每一个决策者与探测范围内的飞行器进行一次博弈，分别获得经典囚徒困境模型中相应的收益，将自身收益进行求和。

3）在下一轮博弈开始前，每一个决策者将获得的收益之和与探测范围内的其他节点收益和相比较，选择收益最高的邻居，学习它的策略进行更迭。迭代M次或直到所有的决策者都选择一种策略为止。

2 基于总度的牵制机制与基于聚类系数的牵制机制

在网络演化博弈的规则下，当背叛诱惑值T大于1时，因背叛节点获得的收益往往高于合作节点，使入邻节点纷纷倒向背叛。而且，与在规则网格中博弈不同的是，当空域中探测能力强的飞行器在初始化时被赋予背叛策略，因其出邻节点多获得收益高，背叛策略在飞行全过程都很难改变，这在实际飞行中是非常危险的。为了改善这种状况，抵御背叛诱惑值T增大合作频率迅速下降，需要引入牵制机制，即在初始化时有选择地挑出部分“关键”节点赋予合作策略，使合作频率维持在较高水平。那么，什么样的节点才算是关键节点，关键节点的评价标准是什么？

评价牵制效果好坏的标准是控制较少的节点使合作频率维持在较高水平，这就要使选择的节点更具有针对性。主要从两个角度出发：第一，初始化时赋予合作策略的节点在演化博弈过程中，能较稳定地维持自身策略；第二，这些受牵制的节点能够在演化博弈过程中，将合作策略稳定地传播出去。在此基础上，提出了两种牵制机制：

1）基于总度的牵制机制：选取出度与入度之和大的节点施加牵制控制。

基于总度的牵制机制选择的总度大的节点不仅出邻节点多，节点累积收益高，抵御背叛侵蚀能力强，而且入邻节点多，中心节点博弈收益普遍高于入邻节点的收益，入邻节点确定性地学习牵制节点的合作策略，有更大概率将自身合作的策略传播给周围的邻居，使合作频率维持在更高水平，这是特定牵制机制不具备的。这里，飞行器i的节点（总）度d（v）等于入度d+（v）与出度d-（v）之和，即：

其中，飞行器i探测范围内的飞行器属于i的出邻集，其数目等于i的出度d-（v）。

2）基于聚类系数的牵制机制：选取有向网络中聚类系数大的节点施加牵制控制。

聚类系数是定量描述网络中个体邻居的邻居也是个体邻居可能性的指标，反映了网络的聚集程度。从合作策略的维持与传播两个方面考虑，基于聚类系数的牵制机制将网络中聚集程度高的中心节点施加牵制控制，使合作者聚集成簇出现，提高了网络合作频率。给定有向网络的邻接矩阵，则对于网络任意节点i，其出度、入度及总度可表示为：

其中，（A）i为矩阵A的第i行元素所组成的行向量，为 N 维列向量（1，1，…，1）T，表示节点i与邻居形成的双向边的数目。则有向网络中节点i的聚类系数为：

3 仿真分析

为了验证本文所提牵制效果的有效性，在matlab环境中模拟150×150空域中均匀分布的1 000个飞行器，比较4种不同牵制对于合作频率fc的影响（为采取合作策略的个体数目，Nd为采取背叛策略的个体数目）。其中，飞行器i的探测半径服从的幂律分布，平均探测半径＜r＞=6，χ为满足均匀分布的随机整数，取n=5。

初始化时飞行器随机选择一种策略合作C或背叛D，根据Richest Following策略规则（选择收益最高的邻居进行确定性学习）演化博弈2 000代观察网络合作频率。虽然这种学习策略比较简单，且考虑噪声因素不足，但体现了向高收益策略学习的思想，是不断达到最优的过程。

实验中，随机牵制机制中选择了50个节点作为牵制对象，另3种特定牵制机制各选择了10个节点作为牵制对象，赋予合作和背叛策略分别进行正、反牵制对比。为了充分显示合作频率变化趋势，将背叛收益T的取值从1～2扩大到0.3～2.3，得到的仿真结果如图2所示。

图2 仿真结果

从仿真结果可以看出，无论采取哪一种牵制手段，在背叛收益T＞1时，大量选择合作策略的节点收益小于背叛策略获得的收益，这部分节点纷纷倒向背叛，合作频率fc从0.9附近较高水平迅速下降；在T＞2时，因背叛诱惑巨大决策者纷纷倒向背叛，fc迅速下降趋于0.1左右，这主要是因为节点分布较均匀，探测半径异质化程度有限，随着背叛诱惑T值增大，背叛节点收益普遍高于合作节点，使邻居节点纷纷倒向背叛，与预期理论分析的结果是一致的。图2（a）中将4种方法挑选出的节点赋予合作策略，可以看出基于总度的牵制机制和基于聚类系数的牵制机制效果较好，在背叛诱惑T在1～2间取值时将合作频率维持在更高水平，特定牵制机制其次，随机牵制机制最次。图2（b）中将选择的节点赋予背叛的策略，基于聚类系数和总度的牵制控制在T＞1时，合作频率被控制在0.2附近，效果突出，且各方法牵制效果与（a）中所得出结论一致。另外，对比（a）（b）中随机牵制机制可以发现，在正向牵制与反向牵制中，合作频率fc变化趋势一致，合作频率没有因选择正向牵制明显提高，也没有因反向牵制迅速下降，说明随机牵制机制即使牵制节点数量是特定牵制机制的5倍，但由于选择节点不够重要，在初始化后的演化中被迅速侵蚀，牵制效果最次。

为了量化比较4种牵制效果，在固定背叛诱惑T取值的条件下，观察4种牵制机制在不同受控节点下的合作频率变化趋势。因T＜1时合作频率维持在较高水平，而T＞2时大部分节点都因背叛诱惑过大而选择背叛，对研究没有太大的参考价值，因而把T的取值控制在（1，2）的区间内。这里，分别取T=1.15和1.5，P代表牵制机制，N代表受控节点数目，结果如下页表1、表2所示。

从表1与表2的对比中可以看出，对于同一种牵制方式，合作频率在T=1.15时高于T=1.5时，这是因为背叛诱惑越大，在演化博弈中更多的节点倾向于选择收益大的背叛策略，使大部分节点都倒向背叛。即使在T=1.5时控制90个节点，也不能使合作频率维持在T=1.15时控制10个节点的水平，可以看出牵制机制只是在演化博弈中提高合作频率，避免背叛节点使邻居大规模陷入背叛的牵制手段，并不能起主导作用，应用到飞行器集群的冲突解脱中并不能保证绝对的安全；从4种牵制机制效果的比较中，可以看出无论T=1.15还是T=1.5，在控制相同节点的情况下，基于总度的牵制机制与基于聚类系数的牵制机制效果最好，特定牵制机制效果其次，随机牵制效果最次。

表1 背叛诱惑T=1.15时合作频率随受控节点的变化

表2 背叛诱惑T=1.5时合作频率随受控节点的变化

4 结论

本文研究了网络演化博弈动力学在飞行器冲突解脱领域的应用，将飞行器冲突场景构建为有向网络，提出了基于总度的牵制机制和基于聚类系数的牵制机制，与在原无向网络基础上使用的随机牵制机制和特定牵制机制比较，提出的两种方法分别从合作策略的传播和合作节点聚集两个方面为突破口，使网络合作频率维持在较高水平。此外，模型运用到实际飞行冲突解脱中时，选择重要节点的依据除了度和聚类系数以外，还可以引入节点权重等其他指标，使网络更加符合实际。