流量擁堵空域內(nèi)一種基于Q-Learning算法的改航路徑規(guī)劃

向征，何雨陽, 全志偉

(中國民用航空飛行學(xué)院空中交通管理學(xué)院，廣漢 618307)

近年來，隨著國民經(jīng)濟(jì)的穩(wěn)定增長，中國的民用航空交通運(yùn)輸行業(yè)也欣欣向榮，航班架次逐年遞增。然而，隨之而來的便是空中流量急劇增加與空域資源有限的矛盾，導(dǎo)致了難以估量的社會經(jīng)濟(jì)損失，還誘發(fā)了嚴(yán)重的安全隱患，造成飛行事故或者事故癥候，成為制約民航業(yè)發(fā)展的痼疾。因此，針對流量擁堵空域內(nèi)的航空器改航路徑規(guī)劃研究迫在眉睫。在此情況下，原有的部分空中交通管理規(guī)則和概念不再適用于如今新時代的運(yùn)輸環(huán)境，為了突破這一瓶頸，2004年，歐洲率先提出了歐洲單一天空空中交通管理研究規(guī)劃(single European sky air traffic management research, SESAR)，隨后美國又緊接著提出了新一代空中運(yùn)輸系統(tǒng)(next generation air transportation system, NextGen)[1]，而在2012年國際民航組織將二者的內(nèi)容進(jìn)行整合加以補(bǔ)充改進(jìn)，最終提出了全球空中航行計劃(global air navigation plan，GANP)[2]等一系列相關(guān)的運(yùn)行概念和航行新技術(shù)，進(jìn)一步在全球范圍內(nèi)使空中交通管理體系在安全性、可靠性、可持續(xù)性等方面進(jìn)行提升，實現(xiàn)改航策略的優(yōu)化以改善空中延誤，為現(xiàn)如今的航跡規(guī)劃研究奠定了夯實的基礎(chǔ)，促進(jìn)了一系列研究成果的發(fā)展。

中外學(xué)者針對最優(yōu)路徑的規(guī)劃開展了大量研究。向征等[3]通過柵格法對雷暴所在的空域進(jìn)行柵格化，并引入人工勢場法，改進(jìn)傳統(tǒng)蟻群算法中的啟發(fā)信息因子，建立基于多航空器沖突避讓的繞飛雷暴區(qū)的航跡優(yōu)化模型。陳可嘉等[4]針對危險天氣，以改航路徑長度最短為目標(biāo)，在傳統(tǒng)的人工勢場法中考慮到中間目標(biāo)點(diǎn)這一因素，引進(jìn)相對位置和相對速度等變量，從而建立基于改進(jìn)人工勢場法的動態(tài)改航路徑優(yōu)化模型。孫瑜[5]根據(jù)航空器路徑規(guī)劃需求，結(jié)合改進(jìn)的A*算法對航空器進(jìn)行4D航跡的預(yù)測，并完成航空器的場面滑行動態(tài)路徑規(guī)劃及仿真運(yùn)行。羅如學(xué)等[6]通過改進(jìn)人工魚群算法，有效改善了傳統(tǒng)魚群算法中視覺范圍固定不變的這一特性，并且改進(jìn)了擁擠度因子函數(shù)以提高算法的收斂性，從而提高機(jī)器人路徑規(guī)劃的合理性。李少波等[7]探析了遺傳算法的優(yōu)缺點(diǎn),并對其在機(jī)器人路徑規(guī)劃應(yīng)用領(lǐng)域進(jìn)行了深入的研究，闡明了現(xiàn)如今需要突破的技術(shù)難點(diǎn)，對其發(fā)展趨勢進(jìn)行了預(yù)測。朱永強(qiáng)等[8]對于機(jī)器人路徑規(guī)劃問題提出了一種基于A*算法的改進(jìn)蟻群算法，首先利用A*算法尋找一條最短路徑作為較優(yōu)解,再提高其信息素濃度，從而有效證實了該改進(jìn)蟻群算法路徑尋優(yōu)效果更好。趙元棣等[9]在危險天氣條件下基于A*算法對進(jìn)場航空器分別進(jìn)行靜態(tài)和動態(tài)的改航路徑規(guī)劃，并用仿真實驗證明其可行性和有效性。李楠等[10]基于改進(jìn)的A*算法建立航空器場面滑行最短路徑規(guī)劃模型, 并考慮到航空器的場面滑行時間及相應(yīng)油耗，結(jié)合啟發(fā)式搜索建立了多目標(biāo)速度剖面模型, 獲得航空器場面滑行的4D軌跡。李志龍[11]針對沖突熱點(diǎn)提出了基于改進(jìn)Q-Learning和基于改進(jìn)A*的航空器場面滑行的靜態(tài)路徑規(guī)劃算法，并對這兩種場面路徑規(guī)劃策略進(jìn)行分析比較，建立了基于沖突熱點(diǎn)等級分配的動態(tài)路徑規(guī)劃模型,以便更加合理地規(guī)劃滑行路徑。魏彤[12]針對航空器起飛前的靜態(tài)塊狀受限區(qū)和靜態(tài)帶狀受限區(qū),分別基于MAKLINK圖和多邊形法建立改航環(huán)境模型,應(yīng)用改進(jìn)遺傳算法獲得全局最優(yōu)路徑。并建立基于最小二乘法的強(qiáng)對流天氣短時移動預(yù)測模型，通過馬爾科夫決策過程模型推算在強(qiáng)對流天氣條件下的航空器可航狀態(tài)概率,從而完成改航路徑動態(tài)規(guī)劃。李海等[13]建立一種針對多種危險氣象的分層航跡動態(tài)規(guī)劃模型，通過稀疏A*算法對分層的改航空域進(jìn)行全局航跡規(guī)劃，并結(jié)合動態(tài)窗口法對全局航跡進(jìn)行分段的實時航跡動態(tài)規(guī)劃。疏利生等[14]根據(jù)航空器滑行規(guī)則建立基于強(qiáng)化學(xué)習(xí)的靜態(tài)的機(jī)場場面滑行路徑優(yōu)化模型，并通過Off-Policy中Q-Learning算法進(jìn)行求解。

