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

閆明亮 侯光華

摘要：傳統(tǒng)快速擴(kuò)展隨機(jī)樹(shù)（RRT）算法在生成采樣點(diǎn)時(shí)采用隨機(jī)擴(kuò)展的策略，導(dǎo)致路徑的生長(zhǎng)無(wú)方向性且路徑規(guī)劃速度較慢。針對(duì)此問(wèn)題，在采樣點(diǎn)選取策略上采用雙采樣點(diǎn)的方法，同時(shí)隨機(jī)生成2個(gè)采樣點(diǎn)，并選取其中距離目標(biāo)點(diǎn)較近的點(diǎn)作為最終采樣點(diǎn)，可使路徑的生長(zhǎng)在一定程度上具有方向性，提高路徑規(guī)劃的效率。仿真試驗(yàn)中，與傳統(tǒng)RRT和雙向RRT路徑規(guī)劃算法進(jìn)行對(duì)比分析，驗(yàn)證了算法的有效性。

關(guān)鍵詞：快速擴(kuò)展隨機(jī)樹(shù)；雙向RRT路徑規(guī)劃；雙采樣點(diǎn)

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2019）15-55-4

0引言

路徑規(guī)劃是指在某種環(huán)境內(nèi)，按照一定的評(píng)價(jià)標(biāo)準(zhǔn)，如路徑最短或規(guī)劃時(shí)間最少等，尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的無(wú)碰撞路徑[1]。

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

為解決上述方法出現(xiàn)的問(wèn)題，提出一種基于雙采樣點(diǎn)的雙向RRT路徑規(guī)劃（DBi-RRT）算法，該算法在隨機(jī)點(diǎn)采樣策略上使用雙采樣點(diǎn)方法對(duì)隨機(jī)點(diǎn)進(jìn)行采樣，減少過(guò)多無(wú)用節(jié)點(diǎn)擴(kuò)展的同時(shí)使得隨機(jī)樹(shù)的生長(zhǎng)具有方向性。

1雙采樣點(diǎn)的雙向RRT算法

1.1算法原理

本算法分別以起始點(diǎn)和目標(biāo)點(diǎn)為根節(jié)點(diǎn)，同時(shí)生成2棵隨機(jī)樹(shù)進(jìn)行相向生長(zhǎng)，通過(guò)2次隨機(jī)采樣生成2個(gè)隨機(jī)采樣點(diǎn)，比較2個(gè)候選采樣點(diǎn)與目標(biāo)點(diǎn)的距離大小，選取距離較小的點(diǎn)作為最終采樣點(diǎn)，使得隨機(jī)樹(shù)具有一定的方向性。

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

2實(shí)驗(yàn)與分析

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

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

2.1地圖1試驗(yàn)

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

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

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

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

2.2地圖2試驗(yàn)

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

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

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

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

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

3結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

[5]孫豐財(cái)，張亞楠，史旭華.改進(jìn)的快速擴(kuò)展隨機(jī)樹(shù)路徑規(guī)劃算法[J].傳感器與微系統(tǒng)，2017，36（9）：129-131.

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