基于核仁解的低空无人机协作冲突解脱算法*

钱晓鹏 张洪海 田 宇 王立超

(南京航空航天大学民航学院 南京 210016)

0 引 言

为应对无人机民用空域混合运行需要，当前国内外有不少学者对无人机交通管理系统(UTM)的构建展开研究.NASA开发了无人机交通管理系统快速仿真平台.作为无人机交通管理系统的核心技术，冲突探测与解脱算法是无人机在空域内安全运行的保障，也是无人机走出隔离区、进入国家当前空域系统与其他航空器融合运行的必要前提.

当前国内外对无人机冲突解脱技术有一定研究基础.Klaus等[1]为了满足小型无人机尺寸、重量、能源等限制因素，提出了一种适用于小型无人机(sUAS)的冲突 “感知与避让”技术.Castillo等[2]针对不断增长的无人机运行需求，在自由飞概念下提出了两种基于agent合作的分布式冲突解脱算法：IPPCA算法以及MPCA算法.Schmitt等[3]提出了基于导航的三维冲突避让算法，使用部分离散的方法减少计算复杂性，使方法更加贴近实际应用.Alonso等[4]将集中冲突解脱转化为混合整数线性规划问题，在满足所有冲突解脱限制条件的基础上，以调速或者调航向总和最小为目标求解，实现了冲突解脱过程的系统最优.周建等[5]将多Agent技术与启发式算法结合，研究了基于分布式MAS框架的飞行冲突探测与解脱方法.王渊等[6]针对同一空域内多无人机飞行冲突解脱问题，提出了一种基于改进人工蜂群算法的冲突解脱策略.

目前研究大多以实现无人机冲突的有效解脱以及系统的整体效率较优为目标，并没有考虑无人机实际运行过程中解脱的公平性、优先级合理性问题，不够符合实际需求.在低空环境下，无人机具有各自的任务特点，实际飞行冲突解脱过程中必然要将解脱是否符合优先级关系以及解脱方案对每架无人机的公平性等因素考虑在内.为此，本文基于智能体(Agent)技术，将博弈论“核仁解”概念引入到冲突解脱协商机制中，研究考虑无人机冲突解脱公平性、优先级等因素的冲突解脱方法.

1 低空冲突解脱智能协作机制

假设空域内无人机均为智能体，所有无人机均能通过ADS-B获取本机及周边无人机状态数据且能与上级Agent进行通信，见图1.低空无人机系统是分布式人工智能系统(DAI)，无人机与其他无人机发生冲突进行解脱是一种动态协作任务求解问题.提出协作流程如下.

步骤1所有具有关联冲突的飞行器形成一个冲突团体.

步骤2冲突团体内飞行器将各自状态、属性数据上传至上级Agent.

步骤3上级Agent依据协商策略形成冲突解脱方案.

步骤4方案下发至各飞行器并执行.

图1 低空无人机冲突解脱智能协作示意

2 冲突解脱“分支”模型

当无人机遇到冲突，通常会采取一系列机动动作将冲突化解.本文采用确定性采样方法建立冲突解脱“分支”模型规划无人机冲突解脱轨迹.无人机冲突解脱过程被分支为固定采样周期t的M步，其每一步有N种机动策略选择.冲突解脱基本模型见图2.

图2 冲突解脱“分支”模型

模型中，对于无人机i，其初始状态记为X0=[P0,θ0,v0].其中：P0=(x0,y0)，为无人机初始坐标位置；θ0为无人机初始航向角；v0为初始速度.第m步的控制量为Um=[θm,vm]，θm，vm分别为无人机第m步的航向角和速度控制量.无人机经过m步机动后位置Pm=(xm,ym)为

(1)

受无人机转弯率及飞行速度、加速度约束为

(2)

式中：ωmax，αmax，vmin，vmax分别为无人机最大转弯率、最大加速度、最小飞行速度，以及最大飞行速度.

3 基于“核仁解”的冲突协商求解策略

对于MAS动态协作任务求解，协商策略是保证协作能够顺利实现的关键.对于多无人机飞行冲突解脱问题，各无人机均具有利己性，偏向于进行对自己更加有利的机动动作，解脱方案应均衡各无人机解脱代价.对此本文引入合作博弈思想，提出基于“核仁解”的冲突协商求解策略[7].

对无人机冲突解脱过程中“核仁解”作出如下定义.

对于无人机利益分配(成本分摊)联盟博弈(A,v)，A={a1,a2,…,aP}是参与者集合，v是价值函数，S为可行解脱方案集合，S={s1,s2…,sK}，解脱方案sk中任意无人机ai都有对应解脱成本v(sk,ai)，对sk中所有无人机解脱成本v(sk,ai)进行排列，按照从大到小顺序记为ε(sk).

