基于改進DQN 算法的機器人路徑規劃

李奇儒，耿 霞

（江蘇大學 計算機科學與通信工程學院，江蘇 鎮江 212000）

0 概述

近年來，移動機器人的路徑規劃成了研究熱點［1］。路徑規劃問題是指機器人能夠在不發生碰撞的前提下，在陌生環境中規劃出一條從出發點到目標點的最優路徑。傳統的路徑規劃算法包括A*算法［2］、蟻群算法［3］、遺傳算法［4］和強化學習［5］等。近年來，隨著深度學習的快速發展，出現了深度強化學習（Deep Reinforcement Learning，DRL）［6］。該方法 將深度神經網絡與傳統強化學習相結合，解決了強化學習中難以解決的維數災難問題［7］，使機器人能夠應對更加復雜和高維的環境。

在基于深度強化學習的路徑規劃領域，應用較廣泛的是DeepMind 團隊提出的深度Q 網絡（Deep Q Network，DQN）［8］。傳統的DQN 算法存在以下缺點：1）過估計，即網絡模型輸出的估計值大于真實值，且對于值函數的每個點，被過估計的幅度往往不盡相同，這就導致在很多情況下機器人會選擇次優策略而忽略最優策略，從而影響路徑規劃的效果；2）樣本利用率低，由于DQN 算法采用隨機均勻的方式從經驗池中抽取樣本進行訓練，因此導致算法可能會重復選取一部分樣本進行訓練而忽略另一部分，從而降低網絡收斂速度，影響網絡訓練效果。

許多學者提出了多種DQN 改進算法來解決過估計問題。文獻［9］提出雙深度Q 網絡（Double Deep Q Network，DDQN）算法，該算法利用雙網絡二次估計動作價值，解決了貪婪策略導致的過估計問題。文獻［10］提出DDQN-SSQN 算法，通過分類存儲多維狀態信息，采用針對性訓練得到最優路徑信息，提高了算法穩定性和收斂速度。文獻［11］提出一種基于雙估計器的改進Speedy Q-learning 算法，分離對最優動作價值和最大Q 值的選擇，對過估計問題進行了優化。文獻［12］在貪婪策略的Q 值更新方式上考慮了跟蹤行為合格度，降低了過估計的影響。文獻［13］提出一種端到端步驟規劃器SP-ResNet，利用雙分支殘差網絡估計動作價值，提高了路徑規劃的速度。文獻［14］提出帶探索噪聲的EN-DQN 算法，根據添加噪聲引起的網絡輸出值變化選擇動作，并通過循環神經網絡記憶多步變化影響智能體的決策，從而優化網絡訓練效果。文獻［15］引入剪切雙Q 學習和參數探測噪聲網技術，減少了DQN 算法對動作價值的過估計。

針對樣本利用率低的問題，學者們也進行了一系列研究。文獻［16］提出優先經驗回放機制，提高了優質樣本的利用率。文獻［17］提出二次主動采樣方法，根據序列積累回報和TD-error 對樣本二次篩選，提煉高質量的樣本進行訓練。文獻［18］提出經驗的廣度和深度概念，創建經驗價值評價網絡，增加深度經驗的比例，利用并行探索結構，提高了經驗庫的廣度。文獻［19］優化了經驗回放的邏輯，減少了低值迭代，優化了對訓練樣本的選擇。文獻［20］提出IDQNPER算法，賦予存儲樣本權重，并按一定的優先順序發送到網絡進行訓練，同時去除相似度高的序列，提高了網絡訓練效果。文獻［21］提出一種基于優先級的深度強化學習方法，機器人通過傳感器獲取環境信息建立相應的數學模型，并用優先重放機制改進算法，提高了模型的收斂速度和魯棒性。對于基于卷積神經網絡的深度強化學習，文獻［22］提出一種改進經驗重放池的方法，提高了網絡收斂速度。

上述研究在一定程度上提高了DQN 算法的性能，但仍然存在因算法探索能力差導致的網絡收斂速度慢、訓練效果差的問題。針對該問題，本文提出ERDQN 算法，通過修改Q 值的計算方式，減少了重復狀態出現的次數，提高了機器人的探索能力，同時重新設計獎勵函數，使機器人的每一個動作都能得到即時的反饋。

1 深度強化學習方法

1.1 DQN 算法

