基于深度強(qiáng)化學(xué)習(xí)的公路初始路徑尋優(yōu)方法

李懿，韓春華，錢熙，孟靖凱

(昆明理工大學(xué) 交通工程學(xué)院，云南 昆明 650500)

選線是新建道路從規(guī)劃設(shè)計(jì)到投入使用過程中的關(guān)鍵環(huán)節(jié)。目前，中國的道路設(shè)計(jì)選線仍然采用人工的方式。通過設(shè)計(jì)者的經(jīng)驗(yàn)對路線進(jìn)行比選。且通過經(jīng)驗(yàn)選取的路線沒有一個(gè)標(biāo)準(zhǔn)對其優(yōu)劣進(jìn)行評價(jià)，只存在相對而言較優(yōu)的路線。因環(huán)境復(fù)雜決定了路線設(shè)計(jì)將是一個(gè)漫長且包含著大量重復(fù)工作的過程[1]。因此，采用智能化的方式進(jìn)行選線可以縮短設(shè)計(jì)路線和節(jié)省許多重復(fù)工作。

具備學(xué)習(xí)能力是人類智能的特點(diǎn)，人們在處理問題時(shí)之所以能判斷問題的關(guān)鍵并給出正確的決策，其原因在于人們擅長在處理問題的過程中總結(jié)經(jīng)驗(yàn)教訓(xùn)，找到正確處理某項(xiàng)事務(wù)的規(guī)律性。使計(jì)算機(jī)具備學(xué)習(xí)的能力且模擬或?qū)崿F(xiàn)學(xué)習(xí)以專家經(jīng)驗(yàn)為目的的機(jī)器學(xué)習(xí)[2]是人工智能運(yùn)用于智能選線的一個(gè)全新領(lǐng)域，它的研究對于智能選線的進(jìn)一步發(fā)展有著舉足輕重的作用。

本研究在 Mnih[3]用強(qiáng)化學(xué)習(xí)的方式讓智能體自動學(xué)會玩游戲，探索強(qiáng)化學(xué)習(xí)在選線領(lǐng)域的方法應(yīng)用。Mnih提出了“利用強(qiáng)化學(xué)習(xí)從高維輸入中直接學(xué)習(xí)控制策略”的深度學(xué)習(xí)模型。該模型使用卷積神經(jīng)網(wǎng)絡(luò)，經(jīng)過Q-learning算法的訓(xùn)練，輸入圖像像素，輸出預(yù)估的獎勵值(reward)函數(shù)，并將此方法應(yīng)用于7款atari游戲，且在3款游戲中超過了人類專家。得益于Mnih的研究，很多基于感知識別并采取決策的問題得以解決。智能選線的條件與Mnih的研究相關(guān)的眾多決策問題擁有共同的理論基礎(chǔ)，都遵循于馬爾科夫決策過程：理想的狀態(tài)是可檢測的；可以進(jìn)行多次嘗試；系統(tǒng)的下個(gè)狀態(tài)只與目前的狀態(tài)信息有關(guān)，而與較早之前的狀態(tài)無關(guān)；決策過程還與當(dāng)前采取的動作有關(guān)。采用強(qiáng)化學(xué)習(xí)來解決路線優(yōu)化問題。因此，作者提出基于深度強(qiáng)化學(xué)習(xí)的公路初始路徑尋優(yōu)方法，擬實(shí)現(xiàn)的過程為：①構(gòu)建基于馬爾科夫決策過程的最優(yōu)路徑問題模型和適用于選線的強(qiáng)化學(xué)習(xí)方法模型。以全局最大價(jià)值獎勵為目標(biāo)，建立適合于線路標(biāo)準(zhǔn)的智能體獎勵規(guī)則。②將Q-learning算法思想采用神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化。使用“時(shí)間差分”的方法，對神經(jīng)網(wǎng)絡(luò)參數(shù)進(jìn)行更新(神經(jīng)網(wǎng)絡(luò)解決了 Q-learning算法“維度災(zāi)難”的問題，使網(wǎng)絡(luò)能夠快速達(dá)到收斂)。③采用神經(jīng)網(wǎng)絡(luò)接收狀態(tài)和行為信號，并輸出所采取行為的價(jià)值。經(jīng)過多個(gè)回合訓(xùn)練后，神經(jīng)網(wǎng)絡(luò)收斂到一定的水平，生成一條較為合理的最優(yōu)路徑。

基于深度強(qiáng)化學(xué)習(xí)的公路初始路徑生成的實(shí)現(xiàn)可解決人工選擇路線無法趨近于最優(yōu)的問題，為基于深度強(qiáng)化學(xué)習(xí)的公路路線路徑的生成提供基礎(chǔ)。

