分布式MAS在飞行冲突解脱中的应用研究

周建，Ahmed RAHMANI，刘昕，王莉莉

（1.中国民航大学空中交通管理学院，天津300300;2.里尔中央理工学院自动化、信息技术工程和信号实验室，里尔59650，法国）

分布式MAS在飞行冲突解脱中的应用研究

周建*1，Ahmed RAHMANI2，刘昕1，王莉莉1

（1.中国民航大学空中交通管理学院，天津300300;2.里尔中央理工学院自动化、信息技术工程和信号实验室，里尔59650，法国）

在自由飞行的环境下，为解决飞行冲突探测与解脱（conflict detection and resolution，CDR）问题，提出一种基于高度层、航向和速度调配的综合解脱方法，并将多agent系统(multi-agent system,MAS)的分布式技术与启发式算法相结合，进行问题求解.首先设计了分布式MAS框架结构，然后建立了飞行冲突探测模型，高度层调配模型及航向、速度调配模型，最后，综合运用了基于合同网协议的分布式算法和自适应遗传算法进行问题求解.仿真实验表明，所设计的MAS框架是可行的，同时分布式算法和自适应遗传算法的综合应用能很快找到基于高度层、航向和速度分配的近似最优解，为CDR问题提供了新的解决思路.

航空运输；冲突解脱；合同网协议；多agent系统；空中交通管理

1 引言

飞行安全是空管工作的重点，对飞行冲突的探测与解脱方法的研究，一直是国内外学者和专家关注的热点.

国外对用MAS技术解决CDR问题已有研究，如Kuchar和Hojjat Emami等[1,2]对MAS技术在CDR问题的应用进行了综述，David Sislak等[3]提出了基于agent的机载CDR结构框架和相关算法；Miguel A Vilaplana等[4]描述了机载MAS模型框架并综合考虑了飞行成本问题[4]；Michael Heymann等[5]针对San Francisco机场的终端区建立了agent模型，并引入了动态资源优先使用机制；Magnus Ljungberg等[6]介绍了已付诸实践的OASIS系统的MAS框架及相关算法.以上学者提出了非集中式冲突解脱的理念，为CDR问题的研究提供了新的方法.国内方面，刘红红[7]等使用分布式MAS技术解决交通信号控制问题，石文先[8]使用MAS技术解决CDR问题，而大多数研究人员使用启发式算法解决CDR问题[9-13].

以上方法存在下述问题：

(1)偏重于MAS系统框架的宏观设计，对空中交通管理（以下简称空管）行业了解不深入，理论与实践结合不够紧密；

(2)仅从改变航向和速度两个方面提出优化策略，忽略了空管一线单位使用最频繁的高度层调配策略；

(3)在目前集中式管制指挥的环境下，算法最优解的实施会大大增加管制员的工作负荷，增大了安全隐患.

本文将研究改变传统集中式管制指挥模式，提出分布式MAS结构，将分布式人工智能与启发式算法相结合，从高度、航向和速度方面提出飞行冲突解脱综合策略.

2 分布式MAS结构

2.1 航空器agent结构

在分布式MAS框架中，每架航空器被视为一个agent，主要包括通信协调、CDR、飞行计划、知识数据库、性能数据库、环境数据库等模块，如图1所示.

图1 航空器agent结构图Fig.1 Structure of aircraft agent

航空器agent之间将使用通信协调模块，通过ADSB进行通信、协调和协作.CDR和飞行计划模块需要知识数据库、性能数据库和飞行环境数据库的支持，其中知识数据库中存储了相关数学模型和算法，性能数据库中存储了主流航空器的性能数据，而飞行环境数据库存储了航空气象、空域限制等信息.

2.2 飞行冲突探测模块

如图2所示，系统随机选择某航空器为协调agent，协调agent在接收到其他agent相关信息后，冲突探测模块对其他agent的飞行计划FPi和自身的飞行计划FP进行分析，并判断是否存在冲突.

2.3 飞行冲突解脱模块

(1)高度层调配模块.

如图3所示，协调agent与其它agent进行通信、协调并确定调配方案后，将N个agent划分为m个小组，每组有ni(i=1,2,…,m)个高度层相同的agent.再利用冲突探测模块进行冲突探测，如果没有探测到冲突，该agent就将新的飞行计划FP'i发送给其他的agent成员；如果探测到了冲突，则进入冲突解脱第2阶段.

图3 高度层分配Fig.3 Allocation of flight level

（2）航向和速度调配模块.

m个高度层小组中的任何一组冲突，都可以被简化为2维空间的冲突解脱问题，本文将使用改进后的遗传算法计算出最优解脱方案，然后协调agent将最新的飞行计划发送给其他的agent成员.

