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

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

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

具備學習能力是人類智能的特點，人們在處理問題時之所以能判斷問題的關鍵并給出正確的決策，其原因在于人們擅長在處理問題的過程中總結經驗教訓，找到正確處理某項事務的規(guī)律性。使計算機具備學習的能力且模擬或實現學習以專家經驗為目的的機器學習[2]是人工智能運用于智能選線的一個全新領域，它的研究對于智能選線的進一步發(fā)展有著舉足輕重的作用。

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

基于深度強化學習的公路初始路徑生成的實現可解決人工選擇路線無法趨近于最優(yōu)的問題，為基于深度強化學習的公路路線路徑的生成提供基礎。

1 模型的建立

1.1 馬爾科夫決策過程

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

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

圖1 強化學習模型Fig. 1 Reinforcement learning model

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

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

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

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

因為動作空間A，狀態(tài)空間S均為有限集合，所以可以采用求和的方式來計算其對應的期望，對于策略π和任何狀態(tài)S，都可以將式(2)表示為：

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

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

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

1.3 獎勵函數的設定

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

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

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

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

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

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

2 深度Q學習算法在的應用

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

圖3 深度Q學習模型Fig. 3 The deep Q-learning model

2.1 主體框架

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

時間差分采用經驗回放的方法來提升神經網絡的效果。智能體從很多的回合中獲得經驗將它存儲到經驗池D中形成了一個緩存空間，然后，從這個空間中隨機采樣來獲得樣本進行網絡的訓練。則其損失函數可表達為：

經驗回放可以打破數據間的關聯使神經網絡能夠收斂且穩(wěn)定[7]。

2.2 ε-greedy 策略

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

2.3 算法流程

采用強化學習的值函數估計的方法，并使用深度神經網絡來進行擬合。為解決智能體在一個回合中走相同的位置或者陷入一些無效的區(qū)域，采用禁止智能體回頭和重復走相同位置的方法，減少了智能體一些無效的學習?？紤]歷史學習經驗的深度Q學習算法步驟為：

1) 開始。

2) 初始化經驗池 D和設置經驗池的最大容量N。

3) 初始化當前網絡參數θ和目標網絡參數θ-。

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

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

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

9) 從經驗池D中抽取經驗。

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

12) 更新動作值函數逼近的網絡參數θ =θ+Δθ 。

13) 每隔 C步更新一次時間差分目標網絡權值，即令θ-=θ。

14) 結束。

3 實驗結果

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

圖4 訓練過程曲線Fig. 4 Training process

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

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

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

4 結語

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

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