傳統強化學習中的一個經典算法是Q-learning 算法，其核心思想是智能體通過不斷地與環境進行交互，學習更優的行為策略，逐漸更新完善Q-table。Q-table是狀態-動作表，表中值的含義是在某個狀態下執行某個動作時能夠獲得的最大期望獎勵。但當智能體所處的環境維度較高、出現的狀態較多時，繼續使用Q-table存儲狀態-動作值函數將會引起維數災難。

為了解決該問題，DeepMind團隊融合深度神經網絡與Q-learning算法，提出DQN 算法。DQN 算法是對Q-learning算法的改進，利用深度神經網絡動態生成Q值表，并通過不斷迭代更新神經網絡f的參數θ來逼近狀態-動作值函數。DQN算法流程如圖1所示。

圖1 DQN 算法流程Fig.1 Procedure of the DQN algorithm

DQN 算法的神經網絡結構由估計網絡和目標網絡兩部分組成，兩者僅網絡參數不同。算法通過估計網絡來根據當前的狀態估計動作空間中所有動作的Q 值，并協同目標網絡的輸出值來計算損失。估計網絡實時學習和更新網絡參數，且每隔一定回合將參數拷貝給目標網絡，以實現目標網絡的更新。在訓練時，需要隨機均勻地從經驗回放池中選取一批樣本與訓練樣本混合在一起作為訓練數據，從而破壞樣本的相關性。DQN 算法的損失函數是目標網絡與估計網絡輸出Q 值的差值的平方，如式（1）所示：

在計算出損失值后，DQN 通過梯度下降法更新網絡參數θ，梯度下降公式如式（3）所示：

1.2 DDQN 算法

Q-learning 算法通過貪婪策略更新狀態-動作價值，DQN 算法只是采用深度神經網絡來近似狀態-動作值函數，其核心依然是Q-learning 算法。DQN 算法無法克服Q-learning 算法對動作價值過估計的缺陷。因此，DeepMind 提出雙深度Q 網絡算法，以解決上述問題。

DDQN 算法僅改變了目標值的計算方式，其他部分和DQN 算法一致。在DDQN 算法中需要構建兩個網絡，分別用來估計動作和動作的價值。由于DQN 算法中已經采用雙網絡結構，因此在DDQN 算法中，只需要用估計網絡來確定動作，用目標網絡來確定該動作的價值。DDQN 算法中目標值的計算方式如式（4）所示：

2 ERDQN 算法

2.1 基于概率的狀態探索DQN 算法

傳統DQN 中的Q 值更新方式使得算法的探索能力較差，網絡訓練的效率較低［23］，從而影響網絡的收斂速度和路徑規劃效果。本文提出一種基于概率的狀態探索DQN 算法，該算法通過修改Q 值的計算方式，減少機器人在訓練時進入重復狀態的次數，使其能更好地探索新的狀態，同時提高了網絡收斂速度并優化了路徑規劃效果。

Q(s,a)的計算方式如式（5）所示：

其中：λ?(0,1)；E(s,a)是在Q(s,a)上乘以一個概率，計算方式如式（6）所示；P(s,a)的計算方式如式（7）所示。

基于概率的狀態探索DQN 算法通過修改Q 值的計算方式使Q(s,a)的值按權重分成兩部分：一部分是原始的Q(s,a)，另一部分是E(s,a)，其中E(s,a)=Q(s,a)×P(s,a)，P(s,a)是指在狀態s下選擇動作a的概率。在式（7）中，N為在狀態s下已經選擇過動作a的次數，由其計算方式可知在狀態s下選擇動作a的次數越多，即N越大，P(s,a)越小，E(s,a)越小，Q(s,a)總值越小。由于DQN 算法中Q(s,a)為動作價值函數，因此當Q(s,a)降低時，機器人就會更傾向于選擇動作空間中的其他動作，從而探索新的狀態，提高網絡收斂速度，避免收斂于局部最優。

2.2 基于改進獎勵函數的DQN 算法

在強化學習過程中，智能體需要做出動作來與環境進行交互，從而獲取獎勵值。根據獎勵值更新網絡參數和學習更優的行為策略［24］。因此，獎勵函數是基于強化學習的路徑規劃的重要部分，其設置的好壞會直接影響算法路徑規劃的效果和網絡的收斂情況。傳統DQN 算法中獎勵函數的設置方式如式（8）所示：

其中：C1通常為正數；C2通常為負數。

