張?jiān)凭?，?昊，王 帥，孟 斌

(1.鄭州航空工業(yè)管理學(xué)院民航學(xué)院，河南 鄭州 450046;2.河海大學(xué)，江蘇 南京 211100）

0 引 言

航空器滑行路徑規(guī)劃是建設(shè)智慧機(jī)場(chǎng)的重要一環(huán)，也是保證航空器在機(jī)場(chǎng)安全高效運(yùn)行的核心，但我國(guó)在智慧機(jī)場(chǎng)建設(shè)方面仍處于起步階段，國(guó)內(nèi)大多數(shù)機(jī)場(chǎng)仍在使用傳統(tǒng)的人工機(jī)坪管制方法。傳統(tǒng)的人工調(diào)度成本高昂，效率低下，而利用計(jì)算機(jī)輔助的場(chǎng)面滑行路徑規(guī)劃可以更加清晰地建立和實(shí)施場(chǎng)面滑行計(jì)劃，對(duì)建設(shè)智慧機(jī)場(chǎng)和綠色機(jī)場(chǎng)具有重要意義。

場(chǎng)面航空器滑行路徑規(guī)劃問(wèn)題是一個(gè)研究熱點(diǎn)，早有學(xué)者對(duì)此進(jìn)行了相關(guān)研究。路徑規(guī)劃可分為靜態(tài)路徑規(guī)劃和動(dòng)態(tài)路徑規(guī)劃，傳統(tǒng)算法可以滿足靜態(tài)路徑規(guī)劃要求，而動(dòng)態(tài)路徑規(guī)劃則需對(duì)算法進(jìn)行改進(jìn)。李志龍［1］考慮將航空器沖突熱點(diǎn)加入路徑規(guī)劃的約束條件，提出了一種基于沖突熱點(diǎn)等級(jí)劃分的動(dòng)態(tài)路徑規(guī)劃算法。當(dāng)場(chǎng)面沖突等級(jí)值相加高于最低閾值時(shí)，使用改進(jìn)的Q-learning 路徑規(guī)劃算法進(jìn)行路徑規(guī)劃，否則采用改進(jìn)的A*路徑規(guī)劃算法。當(dāng)航空器在滑行中感知到?jīng)_突時(shí)，則使用Q-learning算法進(jìn)行路徑調(diào)整。王玉婷［2］改進(jìn)了傳統(tǒng)的Dijkstra算法，引入了靜態(tài)路徑庫(kù)的預(yù)先選定，并將其作為動(dòng)態(tài)規(guī)劃路由路徑的一種可行方案，從而獲得最優(yōu)路由路徑。馮廣洪［3］建立了航空器地面滑行路徑多目標(biāo)優(yōu)化模型，以機(jī)場(chǎng)航空器地面滑行總時(shí)間最少和航空器滑行油耗最小為最優(yōu)目標(biāo)，并采用多目標(biāo)A*算法對(duì)模型進(jìn)行求解驗(yàn)證。劉成［4］在基于Petri 網(wǎng)模型的基礎(chǔ)上，將遺傳算法與Petri 融合，有效地對(duì)進(jìn)離港滑行路徑進(jìn)行合理規(guī)劃。邱夢(mèng)琦［5］在航班滑行路徑規(guī)劃中，進(jìn)一步利用Petri 網(wǎng)模型，并結(jié)合啟發(fā)式算法和模擬退火算法，進(jìn)行滑行路徑的優(yōu)化。Kawabe Tomoya［6］提出了結(jié)合強(qiáng)化學(xué)習(xí)算法和A*算法的靈活路徑規(guī)劃方法，該方法使用Q-learning 算法來(lái)避免沖突，使用有限狀態(tài)空間的離線學(xué)習(xí)來(lái)縮短總的學(xué)習(xí)時(shí)間。每個(gè)智能體都使用A*算法獨(dú)立尋找最短路徑，并利用Q學(xué)習(xí)來(lái)避免碰撞。