3 问题描述与建模

本文将航路上的飞行冲突探测和解脱分成两个阶段：高度层调配阶段，航向、速度调配阶段，并建立相应的模型.假设条件如下：

（1）自由飞行的背景下，航空器可自主选择飞行路径和高度层；

（2）航空器的航向变化简化为左转30o，右转30o和保持原航向三种，集合为{H-30o,H,H+30o}；

（3）航空器的速度变化简化为减速10%、加速10%和保持原速度三种，集合为{V⋅90%,V,V⋅110%}.

3.1 冲突探测模型

协调agent根据其它agent的相关信息，判断是否存在飞行冲突，冲突探测数学模型为

式中（xi,yi,zi）和（xj,yj,zj）分别为agentAi和Aj的坐标；Sh为最小水平间隔；Sv为最小垂直间隔.当同时满足式（1）和式（2）时，agentAi和Aj存在冲突.

3.2 高度层调配模型

航空公司的直接运营费用（direct operation cost，DOC）可简化为

式中Cfuel为燃油成本，元；Ctime为时间成本，元. Cfuel与Ctime的比值用成本指数CI表示.则航空器飞行单位距离所需成本[14]为

式中R为飞行距离，km；WF为燃油流量，kg/h；NE为发动机台数；VG为地速，km/h；M为马赫数；α为该飞行高度层音速，km/h.

在CI、航空器质量、温度偏差值一定时，根据式（4），使用迭代方法，可计算出航空器在不同高度层上的EC，然后选取最小EC所对应高度层即为最经济巡航高度层.

3.3 航向与速度调配模型

针对m个高度层小组的任一组航空器可建立飞行冲突解脱数学模型，目标函数为

式中nm为航空器总数；Lj为第j架航空器在冲突区内的总飞行距离.

目标函数的约束条件为

4 算法设计

4.1 高度层调配算法

本文使用基于合同网协议的高度层调配算法.合同网协议（contract net protocol,CNP）是用于解决分布式问题求解环境下各agent之间任务分配而进行的一种合约协作过程[15].其基本原理是采用市场“招标—投标—中标”机制进行任务通告、投标，最后签订合同来实现任务分配.

系统开始运行时，协调agent向所有成员agent发出高度层招标书，成员agent选择最优高度层进行投标，协调agent根据空域限制，气象条件等约束条件，确定是否接受投标，如接受投标，则与之签署合同，如果不接受投标，则驳回重新申请，直到签署合同为止，如图4所示.

图4 CNP工作流程Fig.4 CNP workflow

4.2 航向与速度调配算法

本文使用带精英保留策略的自适应遗传算法[16]，从航向和速度调配角度计算最优解脱方案.

（1）染色体编码.

如表1所示，使用1条染色体表示第i组高度层上nm个航空器agentAij，（i=1,2,…,m, j=1,2,…,nm）的解脱航迹.某航空器解脱航迹的前半部分为航向编码，后半部分为速度编码，其二进制编码方案如式(7)和式(8)所示.

表1 染色体编码Table 1Chromosome coding

式中H代表航向，度；V代表速度，km/h.

(2)适应度函数.

该算法的个体适应度函数为

式中E2j表示第j个agent实际退出空域点与原计划退出空域点的距离的平方表示该agent飞行S步过程中，每1步偏离原计划航迹距离平方之和；k1和k2为常数.

(3)自适应交叉率和变异率.

本算法中的交叉概率Pc和变异概率Pm具有自适应性，即在进化过程中，Pc和Pm会根据适应度的大小自动改变.其优点是能避免早熟现象，并具有更高的收敛性和收敛速度.改进后的Pc和Pm按式(10)和式（11）进行自适应调整.

式中fmax和favg分别为适应度的最大值和平均值；Pc1和Pc2分别为最大和最小交叉概率；f'为每对交叉染色体中较大的适应度值；Pm1和Pm2分别为最大和最小变异概率；f为每条染色体的适应度值.

（4）运算过程.

该算法步骤如下：

步骤1初始化.确定种群规模popsize=300，初始种群pop(t),t=0,确定适应度函数f.

步骤2解码和计算适应度.对二进制染色体进行解码，计算pop(t)中每个个体的适应度.

步骤3最大迭代次数为400，若最大适应度连续15次相同，则终止运行.取pop(t)中适应度最大的个体作为输出结果，算法结束.

步骤4种群进化.

①选择.

②交叉.

根据自适应交叉率Pc进行交叉运算，生成新种群pop2(t).

③变异.

根据自适应变异率Pm进行变异运算，生成新种群pop3(t).

