李昭瑩，歐一鳴，石若凌

（1.北京航空航天大學(xué)宇航學(xué)院，北京 100191；2.哈爾濱工業(yè)大學(xué)（深圳）機(jī)電工程與自動(dòng)化學(xué)院，廣東深圳 518055）

0 引言

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

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

隨著人工智能技術(shù)的發(fā)展，深度強(qiáng)化學(xué)習(xí)近年來取得了可喜的進(jìn)展。2017年，DeepMind 團(tuán)隊(duì)推出了AlphaGo，擊敗了圍棋世界冠軍李世石，展現(xiàn)了深度強(qiáng)化學(xué)習(xí)的巨大潛力。作為深度強(qiáng)化學(xué)習(xí)算法之一的DQN算法，將深度學(xué)習(xí)和傳統(tǒng)Q-learning結(jié)合在了一起，很好地解決了Q-learning的維度災(zāi)難問題，可以處理復(fù)雜的、高維的環(huán)境特征，并與環(huán)境進(jìn)行交互，完成決策過程。

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

1 原理簡介

1.1 RRT算法

RRT 算法中起始點(diǎn)作為根節(jié)點(diǎn)，然后通過隨機(jī)采樣增加葉子節(jié)點(diǎn)的方式，生成隨機(jī)樹并不斷拓展，最終隨機(jī)樹到達(dá)目標(biāo)點(diǎn)或目標(biāo)區(qū)域，得到路徑可行解，如圖1所示［11］。

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

圖1所示RRT算法隨機(jī)樹拓展過程可表達(dá)為

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

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

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

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

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

與RRT 算法同理，在RRT-Connect 隨機(jī)拓展中也可以對(duì)采樣點(diǎn)增加限制，使

1.2 DQN算法

在實(shí)際問題中，智能體的狀態(tài)值數(shù)量可能會(huì)非常龐大，傳統(tǒng)的查表式Q-learning 算法將會(huì)耗費(fèi)大量內(nèi)存，甚至可能在現(xiàn)實(shí)中無法實(shí)現(xiàn)，因此需要構(gòu)建神經(jīng)網(wǎng)絡(luò)來近似得到所有Q值。

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

式中：s為狀態(tài)；a為動(dòng)作；w為函數(shù)f(s，a；w)的參數(shù)，函數(shù)的構(gòu)建則通過訓(xùn)練神經(jīng)網(wǎng)絡(luò)來完成。為了便于描述，我們用Q(s，a；w)來表示這個(gè)近似的價(jià)值函數(shù)，即

在DQN算法中，目標(biāo)Q值可表示為

式中：t表示當(dāng)前時(shí)刻；t+1 表示下一時(shí)刻；Rt+1為獎(jiǎng)勵(lì)；maxQ(st+1，a；w-)為st+1下所有動(dòng)作的Q值的最大者；λ為折扣因子，為常量。以目標(biāo)值和預(yù)測(cè)值之間的均方誤差作為損失函數(shù)L，即

式中：Q(st+1，a；w)為預(yù)測(cè)網(wǎng)絡(luò)，Q(st+1，a；w-)為目標(biāo)網(wǎng)絡(luò)。w和w-為神經(jīng)網(wǎng)絡(luò)的相關(guān)參數(shù)。簡而言之，DQN 利用神經(jīng)網(wǎng)絡(luò)作為函數(shù)逼近器來逼近Q(s，a)，并通過梯度下降來最小化誤差［14］。

2 基于深度Q 網(wǎng)絡(luò)的RRT-Connect算法

2.1 避障策略

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

式中：d0為步長長度，為正的實(shí)常數(shù)；θ為旋轉(zhuǎn)角度，范圍(-π，π]；znew、znear、zref分別為xnew、xnear、xref坐標(biāo)對(duì)應(yīng)的復(fù)數(shù)，xref為某個(gè)參考點(diǎn)。根據(jù)復(fù)數(shù)步長的概念，設(shè)計(jì)了復(fù)數(shù)域變步長的避障策略，如圖3所示。

圖3 參考點(diǎn)導(dǎo)向的避障策略Fig.3 Reference point-oriented obstacle avoidance strategy

當(dāng)采樣點(diǎn)為參考點(diǎn)時(shí)，便包含5個(gè)可選擇的步長。當(dāng)樹枝延伸時(shí)，只能選擇其中一個(gè)步長，而具體如何選擇步長，則要結(jié)合DQN算法。