在傳統DQN 算法的獎勵函數中，機器人除了到達目標點和規劃失敗時能夠獲取獎勵值外，在其他狀態下均無法獲得即時有效的反饋。雖然機器人通過訓練仍然能夠規劃出所求路徑，但這個過程通常需要大量的回合且規劃出的路徑往往并非最優。因此，重新設計獎勵函數，如式（9）所示：

在式（9）中，機器人到達目標點時獲得獎勵C1(C1>0)，發生碰撞時獲得獎勵C2(C2<0)，其他情況下機器人獲得的獎勵為，其中，K是獎勵函數調整參數，θ為機器人移動前從機器人所在位置指向目標點位置的向量n1與機器人移動結束后的方向向量n2的夾角，θ?(0,π)。θ角示意 圖如圖2所示。

圖2 θ 角示意圖Fig.2 Diagram of the angle θ

d是機器人做出行動之前與目標點的距離，通過歐氏距離式（10）計算得到：

其中：(x1,y1)是機器人尚未移動時的位置坐標；(x2,y2)為目標點的位置坐標。在未到達目標點且未發生碰撞的情況下，獎勵值與距離d成反比。因為機器人與目標點之間的距離越遠，兩者之間存在障礙等不確定因素的概率越大，所以智能體徑直靠近目標點并不一定總是最優策略。

3 基于ERDQN 算法的機器人路徑規劃

路徑規劃問題是指移動機器人能夠規劃出一條到達終點且避開障礙物的最優路徑［25］。為了驗證ERDQN 算法的有效性，將ERDQN 算法應用在機器人路徑規劃上并設計了相應的對比實驗。圖3 為基于ERDQN 算法的移動機器人路徑規劃流程。

圖3 基于ERDQN 的機器人路徑規劃流程Fig.3 Procedure of robot path planning based on ERDQN

在路徑規劃實驗中，機器人每到達一次目標點，則記作一次成功的路徑規劃，得分為1，并繼續尋找下一個隨機生成的新目標點，當超時或發生碰撞時游戲結束。如果直到游戲結束機器人都沒有到達一個目標點，則記本局得分為0，否則根據該局游戲中機器人到達的目標點數量記錄相應的得分。

實驗設定機器人每到達一個目標點則增加一個單位長度。這種設定使得機器人不僅需要躲避障礙，還需要避免與自身發生碰撞。在多次連續搜尋目標點的情況下，增加了機器人規劃路徑的難度。

實驗獎勵函數采用改進的獎勵函數，如式（11）所示：

上述設定限制了移動機器人無法向后方移動，因此在本文實驗中機器人的動作空間包含3 個動作，如圖4所示，分別為向前移動、向左移動和向右移動。

圖4 機器人動作空間Fig.4 Action space of the robot

4 實驗結果與對比分析

首先，設置消融實驗，將基于概率的狀態探索DQN 算法與基于改進獎勵函數的DQN 算法分別與傳統DQN 算法進行對比，再將上述2 種算法與ERDQN 算法進行對比，驗證ERDQN 算法的有效性和穩定性。其次，將ERDQN 算法與傳統路徑規劃算法進行對比，驗證ERDQN 算法相較于傳統路徑規劃算法的優越性。最后，將ERDQN 與DDQN算法融合為ERDDQN 算法，與DTDDQN 算法進行對比［26］，進一步驗證基于概率的狀態探索DQN 和基于改進獎勵函數的DQN 算法的有效性和魯棒性。

4.1 實驗設計與環境配置

為了簡化實驗，使用PyGame 搭建實驗環境，深度學習框架為PyTorch。實驗設計如下：

1）消融實驗。實驗環境為如圖5（a）所示的環境1。將DQN、基于概率的狀態探索DQN、基于改進獎勵函數的DQN 和ERDQN 這4 種算法進行比較，驗證基于概率的狀態探索DQN 與基于改進獎勵函數的DQN 兩種算法的有效性。對比指標為機器人的平均得分和路徑規劃長度。

圖5 實驗環境Fig.5 Experimental environments

2）與傳統算法的對比。實驗環境為如圖5（b）所示的環境2。將ERDQN 算法與A*算法、RRT 算法進行比較，驗證ERDQN 算法相較于傳統路徑規劃算法的優越性。對比指標為路徑規劃長度和拐點個數。

