基于深度Q網絡的改進RRT路徑規劃算法

李昭瑩，歐一鳴，石若凌

（1.北京航空航天大學宇航學院，北京 100191；2.哈爾濱工業大學（深圳）機電工程與自動化學院，廣東深圳 518055）

0 引言

在無人車智能化的相關領域中，路徑規劃是一個關鍵環節，也是當前的研究熱點。從大型無人駕駛客車，到小型無人配送車、無人掃地車等，均需要進行路徑規劃。路徑規劃是在模型空間中找到一條從起始點到目標點的路徑解，其路徑解需滿足一定的約束條件，并根據實際需要滿足一定的性能指標（路徑長短、時間、能耗等）。通常情況下，周圍的環境由一些障礙物與威脅區域組成，得到的路徑不僅要滿足車輛的各種約束，同時要保證車輛沿該路徑行駛時不與障礙物發生任何碰撞。

經過多年發展，各種各樣的路徑規劃算法相繼出現，如Dijkstra 算法、A*算法、人工勢場法、概率路圖（probabilistic roadmap，PRM）算法、RRT 算法等。Dijkstra 算法和A*算法均需對地圖離散化，存在算法效率低的問題［1-2］；人工勢場法采用虛擬力的思想，保證了實時性但易陷入局部零勢能點［3］；PRM 算法結合了隨機采樣方法和A*算法，使其效率較A*算法效率有了很大提高，但有可能無法得到路徑解［4］；LaValle 于1998年提出的RRT算法，具有無需對狀態空間進行建模、簡單高效等優點［5-6］，但也具有隨機性大、路徑質量非最優等問題。許多學者提出了一系列RRT 算法的改進算法：LaValle和東京大學的Kuffner提出了RRTConnect 算法，搜索效率相比于RRT 算法搜索效率有了顯著提高，但采樣仍具有很強隨機性［7］；Sertac 等提出了漸進最優的RRT*算法，可以得到漸進最優解，但這也導致算法的效率較RRT算法效率有所下降，并且這種現象隨著隨機樹的拓展愈發明顯［8-9］；劉成菊等將人工勢場法中引力的思想引入RRT算法，增強了隨機樹延伸的導向性，但可能會陷入局部極小值，因此如何因地制宜地選擇合適的引力系數Kp是關鍵［10］。

隨著人工智能技術的發展，深度強化學習近年來取得了可喜的進展。2017年，DeepMind 團隊推出了AlphaGo，擊敗了圍棋世界冠軍李世石，展現了深度強化學習的巨大潛力。作為深度強化學習算法之一的DQN算法，將深度學習和傳統Q-learning結合在了一起，很好地解決了Q-learning的維度災難問題，可以處理復雜的、高維的環境特征，并與環境進行交互，完成決策過程。

針對RRT算法及其變體存在效率不高的問題，本文首先提出了一種復數域變步長避障策略，使隨機樹延伸時具有更強的避障能力；根據所設計的避障策略，設計DQN的動作空間，并結合RRT算法的特點，進一步設計DQN 的狀態空間和獎勵函數，完成MDP 的建模。RRT 的算法結構有很多接口，因此可以將設計好的MDP與RRT-Connect的接口相結合［10］；最后設計訓練和路徑規劃相關流程，得到基于深度Q網絡的RRTConnect 算法（DQN-RRT-C），通過在MATLAB 軟件平臺上進行仿真實驗，驗證了算法的優勢。

1 原理簡介

1.1 RRT算法

RRT 算法中起始點作為根節點，然后通過隨機采樣增加葉子節點的方式，生成隨機樹并不斷拓展，最終隨機樹到達目標點或目標區域，得到路徑可行解，如圖1所示［11］。

圖1 RRT算法示意圖Fig.1 Illustration of RRT algorithm

圖1所示RRT算法隨機樹拓展過程可表達為

式中：d為常數，稱為步長（Step），在傳統RRT 算法中為正實數；xrand為隨機采樣點；xnear為隨機樹上距離xrand最近的葉子節點；xnew為新節點；若新樹枝遭遇障礙物，則放棄此次搜索拓展，重新采樣。為了控制隨機樹樹枝密度、減少無效延伸，還可以對采樣點增加限制，使

式中：rs為常數，若不滿足條件則重新采樣。這樣，隨機樹就更傾向于搜索那些還未涉足的區域，從而提高了搜索效率［12］。

為了提高RRT算法效率，RRT-Connect算法被提出。RRT-Connect 算法又被稱為雙向RRT 算法（bidirectional RRT，Bi-RRT）［13］。其基本思想是從初始點和目標點同時生長兩棵隨機樹并使之最終相連接，達到快速構建隨機樹、提高路徑規劃效率的目的，如圖2所示［7］。