1 模型的建立

1.1 馬爾科夫決策過程

馬爾科夫決策過程(Markov Decision Process,簡稱為 MDP)是強(qiáng)化學(xué)習(xí)中最基本的理論模型[4]。通常情況下，MDP可以表示為 ＜ S , A, R, T ＞四元組的形式：S為狀態(tài)空間(State Space)，包含了智能體可能感知到的所有環(huán)境狀態(tài)的集合；A為動作空間(Action Apace)，包含了智能體在每個(gè)狀態(tài)上可以選取的所有動作集合；R：S × A × S → R 為獎勵函數(shù)(Reward Function)， R ( s , a, s′)表示在狀態(tài)s上選取動作 a，并轉(zhuǎn)移到狀態(tài) s?時(shí)，智能體從環(huán)境變換中所反饋的獎勵；T： S ×A×S→[0,1]為環(huán)境的狀態(tài)轉(zhuǎn)移函數(shù)(State Transition Function)，T ( s , a, s′)表示在狀態(tài)s上選取動作a，并轉(zhuǎn)移到狀態(tài)s?的概率。

在MDP中，智能體和環(huán)境之間的交互過程如圖1所示。智能體感知當(dāng)前環(huán)境狀態(tài)st，從動作空間A中選取動作at并執(zhí)行；當(dāng)環(huán)境接收到智能體所選取的動作之后，智能體反饋到相應(yīng)的獎勵信號rt+1，并移動到新的環(huán)境狀態(tài)st+1，等待智能體做出新的決策。因此，可以對基于柵格的最優(yōu)路徑問題建立模型。

圖1 強(qiáng)化學(xué)習(xí)模型Fig. 1 Reinforcement learning model

1.2 基于柵格地形的最優(yōu)路徑DMP模型

設(shè)定一個(gè)智能體在實(shí)際地形中執(zhí)行尋路任務(wù)后，定義柵格地形中包含地理屬性的每個(gè)單元所組成的集合為智能體進(jìn)行交互的環(huán)境，其中：M{m0,m1,m2,…,mt}為每個(gè)柵格單元所包含地理屬性的集合。在與環(huán)境交互的過程中，智能體每移動一個(gè)單元，都會獲得環(huán)境變化所反饋的獎勵，而智能體最終的目標(biāo)是尋求一個(gè)最優(yōu)策略π*，使它在任意狀態(tài)s和任意時(shí)間步驟t下，都能夠獲得最大的長期累積獎勵。即：

為了最優(yōu)策略π*，在智能選線中尋求的最優(yōu)狀態(tài)值函數(shù)為：

或最優(yōu)狀態(tài)-動作值函數(shù)為：

因?yàn)閯幼骺臻gA，狀態(tài)空間S均為有限集合，所以可以采用求和的方式來計(jì)算其對應(yīng)的期望，對于策略π和任何狀態(tài)S，都可以將式(2)表示為：

式(4)即為著名的貝爾曼(Bellman)方程。由式(4)可知，若狀態(tài)轉(zhuǎn)移概率和獎勵函數(shù)已知，則可求得態(tài)值函數(shù)。由狀態(tài)值函數(shù)與狀態(tài)-行為值函數(shù)的關(guān)系，可以將狀態(tài)-行為值函數(shù)表示為：

將式(6)代入式(5)中，得：

由式(8)，(9)可知，在某個(gè)狀態(tài)下的最優(yōu)價(jià)值函數(shù)為智能體在當(dāng)前狀態(tài)下所能獲得的累計(jì)期望獎勵的最大值。

1.3 獎勵函數(shù)的設(shè)定

獎勵函數(shù)定義了智能體在專家采取策略時(shí)所要選擇的目標(biāo)特征，智能體在所感知的環(huán)境狀態(tài)中反饋一個(gè)強(qiáng)化信號 r，對其動作所產(chǎn)生的影響給出一種評價(jià)。因此，對智能體變換環(huán)境所產(chǎn)生的屬性變化設(shè)定一個(gè)評價(jià)規(guī)則，即：

式中：Δm為環(huán)境屬性的變化。

設(shè)：當(dāng)環(huán)境變化時(shí)，高差的變化或者坡度的變化為屬性的改變。當(dāng)高差的變化大于c時(shí)，智能體就會從環(huán)境中反饋到對其不利的信號 r，其他的情況保持獎勵不變，這樣能夠保證智能體在滿足約束條件下有探索最短路徑的能力。

如圖2所示，以s(2,3)為例，將s(2,3)作為狀態(tài)s，則處于當(dāng)前狀態(tài)可以選取的動作空間有上、下、左、右 4種方式，以高差最小為智能體選擇行為所回饋的最大獎勵，則智能體將有較大概率學(xué)習(xí)上、下、左、右的行為中價(jià)值最大的行為，并在每個(gè)回合中不斷強(qiáng)化，最終使獎勵函數(shù)達(dá)到最大值。