合作博弈的核仁即

N(sk)={x∈S|ε(x)≤ε(y),∀y∈S} (3)

基于“核仁解”的冲突解脱方案具备以下优点[8].

1) 解脱方案具备群体合理性与个体合理性.

2) 冲突解脱合作博弈解脱方案具有唯一“核仁解”.

3) 解脱“核仁解”中处于对称地位的参与者解脱代价相近.

3.1 无人机解脱联盟额外支付成本矩阵

对于一个由P架无人机组成的冲突解脱联盟，若存在K个组合解脱策略，则有如下额外支付成本矩阵V.

(4)

式(4)成本矩阵为K行P列矩阵，矩阵中的第k行给出了第k个解脱策略中P架无人机各自的额外支付成本.

解脱联盟最大额外支付成本矩阵为

(5)

式中：v*(sk)=maxv(sk,ai),i=1,2,…P为第k个解脱策略中P架无人机成员所付出额外支付成本的最大值.为获得次大额外支付成本矩阵，核仁解解脱方案集形成潜在解额外支付成本矩阵V潜，矩阵V潜每一行均已剔除最大不满，潜在解脱方案s核k剔除最大不满无人机后的参与者集合A核k为

(6)

(7)

次大潜在解额外支付成本矩阵为

(8)

依次往复，得到从大到小的所有额外支付成本矩阵.

合作博弈的核仁即

∀y∈S}

(9)

式中：vi(sk)为解脱方案k的第i大不满；ki为第i大不满的权重系数；I为解脱团体中无人机数量.

无人机低空飞行冲突解脱过程中，解脱额外支付成本由三部分组成：机动成本vm、位置偏差成本vp,以及航向偏差成本vh.机动成本与每一步机动类型、机动程度相关；位置偏差成本与机动解脱完毕后无人机现位置与原目标位置偏差相关；与机动解脱完毕后无人机现航向与原目标航向偏差相关.

解脱方案sk中无人机i机动成本为

(10)

v(sk,ai,m)=δ1|Δv|+δ2|Δθ|+δ3|Δh|,

δ1+δ2+δ3=1

(11)

式中：δ1，δ2，δ3为0-1参量；Δv,Δθ,Δh分别为速度、航向、高度机动量.

解脱方案sk中无人机i位置偏差成本为

(12)

解脱方案sk中无人机i航向偏差成本为

(13)

解脱方案sk中无人机i在冲突解脱过程中付出的总额外支付成本为

v(sk,ai)=ω(φ·vm(sk,ai)+

φ·vp(sk,ai)+γ·vh(sk,ai))

(14)

式中：φ,φ,γ为各类型成本代价对应权重；ω为优先级增益系数.

3.2 无人机优先级

对于有高优先级无人机的冲突解脱博弈联盟(A,v)，设无人机i#拥有更高优先级(如抢险救灾)，则无人机i#支付成本v(sk,ai#)在优先级增益系数ω加成下，在任何解脱方案中都属于最大值，即

(15)

k=1,2,…,K

(16)

即核仁解必定在高优先级无人机i#所花费代价最小的解脱方案中产生，从而保证了i#意愿的优先满足，达到任务重要的无人机活动更加优先的目的.

3.3 最优解脱策略搜索算法

建立基于改进遗传算法的最优策略搜索算法(optimal strategy searcher based on improved genetic algorithm，OSBGA)，在所有可能的路径策略中寻找满足冲突解脱要求的最优路径方案.OSBGA对冲突解脱“分支”模型中的每一步的n种机动策略进行二进制编码，见图3.

图3 单步机动策略编码示意

路径方案总体二进制编码见表1.

表1 无人机冲突解脱路径方案编码示意

冲突解脱过程中各无人机之间需始终满足最小间隔标准要求，即在解脱过程中的任意时刻τ，任意两无人机之间满足：

∀i,j∈[1,P],i≠j有

遗传算法中某串基因编码是否能够得到继承取决于该基因编码适应度(fitness).在航空领域，除了无人机飞行安全以外，飞行的效率及管制策略对各运行主体的公平性愈加得到关注，本文设计适应度函数为

(18)

式中：vi(sk)为解脱方案k的第i大不满；ki为第i大不满的权重系数；I为解脱团体中无人机数量.根据Schmeidler，核仁解具有群体合理性以及个体间公平性，因此，通过对核仁解的寻找可以实现公平性以及高效性指标.同时，本文通过对ω的设定可以满足解脱优先级合理性要求.

4 实验及分析

为验证本文算法有效性，设置15 km×15 km的飞行仿真环境，分别对基于单策略调速和单策略调航向情景进行仿真验证.设计多种仿真情景见表2.

表2 低空无人机冲突仿真情景