強(qiáng)化學(xué)習(xí)無(wú)須完善的先驗(yàn)知識(shí)，航空器面對(duì)陌生的機(jī)場(chǎng)場(chǎng)面環(huán)境能夠通過(guò)與環(huán)境的動(dòng)態(tài)交互自主獲得最佳決策行為。因此，基于強(qiáng)化學(xué)習(xí)的場(chǎng)面航空器滑行系統(tǒng)，能減少飛機(jī)的運(yùn)行成本，提高機(jī)場(chǎng)的資源利用率以及確保外界環(huán)境的安全，同時(shí)，還有助于減少對(duì)環(huán)境的污染。本文針對(duì)新鄭機(jī)場(chǎng)進(jìn)離港航空器路徑規(guī)劃進(jìn)行研究，構(gòu)建基于改進(jìn)SARSA算法的路徑規(guī)劃方法。仿真結(jié)果表明改進(jìn)的SARSA 算法收斂速度更快，能夠?yàn)楹娇掌骰幸?guī)劃出安全路徑。

1 模型構(gòu)建

1.1 問(wèn)題描述

靜態(tài)規(guī)劃問(wèn)題被表述為整數(shù)規(guī)劃問(wèn)題。在解決航空器靜態(tài)路徑規(guī)劃時(shí)，首先要給定參數(shù)，它是由初始節(jié)點(diǎn)組成的一組任務(wù)集合Rr和目標(biāo)節(jié)點(diǎn)集合Mr組成。對(duì)于任務(wù)r，需要考慮場(chǎng)面系統(tǒng)布局G=（V，E），以及航空器集和H。其中二進(jìn)制變量為，它表示當(dāng)航空器k在時(shí)間t從柵格i移動(dòng)到柵格j時(shí)取1，否則取0。

該靜態(tài)問(wèn)題的目標(biāo)是最小化滑行時(shí)間σk,r，其定義為航空器k執(zhí)行滑行任務(wù)r從初始柵格Rr到目標(biāo)柵格Mr的時(shí)間，如果航空器k從開(kāi)始Rr到達(dá)目標(biāo)柵格Mr則取1，否則為0。該規(guī)劃目的在于為航空器找到一條無(wú)沖突的路線。以下為最小化目標(biāo)函數(shù)。

其中，k代表航空器索引，r代表航空器滑行任務(wù)，可由下面的公式表示，N是所有可以從柵格i移動(dòng)的所有柵格的集合。

式（2）表明航空器任務(wù)r的滑行時(shí)間等于后面變量的時(shí)間總和，該變量在任務(wù)未完成時(shí)為1，否則為0。式（3）確保一旦航空器k從初始點(diǎn)啟動(dòng)變量取1。式（4）要求航空器k未到達(dá)目標(biāo)柵格Mr則滿足δk,r,t≤δk,r,t+1。由式（5）可知，當(dāng)航空器k到達(dá)目的地時(shí)δk,r,t取0。

每架航空器的滑行滿足下列限制：

約束式（6）和式（7）由環(huán)境限制，表明航空器能從i柵格滑行到任意可以到達(dá)的柵格且在一定的時(shí)間內(nèi)航空器只能出現(xiàn)在一個(gè)柵格。式（8）和式（9）分別表示避免航空器之間的碰撞和禁止同時(shí)在一個(gè)滑行道滑行。

1.2 機(jī)場(chǎng)環(huán)境建模

機(jī)場(chǎng)環(huán)境建模是航空器滑行路徑規(guī)劃的核心。建模時(shí)，將機(jī)場(chǎng)環(huán)境信息抽象化為模型化信息，從而將場(chǎng)面環(huán)境劃分為可滑行區(qū)域和不可滑行區(qū)域［7]，柵格化地圖是研究路徑規(guī)劃的常用方法之一。柵格化可以確保連續(xù)的路徑離散化為對(duì)柵格的選擇，且離散化后的信息方便儲(chǔ)存和維護(hù)。本文采用柵格法對(duì)機(jī)場(chǎng)環(huán)境建模，具體情況如下。