圖2 獎勵反饋過程Fig. 2 Reward feedback process

在實(shí)際選線的過程中，由于地形環(huán)境條件的限制，通常專家們會采取一些相對應(yīng)的解決措施。如：自然保護(hù)區(qū)、地質(zhì)災(zāi)害地段，在路線設(shè)計(jì)的過程中會合理地選擇避開；或者有一些站點(diǎn)是路線必須經(jīng)過的地方，在專家的選線經(jīng)驗(yàn)中就得予以考慮。若該情形設(shè)置智能體在途徑禁止通行區(qū)域時(shí)，環(huán)境反饋一個(gè)負(fù)向的信號 r；通過必經(jīng)站點(diǎn)時(shí)，環(huán)境反饋一個(gè)正向的信號 r。這樣，就能保證智能體在經(jīng)歷學(xué)習(xí)之后，會走符合要求的路線，也會順利避開禁止通過的區(qū)域。設(shè)禁止通行的區(qū)域?yàn)榧蟧={o0,o1,o2,…}，必經(jīng)區(qū)域集合為p={p0,p1,p2,…}，則環(huán)境反饋的信號為：

2 深度Q學(xué)習(xí)算法在的應(yīng)用

基于提出的模型，將Q-learning的思想用神經(jīng)網(wǎng)絡(luò)來進(jìn)行優(yōu)化。把智能體所處的位置S和所要采取的行為A輸入神經(jīng)網(wǎng)絡(luò)，再從神經(jīng)網(wǎng)絡(luò)輸出狀態(tài)-行為值，將狀態(tài)-行為值函數(shù)表示為 Q ( s, a;θ) ，其中：θ為神經(jīng)網(wǎng)絡(luò)的參數(shù)。深度Q學(xué)習(xí)模型如圖3所示。

圖3 深度Q學(xué)習(xí)模型Fig. 3 The deep Q-learning model

2.1 主體框架

考慮到有很多離散的方向選擇動作和問題的應(yīng)用情形，本研究采用的深度Q學(xué)習(xí)基于值函數(shù)的強(qiáng)化學(xué)習(xí)方法。先建立2個(gè)結(jié)構(gòu)相同的神經(jīng)網(wǎng)絡(luò)：①值函數(shù)網(wǎng)絡(luò)(target網(wǎng)絡(luò))；②逼近值函數(shù)所用的網(wǎng)絡(luò)(eval網(wǎng)絡(luò))。得到2個(gè)網(wǎng)絡(luò)之間的偏差。通過時(shí)間差分的方式來更新當(dāng)前的行為值函數(shù)。由此，深度Q學(xué)習(xí)中每一輪迭代的損失函數(shù)為[6]：

時(shí)間差分采用經(jīng)驗(yàn)回放的方法來提升神經(jīng)網(wǎng)絡(luò)的效果。智能體從很多的回合中獲得經(jīng)驗(yàn)將它存儲到經(jīng)驗(yàn)池D中形成了一個(gè)緩存空間，然后，從這個(gè)空間中隨機(jī)采樣來獲得樣本進(jìn)行網(wǎng)絡(luò)的訓(xùn)練。則其損失函數(shù)可表達(dá)為：

經(jīng)驗(yàn)回放可以打破數(shù)據(jù)間的關(guān)聯(lián)使神經(jīng)網(wǎng)絡(luò)能夠收斂且穩(wěn)定[7]。

2.2 ε-greedy 策略

通過神經(jīng)網(wǎng)絡(luò)，獎勵被反饋到?jīng)Q策階段，智能體是要采取當(dāng)前最優(yōu)價(jià)值下的路徑還是選擇探索更優(yōu)的路徑是當(dāng)下需要解決的問題。在模擬環(huán)境開始的階段，對Q-網(wǎng)絡(luò)進(jìn)行隨機(jī)初始化。由于它給出的 Q最高的行為是隨機(jī)的，智能體表現(xiàn)出隨機(jī)的“探索”。當(dāng)網(wǎng)絡(luò)收斂時(shí)，隨機(jī)“探索”的情況逐漸減少。但是，這種探索是“貪心的”，智能體只會探索當(dāng)前模型認(rèn)為最好的策略[8]。因此，本研究采用ε-greedy貪心策略來決定動作的選取，ε-greedy策略的最大化平衡了“利用”和“探索”之間的概率關(guān)系，選擇動作空間中價(jià)值最大的動作為利用，其他非最優(yōu)動作仍有概率去進(jìn)行探索。

