基于改進SARSA算法的航空器滑行路徑規劃

張云景，王 昊，王 帥，孟 斌

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

0 引 言

航空器滑行路徑規劃是建設智慧機場的重要一環，也是保證航空器在機場安全高效運行的核心，但我國在智慧機場建設方面仍處于起步階段，國內大多數機場仍在使用傳統的人工機坪管制方法。傳統的人工調度成本高昂，效率低下，而利用計算機輔助的場面滑行路徑規劃可以更加清晰地建立和實施場面滑行計劃，對建設智慧機場和綠色機場具有重要意義。

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

強化學習無須完善的先驗知識，航空器面對陌生的機場場面環境能夠通過與環境的動態交互自主獲得最佳決策行為。因此，基于強化學習的場面航空器滑行系統，能減少飛機的運行成本，提高機場的資源利用率以及確保外界環境的安全，同時，還有助于減少對環境的污染。本文針對新鄭機場進離港航空器路徑規劃進行研究，構建基于改進SARSA算法的路徑規劃方法。仿真結果表明改進的SARSA 算法收斂速度更快，能夠為航空器滑行規劃出安全路徑。

1 模型構建

1.1 問題描述

靜態規劃問題被表述為整數規劃問題。在解決航空器靜態路徑規劃時，首先要給定參數，它是由初始節點組成的一組任務集合Rr和目標節點集合Mr組成。對于任務r，需要考慮場面系統布局G=（V，E），以及航空器集和H。其中二進制變量為，它表示當航空器k在時間t從柵格i移動到柵格j時取1，否則取0。

該靜態問題的目標是最小化滑行時間σk,r，其定義為航空器k執行滑行任務r從初始柵格Rr到目標柵格Mr的時間，如果航空器k從開始Rr到達目標柵格Mr則取1，否則為0。該規劃目的在于為航空器找到一條無沖突的路線。以下為最小化目標函數。

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

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

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

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

1.2 機場環境建模

機場環境建模是航空器滑行路徑規劃的核心。建模時，將機場環境信息抽象化為模型化信息，從而將場面環境劃分為可滑行區域和不可滑行區域［7]，柵格化地圖是研究路徑規劃的常用方法之一。柵格化可以確保連續的路徑離散化為對柵格的選擇，且離散化后的信息方便儲存和維護。本文采用柵格法對機場環境建模，具體情況如下。

結合機場圖，采用20*20 的柵格對機場環境進行仿真，采用二維直角坐標或一維坐標均可確定航空器的空間位置，并對每個柵格從下往上、從左至右分別標號得到400個柵格，每個柵格的標號可作為其位置坐標。圖1 為二維環境矩陣，圖2 為機場道面柵格化處理圖。

圖1 二維環境矩陣

圖2 機場道面柵格化處理圖

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

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

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

（3）基于柵格的機場地圖進行路徑規劃，有橫、縱、斜三個規劃方向，對于場面滑行的低速航空器（一般為5 海里/小時—20 海里/小時海里/小時）完全可以按照規劃路徑滑行。

2 SARSA學習算法的改進

2.1 SARSA學習算法

強化學習是從環境狀態到動作映射的機器學習方法［8］，目的是基于與環境的交互來自主地學習如何做出正確的決策，以最大化預期的累積回報。在強化學習算法中，SARSA 算法是一種經典的在線學習算法，該算法的主要思想是在每個狀態下，根據當前動作和即將采取的動作來更新，SARSA 算法的迭代更新公式為：

其中，Q(s,a)為狀態—動作函數，表示在s狀態下采取動作a的價值；s為狀態；a為選擇的動作；α為學習率，表示每輪更新的步長；r為獎勵信號，表示智能體在采取動作后經環境反饋獲得的獎勵；γ為折扣因子，表示未來獎勵的重要性，使得智能體更傾向于選擇長期的獎勵；Q(s',a')為狀態—動作函數的下一個狀態和動作，即在下一個狀態下選擇下一個動作的預期價值［9］。

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

因此當ε 較大時，智能體傾向于考慮當前狀態下的獎賞值，算法收斂得較慢，訓練效率較低，隨著訓練的進行，可按照預定的步長或時序進行調整。對于其他參數的取值，要根據實際情況經過探索最終確定。表1 為3 個狀態、2 個動作的Agent 生成的Q表示例。

表1 Q表

為使SARSA 算法順利更新，需要設置合適的獎賞集合r，常用末狀態獎勵函數下，當智能體在達到目標時所獲得的獎勵值為1，其他狀態的獎勵值為0［11］。在機場滑行道上，航空器從起始柵格開始滑行時存在某一柵格突然出現障礙物的情況，假設航空器需要經過30 個柵格到達目標柵格，每走一步均可做8種選擇,因此30 步可做出的選擇總數為830，如果采用末狀態獎勵函數設置獎賞，則意味著在每次學習迭代時都需要重新計算獎勵值，會使得SARSA 算法在處理長時間任務時復雜度提高，從而導致算法收斂困難。