綜上可知，目前路徑規(guī)劃是研究熱點(diǎn)，尤其是針對航空器的路徑優(yōu)化模型方面。前人研究主要是對危險天氣情況下的航空器改航路徑規(guī)劃，或是機(jī)場場面滑行最短路徑規(guī)劃。如今，飛行流量激增導(dǎo)致空域資源的緊張，造成航班延誤率不斷攀升。而對于如何優(yōu)化空域結(jié)構(gòu)調(diào)整空中流量，有效實現(xiàn)航空器在流量擁堵空域內(nèi)的運(yùn)行暢通這一關(guān)鍵研究領(lǐng)域，卻鮮見報道。因此，對于流量擁堵空域內(nèi)航空器改航路徑規(guī)劃的研究勢在必行。

動態(tài)路徑規(guī)劃模型一般對于航空器運(yùn)行過程中的實時路徑規(guī)劃具有良好的適應(yīng)性，目前大多都是建立動態(tài)路徑規(guī)劃模型或者動靜態(tài)路徑規(guī)劃相結(jié)合的模型。而航跡規(guī)劃算法則普遍采用智能優(yōu)化算法，如粒子群法、遺傳算法和A*算法，或者在此基礎(chǔ)上加以改進(jìn)并結(jié)合4D航跡進(jìn)行路徑優(yōu)化。隨著人工智能第三次浪潮的到來，學(xué)者們將目光投向深度學(xué)習(xí)或者強(qiáng)化學(xué)習(xí)等，并將其結(jié)合起來應(yīng)用于航空器的改航路徑優(yōu)化。

基于此，根據(jù)航空器在航路階段流量擁堵空域內(nèi)的實際運(yùn)行狀態(tài)，利用智能優(yōu)化算法將強(qiáng)化學(xué)習(xí)中馬爾科夫決策過程模型的獎勵函數(shù)加以改進(jìn)，對流量擁堵程度不同的航路點(diǎn)進(jìn)行劃分，利用Q-Learning 算法求解模型時，采用ε-greedy策略選擇動作來平衡好最優(yōu)動作和非最優(yōu)動作之間的關(guān)系，其中ε∈(0,1)，表示非貪心選擇的概率，即隨機(jī)選擇所有動作(包括最優(yōu)動作和非最優(yōu)動作)的概率，而剩下1-ε的概率采取貪心策略，即只選擇最優(yōu)動作。如此一來便可保證航空器在尋找最優(yōu)動作的同時也具有一定的隨機(jī)性，使得算法更具有合理性。

