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

關鍵詞：路徑規(guī)劃；快速擴展隨機樹(RRT)；目標引力函數

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

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

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

1 RRT算法分析

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

圖1 RRT的構建

Fig.1 The RRT construction

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

2 改進的RRT算法

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

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

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

Fig.3 The path planning for RRT algorithm

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

Fig.3 The path planning for improved RRT algorithm

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

4結論

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

參考文獻

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

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

[3] 康亮,趙春霞,郭劍輝.未知環(huán)境下改進的基于RRT算法的移動機器人路徑規(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].計算機工程與應用,2011,47 (3):210-213.

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

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

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