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

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

文獻(xiàn)標(biāo)識(shí)碼：A    中圖分類號(hào)： 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ù)是移動(dòng)機(jī)器人研究領(lǐng)域的一個(gè)重要方面，主要解決如何在工作空間中找到一條從起始點(diǎn)到終點(diǎn)的最優(yōu)路徑，并在運(yùn)動(dòng)中能夠安全無(wú)碰撞的繞過(guò)障礙物。在未知環(huán)境下，機(jī)器人沒(méi)有先驗(yàn)知識(shí)，不能離線做出一次性的全局規(guī)劃，只能依靠實(shí)時(shí)探測(cè)的局部環(huán)境信息規(guī)劃局部路徑，如何規(guī)劃出全局路徑且使路徑較優(yōu)，研究者已經(jīng)提出了不少解決方法和策略^[1,2]。然而，在環(huán)境趨于復(fù)雜或障礙物的數(shù)目增加時(shí)，如何避免震蕩和死鎖，如何使機(jī)器人所走路徑全局最優(yōu)或較優(yōu)，仍是有待解決的問(wèn)題。

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

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

1 RRT算法分析

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

圖1 RRT的構(gòu)建

Fig.1 The RRT construction

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

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

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

在通過(guò)RRT算法增加新葉節(jié)點(diǎn)時(shí)，目標(biāo)引力函數(shù)會(huì)通過(guò)計(jì)算每個(gè)節(jié)點(diǎn)到目標(biāo)的引力量來(lái)影響新節(jié)點(diǎn)的選取，引導(dǎo)隨機(jī)樹向目標(biāo)方向生長(zhǎng)。

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

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

4結(jié)論

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

參考文獻(xiàn)

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

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

[3] 康亮,趙春霞,郭劍輝.未知環(huán)境下改進(jìn)的基于RRT算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].模式識(shí)別與人工智能.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] 馮林,賈菁輝.基于對(duì)比優(yōu)化的RRT路徑規(guī)劃改進(jìn)算法[J].計(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é)報(bào),2010,2A (38):225-228.

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