分布式MAS在飛行沖突解脫中的應用研究

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

（1.中國民航大學空中交通管理學院，天津300300;2.里爾中央理工學院自動化、信息技術工程和信號實驗室，里爾59650，法國）

分布式MAS在飛行沖突解脫中的應用研究

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

（1.中國民航大學空中交通管理學院，天津300300;2.里爾中央理工學院自動化、信息技術工程和信號實驗室，里爾59650，法國）

在自由飛行的環(huán)境下，為解決飛行沖突探測與解脫（conflict detection and resolution，CDR）問題，提出一種基于高度層、航向和速度調配的綜合解脫方法，并將多agent系統(tǒng)(multi-agent system,MAS)的分布式技術與啟發(fā)式算法相結合，進行問題求解.首先設計了分布式MAS框架結構，然后建立了飛行沖突探測模型，高度層調配模型及航向、速度調配模型，最后，綜合運用了基于合同網協(xié)議的分布式算法和自適應遺傳算法進行問題求解.仿真實驗表明，所設計的MAS框架是可行的，同時分布式算法和自適應遺傳算法的綜合應用能很快找到基于高度層、航向和速度分配的近似最優(yōu)解，為CDR問題提供了新的解決思路.

航空運輸；沖突解脫；合同網協(xié)議；多agent系統(tǒng)；空中交通管理

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機場的終端區(qū)建立了agent模型，并引入了動態(tài)資源優(yōu)先使用機制；Magnus Ljungberg等[6]介紹了已付諸實踐的OASIS系統(tǒng)的MAS框架及相關算法.以上學者提出了非集中式沖突解脫的理念，為CDR問題的研究提供了新的方法.國內方面，劉紅紅[7]等使用分布式MAS技術解決交通信號控制問題，石文先[8]使用MAS技術解決CDR問題，而大多數研究人員使用啟發(fā)式算法解決CDR問題[9-13].

以上方法存在下述問題：

(1)偏重于MAS系統(tǒng)框架的宏觀設計，對空中交通管理（以下簡稱空管）行業(yè)了解不深入，理論與實踐結合不夠緊密；

(2)僅從改變航向和速度兩個方面提出優(yōu)化策略，忽略了空管一線單位使用最頻繁的高度層調配策略；

(3)在目前集中式管制指揮的環(huán)境下，算法最優(yōu)解的實施會大大增加管制員的工作負荷，增大了安全隱患.

本文將研究改變傳統(tǒng)集中式管制指揮模式，提出分布式MAS結構，將分布式人工智能與啟發(fā)式算法相結合，從高度、航向和速度方面提出飛行沖突解脫綜合策略.

2 分布式MAS結構

2.1 航空器agent結構

在分布式MAS框架中，每架航空器被視為一個agent，主要包括通信協(xié)調、CDR、飛行計劃、知識數據庫、性能數據庫、環(huán)境數據庫等模塊，如圖1所示.

圖1 航空器agent結構圖Fig.1 Structure of aircraft agent

航空器agent之間將使用通信協(xié)調模塊，通過ADSB進行通信、協(xié)調和協(xié)作.CDR和飛行計劃模塊需要知識數據庫、性能數據庫和飛行環(huán)境數據庫的支持，其中知識數據庫中存儲了相關數學模型和算法，性能數據庫中存儲了主流航空器的性能數據，而飛行環(huán)境數據庫存儲了航空氣象、空域限制等信息.

2.2 飛行沖突探測模塊

如圖2所示，系統(tǒng)隨機選擇某航空器為協(xié)調agent，協(xié)調agent在接收到其他agent相關信息后，沖突探測模塊對其他agent的飛行計劃FPi和自身的飛行計劃FP進行分析，并判斷是否存在沖突.

2.3 飛行沖突解脫模塊

(1)高度層調配模塊.

如圖3所示，協(xié)調agent與其它agent進行通信、協(xié)調并確定調配方案后，將N個agent劃分為m個小組，每組有ni(i=1,2,…,m)個高度層相同的agent.再利用沖突探測模塊進行沖突探測，如果沒有探測到沖突，該agent就將新的飛行計劃FP'i發(fā)送給其他的agent成員；如果探測到了沖突，則進入沖突解脫第2階段.

圖3 高度層分配Fig.3 Allocation of flight level

（2）航向和速度調配模塊.

m個高度層小組中的任何一組沖突，都可以被簡化為2維空間的沖突解脫問題，本文將使用改進后的遺傳算法計算出最優(yōu)解脫方案，然后協(xié)調agent將最新的飛行計劃發(fā)送給其他的agent成員.

3 問題描述與建模

本文將航路上的飛行沖突探測和解脫分成兩個階段：高度層調配階段，航向、速度調配階段，并建立相應的模型.假設條件如下：

（1）自由飛行的背景下，航空器可自主選擇飛行路徑和高度層；

