基于Q學(xué)習(xí)的管制員Agent學(xué)習(xí)行為研究

劉岳鵬，隋 東，林穎達(dá)

(南京航空航天大學(xué) 民航學(xué)院，南京 211106)

?

基于Q學(xué)習(xí)的管制員Agent學(xué)習(xí)行為研究

劉岳鵬，隋 東，林穎達(dá)

(南京航空航天大學(xué) 民航學(xué)院，南京 211106)

管制員Agent是空中交通運(yùn)行仿真系統(tǒng)中的核心部分，為了提高其知識(shí)庫(kù)的完備程度，做到空中交通的精確仿真，可以考慮將機(jī)器學(xué)習(xí)理論引入管制員Agent模型.研究了相關(guān)機(jī)器學(xué)習(xí)算法，提出管制員Agent的個(gè)體機(jī)器學(xué)習(xí)行為，選擇Q學(xué)習(xí)算法對(duì)管制員Agent的學(xué)習(xí)行為進(jìn)行建模，使管制員Agent能在空中交通運(yùn)行仿真中取得最優(yōu)策略，完善自身沖突解脫知識(shí)庫(kù)的不足.仿真結(jié)果證明了管制員Agent學(xué)習(xí)行為的合理性.

交通運(yùn)輸規(guī)劃與管理；行為建模；Q學(xué)習(xí)；多Agent系統(tǒng)

近年來(lái)，空中交通需求日益增長(zhǎng)，而現(xiàn)有的空中交通管制保障能力有限，需求與供給的矛盾日益突出.無(wú)論是調(diào)整現(xiàn)有交通系統(tǒng)中的空域結(jié)構(gòu)、航路航線等元素還是采用新技術(shù)新概念都需要事先做安全評(píng)估，查找潛在的危險(xiǎn)因素[1].考慮到空中交通管理系統(tǒng)的復(fù)雜性，使用計(jì)算機(jī)軟件來(lái)仿真空中交通管理系統(tǒng)成為了一種重要的研究手段.這種手段不僅可以減少對(duì)新技術(shù)新概念驗(yàn)證的成本，還可以對(duì)現(xiàn)有運(yùn)行模式下所存在的潛在安全問(wèn)題進(jìn)行分析評(píng)估，具有非常重要的理論意義與研究?jī)r(jià)值.但是，由于空中交通管理系統(tǒng)的規(guī)模龐大，基于單機(jī)進(jìn)行計(jì)算的集中式仿真難以勝任.針對(duì)此問(wèn)題，分布式人工智能——多Agent系統(tǒng)技術(shù)被應(yīng)用于空中交通運(yùn)行仿真系統(tǒng)中[2].管制員Agent是整個(gè)仿真系統(tǒng)中的核心，它的任務(wù)是監(jiān)視其所在扇區(qū)內(nèi)的航空器Agent的活動(dòng)并對(duì)其進(jìn)行調(diào)配.隨著空中交通運(yùn)行仿真系統(tǒng)越來(lái)越智能化，傳統(tǒng)的基于知識(shí)庫(kù)的沖突調(diào)配方法較難滿足系統(tǒng)的需要.因此，從仿真過(guò)程中獲得經(jīng)驗(yàn)以擴(kuò)充其知識(shí)庫(kù)是管制員Agent必不可少的能力.本問(wèn)研究了相關(guān)機(jī)器學(xué)習(xí)算法，并在先驗(yàn)知識(shí)庫(kù)的基礎(chǔ)上，提出管制員Agent的個(gè)體機(jī)器學(xué)習(xí)算法，并選擇Q學(xué)習(xí)算法對(duì)管制員Agent的學(xué)習(xí)行為進(jìn)行建模，使管制員Agent能在空中交通運(yùn)行仿真中對(duì)航空器Agent之間的沖突進(jìn)行靈活調(diào)配，完善自身沖突探測(cè)與解脫知識(shí)庫(kù)的不足，提升整個(gè)仿真系統(tǒng)的智能程度[3].

1 Q學(xué)習(xí)算法原理與模型