首先應(yīng)用柵格法將空域環(huán)境進(jìn)行描述，再根據(jù)強(qiáng)化學(xué)習(xí)中的馬爾科夫決策過程模型和Q-Learning算法，結(jié)合ε-greedy策略選擇動作，研究一套減少空中延誤時間、避開擁堵的基于流量管理層面的改航路徑優(yōu)化算法，以有效輔助各級管制員進(jìn)行決策指揮，減輕其工作負(fù)荷，提高運(yùn)行效率，對空中交通流量管理進(jìn)行創(chuàng)新性的探索，使空中交通更加安全、有序和高效地流動。

1 空域環(huán)境建模

最優(yōu)路徑的規(guī)劃通常可以劃分為空域環(huán)境建模和最優(yōu)路徑搜索兩部分，采取合理的空域環(huán)境建模方法可以極大地提高最優(yōu)路徑的搜索效率。目前主要的環(huán)境建模方法有柵格法、可視圖法和拓?fù)浞ǖ取６渲械臇鸥穹ㄒ蚱鋸?qiáng)大的數(shù)據(jù)處理能力，在里程統(tǒng)計、模糊預(yù)測和路徑規(guī)劃等各種模型求解和算法設(shè)計上得到廣泛應(yīng)用，成為當(dāng)前較為常用的建模方法之一。柵格法的核心思想是將空域環(huán)境離散分解化，通過相同尺寸和大小的柵格對整個空域進(jìn)行二值化的綜合分割，來量化空域環(huán)境的復(fù)雜程度，從而提高模型和算法的準(zhǔn)確性、靈活性和搜索效率。鑒于駕駛員的操縱難度以及管制員的工作負(fù)荷等因素，只考慮同一飛行高度層的改航，因此僅在二維柵格上對空域環(huán)境進(jìn)行建模。二維柵格化分析時需要考慮以下3點(diǎn)。

(1)柵格地圖形狀大小問題。所構(gòu)建的柵格地圖形狀采用的是最簡單的正方形，而柵格地圖大小設(shè)定為10×10。

(2)柵格地圖中的柵格尺寸問題。柵格的尺寸大小直接影響后續(xù)數(shù)據(jù)處理的可靠性和使用性，因為網(wǎng)格尺寸過大會影響最終的結(jié)果精度，可能導(dǎo)致搜索出來的最優(yōu)路徑的準(zhǔn)確度降低，而網(wǎng)格尺寸過小又容易導(dǎo)致數(shù)據(jù)冗余。根據(jù)經(jīng)驗，所有空間化的柵格尺寸統(tǒng)一選取為20 km×20 km，所以柵格地圖的實際覆蓋面積為200 km×200 km，將格網(wǎng)化的矢量結(jié)果轉(zhuǎn)為柵格格式。

(3)柵格的標(biāo)識問題。將空域環(huán)境按照一定的規(guī)模劃分柵格后，每個柵格都需要進(jìn)行標(biāo)識。本文采用坐標(biāo)法進(jìn)行標(biāo)號，由圓錐投影法轉(zhuǎn)換成二維笛卡爾直角坐標(biāo)系，每個柵格可用坐標(biāo)進(jìn)行唯一表示，記為xij=(i,j)。其中，i為柵格所在行數(shù)，j為柵格所在列數(shù)，如圖1所示。

