何愛平，張建偉，韓云祥

（1.四川大學(xué)視覺合成圖形圖像技術(shù)國防重點學(xué)科實驗室，成都610065；2.四川大學(xué)計算機(jī)學(xué)院，成都610065）

0 引言

2016 年我國機(jī)場旅客吞吐量突破1 億人次，完成飛機(jī)起降923.8 萬架次，2017 年我國機(jī)場旅客吞吐量達(dá)到11.48 億人次，起降架次達(dá)到1024.9 萬架次，旅客吞吐量、飛機(jī)起降架次逐年增長[1]。如此龐大的載運量使得我國的空域資源與交通流量沖突日益突出。機(jī)場終端區(qū)內(nèi)一般具有多條航路交叉匯聚、空域狹窄、航班密度大、結(jié)構(gòu)復(fù)雜、運行難度大等特點，嚴(yán)重影響到機(jī)場終端區(qū)的運行效率。為了盡量減少飛機(jī)因不必要的等待造成的延誤，前人提出了各種終端區(qū)流量管理手段，進(jìn)場排序就是其中的一種，如何安全高效地指揮進(jìn)港航班落地是一項意義重大的任務(wù)。

現(xiàn)有的進(jìn)港航班排序算法大多為基于優(yōu)先級的算法，如先到先服務(wù)算法（FCFS）[2]，同時還包括啟發(fā)式算法，如遺傳算法（GA）[3-4]、蟻群算法(ACO)[5]、粒子群算法（PSO）[6]、蒙特卡洛模擬[7]等。另外也有少數(shù)學(xué)者采用強(qiáng)化學(xué)習(xí)的研究方法進(jìn)行了相關(guān)探索[8-9]。FCFS 雖然在一定程度上保證了航班進(jìn)港排序的公平性，但該算法可能導(dǎo)致大面積的航班延誤等待，造成直接的經(jīng)濟(jì)損失。這類啟發(fā)式算法雖然能夠搜索到較優(yōu)的進(jìn)港排序序列，但搜索的效率不佳，并且每次搜索得到的結(jié)果可能不同，最壞的情況下甚至需要對進(jìn)港序列進(jìn)行大幅度的調(diào)整，這不僅提高了管制難度，還增加了調(diào)整的開銷。強(qiáng)化學(xué)習(xí)屬于機(jī)器學(xué)習(xí)的分支，建立在馬爾科夫決策過程（MDP）假設(shè)之上，擅于解決序列決策問題，而確定進(jìn)港序列可以抽象為該過程?，F(xiàn)有的強(qiáng)化學(xué)習(xí)進(jìn)港排序模型都是基于Q 學(xué)習(xí)算法和貪心策略的模型，由于Q 學(xué)習(xí)算法使用了貪心策略，可能會存在“過高估計”的問題，同時也缺乏未來狀態(tài)的預(yù)見性，而期望Sarsa 算法在策略上考慮了全部的歷史動作，訓(xùn)練更加穩(wěn)定。通過智能化的方法對進(jìn)港航班實施排序，不僅能夠縮減延誤時間、保障旅客安全、提升管制效率，同時也極大地減少了經(jīng)濟(jì)開銷和管制人力資源。

1 強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)啟發(fā)于行為主義心理學(xué)，是機(jī)器學(xué)習(xí)中產(chǎn)生的一種交互式學(xué)習(xí)方法的分支，用于解決一系列滿足MDP 條件的序列決策問題。MDP 描述了一個智能體（Agent）采取行動（Action）從而改變自身狀態(tài)（State）獲得獎勵（Reward），與環(huán)境（Environment）不斷發(fā)生交互的過程。強(qiáng)化學(xué)習(xí)的基本框架如圖1 所示。

圖1 強(qiáng)化學(xué)習(xí)基本框架圖

強(qiáng)化學(xué)習(xí)的核心要素包括狀態(tài)集S、動作集A 和獎勵反饋R，用St表示t 時刻環(huán)境狀態(tài)集中某一狀態(tài)，At表示t 時刻Agent 采取的動作，At∈A，Rt表示t 時刻Agent 在狀態(tài)St采取的動作At對應(yīng)的獎勵。MDP滿足馬爾科夫假設(shè)（Markov），即轉(zhuǎn)化到下一個狀態(tài)s'的概率僅與上一個狀態(tài)s 有關(guān)，與之前的狀態(tài)無關(guān)。MDP 可以用一個五元組來表示，定義了一個完備的強(qiáng)化學(xué)習(xí)模型：