情景1～3为调速解脱情景，双机90°交叉相遇，仿真过程中初始速度设置为1.5 km/min，调速解脱分为10步，无人机速度变化范围为±32%；情景4～6为调航向解脱情景，五架无人机起始位置均匀分布在半径为7.5 km的圆上，圆上正对位置为其各自终点，其解脱步数设置为5步，每步步长3 km，每步可选择航向变化量{0,±10°,±20°,±30°}，共计七种.

调速解脱3种情景仿真结果速度曲线见图4，各情景a)、b)无人机额外支付成本见图5，可以发现情景2加入“核仁解”优化后，双机不满程度的差异明显较情景1未加“核仁解”优化的要小，解脱更加公平.情景3中，ɑ机具有更高优先级，其额外支付成本远小于b机，符合现实优先级要求.同时可以发现，基于“核仁解”的解脱方案其总体额外支付成本略高于传统解脱，可以认为是为实现公平所不可避免需要付出的代价.

图5 调速解脱各机额外支付成本对比

在调航向解脱仿真实验中，结合实际飞行能耗水平将权重φ,φ,γ分别设定为2，20，1[9]，得到情景4传统调航向解脱与情景5基于“核仁解”调航向解脱的仿真结果见图6.两种情景都能实现冲突的有效化解，但其各机解脱所支付的额外成本有明显差异.表3为调航向解脱过程中各机额外支付成本.为清晰体现出各情景解脱公平性差异，本文绘制洛伦兹曲线对数据进行更直观呈现.洛伦兹曲线为经济领域评价公平性的常用方法，由美国统计学家洛伦兹提出.洛伦兹曲线通过曲线与公平基准线之间所夹面积的大小判断公平程度，若洛伦兹曲线与公平基准线重叠，则表明分配完全公平，相反所夹面积越大表明分配越不公平.

图6 传统和基于“核仁解”的调航向解脱

表3 五机调航向解脱各机额外支付成本

对情景4～5仿真结果中的各机额外支付成本分别绘制洛伦兹曲线，见图7.由图7可知，情景5洛伦兹曲线与公平基准线所夹面积仅为情景4的25%左右，远小于情景4.表明加入“核仁解”优化过后，调航向冲突解脱的公平性较传统方法显著提升.

图7 不同方法调航向解脱公平度对比

图8 最佳优先级增益系数分析

由图8中曲线变化规律可知，f(ω)随着优先级增益系数ω的增大而减小，当ω取值大于等于7后基本保持稳定；而解脱过程中的整体额外支付成本S随着优先级增益系数ω的增大呈不断上升趋势.因此，取优先级增益系数ω为7，使得解脱过程尽可能满足高优先级无人机利益，同时尽可能减少整体额外支付成本.

以典型情景6为例进行多次仿真实验，情景6为五机汇聚相遇，其中一架无人机相较其它四架具有更高优先级，使用本文基于核仁解调航向策略进行解脱.仿真过程中权重φ、φ、γ依旧设定为2，20，1，根据上述优先级增益系数分析结果，设定优先级增益系数ω为7.对多次仿真实验中各机额外支付成本绘制洛伦兹曲线，见图9.

图9 各机支付成本公平性对比

由图9可知，冲突解脱过程中具有更高优先级的无人机所支付额外成本明显低于其余四架无人机，平均额外支付成本约为低优先级航空器的15%，如累计无人机数“0-1”段中所示，表明本文算法能够有效优化降低高优先级无人机解脱额外支付成本，符合现实情况中低优先级无人机避让高优先级无人机的要求.同时，其余4机额外支付成本的洛伦兹曲线基本呈直线走势，表明其余同优先级无人机解脱过程中公平性较好.

5 结 束 语

本文构建无人机冲突解脱“分支模型”，并将“核仁解”引入到低空无人机冲突解脱过程中，提出了基于核仁解的低空无人机协作冲突解脱算法，实现了低空多无人机之间的冲突化解.通过绘制洛伦兹曲线，直观清晰的呈现的当前冲突解脱算法存在的解脱不公平问题.仿真比较发现，本文算法各无人机额外支付成本的洛伦兹曲线包络面积仅为传统算法的25%，能够有效提高无人机冲突解脱过程中的公平性.同时，由于“核仁解”本身具备群体合理性，冲突解脱在满足公平性要求的基础上能够尽可能逼近系统最优.其次，通过引入优先级增益系数ω，本文冲突解脱算法实现了对高优先级航空器的优先避让，使冲突解脱具备实际合理性.

由于当前航空器活动大多按固定高度层飞行，因此本文仅考虑了同一水平面无人机冲突解脱问题.当前低空“自由飞”概念广受关注，低空的“高度层”特征并不特别明显，后续研究将考虑加入无人机垂直方向上的冲突以及调高度的冲突解脱方式.