使用二維柵格法選取規(guī)則的矩形空域環(huán)境進(jìn)行建模，用來描述某一時段內(nèi)的流量擁堵空域，且短期內(nèi)該空域的航路點(diǎn)流量情況基本保持不變。每個柵格代表一個自由區(qū)域或限制區(qū)域，且每個區(qū)域最多含有1個航路點(diǎn)。其中黑色柵格表示限制區(qū)域，在限制區(qū)域內(nèi)存在航路飽和點(diǎn)。在這里定義一個新的概念，航路流量飽和點(diǎn)是指單位時間內(nèi)航空器流經(jīng)該航路點(diǎn)的流量不小于其自身容量，即該航路點(diǎn)上的流量達(dá)到飽和狀態(tài)，容易造成航空器擁堵。白色柵格和灰色柵格表示為自由區(qū)域，在自由區(qū)域內(nèi)沒有航路飽和點(diǎn)，即在自由區(qū)域內(nèi)流經(jīng)該航路點(diǎn)的流量小于其容量，或者該區(qū)域內(nèi)根本就沒有航路點(diǎn)。自由區(qū)域又可劃分為兩類，一類是在自由區(qū)域內(nèi)沒有航路點(diǎn)或流經(jīng)該航路點(diǎn)的平均流量不超過容量的80%，為流量較小的自由區(qū)域，顯示成白色柵格；另一類是該流量大于容量的80%的航路點(diǎn)為繁忙航路點(diǎn)，是流量較大的自由區(qū)域，呈現(xiàn)為灰色柵格。而飛機(jī)僅能在自由區(qū)域內(nèi)飛行，不能通過限制區(qū)域。本文設(shè)定空域的起點(diǎn)為(1,10)，終點(diǎn)為(10,1)，并隨機(jī)選定幾個流量擁擠航路點(diǎn)，如圖1所示。

黑色柵格為限制區(qū)域；白色柵格和灰色柵格為自由區(qū)域

2 馬爾科夫決策

強(qiáng)化學(xué)習(xí)(reinforcement learning, RL)，屬于機(jī)器學(xué)習(xí)中的領(lǐng)域，是實現(xiàn)人工智能的一種有效手段，在很多領(lǐng)域應(yīng)用十分廣泛，而馬爾科夫決策過程(Markov decision process, MDP)是強(qiáng)化學(xué)習(xí)中的一種常見模型。

馬爾可夫決策過程強(qiáng)調(diào)如何基于環(huán)境而行動，在智能體在與環(huán)境的交互過程中獲得相應(yīng)的獎勵用以指導(dǎo)動作，通過學(xué)習(xí)策略從而使得獎勵最大化。這種從環(huán)境中獲得的獎勵是一種反饋信號，是作為一種對智能體所采取動作好壞的度量或評價，間接加強(qiáng)使智能體獲得盡可能大的正獎勵這一趨勢，而不是直接告訴智能體如何采取正確的行為。通過這種方式，智能體依靠自身的經(jīng)歷進(jìn)行學(xué)習(xí)，在行動-評價的環(huán)境中獲得學(xué)習(xí)信息并更新模型參數(shù)，不斷地改進(jìn)行動方案以更好地適應(yīng)環(huán)境，從而使得智能體在任意狀態(tài)下都能搜索出最優(yōu)策略以實現(xiàn)折扣獎勵之和最大化。

2.1 MDP

馬爾科夫決策過程一般用五元組描述, 即M=(S,A,P,R,γ),其中,S為有限的狀態(tài)集合，R為獎勵函數(shù)，γ為折扣系數(shù)，A為有限的動作集合，a∈A，其中a為具體的某個動作，P為狀態(tài)轉(zhuǎn)移概率矩陣。

狀態(tài)轉(zhuǎn)移概率Pss′為智能體從某一時刻的狀態(tài)s轉(zhuǎn)移到下一時刻的其他狀態(tài)s′的概率，可定義為

Pss′=p[St+1=s′|St=s]

(1)

式(1)中：St為在當(dāng)前t時刻的狀態(tài)；St+1為t+1時刻的狀態(tài);p為條件概率。

因此，下一時刻狀態(tài)s′只受到當(dāng)前狀態(tài)s的影響，而與之前的狀態(tài)無關(guān)。

若有n種狀態(tài)可供選擇，那么狀態(tài)轉(zhuǎn)移概率矩陣P可定義為

(2)

(3)

R為獎勵函數(shù)，Rs表示在t時刻狀態(tài)為s的條件下，在下一個時刻所獲得的獎勵,其計算公式為

