基于強(qiáng)化學(xué)習(xí)的航空器機(jī)場(chǎng)智能靜態(tài)路徑規(guī)劃

疏利生，李桂芳，嵇勝

（南京航空航天大學(xué)民航學(xué)院，南京210016）

0 引 言

隨著人工智能技術(shù)的迅速發(fā)展，我國(guó)已有上百個(gè)地區(qū)提出建設(shè)“智慧城市”。民用航空機(jī)場(chǎng)作為城市交通中的重要組成部分，“智慧機(jī)場(chǎng)”概念的提出和發(fā)展也逐漸得到行業(yè)的認(rèn)可和推廣。機(jī)場(chǎng)地面作為飛機(jī)活動(dòng)的主要區(qū)域，研究人工智能在機(jī)場(chǎng)地面航空器運(yùn)行中的應(yīng)用具有重要意義。

目前研究航空器在機(jī)場(chǎng)地面滑行道和跑道上運(yùn)行問題的建模方法中，多采用整數(shù)線性規(guī)劃模型、有向圖模型和Petri網(wǎng)模型。2004年，J.W.Smeltink等［1］在研究中指出，航空器場(chǎng)面滑行優(yōu)化的研究可以通過構(gòu)建整數(shù)線形規(guī)劃模型的方法進(jìn)行研究，提出構(gòu)建模型的過程中需要考慮場(chǎng)面航空器滑行沖突，以此降低航班延誤；2006年，G.Chang等［2］針對(duì)復(fù)雜的停機(jī)坪調(diào)度問題，通過有向圖模型模擬仿真了機(jī)坪管制的調(diào)度過程，并通過面向?qū)ο蟮募夹g(shù)實(shí)現(xiàn)了場(chǎng)面運(yùn)行仿真；2007年，H.Balakrishnan等［3］構(gòu)建了優(yōu)化最短航空器地面滑行時(shí)間的整數(shù)線形規(guī)劃模型，通過調(diào)配場(chǎng)面運(yùn)行沖突點(diǎn)來規(guī)劃滑行路徑；2011年，朱新平等［4］運(yùn)用Petri網(wǎng)構(gòu)建了航空器場(chǎng)面運(yùn)行模型，模型中從避免航空器沖突的方向設(shè)計(jì)了實(shí)時(shí)控制沖突預(yù)測(cè)算法，通過仿真分析了模型有效性；2012年，H.Lee等［5］為縮小MILP模型規(guī)模，在模型中引入了滾動(dòng)窗口，通過仿真實(shí)現(xiàn)了航空器場(chǎng)面滑行路徑優(yōu)化和進(jìn)離場(chǎng)路徑選擇和排序優(yōu)化；2018年，潘衛(wèi)軍等［6］構(gòu)建了基于有色Petri網(wǎng)的航空器滑行路徑優(yōu)化模型，并通過實(shí)例仿真驗(yàn)證了所構(gòu)建的路徑優(yōu)化模型的合理性。綜上所述，國(guó)內(nèi)外針對(duì)機(jī)場(chǎng)場(chǎng)面航空器滑行路徑建模問題研究較多，也較為深入，但研究基本針對(duì)某一條件下的應(yīng)用，對(duì)應(yīng)用條件和范圍限定較大，缺乏普適性。

強(qiáng)化學(xué)習(xí)（Reinforcement Learning，簡(jiǎn)稱RL）理論最早于20世紀(jì)50—60年代提出，經(jīng)過多年發(fā)展，強(qiáng)化學(xué)習(xí)的理論已經(jīng)十分成熟。目前強(qiáng)化學(xué)習(xí)在交通控制、機(jī)器人移動(dòng)和學(xué)習(xí)分類等領(lǐng)域廣泛應(yīng)用，但在機(jī)場(chǎng)地面航空器路徑規(guī)劃中的應(yīng)用還未有學(xué)者對(duì)此研究，而“智慧機(jī)場(chǎng)”未來的發(fā)展離不開更加高效的場(chǎng)面運(yùn)行環(huán)境。

