摘 要：為解決快速擴(kuò)展隨機(jī)樹(shù)（RRT）算法隨機(jī)性強(qiáng)，擴(kuò)展分支多，收斂時(shí)間長(zhǎng)等問(wèn)題，本文提出了一種改進(jìn)的RRT算法。改進(jìn)的RRT算法可以結(jié)合環(huán)境約束問(wèn)題，快速搜索出一條起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的的路徑，該路徑比傳統(tǒng)RRT算法路徑短，且有效減少搜索時(shí)間。通過(guò)在MATLAB上進(jìn)行相關(guān)路徑規(guī)劃仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明了算法的準(zhǔn)確性和有效性。

關(guān)鍵詞：快速擴(kuò)展隨機(jī)樹(shù)；環(huán)境約束；MATLAB；路徑規(guī)劃

DOI：10.16640/j.cnki.37-1222/t.2018.14.193

1 引言

隨著科學(xué)技術(shù)的迅速發(fā)展，機(jī)器人在工業(yè)，農(nóng)業(yè)等各個(gè)領(lǐng)域廣泛應(yīng)用[1，2]，在機(jī)器人大量應(yīng)用的同時(shí)，路徑規(guī)劃問(wèn)題需要被更好的解決[3]。

2 傳統(tǒng)RRT算法

傳統(tǒng)的快速快展隨機(jī)樹(shù)（RRT）算法是由Lavalle[4]提出來(lái)的。RRT算法的主要思想是在路徑規(guī)劃中從一個(gè)已知數(shù)據(jù)的節(jié)點(diǎn)開(kāi)始作為起始節(jié)點(diǎn)，通過(guò)隨機(jī)采樣的方式在環(huán)境中無(wú)規(guī)律的產(chǎn)生大量節(jié)點(diǎn)，新產(chǎn)生的節(jié)點(diǎn)為葉子結(jié)點(diǎn)，通過(guò)增加葉子節(jié)點(diǎn)的數(shù)目，逐漸向目標(biāo)節(jié)點(diǎn)靠近，當(dāng)增加的葉子節(jié)點(diǎn)中包含有目標(biāo)節(jié)點(diǎn)時(shí)，便可在隨機(jī)樹(shù)中找到一條從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的有效路徑。傳統(tǒng)RRT算法的擴(kuò)展過(guò)程如圖2.1所示。

RRT算法的偽代碼為：

傳統(tǒng)的RRT算法是從一個(gè)根節(jié)點(diǎn)向周?chē)h(huán)境中的未知領(lǐng)域搜索擴(kuò)展，可以使得路徑規(guī)劃達(dá)到全局搜索。但傳統(tǒng)RRT算法的隨機(jī)性，造成路徑規(guī)劃的不穩(wěn)定性，且搜索環(huán)境復(fù)雜時(shí)，搜索時(shí)間過(guò)長(zhǎng)，收斂性差。

3 改進(jìn)的RRT算法

基于上述傳統(tǒng)RRT算法的不足，本文提出了一種改進(jìn)的RRT算法，改進(jìn)的RRT算法通過(guò)在路徑規(guī)劃過(guò)程中增加平面墻等環(huán)境約束，縮短搜索區(qū)域，提高了搜索的效率，使得規(guī)劃的路徑比傳統(tǒng)RRT算法路徑更優(yōu)。

改進(jìn)RRT算法的偽代碼如下：

改進(jìn)RRT路徑規(guī)劃圖如圖3.1所示：

為了更好地對(duì)比傳統(tǒng)RRT算法和改進(jìn)RRT算法的路徑規(guī)劃效果，把兩種算法編寫(xiě)到同一個(gè)環(huán)境中進(jìn)行對(duì)比觀察，效果圖如下3.2所示。其中起始點(diǎn)用綠色節(jié)點(diǎn)標(biāo)識(shí)，目標(biāo)點(diǎn)用紅色節(jié)點(diǎn)標(biāo)識(shí)，從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)規(guī)劃出兩條路徑，其中紅色路徑是傳統(tǒng)RRT算法的規(guī)劃路徑，用時(shí)4.391秒，而黑色路徑是改進(jìn)RRT算法所得，用時(shí)1.389秒，在時(shí)間上明顯后者更優(yōu)，且由圖可以明顯觀察到改進(jìn)的RRT算法在路徑的長(zhǎng)度質(zhì)量上優(yōu)于傳統(tǒng)算法。

4 總結(jié)

由上述的路徑規(guī)劃仿真圖可以看出，傳統(tǒng)的RRT算法具有隨機(jī)性，在搜索過(guò)程中產(chǎn)生了大量不必要分支，使得搜索路徑長(zhǎng)，且速度過(guò)慢時(shí)間花費(fèi)大。改進(jìn)后的算法減少了路徑規(guī)劃的時(shí)間，提高了搜索效率。通過(guò)仿真驗(yàn)證了其可行性。

參考文獻(xiàn)：

[1]畢昆，趙馨，機(jī)器人技術(shù)在農(nóng)業(yè)中的應(yīng)用方向和發(fā)展趨勢(shì)[J].中國(guó)農(nóng)學(xué)通報(bào)，2011，27（04）：469-473.

[2]李磊，葉濤，譚民等.移動(dòng)機(jī)器人技術(shù)研究現(xiàn)狀與未來(lái)[J].機(jī)器人，2002，24（05）：475-480.

[3]高曉巍.移動(dòng)機(jī)器人的路徑規(guī)劃和仿真[J].計(jì)算機(jī)仿真，2013，30（07）：379-382.

[4]KHATIB O.Real-Time obstacle Avoidance for Manipulators and Mobile Robots[J].The International Journal Robotics Research，1986，5（01）：90-98.

作者簡(jiǎn)介：郭夢(mèng)詩(shī)（1993-），女，河南輝縣人，碩士研究生，研究方向控制科學(xué)與工程，