3）與改進算法的對比。實驗環境為如圖5（b）所示的環境2。將ERDDQN 與DTDDQN 算法進行比較，進一步驗證基于概率的狀態探索DQN 與基于改進獎勵函數的DQN 兩種算法的有效性和魯棒性。對比指標為機器人所獲得的平均得分和路徑規劃的長度。環境2 相較于環境1 更加復雜，路徑規劃的難度更大，可以更好地驗證算法的魯棒性。

在圖5中，深灰色方格代表移動機器人，黑色方格代表障礙物，淺灰色方格代表目標點的位置。目標點由程序隨機生成。當機器人到達現有的目標點時，則刪除原有目標點，并隨機生成一個新的目標點。

當網絡訓練完畢后，將隨機生成目標點更改為按照一定的次序在10 個不同的位置上生成目標點。當機器人到達一個目標點時，則按照設定生成下一個目標點，直至機器人到達所有10 個目標點，則認為算法完成了一次路徑規劃，否則為一次失敗的路徑規劃。測試環境如圖6 所示，其中目標點的序號即代表目標點生成的次序。實驗配置如表1所示。

圖6 測試環境Fig.6 Testing environments

4.2 實驗參數設置

在路徑規劃實驗中，ERDQN 算法的網絡模型結構如圖7 所示。網絡模型參數如表2 所示。

表2 ERDQN 算法的網絡模型設置Table 2 Setting of network model of ERDQN algorithm 單位：個

神經網絡由3 層全連接神經元結構構成，分別為輸入層、隱藏層和輸出層。網絡的輸入信息是一個11 維的狀態張量，故輸入層由11 個神經元組成。隱藏層由256 個神經元組成。網絡輸出是一個3 維張量，表示動作空間中3 個動作的Q 值，因此輸出層由3 個神經元組成。激活函數為ReLU，優化器使用Adam，損失函數為MSELoss，其他實驗參數如表3所示。

在本文路徑規劃實驗中，探索率均初始化為1，并根據模擬退火的原則逐漸降低［27］。探索率的更新方法如式（12）所示：

其中：T表示人工設置當探索率降低為0 時的迭代次數；n表示當前正在進行的訓練回合數；N為超參數。在實驗中設置T=4 000、N=10 000。通過模擬退火的方式逐步降低探索率，可以使機器人獲取更充分的環境信息，從而得到更加豐富的樣本來訓練更穩定的網絡。

4.3 對比分析

4.3.1 消融實驗

在環境1 中4 種算法均進行了6 000 個回合的訓練，訓練的平均得分對比如表4、圖8 所示。由表4、圖8 可以看出，基于概率的狀態探索DQN 算法和基于改進獎勵函數的DQN 算法在整體上優于DQN 算法。當進行了6 000 個回合的訓練時：DQN 算法的平均得分為1.638；基于概率的狀態探索DQN 算法的平均得分為1.733，相對DQN 算法提高了5.8%；基于改進獎勵函數的DQN 算法的平均得分為1.813，相對DQN 算法提高了10.7%；ERDQN 算法的平均得分為1.947，相對DQN 算法提高了18.9%。由此可見：基于概率的狀態探索和優化獎勵函數的改進算法都能有效提高DQN 算法的性能，使算法避開障礙物并獲取更高得分的次數更多，規劃出的路徑更接近于最優；ERDQN 算法融合了基于概率的狀態探索DQN 和基于改進獎勵函數的DQN 兩種算法，進一步優化了DQN 算法的性能。

表4 4 種算法的平均得分Table 4 Average scores of four algorithms

圖8 4 種算法的平均得分曲線圖Fig.8 Average score curve graph of four algorithms

4 種算法的路徑規劃線路圖如圖9 所示，4 種算法規劃的路徑長度如表5 所示。由圖9、表5 可以看出：DQN 算法規劃出的路徑長度最長，為149；基于概率的狀態探索DQN 算法和基于改進獎勵函數的DQN 算法規劃出的路徑長度相同，為121；ERDQN算法規劃出的路徑長度最短，為119，相較于DQN 算法規劃出的路徑長度減少了20.1%。由此可以進一步證明基于概率的狀態探索和優化獎勵函數的改進算法的有效性。

表5 4 種算法規劃的路徑長度Table 5 Path lengths planned by four algorithms

圖9 環境1 中的4 種算法路徑規劃線路Fig.9 Path planning routes for four algorithms in environment 1