結(jié)合機(jī)場(chǎng)圖，采用20*20 的柵格對(duì)機(jī)場(chǎng)環(huán)境進(jìn)行仿真，采用二維直角坐標(biāo)或一維坐標(biāo)均可確定航空器的空間位置，并對(duì)每個(gè)柵格從下往上、從左至右分別標(biāo)號(hào)得到400個(gè)柵格，每個(gè)柵格的標(biāo)號(hào)可作為其位置坐標(biāo)。圖1 為二維環(huán)境矩陣，圖2 為機(jī)場(chǎng)道面柵格化處理圖。

圖1 二維環(huán)境矩陣

圖2 機(jī)場(chǎng)道面柵格化處理圖

綜合以上，柵格地圖用于路徑規(guī)劃有以下好處：

（1）可以將任意形狀輪廓的地圖，用足夠精細(xì)的柵格進(jìn)行繪制。

（2）每一個(gè)柵格，可以通過(guò)不同顏色表征不同含義，如黑色代表障礙物、白色代表滑行道。

（3）基于柵格的機(jī)場(chǎng)地圖進(jìn)行路徑規(guī)劃，有橫、縱、斜三個(gè)規(guī)劃方向，對(duì)于場(chǎng)面滑行的低速航空器（一般為5 海里/小時(shí)—20 海里/小時(shí)海里/小時(shí)）完全可以按照規(guī)劃路徑滑行。

2 SARSA學(xué)習(xí)算法的改進(jìn)

2.1 SARSA學(xué)習(xí)算法

強(qiáng)化學(xué)習(xí)是從環(huán)境狀態(tài)到動(dòng)作映射的機(jī)器學(xué)習(xí)方法［8］，目的是基于與環(huán)境的交互來(lái)自主地學(xué)習(xí)如何做出正確的決策，以最大化預(yù)期的累積回報(bào)。在強(qiáng)化學(xué)習(xí)算法中，SARSA 算法是一種經(jīng)典的在線學(xué)習(xí)算法，該算法的主要思想是在每個(gè)狀態(tài)下，根據(jù)當(dāng)前動(dòng)作和即將采取的動(dòng)作來(lái)更新，SARSA 算法的迭代更新公式為：

其中，Q(s,a)為狀態(tài)—?jiǎng)幼骱瘮?shù)，表示在s狀態(tài)下采取動(dòng)作a的價(jià)值；s為狀態(tài)；a為選擇的動(dòng)作；α為學(xué)習(xí)率，表示每輪更新的步長(zhǎng)；r為獎(jiǎng)勵(lì)信號(hào)，表示智能體在采取動(dòng)作后經(jīng)環(huán)境反饋獲得的獎(jiǎng)勵(lì)；γ為折扣因子，表示未來(lái)獎(jiǎng)勵(lì)的重要性，使得智能體更傾向于選擇長(zhǎng)期的獎(jiǎng)勵(lì)；Q(s',a')為狀態(tài)—?jiǎng)幼骱瘮?shù)的下一個(gè)狀態(tài)和動(dòng)作，即在下一個(gè)狀態(tài)下選擇下一個(gè)動(dòng)作的預(yù)期價(jià)值［9］。

按照上述迭代更新公式，智能體會(huì)不斷與環(huán)境交互，更新Q表中的值，最終智能體可按照Q表根據(jù)ε-greedy 策略來(lái)進(jìn)行動(dòng)作決策。該策略設(shè)定動(dòng)態(tài)因子ε，ε∈(0，1)代表了航空器擁有ε的概率值，將會(huì)在滑行狀態(tài)中選擇當(dāng)前Q表中獎(jiǎng)勵(lì)較大的動(dòng)作，1-ε 的概率值會(huì)選擇Q表中除最大分值外的其他動(dòng)作［10］。