Rs=E[Rt+1|St=s]

(4)

式(4)中：Rt+1為在t+1時刻所獲得的獎勵;E為數(shù)學(xué)期望。

γ為折扣系數(shù)，且γ∈[0,1]。折扣系數(shù)反映將來的獎勵在當(dāng)前時刻的價值比例，γ越大，說明考慮越長遠(yuǎn)，更加重視遠(yuǎn)期的獎勵。

策略π為關(guān)于動作集上的一個概率集合，策略π(a|s)表示在t時刻給定狀態(tài)s的條件下，從當(dāng)前t時刻的動作集At中選擇動作a的概率，而π是在各種狀態(tài)下選擇各種行動的概率分布，是所有狀態(tài)的π(a|s)共同形成了這個整體策略π，可表示為

π(a|s)=p[At=a|St=s]

(5)

2.2 值函數(shù)

Gt為累計獎勵，表示從t時刻狀態(tài)s開始進(jìn)行狀態(tài)轉(zhuǎn)移的過程中所有的折扣獎勵之和，而且越往后獎勵衰減得越多，當(dāng)t+k+1時刻獎勵所對應(yīng)特定的折扣系數(shù)為γk，即此刻的獎勵會衰減至原本的γk倍，其定義為

Gt=Rt+1+γRt+2+γ2Rt+3+…+γkRt+k+1

(6)

υπ(s)為狀態(tài)值函數(shù)，是指智能體遵循策略π在某一狀態(tài)s下所獲得累計獎勵的數(shù)學(xué)期望Eπ，表示狀態(tài)s的價值，而策略π決定了累計獎勵Gt的分布，從而會影響狀態(tài)值函數(shù)υπ(s)的期望值，定義為

υπ(s)=Eπ[Gt|St=s]

=Eπ[Rt+1+γGt+1|St=s]

=Eπ[Rt+1+γυπ(St+1)|St=s]

(7)

qπ(s,a)為狀態(tài)-行為值函數(shù)，是指智能體遵循策略π在某一狀態(tài)s下，選擇某一具體動作a所獲得的累計獎勵的期望，表示在狀態(tài)s下采取動作a的價值，具體定義為

qπ(s,a)=Eπ[Gt|St=s,At=a]

(8)

Bellman期望方程表示的是υπ(s)和qπ(s,a)自身以及二者之間的遞推關(guān)系，遞推公式如下。

υπ(s)和qπ(s,a)之間的關(guān)系可表示為

(9)

(10)

υπ(s)自身的遞推關(guān)系式為

υπ(s)=Eπ[Rt+1+γυπ(St+1)|St=s]

(11)

qπ(s,a)自身的遞推關(guān)系式為

qπ(s,a)=Eπ[Rt+1+γqπ(St+1,At+1)|St=s,At=a]

(12)

式(12)中：a′為在下一時刻，即t+1時刻所選擇的動作。

2.3 最優(yōu)值函數(shù)

υ*(s)為最優(yōu)狀態(tài)值函數(shù)，表示從所有策略產(chǎn)生的值函數(shù)中最大的那個狀態(tài)值函數(shù)，即

(13)

類似的，q*(s,a)為最優(yōu)狀態(tài)-行為值函數(shù)，表示從所有策略產(chǎn)生的值函數(shù)中最大的那個狀態(tài)-行為值函數(shù)，可表示為

(14)

通過遵循貪婪策略來選擇動作，使得q*(s,a)最大化，從而尋找到最優(yōu)策略。

貪婪策略可表示為

(15)

Bellman最優(yōu)方程表示的是υ*(s)和q*(s,a)自身以及二者之間的遞推關(guān)系，結(jié)合貪婪策略，遞推公式如下。

υ*(s)和q*(s,a)之間的關(guān)系為

(16)

υ*(s)自身的遞推關(guān)系式為

(17)

q*(s,a)自身的遞推關(guān)系式為

(18)