其中P 表示狀態(tài)轉(zhuǎn)移，定義了兩種狀態(tài)之間的轉(zhuǎn)移概率，γ 表示折扣系數(shù)（0 ≤γ ≤1），定義了未來獎勵的對當(dāng)前狀態(tài)的重要程度。狀態(tài)轉(zhuǎn)移描述了從狀態(tài)s執(zhí)行動作a，獲得獎勵r 并轉(zhuǎn)移到狀態(tài)s'的概率，用公式表示如下：

強(qiáng)化學(xué)習(xí)采用累積獎勵機(jī)制進(jìn)行學(xué)習(xí)，為了評估Agent 所處環(huán)境以及采取對應(yīng)動作的好壞，引入狀態(tài)值函數(shù)Vπ(s)和動作值函數(shù)Qπ(s,a)。值函數(shù)評估的指標(biāo)為在相同策略下累計獎勵的期望值，采用期望的形式是由于累計獎賞函數(shù)為一個隨機(jī)變量，無法進(jìn)行確定性描述。值函數(shù)的數(shù)學(xué)表達(dá)式如下：

其中π 表示策略函數(shù)，定義了狀態(tài)到動作的映射關(guān)系。值函數(shù)統(tǒng)一遵循貝爾曼期望方程（Bellman Equation）的約束，通過該方程持續(xù)迭代優(yōu)化到達(dá)策略最優(yōu)的目的，如Q 學(xué)習(xí)的貝爾曼方程表示如下：

其中，R'表示下一時刻與環(huán)境交互獲得的獎勵值，α 為學(xué)習(xí)速率（0 ＜α ≤1）。在多數(shù)應(yīng)用場景下，模型的狀態(tài)轉(zhuǎn)移矩陣是未知的，傳統(tǒng)的基于模型的學(xué)習(xí)方式無法解決問題，而免模型的學(xué)習(xí)方式可以直接從歷史的軌跡片段中學(xué)習(xí)，不需要了解模型的狀態(tài)轉(zhuǎn)移和完備的環(huán)境信息。時序差分算法（TD）是一種免模型算法，根據(jù)值函數(shù)更新策略和動作選取策略是否一致分為兩類：在線策略和離線策略，如Sarsa 算法為在線策略學(xué)習(xí)方式，而Q 學(xué)習(xí)算法為離線策略學(xué)習(xí)方式。

針對環(huán)境模型狀態(tài)、動作有限的問題，一般通過表格型強(qiáng)化學(xué)習(xí)方式進(jìn)行建模，通過維護(hù)一個有限的狀態(tài)-動作Q 表，記錄每種狀態(tài)-動作對的Q 值，采用不同的更新策略結(jié)合公式（4）進(jìn)行迭代學(xué)習(xí)，最終達(dá)到強(qiáng)化的目的。

2 進(jìn)港航班排序模型

基于免模型的進(jìn)港航班排序強(qiáng)化學(xué)習(xí)模型包括三個部分，環(huán)境與Agent 定義、狀態(tài)與動作設(shè)計、獎勵函數(shù)。另外，對比離線策略學(xué)習(xí)方式的Q 學(xué)習(xí)算法，采用在線策略學(xué)習(xí)方式的期望-Sarsa 算法進(jìn)行建模。考慮相關(guān)約束條件并以延誤成本、延誤時間等因素為優(yōu)化指標(biāo)，建立強(qiáng)化學(xué)習(xí)模型對終端區(qū)進(jìn)港航班排序。考慮安全因素方面，航空器在進(jìn)行排序的過程中，必須滿足以下約束：

（1）尾流間隔。由于前機(jī)兩個翼尖處形成的兩個旋渦，后機(jī)若進(jìn)入其中，容易誘導(dǎo)橫滾、損失高度、爬升率減小或增大等危險。國內(nèi)采用的尾流間隔標(biāo)準(zhǔn)如表1 所示，一種為時間間隔（單位為分鐘），另一種方法為距離間隔（如海里）；

表1 國內(nèi)尾流間隔標(biāo)準(zhǔn)（單位：min）

（2）同一進(jìn)場航向上不允許超越。同一股交通流的航空器相互交換位置，叫做超越。管制員一般不愿意讓航空器進(jìn)行超越，由于這種操作極易引發(fā)事故，并且需要花費大量時間和人力對該航空器進(jìn)行監(jiān)視和管控，但允許不同進(jìn)場航向上的航班順序調(diào)換；

（3）為了減少強(qiáng)化學(xué)習(xí)模型中狀態(tài)維度的大小，設(shè)置航班的延誤上限為15 分鐘。

2.1 環(huán)境與Agent

