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

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

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

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

1 引言

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

2 傳統(tǒng)RRT算法

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

RRT算法的偽代碼為：

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

3 改進的RRT算法

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

改進RRT算法的偽代碼如下：

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

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

4 總結

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

參考文獻：

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

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

[3]高曉巍.移動機器人的路徑規(guī)劃和仿真[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-），女，河南輝縣人，碩士研究生，研究方向控制科學與工程，