因此當(dāng)ε 較大時(shí)，智能體傾向于考慮當(dāng)前狀態(tài)下的獎(jiǎng)賞值，算法收斂得較慢，訓(xùn)練效率較低，隨著訓(xùn)練的進(jìn)行，可按照預(yù)定的步長(zhǎng)或時(shí)序進(jìn)行調(diào)整。對(duì)于其他參數(shù)的取值，要根據(jù)實(shí)際情況經(jīng)過(guò)探索最終確定。表1 為3 個(gè)狀態(tài)、2 個(gè)動(dòng)作的Agent 生成的Q表示例。

表1 Q表

為使SARSA 算法順利更新，需要設(shè)置合適的獎(jiǎng)賞集合r，常用末狀態(tài)獎(jiǎng)勵(lì)函數(shù)下，當(dāng)智能體在達(dá)到目標(biāo)時(shí)所獲得的獎(jiǎng)勵(lì)值為1，其他狀態(tài)的獎(jiǎng)勵(lì)值為0［11］。在機(jī)場(chǎng)滑行道上，航空器從起始柵格開(kāi)始滑行時(shí)存在某一柵格突然出現(xiàn)障礙物的情況，假設(shè)航空器需要經(jīng)過(guò)30 個(gè)柵格到達(dá)目標(biāo)柵格，每走一步均可做8種選擇,因此30 步可做出的選擇總數(shù)為830，如果采用末狀態(tài)獎(jiǎng)勵(lì)函數(shù)設(shè)置獎(jiǎng)賞，則意味著在每次學(xué)習(xí)迭代時(shí)都需要重新計(jì)算獎(jiǎng)勵(lì)值，會(huì)使得SARSA 算法在處理長(zhǎng)時(shí)間任務(wù)時(shí)復(fù)雜度提高，從而導(dǎo)致算法收斂困難。

2.2 改進(jìn)的SARSA算法分析

本節(jié)討論將模擬退火算法的策略思想應(yīng)用于SARSA 算法的策略選擇中。模擬退火算法是一種全局優(yōu)化算法，其基本思想是將問(wèn)題看作隨機(jī)熱力學(xué)系統(tǒng)，在系統(tǒng)達(dá)到平衡的過(guò)程中，利用溫度控制的隨機(jī)擾動(dòng)方法，慢慢降低溫度，以一定概率接受劣解，從而逐步趨近于全局最優(yōu)解。算法的具體步驟如下：

（1）設(shè)定初始狀態(tài)和初始溫度。

（2）在每個(gè)溫度下，隨機(jī)產(chǎn)生一個(gè)新的狀態(tài)，并計(jì)算新?tīng)顟B(tài)的代價(jià)函數(shù)。

（3）判斷是否接受新?tīng)顟B(tài)：若新?tīng)顟B(tài)代價(jià)函數(shù)比當(dāng)前狀態(tài)更優(yōu)，則接受新?tīng)顟B(tài)。若新?tīng)顟B(tài)代價(jià)函數(shù)較劣，則以一定的概率接受新?tīng)顟B(tài)，概率由Metropolis準(zhǔn)則來(lái)決定，即p=e(-ΔE/T)，其中ΔE為新舊狀態(tài)的代價(jià)函數(shù)差值，T為當(dāng)前溫度。

（4）降溫，調(diào)整溫度參數(shù)，進(jìn)入下一輪循環(huán)。

（5）當(dāng)溫度達(dá)到最低溫度時(shí)停止算法［12］。

由以上步驟可知，模擬退火算法并非全盤(pán)否定較劣的策略，因此可以避免陷入局部搜索，進(jìn)而得到全局最優(yōu)解。

本文所提出的基于模擬退火策略的SARSA 算法，將上述思想融入SARSA 算法中。模擬退火策略步驟如下：