狀態(tài)s表示飛機(jī)在柵格地圖中所處的位置，s∈S，S為離散的有限狀態(tài)集合，狀態(tài)s可用坐標(biāo)法進(jìn)行表示為(i,j)，一共有100種狀態(tài)。其中，經(jīng)過該空域的過程中起點(diǎn)為(1,10),終點(diǎn)為(10,1)，如果飛機(jī)到達(dá)終點(diǎn)或者航路飽和點(diǎn)，則本次循環(huán)結(jié)束重新回到起點(diǎn)開始下一次循環(huán)。動作a表示飛機(jī)選擇的飛行方向，A為離散的有限動作集合，a∈A。類似的，可以用(i+1,j)表示飛機(jī)向右飛行，用(i,j+1)表示飛機(jī)向上飛行，且每次執(zhí)行動作時只能飛行1個柵格單元，共有4個方向。

當(dāng)飛機(jī)到達(dá)終點(diǎn)(10，1)時，執(zhí)行這一步動作可獲得+1 000的正獎勵，本次循環(huán)結(jié)束。當(dāng)飛機(jī)進(jìn)入限制區(qū)域時，系統(tǒng)將會得到-1 000的負(fù)獎勵。當(dāng)飛機(jī)進(jìn)入自由區(qū)域時，若進(jìn)入的是灰色柵格，則獲得-30的負(fù)獎勵，若進(jìn)入白色柵格，系統(tǒng)將會獲得-10 的負(fù)獎勵。這樣設(shè)置的目的在于尋找的最優(yōu)策略能夠使飛機(jī)盡可能地途經(jīng)流量較小的自由區(qū)域，減少或盡量避免通過繁忙航路點(diǎn)的可能性，禁止經(jīng)過飽和航路點(diǎn)，并且為了能夠讓Gt較大所以會迫使改航路徑更短。根據(jù)上述說明可得到馬爾科夫決策問題的獎勵函數(shù)如下所示：

(19)

3 基于Q-Learning算法的最優(yōu)路徑

Q-Learning算法是一種通過不斷迭代值函數(shù)來逼近最優(yōu)策略的強(qiáng)化學(xué)習(xí)方法，是基于時間差分法的離策略學(xué)習(xí)方法，同時也是目前解決馬爾科夫決策問題，廣泛應(yīng)用于路徑規(guī)劃的有效算法。算法的核心思想就是創(chuàng)建一張Q值表，并通過每次循環(huán)后的獎勵R和Q估計值來更新Q表中的Q(s,a),即qπ(s,a)。待更新完Q值表后，選取該狀態(tài)下Q值最大，即狀態(tài)動作值函數(shù)最大所對應(yīng)的動作為最優(yōu)策略。具體算法原理如下。

步驟1對Q值表中的Q值進(jìn)行初始化。通常是以隨機(jī)設(shè)定的Q的初始值作為Q值初始表。

步驟2確定當(dāng)前狀態(tài)st。

步驟3基于ε-greedy策略根據(jù)Q值表選擇動作at并執(zhí)行。ε-greedy策略是一種最常見的隨機(jī)策略，利用ε-greedy策略來采取行動在迭代足夠多次的情況下可以有效避免某些動作的Q值無法更新，使得動作的選擇具有一定的隨機(jī)性。具體來說，飛機(jī)有1-ε的概率選擇該狀態(tài)下Q值最大所對應(yīng)的動作，而對于剩下ε的概率，則采取等概率的方式隨機(jī)選擇任意一個動作，這樣就能夠平衡好利用(即選擇Q值最大的動作)與探索(即選擇非最優(yōu)動作),具體公式為

(20)

式(20)中：argmaxf(x)函數(shù)表示使得f(x)達(dá)到最大值的自變量，在式(20)中是指使?fàn)顟B(tài)-行為值函數(shù)Q(s,a)取得最大值，也就是最優(yōu)狀態(tài)-行為值函數(shù)所對應(yīng)的動作；|A(s)|為在狀態(tài)s下所有可供選擇的動作數(shù)量。

步驟4獲得下一時刻狀態(tài)st+1和相應(yīng)的獎勵Rt+1。

步驟5根據(jù)迭代公式更新Q(st,at)。具體的迭代公式為

Q(st,at)new=Q(st,at)old+α[Rt+1+

γmax′aQ(st+1,a′)-Q(st,at)old]