本文提出一種基于強(qiáng)化學(xué)習(xí)的航空器靜態(tài)滑行路徑規(guī)劃方法，構(gòu)建機(jī)場(chǎng)地面航空器移動(dòng)強(qiáng)化學(xué)習(xí)模型，模型中考慮了機(jī)場(chǎng)地面航空器滑行規(guī)則；采用Python內(nèi)置工具包Tkinter編寫?？诿捞m機(jī)場(chǎng)模擬環(huán)境，運(yùn)用時(shí)序差分離線控制算法QLearning求解模型，生成符合機(jī)場(chǎng)地面航空器實(shí)際運(yùn)行的滑行路徑。

1 機(jī)場(chǎng)地面航空器移動(dòng)強(qiáng)化學(xué)習(xí)模型

按照機(jī)場(chǎng)真實(shí)環(huán)境轉(zhuǎn)化過程，航空器移動(dòng)到下一個(gè)位置與上個(gè)位置有關(guān)，還與之前的位置有關(guān)，這一模型轉(zhuǎn)換非常復(fù)雜。因此本文對(duì)強(qiáng)化學(xué)習(xí)的模擬機(jī)場(chǎng)環(huán)境轉(zhuǎn)化模型進(jìn)行簡(jiǎn)化，簡(jiǎn)化的方法就是引入狀態(tài)轉(zhuǎn)化的一階馬爾科夫性，也就是智能體（航空器）移動(dòng)到下一個(gè)位置的概率僅和上個(gè)位置有關(guān)，與之前的位置無(wú)關(guān)。

1.1 馬爾科夫決策過程

在強(qiáng)化學(xué)習(xí)的算法中，馬爾科夫決策過程（Markov Decision Process，簡(jiǎn)稱MDP）［7］可表示為(S，A，R，P)：S表示狀態(tài)集合（State），即機(jī)器人可能感知到所有環(huán)境狀態(tài)的集合；A表示動(dòng)作集合（Action）；R表示獎(jiǎng)勵(lì)函數(shù)（Reward Function）；P表示動(dòng)作選擇策略。

智能體集合（Agent）：把在機(jī)場(chǎng)場(chǎng)面運(yùn)行的每一個(gè)航班作為MDP的Agent，每個(gè)Agent都攜帶位置和獎(jiǎng)勵(lì)信息。當(dāng)航班進(jìn)入滑行道時(shí)，Agent進(jìn)入活動(dòng)狀態(tài)，當(dāng)航班離開滑行道時(shí)，Agent進(jìn)入無(wú)效狀態(tài)。Agent的數(shù)量是固定的，但是每個(gè)時(shí)刻t活動(dòng)的Agent數(shù)目隨時(shí)間變化，在本文中，主要考慮靜態(tài)路徑規(guī)劃，故不考慮多駕航空器同時(shí)運(yùn)行的情況。

狀 態(tài) 集 合（State）：s∈S，狀 態(tài)是Agenti∈{1，…，N}在時(shí)刻t∈{1，…，T}的位置。當(dāng)網(wǎng)格化機(jī)場(chǎng)場(chǎng)面時(shí)，表示在時(shí)刻tAgent所處的網(wǎng)格單元。在時(shí)長(zhǎng)T范圍內(nèi)一個(gè)Agent占據(jù)所有單元格表示該航空器在機(jī)場(chǎng)場(chǎng)面的滑行路徑，共設(shè)置231個(gè)狀態(tài)。

動(dòng)作集合（Action）：a∈A，Agent在時(shí)刻t的動(dòng)作表示為at。以網(wǎng)格系統(tǒng)為例（如圖1所示），Agent可以從向上、向下、向左和向右四個(gè)動(dòng)作中選擇動(dòng)作，每個(gè)動(dòng)作會(huì)使得航空器沿滑行道方向移動(dòng)到下一個(gè)狀態(tài)中。

圖1 Action動(dòng)作示意Fig.1 The example of Action

