摘要：傳統(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)

　　《軟件和集成電路》(月刊)創(chuàng)刊于1984年，郵發(fā)代碼：82-469。由中國(guó)電子信息產(chǎn)業(yè)發(fā)展研究院、北京中電報(bào)發(fā)展有限公司主辦的計(jì)算機(jī)科學(xué)技術(shù)刊物。

　　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ì)比分析。

　　由表中數(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)度。

　　由表中數(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.