（2）航空器的航向變化簡化為左轉30o，右轉30o和保持原航向三種，集合為{H-30o,H,H+30o}；

（3）航空器的速度變化簡化為減速10%、加速10%和保持原速度三種，集合為{V?90%,V,V?110%}.

3.1 沖突探測模型

協(xié)調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為發(fā)動機臺數；VG為地速，km/h；M為馬赫數；α為該飛行高度層音速，km/h.

在CI、航空器質量、溫度偏差值一定時，根據式（4），使用迭代方法，可計算出航空器在不同高度層上的EC，然后選取最小EC所對應高度層即為最經濟巡航高度層.

3.3 航向與速度調配模型

針對m個高度層小組的任一組航空器可建立飛行沖突解脫數學模型，目標函數為

式中nm為航空器總數；Lj為第j架航空器在沖突區(qū)內的總飛行距離.

目標函數的約束條件為

4 算法設計

4.1 高度層調配算法

本文使用基于合同網協(xié)議的高度層調配算法.合同網協(xié)議（contract net protocol,CNP）是用于解決分布式問題求解環(huán)境下各agent之間任務分配而進行的一種合約協(xié)作過程[15].其基本原理是采用市場“招標—投標—中標”機制進行任務通告、投標，最后簽訂合同來實現任務分配.

系統(tǒng)開始運行時，協(xié)調agent向所有成員agent發(fā)出高度層招標書，成員agent選擇最優(yōu)高度層進行投標，協(xié)調agent根據空域限制，氣象條件等約束條件，確定是否接受投標，如接受投標，則與之簽署合同，如果不接受投標，則駁回重新申請，直到簽署合同為止，如圖4所示.

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

4.2 航向與速度調配算法

本文使用帶精英保留策略的自適應遺傳算法[16]，從航向和速度調配角度計算最優(yōu)解脫方案.

（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會根據適應度的大小自動改變.其優(yōu)點是能避免早熟現象，并具有更高的收斂性和收斂速度.改進后的Pc和Pm按式(10)和式（11）進行自適應調整.

式中fmax和favg分別為適應度的最大值和平均值；Pc1和Pc2分別為最大和最小交叉概率；f'為每對交叉染色體中較大的適應度值；Pm1和Pm2分別為最大和最小變異概率；f為每條染色體的適應度值.

（4）運算過程.

該算法步驟如下：

步驟1初始化.確定種群規(guī)模popsize=300，初始種群pop(t),t=0,確定適應度函數f.

步驟2解碼和計算適應度.對二進制染色體進行解碼，計算pop(t)中每個個體的適應度.

步驟3最大迭代次數為400，若最大適應度連續(xù)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能根據自身飛行計劃和飛行環(huán)境及時計算出最優(yōu)飛行高度層，然后進行招標、投標和簽署合同等操作.經過5次隨機運算，仿真平均耗時為2 s，結果如表2所示.

5.2 航向和速度調配

根據5.1節(jié)內容，顯然第4組不存在飛行沖突，所以A41的航向和速度保持不變.目前仍存在飛行沖突的有第1組、第2組和第3組.

（1）第2組agent.

經過5次隨機運算，該算法平均迭代163次后能收斂于近似最優(yōu)解，平均耗時為18.1 s.圖5和圖6分別為A21，A22的航向和速度調配結果.

圖6 A21和A22的速度改變Fig.6 Velocity change of A21和A22

（2）第3組agent.

經過5次隨機運算，該算法平均迭代309次后能收斂于近似最優(yōu)解，平均耗時為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次后能收斂于近似最優(yōu)解，平均耗時為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結構，在該框架下，航空器之間可自主進行通信和協(xié)調，并在探測到飛行沖突后，將MAS的分布式技術與啟發(fā)式算法相結合，從高度層、航向和速度調配的角度解決多機飛行沖突解脫問題，仿真實驗表明：

（1）所設計的分布式MAS框架是可行的，同時基于合同網協(xié)議的分布式算法能夠充分考慮每架航空器agent的意愿，快速找到高度層調配的最優(yōu)解；

（2）在航向和速度調配方面，采用精英保留策略的自適應遺傳算法，能夠從全局角度同時解決多架航空器agent的沖突解脫問題，并提高了算法的收斂性；

（3）不足之處在于，雖然對傳統(tǒng)遺傳算法進行了改進，但隨著航空器數量的增多，算法編程變得更加復雜，收斂速度變得更加緩慢，該問題值得進一步研究和優(yōu)化.

[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].交通運輸系統(tǒng)工程與信息，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協(xié)商機制的沖突解脫研究[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)；中央高?；究蒲袠I(yè)務費中國民航大學專項基金資助(ZXH2013D013).

周建（1983-），男，江西宜春人，講師，碩士. ＊

zneblr@sina.com