獎(jiǎng)勵(lì)函數(shù)（Reward Function）：Agent采取某個(gè)動(dòng)作后的即時(shí)或者延時(shí)獎(jiǎng)勵(lì)值。對(duì)于RL，需要設(shè)計(jì)適當(dāng)?shù)莫?jiǎng)勵(lì)函數(shù)以評(píng)估Agent在給定狀態(tài)下采取某一動(dòng)作的價(jià)值。Agent在時(shí)刻t的獎(jiǎng)勵(lì)（以r t來表示）主要考慮兩個(gè)因素，即航班的全部動(dòng)作滿足時(shí)間約束的程度以及航班在滑行過程中是否遭遇障礙。Agent的獎(jiǎng)勵(lì)函數(shù)定義如下：

式（1）中，ξ＞0表示Agent在時(shí)刻t到達(dá)所需網(wǎng)格單元（或者狀態(tài)）s~時(shí)獲得的獎(jiǎng)勵(lì)；φ＞0表示代理移動(dòng)到不允許的網(wǎng)格單元時(shí)受到的負(fù)面激勵(lì)，如滑行道之外的單元格；每個(gè)Agent在時(shí)刻t的目標(biāo)是獲得總預(yù)期累計(jì)最大的獎(jiǎng)勵(lì)。

動(dòng)作選擇策略Pπ(s)→a：航空器Agent根據(jù)當(dāng)前狀態(tài)s來選擇即將進(jìn)行的動(dòng)作，可表現(xiàn)為a=π(s)或者π(a|s)=Pr(s′|s，a)，即在狀態(tài)s下執(zhí)行某個(gè)動(dòng)作的概率，s′表示下一個(gè)環(huán)境狀態(tài)。

1.2 強(qiáng)化學(xué)習(xí)模型

強(qiáng)化學(xué)習(xí)的基本原理：如果Agent的某一個(gè)行為策略獲得環(huán)境的正面獎(jiǎng)勵(lì)，Agent以后產(chǎn)生這個(gè)行為策略的趨勢(shì)便會(huì)加強(qiáng)。Agent的目標(biāo)是在每個(gè)離散狀態(tài)發(fā)現(xiàn)最優(yōu)策略以使期望的折扣獎(jiǎng)勵(lì)累計(jì)值最大。

結(jié)合強(qiáng)化學(xué)習(xí)構(gòu)建的航空器智能移動(dòng)模型，將學(xué)習(xí)看作試探評(píng)價(jià)過程。航空器Agent選擇一個(gè)動(dòng)作用于模擬機(jī)場(chǎng)環(huán)境，模擬機(jī)場(chǎng)環(huán)境接受該動(dòng)作后狀態(tài)發(fā)生變化，同時(shí)反饋航空器Agent一個(gè)即時(shí)或者延時(shí)的獎(jiǎng)勵(lì)或懲罰，航空器Agent根據(jù)環(huán)境當(dāng)前反饋選擇下一個(gè)動(dòng)作，選擇的原則是使航空器Agent得到正面獎(jiǎng)勵(lì)的概率增大。航空器Agent選擇的動(dòng)作不僅影響即時(shí)的獎(jiǎng)勵(lì)值，還會(huì)影響下一個(gè)狀態(tài)的獎(jiǎng)勵(lì)值以及最終的獎(jiǎng)勵(lì)值，即延時(shí)獎(jiǎng)勵(lì)值。強(qiáng)化學(xué)習(xí)模型框架如圖2所示。

圖2 航空器機(jī)場(chǎng)地面移動(dòng)強(qiáng)化學(xué)習(xí)模型框架Fig.2 The framework of aircraft airport ground model based on RL

基于累計(jì)獎(jiǎng)勵(lì)，引入貝爾曼最優(yōu)方程和最優(yōu)價(jià)值函數(shù)。

Bellman最優(yōu)方程［8］：

