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

（1.中國(guó)民航大學(xué)空中交通管理學(xué)院，天津300300;2.里爾中央理工學(xué)院自動(dòng)化、信息技術(shù)工程和信號(hào)實(shí)驗(yàn)室，里爾59650，法國(guó)）

分布式MAS在飛行沖突解脫中的應(yīng)用研究

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

（1.中國(guó)民航大學(xué)空中交通管理學(xué)院，天津300300;2.里爾中央理工學(xué)院自動(dòng)化、信息技術(shù)工程和信號(hào)實(shí)驗(yàn)室，里爾59650，法國(guó)）

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

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

1 引言

飛行安全是空管工作的重點(diǎn)，對(duì)飛行沖突的探測(cè)與解脫方法的研究，一直是國(guó)內(nèi)外學(xué)者和專家關(guān)注的熱點(diǎn).

國(guó)外對(duì)用MAS技術(shù)解決CDR問題已有研究，如Kuchar和Hojjat Emami等[1,2]對(duì)MAS技術(shù)在CDR問題的應(yīng)用進(jìn)行了綜述，David Sislak等[3]提出了基于agent的機(jī)載CDR結(jié)構(gòu)框架和相關(guān)算法；Miguel A Vilaplana等[4]描述了機(jī)載MAS模型框架并綜合考慮了飛行成本問題[4]；Michael Heymann等[5]針對(duì)San Francisco機(jī)場(chǎng)的終端區(qū)建立了agent模型，并引入了動(dòng)態(tài)資源優(yōu)先使用機(jī)制；Magnus Ljungberg等[6]介紹了已付諸實(shí)踐的OASIS系統(tǒng)的MAS框架及相關(guān)算法.以上學(xué)者提出了非集中式?jīng)_突解脫的理念，為CDR問題的研究提供了新的方法.國(guó)內(nèi)方面，劉紅紅[7]等使用分布式MAS技術(shù)解決交通信號(hào)控制問題，石文先[8]使用MAS技術(shù)解決CDR問題，而大多數(shù)研究人員使用啟發(fā)式算法解決CDR問題[9-13].

以上方法存在下述問題：

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

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

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

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

2 分布式MAS結(jié)構(gòu)

2.1 航空器agent結(jié)構(gòu)

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

圖1 航空器agent結(jié)構(gòu)圖Fig.1 Structure of aircraft agent

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

2.2 飛行沖突探測(cè)模塊

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

2.3 飛行沖突解脫模塊

(1)高度層調(diào)配模塊.

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

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

（2）航向和速度調(diào)配模塊.

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

3 問題描述與建模

本文將航路上的飛行沖突探測(cè)和解脫分成兩個(gè)階段：高度層調(diào)配階段，航向、速度調(diào)配階段，并建立相應(yīng)的模型.假設(shè)條件如下：

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

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

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

3.1 沖突探測(cè)模型

協(xié)調(diào)agent根據(jù)其它agent的相關(guān)信息，判斷是否存在飛行沖突，沖突探測(cè)數(shù)學(xué)模型為

式中（xi,yi,zi）和（xj,yj,zj）分別為agentAi和Aj的坐標(biāo)；Sh為最小水平間隔；Sv為最小垂直間隔.當(dāng)同時(shí)滿足式（1）和式（2）時(shí)，agentAi和Aj存在沖突.

3.2 高度層調(diào)配模型

航空公司的直接運(yùn)營(yíng)費(fèi)用（direct operation cost，DOC）可簡(jiǎn)化為

式中Cfuel為燃油成本，元；Ctime為時(shí)間成本，元. Cfuel與Ctime的比值用成本指數(shù)CI表示.則航空器飛行單位距離所需成本[14]為

式中R為飛行距離，km；WF為燃油流量，kg/h；NE為發(fā)動(dòng)機(jī)臺(tái)數(shù)；VG為地速，km/h；M為馬赫數(shù)；α為該飛行高度層音速，km/h.

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

3.3 航向與速度調(diào)配模型

針對(duì)m個(gè)高度層小組的任一組航空器可建立飛行沖突解脫數(shù)學(xué)模型，目標(biāo)函數(shù)為

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

目標(biāo)函數(shù)的約束條件為

4 算法設(shè)計(jì)

4.1 高度層調(diào)配算法

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

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

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

4.2 航向與速度調(diào)配算法

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

（1）染色體編碼.

如表1所示，使用1條染色體表示第i組高度層上nm個(gè)航空器agentAij，（i=1,2,…,m, j=1,2,…,nm）的解脫航跡.某航空器解脫航跡的前半部分為航向編碼，后半部分為速度編碼，其二進(jìn)制編碼方案如式(7)和式(8)所示.

表1 染色體編碼Table 1Chromosome coding

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

(2)適應(yīng)度函數(shù).

該算法的個(gè)體適應(yīng)度函數(shù)為

式中E2j表示第j個(gè)agent實(shí)際退出空域點(diǎn)與原計(jì)劃退出空域點(diǎn)的距離的平方表示該agent飛行S步過程中，每1步偏離原計(jì)劃航跡距離平方之和；k1和k2為常數(shù).

(3)自適應(yīng)交叉率和變異率.

本算法中的交叉概率Pc和變異概率Pm具有自適應(yīng)性，即在進(jìn)化過程中，Pc和Pm會(huì)根據(jù)適應(yīng)度的大小自動(dòng)改變.其優(yōu)點(diǎn)是能避免早熟現(xiàn)象，并具有更高的收斂性和收斂速度.改進(jìn)后的Pc和Pm按式(10)和式（11）進(jìn)行自適應(yīng)調(diào)整.

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