2.2 改進的SARSA算法分析

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

（1）設定初始狀態和初始溫度。

（2）在每個溫度下，隨機產生一個新的狀態，并計算新狀態的代價函數。

（3）判斷是否接受新狀態：若新狀態代價函數比當前狀態更優，則接受新狀態。若新狀態代價函數較劣，則以一定的概率接受新狀態，概率由Metropolis準則來決定，即p=e(-ΔE/T)，其中ΔE為新舊狀態的代價函數差值，T為當前溫度。

（4）降溫，調整溫度參數，進入下一輪循環。

（5）當溫度達到最低溫度時停止算法［12］。

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

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

(1）生成一個隨機數λ；

(2）在溫度T時刻，計算隨機動作a的接受概率

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

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

基于模擬退火策略的SARSA 算法通過溫度參數控制策略進行選擇，增加了搜索空間，提高了局部搜索能力。溫度參數隨著迭代次數的增加而不斷降低，最終可以得到全局最優解。此外，模擬退火策略采用的是基于誤差平方和的獎勵函數，具有較好的收斂性和泛化性能。在更新Q值時，根據當前狀態、動作和下一個狀態的獎勵值來進行更新，以獲得更好的學習效果。

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

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

步驟二：初始化狀態和動作。根據實際問題的需要，給定初始狀態和動作。

步驟三：迭代過程。進行多輪迭代，每一輪都根據當前狀態與動作更新Q值，并基于模擬退火策略選擇下一個狀態和動作。

步驟四：更新Q值。根據當前狀態、動作和下一個狀態的獎勵值來更新Q值，使其逐步趨向全局最優解。

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

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

綜上，基于模擬退火的SARSA 算法可以在搜索解空間時跳出局部最小值，從而有更大機會找到全局最優解，并且在多輪迭代中狀態隨機生成，因此可以在一定程度上探索狀態空間中的各種狀態?？紤]到該算法率分布更加穩定，因此它能夠適應復雜變化的機場場面環境。

3 實驗及結果分析

3.1 分析思路

為驗證整個算法的可行性和規劃效果，本研究使用了新鄭機場滑行道實際道面網絡，對該機場進離港航班分別使用SARSA 算法和改進的SARSA 算法進行路徑規劃，比較不同情況下兩種算法的優劣。

3.2 算法設置

基于上文構建的模型環境進行仿真驗證，根據先驗知識，并結合機場柵格環境，將航空器當前所在柵格作為初始狀態，航空器分為8個運動方向，如圖3所示。

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

為方便表示獎賞函數r，假設目標柵格位于航空器當前柵格正前方，將航空器選擇方向從正前方按順時針分別標號為{1，2，3，4，5，6，7，8}；將SARSA 算法參數進行設置，其中學習率α為0.8，折扣因子γ為0.95，動態因子ε 為0.9，則獎賞函數r可表示為：每進行一次環境交互做出動作獎勵值為r=-1，到達目標柵格的獎勵值r=100，仿真模擬退火參數設置為：初始溫度T=300，降溫速率v=0.95，常溫Tmin= 10-8［14］。

3.3 實驗結果與分析

由柵格仿真環境和設置的算法參數對改進的SARSA 算法和傳統SARSA 算法進行對比，智能體的總收益為每一柵格收益之和。圖4 是航空器仿真運行后的迭代結果圖，本次實驗選擇迭代次數為400，也就是智能體在規劃出400 條路徑后將會結束搜索行為［15］。

圖4 傳統SARSA算法和改進SARSA算法迭代對比圖

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

圖5 是相同起終點情況下對比SARSA 算法和改進SARSA 算法的滑行路徑規劃圖，在該實驗中，假設航空器在左轉過程中遇到前方障礙物，設障礙物坐標為210，左邊是使用傳統SARSA 算法的規劃結果，結果顯示由于障礙物沒有處于滑行路徑所在柵格，在該轉彎過程中，對航空器路徑不產生影響；右邊是使用改進SARSA 算法的路徑規劃結果，在同樣位置設置障礙物后，由于算法的模擬退火行為策略，滑行路徑發生改變，航空器在進行方向選擇時，偏向于遠離障礙物的方案，避免了潛在的沖突和碰撞，且收斂更快，規劃路徑的長度更短。

圖5 傳統SARSA算法和改進SARSA算法的路徑規劃對比圖

4 結 論

基于模擬退火策略的SARSA 算法相對于傳統SARSA 算法具有更加高效的搜索效率、收斂速度和穩定性，并基于柵格地圖環境，得出模擬退火策略相較于ε-greedy 策略搜索效率更高，改進的SARSA 算法實時性好，能夠為航空器快速規劃出安全的路線。