改進Deep Q Network的路徑規劃算法

山東交通學院信息科學與電氣工程學院(人工智能學院) 張洪博

隨著計算機技術、人工智能理論、即時定位與地圖構建（Simultaneous Localization And Mapping，SLAM）等技術的不斷成熟與發展，機器人技術的研究已經發展到一個嶄新的階段。路徑規劃作為機器人運動不可或缺的一部分，近些年國內外專家對其研究的熱情持續高漲，它已經成為移動機器人趨向人工智能化階段的核心技術。路徑規劃的目的是讓機器人在規定的區域內找到一條從起點到終點的無碰撞安全路徑，并讓這條路徑盡可能的短。機器人在運動過程中，能夠實時模擬出所在的環境。通過控制自身運動狀態，探測障礙物并計算安全路徑，最后成功到達任務地點。因此，一個性能良好的路徑規劃算法對移動機器人非常重要。移動機器人目前在許多領域都有著廣泛地應用，比如家庭掃地、物流分揀等。尤其在一些環境比較惡劣的情況下，使用移動機器人可以有效地避免對人身安全的危害。

移動機器人路徑規劃始于20世紀60年代末期，早期的迪杰斯特拉算法，后續的A*算法、人工勢場法、粒子群算法、RRT算法等都是經典之作。但傳統的路徑規劃算法自身的收斂速度較慢、計算復雜度較高及適用性較差，所以將深度強化學習方法引入到路徑規劃中。DQN算法作為深度強化學習的一種，本文在其基礎上，改進樣本訓練方法，提高路徑規劃的效率、準確性以及實時性。

1 算法介紹

1.1 DQN算法

DQN算法作為深度強化學習的代表之一，不僅在Atari游戲中被測試出有很好的效果，在路徑規劃中也表現優異。該算法在Qlearning算法的基礎上，結合了卷積神經網絡來擬合動作值函數。通過經驗回放（Experience Replay）打破數據間的關聯性，從而解決數據的非靜態分布問題，并使用目標網絡和當前網絡共同解決模型穩定性問題。相比較于其他模型，DQN具有較強的通用性，可用于解決不同類型的問題。DQN算法的網絡結構如圖1所示。

圖1中，DQN中存在兩個結構完全相同但是參數卻不同的網絡，即目標網絡和當前網絡。當前網絡使用的是最新的參數，而目標網絡所用的參數是N步之前的。Q(s,a;θ)表示當前網絡的輸出，用來評估當前的狀態-動作對；Q(s′,a′;θ－)表示目標網絡的輸出。根據公式(1)可以解出TargetQ，并根據公式(2)更新當前網絡的參數。每經過一定次數的迭代，將當前網絡的參數復制給目標網絡。這樣就完成了一次學習過程。

圖1 DQN算法結構圖

1.2 本文算法

DQN算法在進行樣本數據采集的時候，沒有對樣本數據進行優良區分。在訓練的時候，所有的樣本都有相同的概率被隨機抽取到。然而，每個樣本對訓練的貢獻度是不一樣的。本文對原DQN算法進行了改進，重點關注機器人當前位置的相鄰位置，設計如圖2所示的矩陣，對訓練樣本進行相似度篩選。

圖2 篩選矩陣

首先對當前點的周邊情況進行計算，返回一個代表周邊障礙物情況的3×3矩陣，1代表障礙物，0代表空白，如圖3所示。

圖3 障礙物矩陣

對兩個矩陣進行哈達馬積運算，然后求和，由此得到一個數值。通過實驗驗證得到，當表示周邊障礙物的矩陣改變時，最后求出的結果也會改變，這說明設計的矩陣可以用來計算訓練樣本的相似性。通過此方法，將相似度高的樣本數據剔除，減少冗余樣本，保留樣本的多樣性。

2 實驗過程

2.1 實驗設置

本實驗采用柵格地圖進行仿真，其中柵格地圖的大小為25×25。在每一張測試地圖里設定起始點和目標點，然后隨機生成設定數量的障礙物。如圖4所示。

圖4 仿真環境

將每一張柵格地圖作為輸入輸送到神經網絡，分別利用DQN算法和改進后的DQN算法進行測試。如果能從起點走到終點，并且不與障礙物發生碰撞，則把找到的路徑畫出。否則即為失敗，不顯示圖像。

2.2 實驗結果

實驗使用隨機生成的20張25×25的柵格地圖。藍色方塊代表當前位置，綠色方塊代表終點位置，白色為可以通過的路徑。在地圖中隨機生成40個代表障礙物的黑色方塊，從起始點無碰撞走到目標點即為成功。圖5和圖6分別為DQN算法的測試地圖和測試結果，圖7和圖8分別為改進DQN算法的測試地圖和測試結果。

圖7 改進DQN算法的測試地圖

圖8 改進DQN算法的測試結果

DQN算法的測試地圖如圖5所示。

圖5 DQN算法的測試地圖

DQN算法的測試結果如圖6所示。

圖6 DQN算法的測試結果

對DQN算法使用柵格地圖進行測試，經過訓練，獲得了穩定的路徑規劃能力。在20張測試地圖中，成功到達目標點的有16張，成功率達到80%。

改進DQN算法的測試地圖如圖7所示。

改進DQN算法的測試結果如圖8所示。

在實驗中，DQN算法對路徑規劃的成功率達到了80%，改進的DQN算法成功率更是達到95%。相比較而言，改進后的DQN算法比原始DQN算法提高了15%的成功率，效果更好。

結論：本文針對原DQN算法存在樣本訓練效率低下，樣本冗余等問題，提出了一種改進的DQN算法。本文算法通過使用設計的矩陣對數據樣本的訓練方式進行優化，剔除相似度高的數據樣本，獲得高質量的樣本數據。通過測試，本文算法提高了訓練模型的準確度，在規劃路徑方面有明顯地提升。