(1）生成一個(gè)隨機(jī)數(shù)λ；

(2）在溫度T時(shí)刻，計(jì)算隨機(jī)動(dòng)作a的接受概率

(3)策略判斷做出選擇：若e(Q(s',a')-Q(s,a))/T＞λ，則隨機(jī)選擇一個(gè)動(dòng)作，反之選擇動(dòng)作arg maxQ(s,a)；

(4）判斷是否至冷卻狀態(tài)，若至冷卻狀態(tài)，則T=Tmin［13］。

基于模擬退火策略的SARSA 算法通過(guò)溫度參數(shù)控制策略進(jìn)行選擇，增加了搜索空間，提高了局部搜索能力。溫度參數(shù)隨著迭代次數(shù)的增加而不斷降低，最終可以得到全局最優(yōu)解。此外，模擬退火策略采用的是基于誤差平方和的獎(jiǎng)勵(lì)函數(shù)，具有較好的收斂性和泛化性能。在更新Q值時(shí)，根據(jù)當(dāng)前狀態(tài)、動(dòng)作和下一個(gè)狀態(tài)的獎(jiǎng)勵(lì)值來(lái)進(jìn)行更新，以獲得更好的學(xué)習(xí)效果。

基于模擬退火策略的SARSA 算法流程的步驟如下：

步驟一：初始化參數(shù)。包括初始溫度、最終溫度、溫度下降率、可接受解的概率等參數(shù)。

步驟二：初始化狀態(tài)和動(dòng)作。根據(jù)實(shí)際問(wèn)題的需要，給定初始狀態(tài)和動(dòng)作。

步驟三：迭代過(guò)程。進(jìn)行多輪迭代，每一輪都根據(jù)當(dāng)前狀態(tài)與動(dòng)作更新Q值，并基于模擬退火策略選擇下一個(gè)狀態(tài)和動(dòng)作。

步驟四：更新Q值。根據(jù)當(dāng)前狀態(tài)、動(dòng)作和下一個(gè)狀態(tài)的獎(jiǎng)勵(lì)值來(lái)更新Q值，使其逐步趨向全局最優(yōu)解。

步驟五：修改溫度和可接受解的概率。隨著迭代次數(shù)的增加，不斷降低溫度并逐漸收縮可接受解的概率，以逼近最優(yōu)解。

步驟六：判斷是否收斂。如果滿足停止條件，算法結(jié)束；否則，回到第3步繼續(xù)迭代。

綜上，基于模擬退火的SARSA 算法可以在搜索解空間時(shí)跳出局部最小值，從而有更大機(jī)會(huì)找到全局最優(yōu)解，并且在多輪迭代中狀態(tài)隨機(jī)生成，因此可以在一定程度上探索狀態(tài)空間中的各種狀態(tài)?？紤]到該算法率分布更加穩(wěn)定，因此它能夠適應(yīng)復(fù)雜變化的機(jī)場(chǎng)場(chǎng)面環(huán)境。

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

3.1 分析思路

為驗(yàn)證整個(gè)算法的可行性和規(guī)劃效果，本研究使用了新鄭機(jī)場(chǎng)滑行道實(shí)際道面網(wǎng)絡(luò)，對(duì)該機(jī)場(chǎng)進(jìn)離港航班分別使用SARSA 算法和改進(jìn)的SARSA 算法進(jìn)行路徑規(guī)劃，比較不同情況下兩種算法的優(yōu)劣。

3.2 算法設(shè)置

基于上文構(gòu)建的模型環(huán)境進(jìn)行仿真驗(yàn)證，根據(jù)先驗(yàn)知識(shí)，并結(jié)合機(jī)場(chǎng)柵格環(huán)境，將航空器當(dāng)前所在柵格作為初始狀態(tài)，航空器分為8個(gè)運(yùn)動(dòng)方向，如圖3所示。

圖3 智能體搜索方向示意圖

為方便表示獎(jiǎng)賞函數(shù)r，假設(shè)目標(biāo)柵格位于航空器當(dāng)前柵格正前方，將航空器選擇方向從正前方按順時(shí)針?lè)謩e標(biāo)號(hào)為{1，2，3，4，5，6，7，8}；將SARSA 算法參數(shù)進(jìn)行設(shè)置，其中學(xué)習(xí)率α為0.8，折扣因子γ為0.95，動(dòng)態(tài)因子ε 為0.9，則獎(jiǎng)賞函數(shù)r可表示為：每進(jìn)行一次環(huán)境交互做出動(dòng)作獎(jiǎng)勵(lì)值為r=-1，到達(dá)目標(biāo)柵格的獎(jiǎng)勵(lì)值r=100，仿真模擬退火參數(shù)設(shè)置為：初始溫度T=300，降溫速率v=0.95，常溫Tmin= 10-8［14］。

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

由柵格仿真環(huán)境和設(shè)置的算法參數(shù)對(duì)改進(jìn)的SARSA 算法和傳統(tǒng)SARSA 算法進(jìn)行對(duì)比，智能體的總收益為每一柵格收益之和。圖4 是航空器仿真運(yùn)行后的迭代結(jié)果圖，本次實(shí)驗(yàn)選擇迭代次數(shù)為400，也就是智能體在規(guī)劃出400 條路徑后將會(huì)結(jié)束搜索行為［15］。

圖4 傳統(tǒng)SARSA算法和改進(jìn)SARSA算法迭代對(duì)比圖

對(duì)比實(shí)驗(yàn)結(jié)果可知，迭代前期初始溫度高搜索率大，因此路徑長(zhǎng)度變化較大，策略上隨機(jī)選擇動(dòng)作，隨著溫度降低搜索加快，收斂速度明顯加快，路徑長(zhǎng)度變化幅度減??；傳統(tǒng)SARSA 算法由于其較小的動(dòng)態(tài)因子ε，導(dǎo)致算法收斂較慢，且穩(wěn)定性差，后逐漸趨于收斂。在收斂所需迭代次數(shù)方面，改進(jìn)的SARSA 算法迭代次數(shù)為66，而傳統(tǒng)SARSA 算法的迭代次數(shù)為93，表明模擬退火策略迭代次數(shù)更少，有更好的訓(xùn)練效果［16］。

圖5 是相同起終點(diǎn)情況下對(duì)比SARSA 算法和改進(jìn)SARSA 算法的滑行路徑規(guī)劃圖，在該實(shí)驗(yàn)中，假設(shè)航空器在左轉(zhuǎn)過(guò)程中遇到前方障礙物，設(shè)障礙物坐標(biāo)為210，左邊是使用傳統(tǒng)SARSA 算法的規(guī)劃結(jié)果，結(jié)果顯示由于障礙物沒(méi)有處于滑行路徑所在柵格，在該轉(zhuǎn)彎過(guò)程中，對(duì)航空器路徑不產(chǎn)生影響；右邊是使用改進(jìn)SARSA 算法的路徑規(guī)劃結(jié)果，在同樣位置設(shè)置障礙物后，由于算法的模擬退火行為策略，滑行路徑發(fā)生改變，航空器在進(jìn)行方向選擇時(shí)，偏向于遠(yuǎn)離障礙物的方案，避免了潛在的沖突和碰撞，且收斂更快，規(guī)劃路徑的長(zhǎng)度更短。

圖5 傳統(tǒng)SARSA算法和改進(jìn)SARSA算法的路徑規(guī)劃對(duì)比圖

4 結(jié) 論

基于模擬退火策略的SARSA 算法相對(duì)于傳統(tǒng)SARSA 算法具有更加高效的搜索效率、收斂速度和穩(wěn)定性，并基于柵格地圖環(huán)境，得出模擬退火策略相較于ε-greedy 策略搜索效率更高，改進(jìn)的SARSA 算法實(shí)時(shí)性好，能夠?yàn)楹娇掌骺焖僖?guī)劃出安全的路線。