強(qiáng)化學(xué)習(xí)的主要思想是處于環(huán)境中的一個(gè)Agent可以感知環(huán)境狀態(tài)，并且自身帶有確定的動(dòng)作集S，Agent根據(jù)當(dāng)前環(huán)境的狀態(tài)執(zhí)行動(dòng)作集A中的一個(gè)動(dòng)作a，通過(guò)接受獎(jiǎng)勵(lì)或懲罰，由此決定當(dāng)前狀態(tài)應(yīng)該執(zhí)行哪種動(dòng)作.在該學(xué)習(xí)系統(tǒng)中，存在預(yù)先制定好的獎(jiǎng)勵(lì)和懲罰措施，Agent每執(zhí)行一個(gè)動(dòng)作，系統(tǒng)都會(huì)對(duì)這個(gè)動(dòng)作進(jìn)行一個(gè)評(píng)價(jià).最后，Agent會(huì)選擇那些評(píng)價(jià)相對(duì)較高的動(dòng)作并執(zhí)行，經(jīng)過(guò)大量訓(xùn)練樣本的訓(xùn)練，最終能得到一套狀態(tài)-動(dòng)作映射關(guān)系，即策略π：S→A.

(1)

其中:r(s,a)為立即回報(bào)，γ為折算因子.

2 管制員Agent的學(xué)習(xí)行為實(shí)現(xiàn)

2.1 航空器Agent狀態(tài)信息描述

Q學(xué)習(xí)解決的問(wèn)題有如下特點(diǎn)：規(guī)模相對(duì)較小、環(huán)境狀態(tài)和動(dòng)作集是離散的.因此，如果環(huán)境狀態(tài)和動(dòng)作集是連續(xù)的，使用Q學(xué)習(xí)解決此類問(wèn)題必然會(huì)出現(xiàn)“維數(shù)災(zāi)難”，學(xué)習(xí)的效率不能得到保證[6].由于管制員Agent所處的環(huán)境是連續(xù)的，因此在管制員Agent中實(shí)現(xiàn)Q學(xué)習(xí)行為，應(yīng)將管制員Agent獲取的航空器Agent的狀態(tài)信息進(jìn)行離散化.

航空器Agent有很多狀態(tài)，在沖突探測(cè)與解脫時(shí)，主要判斷的是航空器Agent的高度和速度.在程序設(shè)計(jì)中，構(gòu)建State類，通過(guò)調(diào)用State類中的函數(shù)，可得到航空器Agent的部分狀態(tài)值.其中，定義離散高度層數(shù)量40個(gè)，離散真空速數(shù)量20個(gè)，沖突類型分為同航跡、逆向航跡和交叉航跡3種，兩個(gè)航空器Agent的上升/下降率按照上升、平飛和下降分為3個(gè).其中，根據(jù)狀態(tài)組合，共得到40×20×3×3×3=21 600種可能存在的狀態(tài).

2.2 航空器Agent高度離散化

航空器進(jìn)行航路和航線飛行時(shí)，按照我國(guó)生效的巡航高度層配備方案所配備的巡航高度層飛行，根據(jù)飛行高度層的配備，可以將飛行高度進(jìn)行離散化處理.根據(jù)真航線角建立東向飛行高度層數(shù)組和西向飛行高度層數(shù)組，共設(shè)置20個(gè)西向飛行高度層和20個(gè)東向飛行高度層，完成航空器Agent高度的離散化.

2.3 航空器Agent速度離散化

根據(jù)航空器在航路飛行時(shí)真空速的大小，本文將航空器Agent的真空速范圍設(shè)定為110 ～300m/s.但實(shí)際的航空器的速度是個(gè)連續(xù)變量，并不利于Q學(xué)習(xí)算法的實(shí)現(xiàn)，因此根據(jù)實(shí)際管制規(guī)則，將速度步長(zhǎng)設(shè)置為10 m/s.設(shè)置110 m/s為第1個(gè)真空速離散值，將真空速按照從小到大的順序排列并編號(hào)0～19共20個(gè)離散真空速.以航空器Agent的真空速作為計(jì)算依據(jù)，與最小值110 m/s進(jìn)行比較，即可得到當(dāng)前真空速的編號(hào)，完成航空器Agent速度的離散化.

2.4 管制員Agent動(dòng)作描述