(21)

式(21)中：α為學(xué)習(xí)率；γ為折扣系數(shù)；Q(st,at)old為t時刻在迭代更新之前的狀態(tài)-行為值函數(shù)；Q(st,at)new為在迭代更新之后的狀態(tài)-行為值函數(shù)；max′aQ(st+1,a′)為在下一時刻狀態(tài)st+1下所對應(yīng)的最大的Q值。

步驟6若飛機(jī)到達(dá)目標(biāo)狀態(tài)，也就是終點(diǎn)或者限制區(qū)域，停止迭代并返回到起始狀態(tài)，開始新一回合的迭代；否則，將回到步驟2開始繼續(xù)迭代更新Q值。

步驟7當(dāng)滿足式(21)時，迭代收斂，Q值表更新完成。此時基于貪婪策略根據(jù)最大的Q值選擇動作，即可尋找最優(yōu)策略搜索出最優(yōu)路徑。

相應(yīng)Q-Learning算法流程圖如圖2所示。

圖2 Q-Learning算法流程圖

4 仿真運(yùn)行

通過仿真進(jìn)行改航路徑規(guī)劃，從而為航空器計算出在某一時段內(nèi)經(jīng)過流量擁堵空域時從起點(diǎn)到終點(diǎn)且避開擁擠點(diǎn)的最優(yōu)路徑。仿真空域運(yùn)行環(huán)境為邊長20 km、區(qū)域為10×10的矩形柵格。其中，黑色柵格為限制區(qū)域，表示航路點(diǎn)上存在流量飽和現(xiàn)象，禁止航空器通行。灰色柵格和白色柵格為自由區(qū)域，允許航空器經(jīng)過，并且灰色柵格內(nèi)的航路點(diǎn)平均流量較高，接近飽和狀態(tài)，而白色柵格代表區(qū)域中的流量較低，航空器飛行較為暢通。

在仿真過程中，令折扣系數(shù)γ=0.99，學(xué)習(xí)率α=0.7。鑒于ε的取值會影響最終生成的航跡，ε取值越大，則說明智能體隨機(jī)選擇動作的概率就越大，相應(yīng)的，根據(jù)Q值表選擇該狀態(tài)下Q值最大的動作這一概率就會減小。為了探究ε的最佳取值，分別給ε以[0.1,0.5]為區(qū)間，0.1為步長進(jìn)行賦值，使ε在不同取值下分別運(yùn)行10次，計算出生成最優(yōu)改航路徑的長度、拐點(diǎn)和平均響應(yīng)時間等性能指標(biāo)，并進(jìn)行綜合比較，從而尋找出一條相對合適的改航路徑。其中，空域的起點(diǎn)是(1,10)，終點(diǎn)是(10,1)，黑線為原標(biāo)稱航跡，如圖3所示。

黑線為原標(biāo)稱航跡；黑色柵格為限制區(qū)域，表示航路點(diǎn)上存在流量飽和現(xiàn)象，禁止航空器通行；灰色柵格和白色柵格為自由區(qū)域，允許航空器經(jīng)過

如圖4所示，紅線是ε在不同賦值下的最優(yōu)改航路徑。

紅線為ε在不同賦值下的最優(yōu)改航路徑；黑色柵格為限制區(qū)域，表示航路點(diǎn)上存在流量飽和現(xiàn)象，禁止航空器通行；灰色柵格和白色柵格為自由區(qū)域，允許航空器經(jīng)過

鑒于航空器在實際航行過程中應(yīng)盡量沿原標(biāo)稱航跡飛行，可使其偏航距離(cross track error, XTK)較小，所以將改航路徑與標(biāo)稱航跡進(jìn)行分析對比，并把生成各改航路徑相應(yīng)的性能指標(biāo)整理出來，結(jié)果如表1所示。

分析仿真結(jié)果(表1)，總結(jié)如下。

表1 ε不同賦值下的仿真性能指標(biāo)

(1)觀察路徑長度的數(shù)值變化可知，當(dāng)對ε進(jìn)行不同的賦值時，所生成的最優(yōu)改航路徑的長度是一樣的。

