摘 要：針對移動機(jī)器人運用快速擴(kuò)展樹(RRT)算法進(jìn)行路徑規(guī)劃，隨機(jī)性大的問題，提出了一種目標(biāo)引力式的RRT路徑規(guī)劃算法。該算法在RRT算法的基礎(chǔ)上，引入了一個目標(biāo)引力函數(shù)，促使擴(kuò)展隨機(jī)樹朝目標(biāo)點方向生長。仿真結(jié)果表明，該算法提高了復(fù)雜環(huán)境下機(jī)器人路徑規(guī)劃的效率，能夠得到接近于最短的路徑，并對同一任務(wù)的規(guī)劃具有一定的可重復(fù)性，能夠安全的避開障礙物。

關(guān)鍵詞：路徑規(guī)劃；快速擴(kuò)展隨機(jī)樹(RRT)；目標(biāo)引力函數(shù)

文獻(xiàn)標(biāo)識碼：A    中圖分類號： TP24   

The Improved RRT Path Planning Algorithm Based on Unknown Environment

SUN Lina，SHEN Zhengjun

(College of Automation & Electronic Engineering，Qingdao University of Science and Technology, 266042, China)

Abstract: Aiming to solve the uncertainty using rapidly-exploring random tree (RRT) for path planning algorithm, an algorithm of mobile robot path planning based on target gravity is proposed. The algorithm introduces target gravitational function, which makes the random tree grow toward the target. Simulation results show that the algorithm improves path planning efficiency in the complex environment; the path is close to the shortest path, avoids obstacles safely and has a certain repeatability for the planning of same task.

Key Words: Path Planning; Rapidly-Exploring Random Tree (RRT); target gravitational function

路徑規(guī)劃技術(shù)是移動機(jī)器人研究領(lǐng)域的一個重要方面，主要解決如何在工作空間中找到一條從起始點到終點的最優(yōu)路徑，并在運動中能夠安全無碰撞的繞過障礙物。在未知環(huán)境下，機(jī)器人沒有先驗知識，不能離線做出一次性的全局規(guī)劃，只能依靠實時探測的局部環(huán)境信息規(guī)劃局部路徑，如何規(guī)劃出全局路徑且使路徑較優(yōu)，研究者已經(jīng)提出了不少解決方法和策略^[1,2]。然而，在環(huán)境趨于復(fù)雜或障礙物的數(shù)目增加時，如何避免震蕩和死鎖，如何使機(jī)器人所走路徑全局最優(yōu)或較優(yōu)，仍是有待解決的問題。

快速擴(kuò)展隨機(jī)樹（RRT）是目前應(yīng)用比較廣泛的基于采樣的單查詢運動規(guī)劃方法，通過狀態(tài)空間的隨機(jī)采樣點，把搜索導(dǎo)向空白區(qū)域，從而尋找一條從起點到目標(biāo)點的路徑規(guī)劃，適合于復(fù)雜環(huán)境和變化場景的路徑規(guī)劃。但是RRT算法所具有的采樣隨機(jī)性，產(chǎn)生了路徑規(guī)劃實時性不高，在執(zhí)行同一任務(wù)時可重復(fù)性比較差和很難規(guī)劃出最優(yōu)路徑等問題。

目前RRT算法產(chǎn)生了許多改進(jìn)，如具有啟發(fā)式的RRT算法、基于滾動窗口的RRT算法等^[3-5]，可是產(chǎn)生的路徑存在繞遠(yuǎn)或者出現(xiàn)明顯的拐角，使路徑不平滑；或產(chǎn)生死鎖振蕩等。為此，本文引入人工勢場法中的目標(biāo)引力，使規(guī)劃路徑接近最優(yōu)或次優(yōu)，并改進(jìn)了路徑不平滑這一缺陷，通過合理的設(shè)置引力系數(shù)，克服了局部極小的問題。

1 RRT算法分析

RRT算法是以狀態(tài)空間中的一個初始點作為根節(jié)點，用過隨機(jī)采樣擴(kuò)展，逐漸增加葉節(jié)點，生成一個隨機(jī)擴(kuò)展樹，當(dāng)隨機(jī)樹的葉節(jié)點中包含了目標(biāo)點或目標(biāo)區(qū)域中的點時，從初始點到目標(biāo)點之間的一條以隨機(jī)樹的葉節(jié)點組成的路徑就是路徑規(guī)劃。

圖1 RRT的構(gòu)建