管制員主要是通過(guò)調(diào)節(jié)速度和調(diào)節(jié)高度來(lái)對(duì)航空器之間的沖突進(jìn)行調(diào)配，在此處，管制員Agent的主要?jiǎng)幼鳛檎{(diào)節(jié)速度和調(diào)節(jié)高度.在動(dòng)作定義過(guò)程中，主要分為保持速度、加速、減速、保持高度、上升高度和下降高度.在構(gòu)建管制員Agent動(dòng)作集時(shí)，建立Action類，包括15個(gè)靜態(tài)變量.第0～4個(gè)變量為加速指令，其中，加速步長(zhǎng)取10 m/s.第5～9個(gè)變量為減速指令，步長(zhǎng)跟加速步長(zhǎng)相同.其余變量分別定義為保持速度、保持高度、上升高度和下降高度.具體變量及含義如表1所示.

表1 管制員Agent的動(dòng)作集定義

動(dòng)作定義描述ATCAccelerateSpeedX加速(X×10)ATCDecelerateSpeedX減速(X×10)ATCMaintainSpeed保持速度ATCMaintainAltitude保持高度ATCAscendAltitude上升高度ATCDescendAltitude下降高度NumATCActions動(dòng)作集中的動(dòng)作總數(shù)量

2.5 回報(bào)的確定

狀態(tài)和動(dòng)作經(jīng)過(guò)離散化后，整個(gè)仿真環(huán)境由連續(xù)狀態(tài)和動(dòng)作轉(zhuǎn)化為離散化的狀態(tài)和動(dòng)作，已滿足Q學(xué)習(xí)算法的使用條件.但是，Q函數(shù)中的各個(gè)變量還未確定.通過(guò)觀察，在航空器Agent的狀態(tài)改變時(shí)，對(duì)管制員Agent的動(dòng)作即當(dāng)前的管制指令進(jìn)行評(píng)價(jià)，并優(yōu)先選取評(píng)價(jià)較高的管制指令.

設(shè)定管制員Agent的每個(gè)動(dòng)作初始Q值均為0.如果當(dāng)前管制指令可以解決航空器Agent之間的沖突，則立即回報(bào)設(shè)置為正值，如果不能，則設(shè)置為負(fù)值.如前所述，管制指令只能執(zhí)行一個(gè)，因此需要獲得最優(yōu)管制指令，還需要再評(píng)價(jià)一次Q值為正的管制指令.使用解脫時(shí)間t來(lái)進(jìn)行衡量，其內(nèi)部回報(bào)為：

(2)

其中

(3)

2.6 具體學(xué)習(xí)行為實(shí)現(xiàn)方案

在確定了Q學(xué)習(xí)中的所有元素后，就可以用這些元素來(lái)實(shí)現(xiàn)管制員Agent的學(xué)習(xí)方案.

1)首先在程序中將所有Q值進(jìn)行初始化；

2)管制員Agent獲取航空器Agent信息后，將航空器Agent的信息通過(guò)State類中的函數(shù)進(jìn)行離散化；

3)管制員Agent對(duì)動(dòng)作集中的所有動(dòng)作，根據(jù)能否解脫沖突和解脫沖突的代價(jià)對(duì)每一個(gè)管制指令進(jìn)行評(píng)價(jià)，選取評(píng)價(jià)最高的一個(gè)動(dòng)作作為最終輸出的管制指令；

4)將航空器Agent的狀態(tài)和指令綁定，進(jìn)行Q值的更新，即迭代Q值.

3 仿真驗(yàn)證

3.1 仿真環(huán)境構(gòu)建

基于Eclipse集成開(kāi)發(fā)環(huán)境，歐盟開(kāi)源項(xiàng)目JADE[7]開(kāi)發(fā)框架，利用C#語(yǔ)言對(duì)ArcGIS Engine進(jìn)行二次開(kāi)發(fā)并構(gòu)建仿真運(yùn)行場(chǎng)景，并使用MySQL構(gòu)建相關(guān)數(shù)據(jù)庫(kù)，對(duì)空域、航路、機(jī)型、飛機(jī)性能數(shù)據(jù)進(jìn)行管理，系統(tǒng)主界面如圖1所示.

圖1 仿真系統(tǒng)主控界面

航空器Agent的軌跡預(yù)測(cè)模型采用BADA 3.10[8]性能數(shù)據(jù)庫(kù)，軌跡預(yù)測(cè)步長(zhǎng)設(shè)置為Δt=4 s，與空管雷達(dá)刷新頻率保持一致.

3.2 沖突場(chǎng)景構(gòu)建

將沖突分為同航跡、逆向航跡和交叉航跡沖突，分別對(duì)不同種類的沖突進(jìn)行沖突場(chǎng)景構(gòu)建.以逆向航跡沖突為例，構(gòu)造飛行計(jì)劃，如表2、3所示，CXA1111從SASAN航路點(diǎn)飛行至P41航路點(diǎn)，起始高度600 m，巡航高度4 200 m.CXA2341從P41航路點(diǎn)飛行至SASAN航路點(diǎn)，起始高度600 m，巡航高度4 500 m.兩架航班均處于A593航路飛行，兩個(gè)航班均處于爬升狀態(tài)并逆向飛行，如圖2所示.

表2 逆向航跡沖突飛行計(jì)劃