2.3 算法流程

采用強(qiáng)化學(xué)習(xí)的值函數(shù)估計(jì)的方法，并使用深度神經(jīng)網(wǎng)絡(luò)來進(jìn)行擬合。為解決智能體在一個(gè)回合中走相同的位置或者陷入一些無效的區(qū)域，采用禁止智能體回頭和重復(fù)走相同位置的方法，減少了智能體一些無效的學(xué)習(xí)?？紤]歷史學(xué)習(xí)經(jīng)驗(yàn)的深度Q學(xué)習(xí)算法步驟為：

1) 開始。

2) 初始化經(jīng)驗(yàn)池 D和設(shè)置經(jīng)驗(yàn)池的最大容量N。

3) 初始化當(dāng)前網(wǎng)絡(luò)參數(shù)θ和目標(biāo)網(wǎng)絡(luò)參數(shù)θ-。

4) 初始化狀態(tài)空間s0。

5) 利用概率ε選取隨機(jī)行為at。若隨機(jī)事件沒有發(fā)生，則用貪婪策略選取最大動作值函數(shù)對應(yīng)的動作。

6) 模擬動作 at并觀察獎勵 rt和執(zhí)行動作下的環(huán)境st+1。

9) 從經(jīng)驗(yàn)池D中抽取經(jīng)驗(yàn)。

11) 執(zhí)行一次梯度下降算法。

12) 更新動作值函數(shù)逼近的網(wǎng)絡(luò)參數(shù)θ =θ+Δθ 。

13) 每隔 C步更新一次時(shí)間差分目標(biāo)網(wǎng)絡(luò)權(quán)值，即令θ-=θ。

14) 結(jié)束。

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

依托云南某山地地形進(jìn)行訓(xùn)練，選取地形范圍為2.02×1.16 km2。為避免智能體過早地陷入局部最優(yōu)以及權(quán)衡當(dāng)前和遠(yuǎn)期的利益，需要合理設(shè)置學(xué)習(xí)率和折扣率，本實(shí)驗(yàn)設(shè)置學(xué)習(xí)率為0.01，折扣率為0.9，貪心度為0.1，坡度約束為8%。將實(shí)驗(yàn)的過程以可視化的方式進(jìn)行了展示。訓(xùn)練過程曲線如圖4所示。從圖4中可以看出，在150個(gè)回合前，為智能體對路徑的探索；在150個(gè)回合后，網(wǎng)絡(luò)達(dá)到了收斂，路徑探索終止。

圖4 訓(xùn)練過程曲線Fig. 4 Training process

圖5 虛擬環(huán)境下生成最優(yōu)路徑Fig. 5 The generation of the optimal path in the virtual environment

實(shí)驗(yàn)采用python語言進(jìn)行了編程，以圖形化的方式將智能體與環(huán)境交互的過程展示出來，并在模擬環(huán)境下繪制路徑，如圖5所示。在圖5中區(qū)域?yàn)槁肪€走向，藍(lán)色區(qū)域?yàn)槎x的禁止通行區(qū)域。導(dǎo)出最終路徑數(shù)據(jù)，在地形圖中生成路徑，路徑長度為2.21 km，如圖6所示。智能體在山體中探索路徑具有對禁止通行的區(qū)域進(jìn)行繞避的能力，也能成功避開地勢較高的區(qū)域，選擇符合要求的最優(yōu)路徑。

圖6 地形環(huán)境中生成最優(yōu)路徑Fig. 6 The generation of the optimal path in the terrain environment

4 結(jié)語

公路初始路徑的生成以最小坡度為目標(biāo)，通過智能體反復(fù)遍歷全圖柵格，不斷強(qiáng)化目標(biāo)信息，生成目標(biāo)條件下的最優(yōu)路徑。該方法可以在指定的起始點(diǎn)和終點(diǎn)之間生成滿足要求的最優(yōu)路徑，解決了選線過程中通過經(jīng)驗(yàn)選擇路線的弊端，也為基于強(qiáng)化學(xué)習(xí)的公路路線路徑生成打下了基礎(chǔ)。

本研究采用強(qiáng)化學(xué)習(xí)法在智能選線中的應(yīng)用做出了一些嘗試，但還未成熟。如：在復(fù)雜的地形條件下，智能體所學(xué)習(xí)的特征過于單一。在實(shí)際地形情況下，存在著高山變平地，平地變高山，或者需要跨過河流諸如此類的復(fù)雜地形，這就需要智能體有感知能力。監(jiān)督學(xué)習(xí)能通過智能體對地形的識別來決定未來探索的方向。強(qiáng)化學(xué)習(xí)在選線方面的應(yīng)用還存在著較大的潛力，且前景廣闊。