式中：γ為折扣因子，折扣因子表示對(duì)未來獎(jiǎng)勵(lì)的重視程度［9］；u*(s)為航空器Agent處于s狀態(tài)的長(zhǎng)期最優(yōu)化價(jià)值，即在s狀態(tài)下航空器Agent考慮到所有可能選擇的后續(xù)動(dòng)作，并且都選擇最大價(jià)值的動(dòng)作來執(zhí)行所帶來的長(zhǎng)期狀態(tài)價(jià)值；q*(s，a)為處于s狀態(tài)下選擇并執(zhí)行某個(gè)動(dòng)作后所帶來的長(zhǎng)期最優(yōu)價(jià)值，即在s狀態(tài)下航空器Agent選擇并執(zhí)行某一特定動(dòng)作后，假設(shè)在以后的所有狀態(tài)下進(jìn)行狀態(tài)更新時(shí)都選擇并執(zhí)行最大價(jià)值動(dòng)作所帶來的長(zhǎng)期動(dòng)作價(jià)值。

最優(yōu)價(jià)值函數(shù)［10］為所有最優(yōu)策略下價(jià)值函數(shù)的最大值。

式中：u(s)為所有狀態(tài)下最優(yōu)選擇策略下狀態(tài)價(jià)值目標(biāo)函數(shù)；q(s，a)為所有狀態(tài)下最優(yōu)選擇策略下動(dòng)作價(jià)值目標(biāo)函數(shù)。

本文目標(biāo)是輸出從起點(diǎn)到終點(diǎn)的智能決策路徑，路徑?jīng)Q策的依據(jù)是Agent在經(jīng)過學(xué)習(xí)的過程后，在每一個(gè)狀態(tài)選擇最大價(jià)值動(dòng)作進(jìn)行執(zhí)行。Bellman最優(yōu)方程計(jì)算了各狀態(tài)下動(dòng)作最大價(jià)值和狀態(tài)最大價(jià)值，最優(yōu)價(jià)值函數(shù)計(jì)算從起始狀態(tài)到終止?fàn)顟B(tài)的最大價(jià)值動(dòng)作和狀態(tài)的決策序列。

2 時(shí)序差分離線控制算法

時(shí)序差分離線控制算法Q-Learning［11］是一種基于機(jī)器學(xué)習(xí)的強(qiáng)化學(xué)習(xí)算法，Q-Learning算法的核心思想是學(xué)習(xí)一種最優(yōu)選擇策略，即指導(dǎo)Agent在什么情況下要采取什么行動(dòng)，該算法可以處理隨機(jī)轉(zhuǎn)換和獎(jiǎng)勵(lì)的問題，隨機(jī)轉(zhuǎn)換狀態(tài)采用ε-greedy策略［12］，該策略會(huì)設(shè)定一個(gè)ε∈(0，1)值，表示Agent有ε概率會(huì)選擇當(dāng)前最大價(jià)值動(dòng)作，有1-ε概率會(huì)隨機(jī)選擇除最大價(jià)值外的動(dòng)作。

對(duì)任何有限MDP問題，Q-Learning總能找到一種最優(yōu)的策略，即從當(dāng)前狀態(tài)開始，在當(dāng)前和所有后續(xù)狀態(tài)轉(zhuǎn)換中尋求最大總回報(bào)的一種策略。在給定無(wú)限探索時(shí)間和部分隨機(jī)策略的情況下，Q-Learning算法可以為任何給定MDP問題確定最佳動(dòng)作選擇策略。

在本文中，Q-Learning算法的目標(biāo)是輸出一組Agent到達(dá)終點(diǎn)獲得最終獎(jiǎng)勵(lì)的最優(yōu)決策序列，此決策序列中每一次狀態(tài)轉(zhuǎn)換均選擇當(dāng)前狀態(tài)最大價(jià)值動(dòng)作。為評(píng)估算法收斂性，算法迭代過程中計(jì)算每次迭代從起始狀態(tài)到終止?fàn)顟B(tài)所運(yùn)動(dòng)的次數(shù)，用計(jì)步器N表示。

對(duì)于迭代過程中狀態(tài)轉(zhuǎn)換時(shí)動(dòng)作價(jià)值更新，Q-Learning算法引入Q表更新公式［13］：

式中：α為學(xué)習(xí)效率。

Q-Learning算法流程包括四個(gè)步驟，算法流程如圖3所示。