ID航班號(hào)機(jī)型計(jì)劃時(shí)間起始航路點(diǎn)結(jié)束航路點(diǎn)飛行路徑1CXA1111B73720131116160000SASANP41SASAN-P412CXA2341B73720131116160005P41SASANP41-SASAN

表3 飛行高度數(shù)據(jù)表

飛行路徑起始高度/m結(jié)束高度/m巡航高度/mSASAN-P4160042004200P41-SASAN60045004500

圖2 兩航空器Agent逆向航跡飛行

3.3 管制員Agent的學(xué)習(xí)行為驗(yàn)證

如前所述，航空器Agent的狀態(tài)按照離散飛行

高度、離散飛行速度、沖突類型和航空器Agent的上升/下降率共分為五類.本文中只考慮兩機(jī)之間的影響，因此取折算因子γ為0，即只考慮當(dāng)前狀態(tài)的影響，不考慮后續(xù)狀態(tài)對(duì)當(dāng)前的影響，因此對(duì)于每一個(gè)狀態(tài)訓(xùn)練一次即可.在保證立即回報(bào)有界的情況下，Q函數(shù)可以確保是收斂的，并根據(jù)式(1)更新Q值.

管制員Agent根據(jù)狀態(tài)-動(dòng)作值自主進(jìn)行決策，并得到狀態(tài)-動(dòng)作值最大的動(dòng)作作為管制指令對(duì)航空器Agent之間的沖突進(jìn)行調(diào)配.管制員Agent根據(jù)Q學(xué)習(xí)算法得出的結(jié)果如表4所示，管制員Agent可以將要調(diào)配的航空器Agent的狀態(tài)進(jìn)行離散化，得到離散的高度、速度、沖突類型以及上升下降率，并根據(jù)當(dāng)前離散的狀態(tài)對(duì)每個(gè)動(dòng)作即管制指令進(jìn)行評(píng)估，得到狀態(tài)-動(dòng)作值，即為該狀態(tài)下每個(gè)動(dòng)作的獎(jiǎng)賞值.管制員Agent根據(jù)獎(jiǎng)賞值的大小選擇最優(yōu)動(dòng)作即當(dāng)前狀態(tài)下的最優(yōu)管制指令，并將該狀態(tài)的所有狀態(tài)-動(dòng)作值記錄到Q表中，完成對(duì)該狀態(tài)下的訓(xùn)練，并發(fā)送至航空器Agent進(jìn)行沖突調(diào)配.

表4 逆向航跡沖突下的狀態(tài)-動(dòng)作值

高度離散值速度離散值沖突類型航空器Agent1的上升/下降率航空器Agent2的上升/下降率動(dòng)作Q值5210001.058823529411765210011.030303030303035210021.020000000000005210031.015151515151515210041.012048192771085210051.010101010101015210061.008695652173915210071.00757575757575

續(xù)表4

高度離散值速度離散值沖突類型航空器Agent1的上升/下降率航空器Agent2的上升/下降率動(dòng)作Q值5210081.006756756756755210091.0060606060606052100102.0000000000000052100111.0909090909090952100121.0500000000000052100131.03846153846153

注：沖突類型0、1、2分別代表同航跡、逆向航跡和交叉航跡沖突；上升/下降率0、1、2分別代表上升、下降和平飛

從表4中可以看出，所有動(dòng)作中動(dòng)作10的Q值是所有動(dòng)作中的最大值，因此動(dòng)作10被選為最優(yōu)管制指令進(jìn)行輸出.在動(dòng)作集中定義動(dòng)作10為保持當(dāng)前速度，即對(duì)航空器Agent進(jìn)行調(diào)速.從圖3(B)中可以看出，CXA2341收到指令后即開(kāi)始按當(dāng)前速度飛行，而不是圖3(A)中無(wú)管制指令情況下繼續(xù)進(jìn)行加速.從圖4中可以看出，通過(guò)速度的減小而使航空器Agent的上升率減小，同樣可以達(dá)到拉開(kāi)垂直間隔并使沖突解脫的效果.圖5將基于知識(shí)庫(kù)的沖突解脫軌跡與基于Q學(xué)習(xí)算法的沖突解脫軌跡進(jìn)行了對(duì)比，從圖中可以看出兩種指令分別進(jìn)行了調(diào)高和調(diào)速，但均可以對(duì)沖突進(jìn)行解脫.因此，一種沖突可能有不同的解脫方法，基于Q學(xué)習(xí)算法動(dòng)態(tài)生成管制指令，可以對(duì)知識(shí)庫(kù)進(jìn)行完善.[9]

