基于雙采樣點的雙向RRT路徑規(guī)劃算法

閆明亮 侯光華

摘要：傳統快速擴展隨機樹（RRT）算法在生成采樣點時采用隨機擴展的策略，導致路徑的生長無方向性且路徑規(guī)劃速度較慢。針對此問題，在采樣點選取策略上采用雙采樣點的方法，同時隨機生成2個采樣點，并選取其中距離目標點較近的點作為最終采樣點，可使路徑的生長在一定程度上具有方向性，提高路徑規(guī)劃的效率。仿真試驗中，與傳統RRT和雙向RRT路徑規(guī)劃算法進行對比分析，驗證了算法的有效性。

關鍵詞：快速擴展隨機樹；雙向RRT路徑規(guī)劃；雙采樣點

中圖分類號：TP301.6文獻標志碼：A文章編號：1008-1739（2019）15-55-4

0引言

路徑規(guī)劃是指在某種環(huán)境內，按照一定的評價標準，如路徑最短或規(guī)劃時間最少等，尋找一條從起始點到目標點的無碰撞路徑[1]。

目前，一種傳統的路徑規(guī)劃算法是基于采樣的快速擴展隨機樹[2]算法。但由于在RRT的擴展過程中，采樣點的選取使用全局的均勻隨機采樣策略[3]，導致路徑搜索效率低[4]。由此提出了雙向RRT（Bi-RRT）算法，從起始點和目標點同時生成2棵RRT并進行相向擴展，加速了算法的收斂速度[5]。但節(jié)點的擴展方式仍使用在全局環(huán)境中進行均勻隨機采樣的策略，缺乏目標導向性，降低了路徑規(guī)劃效率[6]。

為解決上述方法出現的問題，提出一種基于雙采樣點的雙向RRT路徑規(guī)劃（DBi-RRT）算法，該算法在隨機點采樣策略上使用雙采樣點方法對隨機點進行采樣，減少過多無用節(jié)點擴展的同時使得隨機樹的生長具有方向性。

1雙采樣點的雙向RRT算法

1.1算法原理

本算法分別以起始點和目標點為根節(jié)點，同時生成2棵隨機樹進行相向生長，通過2次隨機采樣生成2個隨機采樣點，比較2個候選采樣點與目標點的距離大小，選取距離較小的點作為最終采樣點，使得隨機樹具有一定的方向性。

雙采樣點示意圖如圖1所示，同時隨機生成2個候選采樣點rand1，rand2，比較2個點到目標點goal的距離，可知|rand1， goal|<|rand2，goal|，因此選取rand1作為最終采樣點rand，進而對隨機樹進行擴展得到擴展節(jié)點new。若對隨機樹進行擴展，則將起始點init作為目標點，采用相同的方法進行判斷和擴展。本方法可解決傳統隨機采樣隨機性太大，不具有方向性，路徑規(guī)劃效率低的問題。

2實驗與分析

為驗證DBi-RRT算法的性能，選取了2種不同的環(huán)境地圖進行仿真試驗，在每種環(huán)境地圖中將本文算法分別與傳統RRT和DBi-RRT算法進行對比分析。

如圖3所示，為充分模擬現實環(huán)境中的障礙物，本文設置了2種不同環(huán)境的試驗地圖。試驗地圖1中為形狀不規(guī)則的障礙物，且障礙物有大有小；試驗地圖2中為外形規(guī)則的障礙物。2種地圖中障礙物分布都不均勻。地圖尺寸大小均為 800×800，起始點和目標點坐標均為[20，20]，[780，780]。仿真實驗均在CPU為Intel Core i5-3210M， 2.5 GHz，內存4 G的計算機上進行，編程環(huán)境為Matlab R2013b。

2.1地圖1試驗

將DBi-RRT算法分別與RRT和Bi-RRT算法在試驗地圖1中進行路徑規(guī)劃對比分析，在地圖1中將3種算法分別運行30次，取其中的一次運行結果如圖4所示，記錄每次路徑規(guī)劃所用時間、算法迭代次數和所規(guī)劃路徑的長度。