圖3 Q-Learning算法流程Fig.3 The algorithm flow chart of Q-Learning

步驟一：初始化Q表，初始化狀態(tài)，設(shè)定參數(shù)集，導(dǎo)入模擬環(huán)境模型。

步驟二：智能體Agent從當(dāng)前狀態(tài)s出發(fā)，計(jì)算機(jī)隨機(jī)生成ε1∈(0，1)。

（1）若ε1≤ε，遍歷Q表，選擇Q表中最大價(jià)值動(dòng)作，若有多個(gè)最大價(jià)值動(dòng)作，則在此多個(gè)動(dòng)作中隨機(jī)選擇動(dòng)作；

（2）若ε1＞ε，則隨機(jī)選擇動(dòng)作。

步驟三：狀態(tài)更新至s′，根據(jù)公式（6）更新動(dòng)作價(jià)值，計(jì)步器N+1。

步驟四：智能體Agent與模擬環(huán)境進(jìn)行交互。

（1）獲得最終環(huán)境獎(jiǎng)勵(lì)，算法結(jié)束；

（2）未獲得最終環(huán)境獎(jiǎng)勵(lì)，返回步驟二。

3 仿真分析

調(diào)用Python中的標(biāo)準(zhǔn)TKGUI接口Tkinter模塊編寫?？诿捞m機(jī)場(chǎng)環(huán)境，用填充三角形方格代表停機(jī)位區(qū)域，黑色方格代表障礙以及非跑道滑行道部分的機(jī)場(chǎng)區(qū)域。

為考慮所建模型的實(shí)際意義，選擇以下兩組模型參數(shù)。

模型參數(shù)集一：在Agent運(yùn)動(dòng)過程中，主要考慮兩個(gè)管制員地面管制規(guī)則：（1）全跑道起飛；（2）靠近跑道的平行滑行道上航空器滑行方向一致。

獎(jiǎng)勵(lì)函數(shù)中，取跑道出口方格ξ=50，環(huán)境障礙方格φ=10。

Q表更新函數(shù)中，初始Q表中Q(s，a)=0，α=0.1，γ=0.9［14-15］，ε-greedy策略中ε=0.8。

仿真過程中迭代次數(shù)為200次。

模型參數(shù)集二：獎(jiǎng)勵(lì)函數(shù)中，取跑道出口方格ξ=50，環(huán)境障礙方格φ=10。

Q表更新函數(shù)中，初始Q表中Q(s，a)=0，α=0.1，γ=0.9，ε-greedy策略中ε=0.8。

仿真過程中迭代次數(shù)為200次。

3.1 數(shù)據(jù)結(jié)果及分析

算法經(jīng)過200次迭代后ε=1輸出的結(jié)果如圖4所示，ε=1表示在所有狀態(tài)下選擇所有動(dòng)作中最大價(jià)值動(dòng)作轉(zhuǎn)換狀態(tài)。圖4中實(shí)線表示考慮機(jī)場(chǎng)航空器地面滑行規(guī)則的滑行路徑，參數(shù)按照模型參數(shù)集一設(shè)置；虛線表示未考慮機(jī)場(chǎng)航空器地面滑行規(guī)則的滑行路徑，參數(shù)按照模型參數(shù)集二設(shè)置。

圖4 不同滑行規(guī)則下滑行路徑Fig.4 The taxiing path of different taxiing rules

從圖4可以看出：實(shí)線路徑中Agent從初始狀態(tài)出發(fā)，經(jīng)46次移動(dòng)到達(dá)跑道出口，虛線路徑中Agent從同一初始狀態(tài)出發(fā)，經(jīng)30次移動(dòng)到達(dá)跑道出口。兩者相比，實(shí)線路徑Agent移動(dòng)次數(shù)雖然增加，但從機(jī)場(chǎng)實(shí)際運(yùn)行規(guī)范來看，虛線路徑并不符合機(jī)場(chǎng)實(shí)際運(yùn)行要求，實(shí)線路徑比較符合實(shí)際滑行路徑。因此，考慮滑行規(guī)則的機(jī)場(chǎng)地面航空器強(qiáng)化學(xué)習(xí)移動(dòng)模型更接近實(shí)際，仿真結(jié)果有較高的實(shí)際價(jià)值。