進(jìn)港排序Agent 為排序的核心主體，對終端區(qū)進(jìn)港航班的序列進(jìn)行調(diào)整，如實施延誤動作調(diào)整航班進(jìn)港的時間，以達(dá)到整體序列延誤最小，且燃油消耗最少為目標(biāo)進(jìn)行優(yōu)化。環(huán)境的組成基于真實的進(jìn)港數(shù)據(jù)及其他約束條件，包括航班的ETA（預(yù)計到達(dá)時間）、尾流類型、機(jī)型等。終端區(qū)管制移交方式如圖2 所示，首先終端區(qū)的進(jìn)港航空器會從不同的進(jìn)場航段飛至IAF（起始進(jìn)近定位點），完成進(jìn)場任務(wù)，隨后由IAF 飛至IF（中間進(jìn)近定位點），最后根據(jù)排序結(jié)果選擇相應(yīng)的FAF（最終進(jìn)近定位點），等待落地或者復(fù)飛，完成進(jìn)近任務(wù)。

圖2 終端區(qū)管制移交方式

2.2 狀態(tài)與動作

強(qiáng)化學(xué)習(xí)中智能體的狀態(tài)描述了智能體可感知環(huán)境的一部分，合適的定義可加快智能體的學(xué)習(xí)速度，同時，狀態(tài)與動作設(shè)置的好壞直接影響了模型的性能。排序智能體的狀態(tài)空間定義為以ETA 為基準(zhǔn)的提前或者延后15 分鐘范圍內(nèi)的時間集合，動作空間定義為排序智能體給出的提前/延誤時間，用公式表示如下：

狀態(tài)集S 中，ETAi表示第i 架航空器的預(yù)計到達(dá)時間，即圖2 中的IAF 點，智能體根據(jù)設(shè)定的獎勵函數(shù)采取最佳的動作，用a 表示，即延誤/提前的時間（設(shè)定時間跨度為15 分鐘），n 表示設(shè)定的提前或延誤的分鐘數(shù)。

2.3 獎勵函數(shù)

強(qiáng)化學(xué)習(xí)航班進(jìn)港排序的獎勵函數(shù)主要分為總延誤時間、經(jīng)濟(jì)開銷、最晚落地時間獎勵項三個部分。原則上獎勵函數(shù)設(shè)計既要滿足計算盡可能簡單，又要滿足能全面評估智能體的學(xué)習(xí)指標(biāo)這兩個條件，而對于航班進(jìn)港排序最直接反映進(jìn)港航班序列好壞的指標(biāo)之一就是總延誤時間，其次為不同機(jī)型的航班因延誤而產(chǎn)生的經(jīng)濟(jì)總開銷。另外，最晚落地時間指標(biāo)表明了整體的進(jìn)港時間長短，與總延誤時間不同的是最晚落地時間并不總是簡單地將總延誤時間進(jìn)行加和，由于多個進(jìn)場航向的存在，在時間上有重疊關(guān)系。依據(jù)上面的描述，將獎勵函數(shù)設(shè)計為如下的表達(dá)式：

其中，D 表示總延誤時間，C 表示總經(jīng)濟(jì)開銷，T表示最晚落地時間的獎勵項，ρ、σ 與τ 為超參數(shù)，且滿足ρ+σ+τ=1，分別表示不同指標(biāo)下的權(quán)重因子。各部分具體的定義如下，CTAi表示第i 架航班的排序落地時間，ηi表示該航班的燃油消耗經(jīng)濟(jì)指標(biāo)，具體定義在3.2 小節(jié)說明。最晚落地時間獎勵項對整體的進(jìn)港時間進(jìn)行獎勵，時間越短獎勵值越大。

2.4 期望Sarsa算法

Q 學(xué)習(xí)與期望Sarsa 算法的不同點在于行動策略與評估策略的異同，前者的行動策略和評估策略均采用貪婪算法，如在評估策略上每次選擇下一狀態(tài)的可選集中使得Q 值最大對應(yīng)的動作，而后者考慮了下一狀態(tài)的整個可選集，將Q 值的期望作為目標(biāo)值。期望Sarsa 的貝爾曼方程如下：

智能體的行動策略采用如下的公式進(jìn)行選擇，即當(dāng)前的動作若與貪婪算法選擇的動作一致，則以一定概率執(zhí)行該動作，否則以設(shè)定的概率選擇非貪婪算法執(zhí)行該動作。其中A 表示動作集的大小，A_greedy 表示采用當(dāng)前動作與貪婪算法選擇的動作命中的次數(shù)，?表示貪婪度，即以貪婪算法作為行動策略的概率。

3 實驗結(jié)果分析

3.1 實驗平臺及數(shù)據(jù)來源