圖10 為DQN 與ERDQN 算法單次路徑規劃的平均獎勵值變化。由圖10 可以看出，在一定的訓練回合內，DQN 和ERDQN 算法的平均獎勵值都能穩定在一定范圍內，但ERDQN 算法在2 000 個回合左右收斂，而DQN 算法在2 500 個回合左右收斂，ERDQN 算法的收斂速度相較于DQN 算法提前了500 個回合，且收斂后ERDQN 算法的平均獎勵值比DQN 算法更高，證明了ERDQN 算法的性能優于DQN 算法。

圖10 DQN 與ERDQN 算法的平均獎勵值Fig.10 Average reward values between DQN and ERDQN algorithms

綜上所述，相較于傳統DQN 算法，ERDQN 算法具有更優的性能和更好的收斂性，可以使機器人在更少的訓練回合內獲取更高的得分并規劃出更優路徑。

4.3.2 與傳統算法的對比

將ERDQN 算法與A*、RRT 傳統路徑規劃算法進行對比。圖11 為3 種算法的路徑規劃線路圖，表6為3 種算法的路徑規劃長度，表7 為3 種算法的路徑規劃拐點個數。由圖11、表6、表7 可以看出，在環境2 中，ERDQN 算法與A*算法規劃的路徑長度均為131，低于RRT 算法的163。ERDQN 算法規劃出的路徑拐點個數為27，小于A*算法的32，并且小于RRT 算法的74。可見，ERDQN 算法在路徑規劃的效果上優于傳統A*算法和RRT 算法。

表6 3 種算法規劃的路徑長度Table 6 Path length planned by three algorithms

表7 3 種算法規劃路徑中的拐點個數Table 7 Number of inflection points in path planned by three algorithms 單位：個

4.3.3 與改進算法的對比

將基于概率的狀態探索DQN 與基于改進獎勵函數的DQN 兩種算法與DDQN 算法結合為ERDDQN 算法，與DTDDQN 算法進行對比，在環境2 中進行對比實驗。2 種算法均進行了6 000 個訓練回合。實驗指標為機器人的平均得分和路徑長度。平均得分如表8、圖12 所示。由表8、圖12 可以看出，當訓練進行到第6 000 個回合時，DTDDQN 算法的平均得分為1.303，ERDDQN 算法的平均得分為1.608，在整體上ERDDQN 算法的平均得分都要優于DTDDQN 算法，且隨著迭代次數的增加，探索率不斷降低，到第4 000 個回合探索率降低為0 時，DTDDQN 算法的平均得分有所下降，而ERDDQN算法的平均得分始終保持上升。

表8 2 種算法的平均得分Table 8 Average scores of two algorithms

圖12 2 種算法的平均得分曲線圖Fig.12 Average score curve graph of two algorithms

2 種算法的路徑規劃線路如圖13 所示，2 種算法規劃出的路徑長度如表9 所示。由圖13、表9 可以看出，在測試環境2 中進行機器人路徑規劃時，ERDDQN 和DTDDQN 算法規劃的路徑長度分別為133 和169，進一步證明了ERDDQN 算法在路徑規劃性能上要優于DTDDQN 算法。

表9 2 種算法規劃的路徑長度Table 9 Path lengths planned by two algorithms

圖13 環境2 中2 種算法的路徑規劃線路Fig.13 Path planning routes for two algorithms in environment 2

由此可以看出，ERDDQN 算法相較DTDDQN算法探索能力更強，能夠獲取更優路徑，更好地將環境探索與信息利用相結合。

5 結束語

本文對傳統DQN 算法進行改進，提出ERDQN算法。一方面，通過修改Q 值的計算方式，使得在網絡訓練過程中，某個狀態重復出現的次數越多，下一次出現該狀態的概率越低，從而使機器人可以更好地探索新狀態，更快地獲取更優的路徑。另一方面，改進了獎勵函數，通過結合機器人的移動方向和當前時刻機器人與目標點的距離，使機器人除到達目標點和發生碰撞的情況以外也能獲得即時反饋，優化了機器人路徑規劃的性能。通過多種環境下的實驗和測試分別驗證了ERDQN 算法的有效性和穩定性。但由于本文僅研究了靜態避障，未考慮存在動態障礙的情況，因此后續將針對ERDQN 算法做進一步改進，在環境中添加動態障礙物，使其在更復雜的環境中仍能夠獲取較優的路徑。