疏利生，李桂芳，嵇勝

（南京航空航天大學民航學院，南京210016）

0 引 言

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

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

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

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

1 機場地面航空器移動強化學習模型

按照機場真實環(huán)境轉化過程，航空器移動到下一個位置與上個位置有關，還與之前的位置有關，這一模型轉換非常復雜。因此本文對強化學習的模擬機場環(huán)境轉化模型進行簡化，簡化的方法就是引入狀態(tài)轉化的一階馬爾科夫性，也就是智能體（航空器）移動到下一個位置的概率僅和上個位置有關，與之前的位置無關。

1.1 馬爾科夫決策過程

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

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

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

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

圖1 Action動作示意Fig.1 The example of Action

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

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

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

1.2 強化學習模型

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

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

圖2 航空器機場地面移動強化學習模型框架Fig.2 The framework of aircraft airport ground model based on RL

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

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

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

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

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

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

2 時序差分離線控制算法

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

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

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

對于迭代過程中狀態(tài)轉換時動作價值更新，Q-Learning算法引入Q表更新公式［13］：

式中：α為學習效率。

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

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

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

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

（1）若ε1≤ε，遍歷Q表，選擇Q表中最大價值動作，若有多個最大價值動作，則在此多個動作中隨機選擇動作；

（2）若ε1＞ε，則隨機選擇動作。

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

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

（1）獲得最終環(huán)境獎勵，算法結束；

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

3 仿真分析

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

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

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

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

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

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

模型參數(shù)集二：獎勵函數(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ù)結果及分析

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

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

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

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

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

3.2 ε-greedy策略貪婪性分析

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

表1 計步器N理論值實際值Table 1 Theoretical value and actual value of step counter N

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

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

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

3.3 模型對比分析

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

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

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

4 結 論

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

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

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