步骤5使用精英保留策略，将pop(t)中占比Pe的精英染色体保留下来，替换pop3(t)中相同比例适应度较小的染色体，生成新一代种群pop(t+1)，转步骤2.

5 仿真分析

以MATLAB为平台进行仿真.仿真实验中，10架航空器同时出现在300 km×300 km空域的不同位置，并以相同速度飞行，飞行过程分为20步，每步距离为15 km，飞行时间为1 min.10个航空器agent的详细信息如表2所示，仿真实验参数设置如表3所示.

表2 10架航空器的飞行计划Table 2Flight plan of 10 aircraft agents

表3 参数设置Table 3Parameter setting

5.1 高度层调配

在仿真过程中，每个agent能根据自身飞行计划和飞行环境及时计算出最优飞行高度层，然后进行招标、投标和签署合同等操作.经过5次随机运算，仿真平均耗时为2 s，结果如表2所示.

5.2 航向和速度调配

根据5.1节内容，显然第4组不存在飞行冲突，所以A41的航向和速度保持不变.目前仍存在飞行冲突的有第1组、第2组和第3组.

（1）第2组agent.

经过5次随机运算，该算法平均迭代163次后能收敛于近似最优解，平均耗时为18.1 s.图5和图6分别为A21，A22的航向和速度调配结果.

图6 A21和A22的速度改变Fig.6 Velocity change of A21和A22

（2）第3组agent.

经过5次随机运算，该算法平均迭代309次后能收敛于近似最优解，平均耗时为53.02 s.图7和图8分别为A31，A32，A33的航向和速度调配结果.

图7 A31,A32和A33的航向改变Fig.7 Heading change of A31,A32和A33

图8 A31,A32和A33的速度改变Fig.8 Velocity change of A31,A32和A33

（3）第1组agent.

经过5次随机运算，该算法平均迭代335次后能收敛于近似最优解，平均耗时为88.6 s.图9和图10分别为A11，A12，A13，A14的航向和速度调配结果.

图9 A11,A12,A13和A14的航向改变Fig.9 Heading change of A11,A12,A13和A14

图10 A11,A12,A13和A14的速度改变Fig.10 Velocity change of A11,A12,A13和A14

图11为飞行过程前半部分t=[0,T/2]的总体解决方案示意图，图12为飞行过程后半部分t=[T/2,T]的总体解决方案示意图.

图11 总体解决方案[0,T/2]Fig.11 Overall solution[0,T/2]

图12 总体解决方案[T/2,T]Fig.12 Overall solution[T/2,T]

6 研究结论

本文首先提出了自由飞行背景下飞行冲突探测与解脱的分布式MAS结构，在该框架下，航空器之间可自主进行通信和协调，并在探测到飞行冲突后，将MAS的分布式技术与启发式算法相结合，从高度层、航向和速度调配的角度解决多机飞行冲突解脱问题，仿真实验表明：

（1）所设计的分布式MAS框架是可行的，同时基于合同网协议的分布式算法能够充分考虑每架航空器agent的意愿，快速找到高度层调配的最优解；

（2）在航向和速度调配方面，采用精英保留策略的自适应遗传算法，能够从全局角度同时解决多架航空器agent的冲突解脱问题，并提高了算法的收敛性；

（3）不足之处在于，虽然对传统遗传算法进行了改进，但随着航空器数量的增多，算法编程变得更加复杂，收敛速度变得更加缓慢，该问题值得进一步研究和优化.

[1]Kuchar J K，Yang L C.A review of conflict detection and resolution modeling methods[J].IEEE Transactions on Intelligent Transportation Systems，2000，1(4)：179-189.

[2]Hojjat E，Kamyar N.A comparisonframeworkfor conflict detection and resolution multi agent modeling methods in air traffic management[J].International JournalofInformationTechnology，Controland Automation(IJITCA)，2012，2(4)：51-64.

[3]DavidS，PremyslV，Michal pechoucek.Agentbasedcooperativedecentralizedairplane-collision avoidance[J].IEEETransactionsonIntelligent Transportations Systems，2011，12(1)：36-46.

[4]Miguel A V，Colin G.Application of distributed artificial intelligence in autonomous aircraft operations[C].20th ConferenceonDigitalAvionicsSystems.Daytona Beach，FL：IEEE，2001：7B3/1-7B3/14.

[5]Michael H，George M，Stefan R.An agent based framework for control of mergingair-traffic[C].In Proceedings16thIFACSymposiumonAutomatic Control in Aerospace.St.Petersburg，Russia,2004.

[6]Magnus L，Andrew L.The OASIS air traffic management system[C].Proceedings of the Second Pacific Rim InternationalConferenceonArtificialIntelligence，PRICAI.Seoul，Korea,1992.