2.2 MDP模型

根據(jù)2.1 節(jié)的避障策略，可以設(shè)計(jì)出DQN 算法相應(yīng)的MDP模型。

1）狀態(tài)空間S

RRT 算法一般是基于一張二值像素地圖來進(jìn)行路徑規(guī)劃的，灰度值為255 的區(qū)域是障礙物空間，為0的區(qū)域則是自由空間。圖中的每一個(gè)像素都作為地圖上的一個(gè)已知點(diǎn)，并有其對(duì)應(yīng)的二維坐標(biāo)。因此，模型的狀態(tài)空間S可表達(dá)為

式中：W為地圖的寬度，H為地圖的高度，由地圖的寬高像素?cái)?shù)量決定。

2）動(dòng)作空間A

動(dòng)作空間即圖3 中5 個(gè)復(fù)數(shù)步長的集合，用一個(gè)列向量來表示

3）獎(jiǎng)勵(lì)函數(shù)

由于以不同步長延伸，所得到的樹節(jié)點(diǎn)與目標(biāo)點(diǎn)的接近程度不同，因此獎(jiǎng)勵(lì)R是步長d的函數(shù)。

式中：Arg(d)表示復(fù)數(shù)步長d的輻角主值，條件P 的表述為：當(dāng)樹枝以動(dòng)作到達(dá)最優(yōu)動(dòng)作為或的區(qū)域時(shí)。最優(yōu)動(dòng)作的定義會(huì)在2.3.2 小節(jié)中介紹，該區(qū)域通常為十分接近障礙物的區(qū)域。

2.3 算法流程

2.3.1 訓(xùn)練Q網(wǎng)絡(luò)

DQN 算法中Q 值的更新，可以概括為“當(dāng)前狀態(tài)下選擇動(dòng)作→執(zhí)行動(dòng)作→下一狀態(tài)→獎(jiǎng)勵(lì)→更新Q值”幾步，而Q 值則使用神經(jīng)網(wǎng)絡(luò)來擬合［14-15］。根據(jù)DQN 算法的神經(jīng)網(wǎng)絡(luò)訓(xùn)練方法，可以設(shè)計(jì)DQNRRT-C更新一次神經(jīng)網(wǎng)絡(luò)的流程圖，如圖4所示。

圖4 中：Batchsize 表示一次訓(xùn)練的樣本數(shù)。實(shí)際上往往需要進(jìn)行多次訓(xùn)練更新，在DeepMind 于2015年提出的DQN 算法中，每隔C次訓(xùn)練就要把預(yù)測(cè)網(wǎng)絡(luò)的權(quán)值賦給目標(biāo)網(wǎng)絡(luò)［16］。

圖4 一次訓(xùn)練更新的流程圖Fig.4 Flow chart of training updating

2.3.2 提取最優(yōu)動(dòng)作表

最優(yōu)動(dòng)作即動(dòng)作空間中Q 值最大的動(dòng)作，一個(gè)狀態(tài)對(duì)應(yīng)一個(gè)最優(yōu)動(dòng)作。最優(yōu)動(dòng)作表就是將自由區(qū)域中所有狀態(tài)下的最優(yōu)動(dòng)作用表格儲(chǔ)存。在擁有Q 網(wǎng)絡(luò)的情況下，可以使用Q 網(wǎng)絡(luò)分別計(jì)算所有狀態(tài)下的所有動(dòng)作對(duì)應(yīng)的Q 值，然后將各狀態(tài)下的最優(yōu)動(dòng)作提取出來制成最優(yōu)動(dòng)作表。提取出來的最優(yōu)動(dòng)作表，可以直接用于路徑規(guī)劃的動(dòng)作選擇。

2.3.3 路徑規(guī)劃

根據(jù)得到的最優(yōu)動(dòng)作表，在地圖環(huán)境固定的情況下，可使用DQN-RRT-C算法進(jìn)行路徑規(guī)劃。

與傳統(tǒng)RRT-Connect 算法相同，DQN-RRT-C 算法也包括隨機(jī)拓展和貪婪拓展2大步驟。隨機(jī)拓展具體方法與RRT-Connect 算法相同，貪婪拓展則增加了參考點(diǎn)導(dǎo)向避障的環(huán)節(jié)，如圖5所示。

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