由試驗地圖1中的運行結果可知，RRT算法由于在采樣策略上使用全局范圍內的均勻隨機采樣方法，生成了大量的無用節(jié)點；Bi-RRT算法相對RRT算法，大大減少了無用節(jié)點的生成；DBi-RRT算法只有少量的無用節(jié)點，使得算法的迭代次數顯著減少，加速了路徑規(guī)劃的速度。3種參數的對比分別如圖5、圖6和圖7所示，將3個參數的記錄值分別求取平均值進行對比分析如表1所示。

由3幅圖可知，DBi-RRT算法在路徑規(guī)劃時間、算法迭代次數和規(guī)劃路徑長度上均優(yōu)于RRT， Bi-RRT算法。

由表中數據可得，在平均規(guī)劃時間方面，DBi-RRT算法相對于RRT， Bi-RRT算法分別縮短了94.70%， 46.85%；在平均迭代次數方面，DBi-RRT算法相對于RRT， Bi-RRT算法分別減少了90.28%， 50.48%；在平均規(guī)劃路徑長度方面，DBi-RRT算法相對于RRT， Bi-RRT算法分別減少了11.50%， 8.4%。

2.2地圖2試驗

將DBi-RRT算法分別與RRT和Bi-RRT算法在試驗地圖2中進行路徑規(guī)劃對比分析，在地圖2中將3種算法分別運行30次，取其中的一次運行結果如圖8所示，記錄每次路徑規(guī)劃所用時間、算法迭代次數和所規(guī)劃路徑的長度。

由試驗地圖2中的運行結果可知，RRT算法生成了大量的無用節(jié)點，布滿整個地圖；Bi-RRT算法相對RRT算法，無用節(jié)點數量大大減少；DBi-RRT算法的無用節(jié)點數量最少，3種參數的對比如圖9、圖10和圖11所示，將3個參數的記錄值分別求取平均值進行對比分析如表2所示。

由圖可知，DBi-RRT算法在路徑規(guī)劃時間和算法迭代次數相對于RRT和Bi-RRT算法均有較大優(yōu)勢。

由表中數據可得，在平均規(guī)劃時間方面，DBi-RRT算法相對于RRT， Bi-RRT算法分別縮短了93.66%， 60.34%；在平均迭代次數方面，DBi-RRT算法相對于RRT， Bi-RRT算法分別減少了84.57%， 55.11%；在規(guī)劃平均路徑長度方面，DBi-RRT算法相對于RRT， Bi-RRT算法分別減少了6.4%， 4.7%。

通過以上仿真試驗及數據分析，本文提出的DBi-RRT路徑規(guī)劃算法，由于采用了雙采樣點方法，使得在路徑規(guī)劃過程中路徑的生長具有了方向性，大大減少了無用節(jié)點的擴展，減少了算法的迭代次數，顯著提高了路徑規(guī)劃的效率。

3結束語

DBi-RRT算法在采樣點的選取方式上進行了改進，雙采樣點方法的使用使得隨機樹的擴展具有了方向性，大大提高了路徑的規(guī)劃速度。仿真試驗結果表明：DBi -RRT算法相對于 RRT， Bi-RRT算法在路徑規(guī)劃時間和算法迭代次數上均有較大提升，極大提升了路徑規(guī)劃的效率。提出的算法可應用于室內服務機器人的路徑規(guī)劃應用領域，在指定目的地后，服務機器人可根據環(huán)境地圖快速規(guī)劃出行走路徑，提高服務質量。

參考文獻

[1]宋金澤，戴斌，單恩忠.一種改進的RRT路徑規(guī)劃算法[J].電子學報，2010，38（1）： 225-228.

[2]莫棟成，劉國棟.改進的RRT-Connect雙足機器人路徑規(guī)劃算法[J].計算機應用，2013，33（8）：2289-2292.

[3]杜明博，梅濤，陳佳佳，等.復雜環(huán)境下基于RRT的智能車輛運動規(guī)劃算法[J].機器人，2015，37（4）： 443-450.

[4]王道威，朱明富，劉慧.動態(tài)步長的RRT路徑規(guī)劃算法[J].計算機技術與發(fā)展，2016，26（3）：105-107.

[5]孫豐財，張亞楠，史旭華.改進的快速擴展隨機樹路徑規(guī)劃算法[J].傳感器與微系統，2017，36（9）：129-131.

[6]陳波芝，陸亮，雷新宇.基于改進快速擴展隨機樹算法的雙機械臂協同避障規(guī)劃方法[J].中國機械工程，2018，29（10）： 1220-1226.