（4）運(yùn)算過程.

該算法步驟如下：

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

步驟2解碼和計(jì)算適應(yīng)度.對(duì)二進(jìn)制染色體進(jìn)行解碼，計(jì)算pop(t)中每個(gè)個(gè)體的適應(yīng)度.

步驟3最大迭代次數(shù)為400，若最大適應(yīng)度連續(xù)15次相同，則終止運(yùn)行.取pop(t)中適應(yīng)度最大的個(gè)體作為輸出結(jié)果，算法結(jié)束.

步驟4種群進(jìn)化.

①選擇.

②交叉.

根據(jù)自適應(yīng)交叉率Pc進(jìn)行交叉運(yùn)算，生成新種群pop2(t).

③變異.

根據(jù)自適應(yīng)變異率Pm進(jìn)行變異運(yùn)算，生成新種群pop3(t).

步驟5使用精英保留策略，將pop(t)中占比Pe的精英染色體保留下來，替換pop3(t)中相同比例適應(yīng)度較小的染色體，生成新一代種群pop(t+1)，轉(zhuǎn)步驟2.

5 仿真分析

以MATLAB為平臺(tái)進(jìn)行仿真.仿真實(shí)驗(yàn)中，10架航空器同時(shí)出現(xiàn)在300 km×300 km空域的不同位置，并以相同速度飛行，飛行過程分為20步，每步距離為15 km，飛行時(shí)間為1 min.10個(gè)航空器agent的詳細(xì)信息如表2所示，仿真實(shí)驗(yàn)參數(shù)設(shè)置如表3所示.

表2 10架航空器的飛行計(jì)劃Table 2Flight plan of 10 aircraft agents

表3 參數(shù)設(shè)置Table 3Parameter setting

5.1 高度層調(diào)配

在仿真過程中，每個(gè)agent能根據(jù)自身飛行計(jì)劃和飛行環(huán)境及時(shí)計(jì)算出最優(yōu)飛行高度層，然后進(jìn)行招標(biāo)、投標(biāo)和簽署合同等操作.經(jīng)過5次隨機(jī)運(yùn)算，仿真平均耗時(shí)為2 s，結(jié)果如表2所示.

5.2 航向和速度調(diào)配

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

（1）第2組agent.

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

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

（2）第3組agent.

經(jīng)過5次隨機(jī)運(yùn)算，該算法平均迭代309次后能收斂于近似最優(yōu)解，平均耗時(shí)為53.02 s.圖7和圖8分別為A31，A32，A33的航向和速度調(diào)配結(jié)果.

圖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.

經(jīng)過5次隨機(jī)運(yùn)算，該算法平均迭代335次后能收斂于近似最優(yōu)解，平均耗時(shí)為88.6 s.圖9和圖10分別為A11，A12，A13，A14的航向和速度調(diào)配結(jié)果.

圖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 研究結(jié)論

本文首先提出了自由飛行背景下飛行沖突探測(cè)與解脫的分布式MAS結(jié)構(gòu)，在該框架下，航空器之間可自主進(jìn)行通信和協(xié)調(diào)，并在探測(cè)到飛行沖突后，將MAS的分布式技術(shù)與啟發(fā)式算法相結(jié)合，從高度層、航向和速度調(diào)配的角度解決多機(jī)飛行沖突解脫問題，仿真實(shí)驗(yàn)表明：

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

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

（3）不足之處在于，雖然對(duì)傳統(tǒng)遺傳算法進(jìn)行了改進(jìn)，但隨著航空器數(shù)量的增多，算法編程變得更加復(fù)雜，收斂速度變得更加緩慢，該問題值得進(jìn)一步研究和優(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，F(xiàn)L：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īng)網(wǎng)絡(luò)的實(shí)時(shí)交通信號(hào)控制與仿真研究[J].交通運(yùn)輸系統(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é)商機(jī)制的沖突解脫研究[D].南京：南京航空航天大學(xué)，2008.[SHI W X.A cooperative MAS approach to conflict resolution[D]. Nanjing:NanjingUniversityofAeronauticsand Astronautics,2008.]

[9]馮興杰，趙睿.多目標(biāo)遺傳算法在飛行沖突解脫中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(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ìn)人工蜂群算法的多機(jī)飛行沖突解脫策略[J].空軍工程大學(xué)學(xué)報(bào)（自然科學(xué)版），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]裴志剛，李華星，王慶勝.模擬退火遺傳算法在飛行沖突解脫中的應(yīng)用[J].交通與計(jì)算機(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]郭茜，聶潤(rùn)兔.改進(jìn)人工勢(shì)場(chǎng)法在解決飛行沖突問題中的應(yīng)用[J].交通與計(jì)算機(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].計(jì)算機(jī)工程與應(yīng)用，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]魏志強(qiáng).基于最小成本的高度能力計(jì)算方法[J].交通運(yùn)輸工程學(xué)報(bào)，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

國(guó)家自然科學(xué)基金資助(U1333116)；國(guó)家空管科研課題(GKG201405002)；中央高校基本科研業(yè)務(wù)費(fèi)中國(guó)民航大學(xué)專項(xiàng)基金資助(ZXH2013D013).

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

zneblr@sina.com