Fig.1 The RRT construction

由于RRT算法是按照樹枝的生長路徑進(jìn)行規(guī)劃，從而導(dǎo)致規(guī)劃的路徑有時接近最短路徑，有時遠(yuǎn)離最短路徑，缺乏光滑性，并對同一任務(wù)的規(guī)劃缺乏可重復(fù)性。該算法具有很多的隨機(jī)性，其本身所包含的一些缺點，對其在移動機(jī)器人中的應(yīng)用產(chǎn)生了一定的限制。

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

將人工勢場法中的目標(biāo)引力思想引入RRT算法，引導(dǎo)隨機(jī)樹朝著目標(biāo)方向生長，大大減少規(guī)劃時間,提高了算法的實時性保證了規(guī)劃路徑的最優(yōu)性，改進(jìn)路徑不光滑的缺點，避免了產(chǎn)生局部極小，使算法在規(guī)劃路徑方面的能力得到很大的提高。

在通過RRT算法增加新葉節(jié)點時，目標(biāo)引力函數(shù)會通過計算每個節(jié)點到目標(biāo)的引力量來影響新節(jié)點的選取，引導(dǎo)隨機(jī)樹向目標(biāo)方向生長。

3仿真分析

圖2 RRT算法規(guī)劃的路徑

Fig.3 The path planning for RRT algorithm

圖3 算法改進(jìn)后規(guī)劃的路徑

Fig.3 The path planning for improved RRT algorithm

仿真實驗結(jié)果顯示：通過合理地設(shè)置引力系數(shù)，使改進(jìn)后的算法保留了RRT算法中向空曠地帶搜索的特性，可以快速繞過障礙物找到可行路徑，大大減少了不必要的擴(kuò)展，提高了機(jī)器人運動的實時性，使生成的路徑相對平滑，滿足機(jī)器人機(jī)器人在復(fù)雜環(huán)境下的路徑規(guī)劃。

4結(jié)論

本文針對復(fù)雜環(huán)境下移動機(jī)器人的路徑規(guī)劃問題，在隨機(jī)擴(kuò)展樹算法的基礎(chǔ)上，結(jié)合勢場法的目標(biāo)引力函數(shù)，對原有算法進(jìn)行了改進(jìn)。改進(jìn)后的算法能夠引導(dǎo)新葉節(jié)點向目標(biāo)方向擴(kuò)展，減少了采樣點的數(shù)目，大大縮短了規(guī)劃時間，規(guī)劃出的路徑更接近最優(yōu)或次優(yōu)；同時，使機(jī)器人在執(zhí)行同一任務(wù)的可重復(fù)性得到提高，路徑也更加的光滑。大量的仿真實驗結(jié)果表明，該算法顯著提高機(jī)器人規(guī)劃效率，具有較高的計算實時性，適合機(jī)器人實際應(yīng)用。

參考文獻(xiàn)

[1] 張純剛,席裕庚.動態(tài)未知環(huán)境中移動機(jī)器人的滾動路徑規(guī)劃及安全性分析.控制理論與應(yīng)用, 2003, 20(1): 37-44.

[2] 王麗.移動機(jī)器人路徑規(guī)劃方法研究[D].西北工業(yè)大學(xué)碩士論文.2007,3.

[3] 康亮,趙春霞,郭劍輝.未知環(huán)境下改進(jìn)的基于RRT算法的移動機(jī)器人路徑規(guī)劃[J].模式識別與人工智能.2009,22(3)337-343.

[4] MelchiorNA, SimmonsR. Particle RRT for Path Planning with Uncertainty[J].Proc of the IEEE International Conference on Robotics and Automation. Roma, Italy, 2007:1617- 1624.

[5] 馮林,賈菁輝.基于對比優(yōu)化的RRT路徑規(guī)劃改進(jìn)算法[J].計算機(jī)工程與應(yīng)用,2011,47 (3):210-213.

[6] 王濱,金明河,謝宗武等.基于啟發(fā)式的快速擴(kuò)展隨機(jī)樹路徑規(guī)劃算法[J].機(jī)械制造,2007, 45 (12):1-4.

[7] 宋金澤,戴斌,單恩忠等.一種改進(jìn)的RRT路徑規(guī)劃算法[J].電子學(xué)報,2010,2A (38):225-228.

[8] 高云峰,黃海.復(fù)雜環(huán)境下基于勢場原理的路徑規(guī)劃方法[J].機(jī)器人,2004,26(2):114-118.