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

　　關鍵詞：快速擴展隨機樹;雙向RRT路徑規劃;雙采樣點

　　《軟件和集成電路》(月刊)創刊于1984年，郵發代碼：82-469。由中國電子信息產業發展研究院、北京中電報發展有限公司主辦的計算機科學技術刊物。

　　0引言

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

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

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

　　1雙采樣點的雙向RRT算法

　　1.1算法原理

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

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

　　2實驗與分析

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

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

　　2.1地圖1試驗

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

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

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

　　2.2地圖2試驗

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

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

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

　　3結束語

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

　　參考文獻

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

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