圖2 RRT-Connect算法示意圖Fig.2 Illustration of RRT-Connect algorithm

圖2 中：xrand為隨機采樣點；xnear1為隨機樹1（圖2左側）上距離xrand最近的葉子節點；xnew1為隨機樹1 上的新節點；xnear2為隨機樹2（圖2 右側）上距離xnew1最近的葉子節點；xnew2為隨機樹2 上的新節點。一次搜索拓展包括隨機拓展和貪婪拓展兩大步驟，隨機樹1進行隨機拓展，隨機樹2 進行貪婪拓展。隨機拓展的過程與傳統的RRT算法的拓展過程相同；貪婪拓展則使用貪婪函數作為啟發函數，使xnew1與xnear2之間反復迭代產生新樹枝，直到遭遇障礙物或兩棵隨機樹成功連接［5］。若貪婪拓展后兩棵隨機樹未成功連接，則更換兩棵隨機樹的地位，進行下一次的搜索拓展。

與RRT 算法同理，在RRT-Connect 隨機拓展中也可以對采樣點增加限制，使

1.2 DQN算法

在實際問題中，智能體的狀態值數量可能會非常龐大，傳統的查表式Q-learning 算法將會耗費大量內存，甚至可能在現實中無法實現，因此需要構建神經網絡來近似得到所有Q值。

Q 值可以用一個近似的價值函數f(s，a；w)來擬合，即

式中：s為狀態；a為動作；w為函數f(s，a；w)的參數，函數的構建則通過訓練神經網絡來完成。為了便于描述，我們用Q(s，a；w)來表示這個近似的價值函數，即

在DQN算法中，目標Q值可表示為

式中：t表示當前時刻；t+1 表示下一時刻；Rt+1為獎勵；maxQ(st+1，a；w-)為st+1下所有動作的Q值的最大者；λ為折扣因子，為常量。以目標值和預測值之間的均方誤差作為損失函數L，即

式中：Q(st+1，a；w)為預測網絡，Q(st+1，a；w-)為目標網絡。w和w-為神經網絡的相關參數。簡而言之，DQN 利用神經網絡作為函數逼近器來逼近Q(s，a)，并通過梯度下降來最小化誤差［14］。

2 基于深度Q 網絡的RRT-Connect算法

2.1 避障策略

在傳統RRT 和RRT-Connect 算法中，若延伸遭遇障礙物，則放棄本次拓展重新采樣，因此，與RRT算法相比較，RRT-Connect 算法的導向性有所提高，但其避障能力卻有所下降。針對RRT-Connect 避障能力下降的問題，引入了復數步長的概念，即

式中：d0為步長長度，為正的實常數；θ為旋轉角度，范圍(-π，π]；znew、znear、zref分別為xnew、xnear、xref坐標對應的復數，xref為某個參考點。根據復數步長的概念，設計了復數域變步長的避障策略，如圖3所示。

圖3 參考點導向的避障策略Fig.3 Reference point-oriented obstacle avoidance strategy

當采樣點為參考點時，便包含5個可選擇的步長。當樹枝延伸時，只能選擇其中一個步長，而具體如何選擇步長，則要結合DQN算法。

2.2 MDP模型

根據2.1 節的避障策略，可以設計出DQN 算法相應的MDP模型。

1）狀態空間S

RRT 算法一般是基于一張二值像素地圖來進行路徑規劃的，灰度值為255 的區域是障礙物空間，為0的區域則是自由空間。圖中的每一個像素都作為地圖上的一個已知點，并有其對應的二維坐標。因此，模型的狀態空間S可表達為

式中：W為地圖的寬度，H為地圖的高度，由地圖的寬高像素數量決定。

2）動作空間A

動作空間即圖3 中5 個復數步長的集合，用一個列向量來表示

3）獎勵函數

由于以不同步長延伸，所得到的樹節點與目標點的接近程度不同，因此獎勵R是步長d的函數。

式中：Arg(d)表示復數步長d的輻角主值，條件P 的表述為：當樹枝以動作到達最優動作為或的區域時。最優動作的定義會在2.3.2 小節中介紹，該區域通常為十分接近障礙物的區域。

2.3 算法流程

2.3.1 訓練Q網絡

DQN 算法中Q 值的更新，可以概括為“當前狀態下選擇動作→執行動作→下一狀態→獎勵→更新Q值”幾步，而Q 值則使用神經網絡來擬合［14-15］。根據DQN 算法的神經網絡訓練方法，可以設計DQNRRT-C更新一次神經網絡的流程圖，如圖4所示。