[7]刘红红，杨兆升.基于神经网络的实时交通信号控制与仿真研究[J].交通运输系统工程与信息，2008，8 (2)：43-47.[LIU H H,YANG Z S.Real-time traffic signalcontrolandsimulationbasedonneural networks[J].JournalofTransportationSystems Engineering and Information Technology,2008,8(2): 43-47.]

[8]石文先.基于MAS协商机制的冲突解脱研究[D].南京：南京航空航天大学，2008.[SHI W X.A cooperative MAS approach to conflict resolution[D]. Nanjing:NanjingUniversityofAeronauticsand Astronautics,2008.]

[9]冯兴杰，赵睿.多目标遗传算法在飞行冲突解脱中的应用[J].计算机工程与设计，2014，35(7)：2577-2581.[FENG X J,ZHAO R.Conflict resolution of airplanes based on multi-objective genetic algorithm[J].Computer Engineering and Design,2014,35(7):2577-2581.]

[10]王渊，孙秀霞，刘树光，等.基于改进人工蜂群算法的多机飞行冲突解脱策略[J].空军工程大学学报（自然科学版），2014，15(3)：10-14.[WANG Y,SUN X X, LIU S G,et al.Research on multi-aircraft confliction resolution based on a modified artificial bee colony algorithm[J].JournalofAirForceEngineering University(Natural Science Edition),2014,15(3):10-14.]

[11]裴志刚，李华星，王庆胜.模拟退火遗传算法在飞行冲突解脱中的应用[J].交通与计算机，2005，1(23)：115-117.[PEI Z G,LI H X,WANG Q S.Application of simulated annealing/genetic algorithms in flight conflict resolution[J].Traffic and Computer,2005,1(23):115-117.]

[12]郭茜，聂润兔.改进人工势场法在解决飞行冲突问题中的应用[J].交通与计算机，2008，5(26)：103-106. [GUO Q,NIE R T.Application of improved artificial field method in aircraft conflict resolution[J].Traffic and Computer,2008,5(26):103-106.]

[13]崔莉薇，石为人，刘祥明,等.基于遗传粒子群算法的飞行冲突解脱[J].计算机工程与应用，2013，49(7)：263-266.[CUI L W,SHI W R,LIU X M,et al.Air conflict resolution based on genetic algorithm and particle swarm optimization[J].Computer Engineering and Applications,2013,49(7):263-266.]

[14]魏志强.基于最小成本的高度能力计算方法[J].交通运输工程学报，2005，5(2)：77-79.[WEI Z Q.Altitude capability calculation methods based on minimum flight cost[J].JournalofTrafficandTransportation Engineering,2005,5(2):77-79.]

[15]Smith R G，Davis R.The contract net protocol：Highlevelcommunicationandcontrolinadistributed problem solver[J].IEEE Tran Computers，1980，C-29 (12)：1104-1113.

[16]Srinivas M，Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Trans on Systems，Man and Cybernetics，1994，24(4)：656-667.

Application of Distributed MAS in Flight Conflict Avoidance

ZHOU Jian1,RAHMANIAhmed2,LIU Xin1,WANG Li-li1(1.School ofAir Traffic Management,CivilAviation University of China,Tianjin 300300,China; 2.Institute ofAutomatic,Information Engineering and Signal,Ecole Centrale de Lille,Lille 59650,France)

In order to solve the problem of flight conflict detection and resolution(CDR)in the background of free flight,an integrated CDR method based on assignment of flight level,heading and velocity is proposed,and distributed technology of MAS(multi-agent system)and a heuristic algorithm are combined for the algorithm implementation.Firstly,a framework of distributed MAS is designed.Secondly,a conflict detection model,a flight level allocation model and a heading&velocity assignment model are established. Finally,a distributed algorithm based on contract net protocol and an adaptive genetic algorithm are designed to solve the problem.Simulation results show that the MAS framework is feasible,and the combination of the designed distributed algorithm and adaptive genetic algorithm can search the approximate optimal solution rapidly,based on the allocation of flight level,heading and velocity,which provides a new solution to the CDR problem.

air transportation;conflict resolution;contract net protocol;multi-agent system;air traffic management

1009-6744（2015）05-0231-08

V355.1;V328.3

A

2015-05-19

2015-06-26录用日期：2015-07-06

国家自然科学基金资助(U1333116)；国家空管科研课题(GKG201405002)；中央高校基本科研业务费中国民航大学专项基金资助(ZXH2013D013).

周建（1983-），男，江西宜春人，讲师，硕士. ＊

zneblr@sina.com