(2)訓(xùn)練次數(shù)和平均響應(yīng)時間隨著ε的增加表現(xiàn)出先暫時波動后顯著增加的特點(diǎn)。當(dāng)ε取值為0.1，0.2，0.3時，完成改航路徑規(guī)劃所需的訓(xùn)練次數(shù)均在190±20次內(nèi)上下浮動，而相應(yīng)的平均響應(yīng)時間則都屬于(50, 60)這個區(qū)間內(nèi)，其數(shù)值相差不大。當(dāng)ε=0.4時，訓(xùn)練次數(shù)和平均響應(yīng)時間則大幅度增加，而把ε設(shè)為0.5時，該數(shù)值將會繼續(xù)呈現(xiàn)明顯的增長趨勢。而出現(xiàn)這樣的現(xiàn)象是因為當(dāng)ε越大，隨機(jī)選擇動作的概率就越大，也就是探索的概率會更大，那么反過來利用的可能性就隨之減少，這樣智能體想要尋找出一條最優(yōu)路徑所需要的時間就會大大增加。

(3)通過對比拐點(diǎn)個數(shù)和最大偏航距離之間的變化規(guī)律可以發(fā)現(xiàn)二者之間為負(fù)相關(guān)關(guān)系。當(dāng)拐點(diǎn)個數(shù)增加時，改航路徑就會更加貼合原標(biāo)稱航跡，從而能夠減小最大偏航距離。拐點(diǎn)個數(shù)增加也會導(dǎo)致轉(zhuǎn)彎次數(shù)等量增多，從而不利于管制員的指揮工作，同時對飛機(jī)的機(jī)動性提出更高的要求，加大駕駛員的操縱難度。因此，想要選擇一條合適的改航路徑，需要綜合考慮平衡好拐點(diǎn)個數(shù)和最大偏航距離之間的關(guān)系。既要控制拐點(diǎn)個數(shù)以保證管制員和駕駛員的工作負(fù)荷在規(guī)定范圍內(nèi)，又要讓航空器盡量沿原標(biāo)稱航跡飛行以免偏航距離過大，使其在臨近空域內(nèi)飛行進(jìn)而干擾到其他航空器的正常通行。

5 結(jié)論

(1)用柵格化的方式對空域運(yùn)行環(huán)境進(jìn)行簡化處理。根據(jù)航路點(diǎn)的流量將空域劃分為3種不同類型的柵格，分別代表不同擁擠程度的區(qū)域。其中，黑色柵格表示空中流量達(dá)到飽和的限制柵格，灰色柵格表示該區(qū)域平均流量超過實際容量的80%，而其他區(qū)域則顯示為白色柵格，如此一來便能對空域進(jìn)行離散化建模。

(2)結(jié)合航空器的實際運(yùn)行過程，采用馬爾科夫模型并將其中的獎勵進(jìn)行合理的設(shè)置。除了終點(diǎn)的獎勵為正值，剩下不同類型的柵格對應(yīng)不同的負(fù)獎勵，這樣便可保證航空器所飛行的改航路徑盡可能更短。并利用Q-Learning算法基于ε-greedy策略進(jìn)行迭代求解，對ε的取值進(jìn)行探究，從而尋找出一條較為合適的改航路徑。

(3)仿真結(jié)果表明：應(yīng)用該模型和算法能夠及時在某一時段的流量擁堵空域內(nèi)尋找出一條從起點(diǎn)飛往目標(biāo)點(diǎn)，且能夠遠(yuǎn)離流量擁擠點(diǎn)、縮短空中延誤時間的改航路徑，且路徑長度較短，拐點(diǎn)個數(shù)較少，具有良好的響應(yīng)速度。根據(jù)飛行計劃、氣象信息、航空器發(fā)送的廣播式自動相關(guān)監(jiān)視(automatic dependent surveillance-broadcast，ADS-B)數(shù)據(jù)等一系列航行情報計算出相應(yīng)的實時飛行流量，并結(jié)合該空域的實際容量進(jìn)行飛行航跡的規(guī)劃，使其能廣泛應(yīng)用于流量管理層面，智能化地為管制人員進(jìn)行輔助決策，是有效解決空域擁堵的重要方式之一。