兩組模型參數(shù)的算法迭代曲線如圖5所示，橫軸表示迭代次數(shù)，縱軸表示每一次迭代算法輸出計(jì)步器N的值，可以看出：在考慮了航空器地面滑行規(guī)則后，相當(dāng)于為航空器智能體添加約束，參數(shù)集二的曲線經(jīng)過56次迭代后趨于收斂，參數(shù)集一的曲線經(jīng)過25次迭代后趨于收斂，算法的收斂速度加快。參數(shù)集一曲線收斂后，N值趨近于理論計(jì)算值66，說明結(jié)果真實(shí)有效。

圖5 不同滑行規(guī)則下算法迭代曲線Fig.5 The algorithm iteration curve of different taxiing rules

3.2 ε-greedy策略貪婪性分析

由ε-greedy策略定義可知，ε值的大小影響Agent對(duì)環(huán)境的探索情況。設(shè)置ε={0.4，0.6，0.8}三個(gè)值探究ε對(duì)于算法影響，其余參數(shù)按照模型參數(shù)集一設(shè)置，算法曲線收斂后計(jì)步器N結(jié)果如表1所示，其中理論值的計(jì)算規(guī)則為2（1-ε）N。

表1 計(jì)步器N理論值實(shí)際值Table 1 Theoretical value and actual value of step counter N

ε貪婪性對(duì)比圖如圖6所示，其中紅線代表ε=0.8時(shí)的迭代結(jié)果，算法收斂后曲線趨近于定值66；綠線代表ε=0.6的結(jié)果，算法收斂后曲線趨近于定值90；粉線代表ε=0.4的實(shí)驗(yàn)結(jié)果，算法收斂后曲線趨近于定值120。

圖6 不同ε值貪婪性對(duì)比Fig.6 Comparison greedy of differentεvalues

從圖6可以看出：ε對(duì)算法迭代速度影響不大，主要影響了算法曲線收斂后計(jì)步器N值的波動(dòng)情況。

3.3 模型對(duì)比分析

相較于傳統(tǒng)的整數(shù)線性規(guī)劃模型、有向圖及Petri網(wǎng)模型，本文所構(gòu)建的機(jī)場(chǎng)地面航空器移動(dòng)強(qiáng)化學(xué)習(xí)模型具備以下優(yōu)點(diǎn)：

（1）模型無(wú)需人工指派停機(jī)位、滑行道和跑道等地面滑行資源，通過環(huán)境狀態(tài)轉(zhuǎn)換設(shè)定獎(jiǎng)勵(lì)函數(shù)的方式由智能體自主識(shí)別航空器可滑行區(qū)域，智能化程度較高。

（2）模型基于強(qiáng)化學(xué)習(xí)算法構(gòu)建，航空器Agent可根據(jù)不同的模擬環(huán)境學(xué)習(xí)生成適用于不同機(jī)場(chǎng)的靜態(tài)路徑，普適性較強(qiáng)。

4 結(jié) 論

（1）本文所構(gòu)建的航空器機(jī)場(chǎng)地面移動(dòng)強(qiáng)化學(xué)習(xí)模型，通過航空器Agent與機(jī)場(chǎng)模擬環(huán)境之間的交互，實(shí)現(xiàn)了從停機(jī)位到跑道出口智能靜態(tài)路徑規(guī)劃。

（2）模型規(guī)劃的路徑與機(jī)場(chǎng)航空器實(shí)際滑行路徑相符，能輔助塔臺(tái)管制員進(jìn)行初始靜態(tài)路徑規(guī)劃，具有較高的應(yīng)用價(jià)值。

本文主要考慮航空器Agent與機(jī)場(chǎng)模擬環(huán)境之間的交互，并未考慮時(shí)間序列下多航空器Agent運(yùn)行之間的沖突交互，這是下一步的研究?jī)?nèi)容。