本實驗采用Python 3.6 實現(xiàn)，硬件平臺為Windows10×64 位系統(tǒng)，內(nèi)存為24G，處理器為Intel Core i7-7700@3.6GHz CPU。實驗數(shù)據(jù)來源于flightradar24網(wǎng)站提供的真實進(jìn)港數(shù)據(jù)，選取成都雙流機(jī)場2020 年10 月晚間高峰時段的20 架進(jìn)港航班的數(shù)據(jù)。數(shù)據(jù)包括航班號、機(jī)型號、尾流類型、預(yù)計到達(dá)時間、后續(xù)航班、實際到達(dá)時間。

3.2 模型評價指標(biāo)

宏觀上分析，根據(jù)《2019 年民航行業(yè)發(fā)展統(tǒng)計公報》[10]對不正常航班的分類統(tǒng)計結(jié)果顯示，導(dǎo)致航班延誤的主要因素為天氣原因，其次為航空公司的原因和其他原因，具體如表2 所示。

表2 2019 年航班不正常原因分類統(tǒng)計

從一個航班的完整運行過程上來分析，造成航班延誤的因素是多方面的，其中包括起飛前的關(guān)艙延誤、地面滑行延誤、空管起飛延誤、航路延誤、空管著陸等待延誤、流量控制延誤等[11]。進(jìn)港航班排序模型的評價指標(biāo)除了總延誤時間外，還應(yīng)考慮這些延誤帶來的經(jīng)濟(jì)開銷，而不同類型的航班在不同程度的延誤情況下產(chǎn)生的開銷也不同，因此精確計算延誤開銷尚存在困難。武喜萍等人[9]根據(jù)航班的類型確定延誤開銷水平，將重型機(jī)、中型機(jī)、輕型機(jī)的經(jīng)濟(jì)開銷分別量化為4000元/小時、3000 元/小時、200 元/小時。楊晶妹[12]從機(jī)場容量方面考慮，將該時段降落航班的數(shù)量作為評估指標(biāo)，即排序后最后一個航班的實際降落時間與第一個航班的降落時間差越小越好。

3.3 實驗結(jié)果分析

實驗主要對比了期望Sarsa 算法與強(qiáng)化學(xué)習(xí)算法，以及常規(guī)的啟發(fā)式算法。其中強(qiáng)化學(xué)習(xí)航班進(jìn)港排序期望Sarsa 算法中的相關(guān)超參數(shù)設(shè)置如表3 所示。

表3 期望Sarsa 模型超參數(shù)設(shè)置

以延誤時間、最晚落地時間、延誤開銷和運行時間作為比對指標(biāo)進(jìn)行實驗，得到不同啟發(fā)式算法與強(qiáng)化學(xué)習(xí)算法的對比結(jié)果如表4 所示。

表4 航空器進(jìn)港排序算法結(jié)果對比

遺傳算法在進(jìn)港航班排序上迭代優(yōu)化的收斂情況如圖3 所示，在1180 代時算法模型已經(jīng)收斂，目標(biāo)函數(shù)最優(yōu)值已到達(dá)0.78，對比其他算法計算得到的經(jīng)濟(jì)開銷結(jié)果也表明遺傳算法在該指標(biāo)上具有一定的優(yōu)越性。

圖3 遺傳算法在航班進(jìn)港排序上的迭代優(yōu)化收斂結(jié)果

4 結(jié)語

本文給出了基于強(qiáng)化學(xué)習(xí)算法期望Sarsa 和Q 學(xué)習(xí)算法以及常用的啟發(fā)式算法在航空器進(jìn)港排序應(yīng)用上的效果對比，分別從總延誤時間、最晚落地時間、延誤經(jīng)濟(jì)開銷以及程序運行時間四個維度進(jìn)行對比。啟發(fā)式算法中，遺傳算法的運行時間最長但消耗的總經(jīng)濟(jì)開銷最少。另外，先到先服務(wù)算法雖然運行時間最短，但經(jīng)濟(jì)開銷較大。Q 學(xué)習(xí)算法在經(jīng)濟(jì)開銷和運行時間上均表現(xiàn)較優(yōu)，但在經(jīng)濟(jì)指標(biāo)上遜色于遺傳算法。對比Q 學(xué)習(xí)算法，期望Sarsa 算法由于其貝爾曼方程中的一個差分項需要計算后續(xù)狀態(tài)Q 值的期望值，計算量增加，導(dǎo)致該算法的運行時間較長，但得到的排序結(jié)果在經(jīng)濟(jì)開銷上優(yōu)于Q 學(xué)習(xí)算法，在一定程度上證實了期望Sarsa 算法的性能優(yōu)于采用最優(yōu)Q 值的Q學(xué)習(xí)算法[13]。