基于避障空間的移動機(jī)器人路徑規(guī)劃的研究

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

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

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

1 引言

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

2 傳統(tǒng)RRT算法

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

RRT算法的偽代碼為：

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

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

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

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

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

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

4 總結(jié)

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

參考文獻(xiàn)：

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

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

[3]高曉巍.移動機(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.

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