當(dāng)貪婪拓展遭遇障礙物時(shí)，算法便會(huì)啟用參考點(diǎn)導(dǎo)向避障策略，即：以參考點(diǎn)為基準(zhǔn)，結(jié)合最優(yōu)動(dòng)作表，使樹枝以5個(gè)復(fù)數(shù)步長中的一個(gè)延伸，達(dá)到避開障礙物的目的。由于參考點(diǎn)的坐標(biāo)往往與起始點(diǎn)或者目標(biāo)點(diǎn)并不相同，而在DQN-RRT-C 算法中，隨機(jī)樹向參考點(diǎn)、起始點(diǎn)或目標(biāo)點(diǎn)都有延伸的趨勢(shì)，在某些情況下會(huì)產(chǎn)生矛盾，造成路徑變長，折點(diǎn)變多，嚴(yán)重時(shí)甚至?xí)霈F(xiàn)局部振蕩或者樹枝纏繞的現(xiàn)象，從而導(dǎo)致路徑質(zhì)量下降，也不利于路徑規(guī)劃效率的提高。因此在圖5中，當(dāng)貪婪拓展出現(xiàn)“折回”現(xiàn)象，也就是相鄰樹枝夾角為銳角時(shí)，便停止貪婪拓展。

3 仿真實(shí)驗(yàn)及結(jié)果分析

3.1 地圖模型建立

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

圖6 地圖模型Fig.6 Maps

3.2 前期訓(xùn)練

用MATLAB 編寫相關(guān)程序，取目標(biāo)點(diǎn)坐標(biāo)為（450，450），參考點(diǎn)坐標(biāo)為（250，250），步長長度d0=30，對(duì)2張地圖進(jìn)行訓(xùn)練，并提取最優(yōu)動(dòng)作表。

提取出來的最優(yōu)動(dòng)作表，可以在地圖上進(jìn)行可視化。將式（11）中各動(dòng)作分別用相應(yīng)的列序號(hào)1～5 來表示，并用顏色區(qū)分，可得到可視化圖，如圖7所示。

圖7 DQN-RRT-C算法的最優(yōu)動(dòng)作可視化圖Fig.7 Optimal action visualization diagram of DQN-RRT-C

3.3 路徑規(guī)劃仿真

記（50，50）→（450，450）為路線a，（450，50）→（450，450）為路線b，其中路線a 起始點(diǎn)和目標(biāo)點(diǎn)的連線經(jīng)過中心的參考點(diǎn)，路線b 起始點(diǎn)和目標(biāo)點(diǎn)的連線則離參考點(diǎn)較遠(yuǎn)。取步長長度d0=30，在2 張地圖對(duì)所有算法各進(jìn)行1 000 次實(shí)驗(yàn)，分別求取時(shí)間指標(biāo)的樣本均值-t和標(biāo)準(zhǔn)差σ，如表1所示。

表1 時(shí)間指標(biāo)Tab.1 Time index

將1 000 次實(shí)驗(yàn)的時(shí)間作圖展示，如圖8～10所示，圖中縱軸表示每進(jìn)行一次路徑規(guī)劃的運(yùn)行時(shí)間，橫軸為實(shí)驗(yàn)序號(hào)。

圖8 地圖a路線a的時(shí)間指標(biāo)Fig.8 Time of path a in map a

圖9 地圖b路線a的時(shí)間指標(biāo)Fig.9 Time of path a in map b

圖10 地圖b路線b的時(shí)間指標(biāo)Fig.10 Time of path b in map b

4 結(jié)束語

DQN-RRT-C 算法只需要依賴固定地圖的信息，運(yùn)算時(shí)間的樣本均值越小，表明算法的平均運(yùn)行時(shí)間越少，算法效率越高；運(yùn)算時(shí)間的標(biāo)準(zhǔn)差越小，表明算法運(yùn)行時(shí)間隨機(jī)性越小，算法時(shí)間性能越穩(wěn)定，可靠性越好。由時(shí)間指標(biāo)的實(shí)驗(yàn)結(jié)果可知，無論是在效率上還是在時(shí)間性能穩(wěn)定性上，DQN-RRT-C 算法的時(shí)間性能均優(yōu)于RRT-Connect 算法的時(shí)間性能，但受路線的影響較大，且仍存在一定的隨機(jī)性。