圖4 中：Batchsize 表示一次訓練的樣本數。實際上往往需要進行多次訓練更新，在DeepMind 于2015年提出的DQN 算法中，每隔C次訓練就要把預測網絡的權值賦給目標網絡［16］。

圖4 一次訓練更新的流程圖Fig.4 Flow chart of training updating

2.3.2 提取最優動作表

最優動作即動作空間中Q 值最大的動作，一個狀態對應一個最優動作。最優動作表就是將自由區域中所有狀態下的最優動作用表格儲存。在擁有Q 網絡的情況下，可以使用Q 網絡分別計算所有狀態下的所有動作對應的Q 值，然后將各狀態下的最優動作提取出來制成最優動作表。提取出來的最優動作表，可以直接用于路徑規劃的動作選擇。

2.3.3 路徑規劃

根據得到的最優動作表，在地圖環境固定的情況下，可使用DQN-RRT-C算法進行路徑規劃。

與傳統RRT-Connect 算法相同，DQN-RRT-C 算法也包括隨機拓展和貪婪拓展2大步驟。隨機拓展具體方法與RRT-Connect 算法相同，貪婪拓展則增加了參考點導向避障的環節，如圖5所示。

圖5 DQN-RRT-C貪婪拓展流程Fig.5 Flow chart of greedy expansion for DQN-RRT-C

當貪婪拓展遭遇障礙物時，算法便會啟用參考點導向避障策略，即：以參考點為基準，結合最優動作表，使樹枝以5個復數步長中的一個延伸，達到避開障礙物的目的。由于參考點的坐標往往與起始點或者目標點并不相同，而在DQN-RRT-C 算法中，隨機樹向參考點、起始點或目標點都有延伸的趨勢，在某些情況下會產生矛盾，造成路徑變長，折點變多，嚴重時甚至會出現局部振蕩或者樹枝纏繞的現象，從而導致路徑質量下降，也不利于路徑規劃效率的提高。因此在圖5中，當貪婪拓展出現“折回”現象，也就是相鄰樹枝夾角為銳角時，便停止貪婪拓展。

3 仿真實驗及結果分析

3.1 地圖模型建立

仿真實驗的平臺為MATLAB 軟件，首先建立仿真實驗所使用的地圖模型。二值位圖在MATLAB 中對應只有0和1的二值矩陣（0為自由空間，1為障礙物空間），因此可以編寫程序構建二值矩陣得到二值地圖，或者根據灰度閾值將已有的彩色地圖二值化。通過構建二值矩陣，得到兩張仿真實驗使用的500×500地圖，如圖6所示。

圖6 地圖模型Fig.6 Maps

3.2 前期訓練

用MATLAB 編寫相關程序，取目標點坐標為（450，450），參考點坐標為（250，250），步長長度d0=30，對2張地圖進行訓練，并提取最優動作表。

提取出來的最優動作表，可以在地圖上進行可視化。將式（11）中各動作分別用相應的列序號1～5 來表示，并用顏色區分，可得到可視化圖，如圖7所示。

圖7 DQN-RRT-C算法的最優動作可視化圖Fig.7 Optimal action visualization diagram of DQN-RRT-C

3.3 路徑規劃仿真

記（50，50）→（450，450）為路線a，（450，50）→（450，450）為路線b，其中路線a 起始點和目標點的連線經過中心的參考點，路線b 起始點和目標點的連線則離參考點較遠。取步長長度d0=30，在2 張地圖對所有算法各進行1 000 次實驗，分別求取時間指標的樣本均值-t和標準差σ，如表1所示。

表1 時間指標Tab.1 Time index

將1 000 次實驗的時間作圖展示，如圖8～10所示，圖中縱軸表示每進行一次路徑規劃的運行時間，橫軸為實驗序號。

圖8 地圖a路線a的時間指標Fig.8 Time of path a in map a

圖9 地圖b路線a的時間指標Fig.9 Time of path a in map b

圖10 地圖b路線b的時間指標Fig.10 Time of path b in map b

4 結束語

DQN-RRT-C 算法只需要依賴固定地圖的信息，運算時間的樣本均值越小，表明算法的平均運行時間越少，算法效率越高；運算時間的標準差越小，表明算法運行時間隨機性越小，算法時間性能越穩定，可靠性越好。由時間指標的實驗結果可知，無論是在效率上還是在時間性能穩定性上，DQN-RRT-C 算法的時間性能均優于RRT-Connect 算法的時間性能，但受路線的影響較大，且仍存在一定的隨機性。