基于期望Sarsa 的進(jìn)港航班排序模型研究

何愛平，張建偉，韓云祥

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

0 引言

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

現(xiàn)有的進(jìn)港航班排序算法大多為基于優(yōu)先級的算法，如先到先服務(wù)算法（FCFS）[2]，同時(shí)還包括啟發(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)港序列可以抽象為該過程。現(xiàn)有的強(qiáng)化學(xué)習(xí)進(jìn)港排序模型都是基于Q 學(xué)習(xí)算法和貪心策略的模型，由于Q 學(xué)習(xí)算法使用了貪心策略，可能會(huì)存在“過高估計(jì)”的問題，同時(shí)也缺乏未來狀態(tài)的預(yù)見性，而期望Sarsa 算法在策略上考慮了全部的歷史動(dòng)作，訓(xùn)練更加穩(wěn)定。通過智能化的方法對進(jìn)港航班實(shí)施排序，不僅能夠縮減延誤時(shí)間、保障旅客安全、提升管制效率，同時(shí)也極大地減少了經(jīng)濟(jì)開銷和管制人力資源。

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

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

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

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

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

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

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

其中，R'表示下一時(shí)刻與環(huán)境交互獲得的獎(jiǎng)勵(lì)值，α 為學(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)境信息。時(shí)序差分算法（TD）是一種免模型算法，根據(jù)值函數(shù)更新策略和動(dòng)作選取策略是否一致分為兩類：在線策略和離線策略，如Sarsa 算法為在線策略學(xué)習(xí)方式，而Q 學(xué)習(xí)算法為離線策略學(xué)習(xí)方式。

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

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

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

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

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

（2）同一進(jìn)場航向上不允許超越。同一股交通流的航空器相互交換位置，叫做超越。管制員一般不愿意讓航空器進(jìn)行超越，由于這種操作極易引發(fā)事故，并且需要花費(fèi)大量時(shí)間和人力對該航空器進(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)整，如實(shí)施延誤動(dòng)作調(diào)整航班進(jìn)港的時(shí)間，以達(dá)到整體序列延誤最小，且燃油消耗最少為目標(biāo)進(jìn)行優(yōu)化。環(huán)境的組成基于真實(shí)的進(jìn)港數(shù)據(jù)及其他約束條件，包括航班的ETA（預(yù)計(jì)到達(dá)時(shí)間）、尾流類型、機(jī)型等。終端區(qū)管制移交方式如圖2 所示，首先終端區(qū)的進(jìn)港航空器會(huì)從不同的進(jìn)場航段飛至IAF（起始進(jìn)近定位點(diǎn)），完成進(jìn)場任務(wù)，隨后由IAF 飛至IF（中間進(jìn)近定位點(diǎn)），最后根據(jù)排序結(jié)果選擇相應(yīng)的FAF（最終進(jìn)近定位點(diǎn)），等待落地或者復(fù)飛，完成進(jìn)近任務(wù)。

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

2.2 狀態(tài)與動(dòng)作

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

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

2.3 獎(jiǎng)勵(lì)函數(shù)

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

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

2.4 期望Sarsa算法

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

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

3 實(shí)驗(yàn)結(jié)果分析

3.1 實(shí)驗(yàn)平臺及數(shù)據(jù)來源

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

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

遺傳算法在進(jìn)港航班排序上迭代優(yōu)化的收斂情況如圖3 所示，在1180 代時(shí)算法模型已經(jīng)收斂，目標(biāo)函數(shù)最優(yōu)值已到達(dá)0.78，對比其他算法計(jì)算得到的經(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)用上的效果對比，分別從總延誤時(shí)間、最晚落地時(shí)間、延誤經(jīng)濟(jì)開銷以及程序運(yùn)行時(shí)間四個(gè)維度進(jìn)行對比。啟發(fā)式算法中，遺傳算法的運(yùn)行時(shí)間最長但消耗的總經(jīng)濟(jì)開銷最少。另外，先到先服務(wù)算法雖然運(yùn)行時(shí)間最短，但經(jīng)濟(jì)開銷較大。Q 學(xué)習(xí)算法在經(jīng)濟(jì)開銷和運(yùn)行時(shí)間上均表現(xiàn)較優(yōu)，但在經(jīng)濟(jì)指標(biāo)上遜色于遺傳算法。對比Q 學(xué)習(xí)算法，期望Sarsa 算法由于其貝爾曼方程中的一個(gè)差分項(xiàng)需要計(jì)算后續(xù)狀態(tài)Q 值的期望值，計(jì)算量增加，導(dǎo)致該算法的運(yùn)行時(shí)間較長，但得到的排序結(jié)果在經(jīng)濟(jì)開銷上優(yōu)于Q 學(xué)習(xí)算法，在一定程度上證實(shí)了期望Sarsa 算法的性能優(yōu)于采用最優(yōu)Q 值的Q學(xué)習(xí)算法[13]。