圖3 航空器Agent的速度剖面對(duì)比

圖4 CXA2341調(diào)速后兩航空器Agent的垂直間隔修正空速/(m·s-1)t/s高度/m

圖5 基于知識(shí)庫(kù)的沖突解脫與基于Q學(xué)習(xí)的沖突解脫三維軌跡對(duì)比

4 結(jié) 語(yǔ)

本文提出了管制員Agent的學(xué)習(xí)行為，使用Q學(xué)習(xí)算法實(shí)現(xiàn)管制員Agent的學(xué)習(xí)行為.首先將航空器Agent的狀態(tài)參數(shù)和管制員Agent的動(dòng)作進(jìn)行離散化，使環(huán)境滿足Q學(xué)習(xí)算法的要求.然后，通過(guò)確定Q學(xué)習(xí)算法中的回報(bào)、折算因子等參數(shù)，確定了Q值的更新方式，從而設(shè)計(jì)了管制員Agent的學(xué)習(xí)行為.最后，通過(guò)構(gòu)建逆向沖突飛行計(jì)劃驗(yàn)證了該學(xué)習(xí)行為的有效性.我國(guó)的空中交通正處于發(fā)展階段，將機(jī)器學(xué)習(xí)技術(shù)應(yīng)用于基于多Agent的空中交通運(yùn)行仿真系統(tǒng)中，可為我國(guó)的扇區(qū)劃設(shè)、跑道建設(shè)、航路設(shè)計(jì)以及航路網(wǎng)絡(luò)優(yōu)化等方面提供技術(shù)支持及工具，保證空中交通的安全運(yùn)行.

[1] 王 超, 徐肖豪. 基于Agent的空中交通系統(tǒng)建模與仿真研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 2008, 44(31): 12-14.

[2] 劉成杰. 空中交通管制仿真分析——基于MAS的區(qū)域管制仿真[D]. 南京: 南京航空航天大學(xué), 2013.

[3] 陳中祥. 基于BDI Agent的CGF主體行為建模理論與技術(shù)研究[D]. 武漢: 華中科技大學(xué), 2004.

[4] POOLE D L, MACKWORTH A K. Artificial Intelligence: foundations of computational agents[M]. Cambridge University Press, 2010. 309-312.

[5] TZIORTZIOTIS N, TZIORTZIOTIS K, BLEKAS K. Play Ms. Pac-Man using an advanced reinforcement learning agent [M]. Artificial Intelligence: Methods and Applications. Springer International Publishing, 2014. 71-83.

[6] 王雪松, 朱美強(qiáng), 程玉虎. 強(qiáng)化學(xué)習(xí)原理及其應(yīng)用[M]. 北京: 科學(xué)出版社, 2014.

[7] BELLIFEMINE F L, CAIRE G, GREENWOOD D. Developing multi-agent systems with JADE [M]. [S.l.].John Wiley & Sons, 2007.

[8] NUIC A. User manual for the base of aircraft data (BADA) revision 3.10 [J]. Atmosphere, 2010, 2010: 001.

[9] 周雄飛，胡明華.基于RAMS仿真的扇區(qū)動(dòng)態(tài)容量評(píng)估[J]. 哈爾濱商業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2016，32(5)：626-630.

Research on learning behavior of air traffic controller based on Q-learning

LIU Yue-peng, SUI Dong, LIN Ying-da

(School of Civil Aviation, Nanjing University of Aeronautics & Astronautics, Nanjing 211106, China)

ATC Agent is the core part of an air traffic operation simulation system. In order to increase the degree of completeness of its knowledge base and achieve accurate simulation of air traffic, the machine learning theory was introduced into ATC Agent model. This paper studied the relevant machine learning algorithms and presented the individual learning behavior of ATC Agent. Then Q-learning algorithm wasselected to model the learning behavior of ATC Agent. Thus the ATC Agent was able to obtain the optimal strategy in the process of air traffic operation simulation and improve its knowledge base of conflict resolution.The simulation result proved the rationality of learning behavior of the ATC Agent.

transportation planning and management; behavior modeling; Q-learning; multi-Agentsystem

2016-01-14.

波音項(xiàng)目(1007-EBA14004)；南京航空航天大學(xué)研究生創(chuàng)新基地(實(shí)驗(yàn)室)開(kāi)放基金項(xiàng)目(kfjj20150702)

劉岳鵬(1989-)，碩士，研究方向：空中交通智能化技術(shù).

V355

A

1672-0946(2016)06-0763-06