基于改進RRT算法的移動機器人路徑規劃

郭夢詩 馮麗娟 代傳壘

摘要：針對傳統RRT算法在多障礙物、曲折狹窄道路等無規律環境下，隨機性大、收斂速度慢、效率低等問題，提出一種改進RRT路徑規劃算法，以提高在二維環境下移動機器人的路徑規劃性能。改進算法通過引入障礙物因子進行區域節點采樣，減少采樣時間和次數;同時對新產生的節點進行約束，降低方向隨機性，減少目標區域振蕩情況，加快搜索速度;此外，剔除冗余節點使路徑更加平滑，路徑長度縮短且對內存需求降低。通過實驗仿真驗證：改進算法能滿足復雜環境下的避障路徑規劃，隨機性降低速度較快，具有較好的可行性和有效性。

關鍵詞：改進RRT算法路徑規劃平滑避障

Path Planning of Mobile Robot Based on Improved RRT Algorithm

GUO Mengshi FENG LijuanDAI Chuanlei

（School of electronic and electrical engineering， Zhengzhou University of science and technology， Zhengzhou， Henan Province， 450064 China）

Abstract： Aiming at the problems of large randomness， slow convergence and low efficiency of traditional RRT algorithm in irregular environments such as multi obstacles and tortuous narrow roads， an improved RRT path planning algorithm is proposed to improve the path planning performance of mobile robot in two-dimensional environment. The improved algorithm reduces the sampling time and times by introducing the obstacle factor to sample the regional nodes; at the same time， the new nodes are constrained to reduce the direction randomness， reduce the oscillation in the target area and speed up the search speed; in addition， eliminating redundant nodes makes the path smoother， the path length shorter and the memory demand lower. The experimental simulation shows that the improved algorithm can meet the obstacle avoidance path planning in complex environment， reduce the randomness quickly， and has good feasibility and effectiveness.

Key Words： Improved RRT algorithm;Path planning;Smooth;Obstacle avoidance

隨著科技的發展，機器人機械臂在生產生活中的應用愈加廣泛[1]。與此同時，路徑規劃問題成為此領域的熱點及難點問題。由于機器人應用場景廣、靈活性強，若避障規劃效率低，則工作質量易受到影響[2]。避障規劃是指在有障礙物等特定環境下，機器人機械臂在自身和約束條件下尋找到一條從起點到終點的無碰撞有效路徑[3]。多種路徑規劃算法被廣泛提出，并在實際生產生活中取得了較好的效果，比如基于搜索的粒子群算法[4]、A*算法[5]、人工勢場法[6]等。以上算法當機器人環境維度、自由度、空間復雜度等增加時，其避障規劃復雜度倍增[7]。快速搜索隨機樹（RRT）算法是一種典型的基于采樣的規劃方法，此算法不必對環境障礙物進行精確描述，且在多維復雜環境中效果明顯[8]。

傳統RRT算法采樣均勻，復雜環境收斂慢，且其搜索路徑一般不是最優。因此大量學者對此算法存在的缺陷提出了多種改進和解決方案。Faris 等人通過引入多次樣條曲線將RRT算法路徑點進行排序獲得平滑路徑[9]; Gammell 引入空間約束減少規劃時間[10];尹高揚等人通過改進鄰近點的采樣選取進行全局采樣，但在搜索時間上有所延長[11]。以上算法在路徑規劃長度上明顯減少，但運算時耗時較長。故而，如何高效地獲取一條可行較優的路徑仍是目前避障規劃研究的熱點和重點。

對于傳統RRT算法搜索慢、路徑冗余節點多和終點附近振蕩等問題，本文進行了算法改進，使得機器人機械臂在避障路徑規劃上更加平穩。通過Matlab仿真驗證了本文算法在路徑長度和節點數量等方面的有效性。

1 基本RRT算法

傳統RRT算法在1998年由Lavalle提出[12]，無需對環境進行精確建模即可找到一條可行路徑。此算法的中心思想是從已知的確定的節點作為起始點，通過隨機采樣的方法在狀態空間中無規律地產生大量葉子節點，通過葉子節點逐漸向目標點靠近的樹狀結構，當增加的節點中包括終點時，即找到一條起點到終點的有效路徑。此算法在全局路徑規劃中應用廣泛。傳統RRT算法搜索仿真如圖1所示。

算法的擴展示意圖如圖2所示。

RRT算法的偽代碼為：

其中，qstart為搜索起點，qrand指狀態環境中隨機采樣點，qnear為搜索過程的最近鄰點，qnew是擴展后生成的葉子節點。

首先對算法進行初始化，qstart既是擴展樹起始點同時作為第一個鄰近點qnear，隨后在空間中隨機找尋一點qrand，之后距離此點最近距離的點作為下一個鄰近點qnear，同時以一定的擴展步長獲得新的節點qnew，且qnew和qnear的連線間不能存在障礙物，當qnew找到終點或到達最大迭代次數時，算法終止。

此算法的有效性已得到充分驗證，且在全局搜索和多維空間規劃上應用廣泛，但算法本身也存在一定的不足。由于傳統算法采樣均勻、信息引導不充分、缺乏路徑導向性，因此在狹窄或多障礙物等復雜環境下易出現搜索時間長、占用內存大，且冗余節點多易導致路徑轉折多、距離長等缺陷。

2 改進RRT算法

針對傳統RRT的上述問題進行了改進。首先對算法添加導向因子，增加路徑規劃引導域，同時對環境進行柵格化，可以在低分辨率環境中搜索出有效路徑。其次去除多余采樣節點，可以提高收斂速度。之后改變節點生成方式，在引導域中不斷進行擴展搜索，找到一條可行無碰撞漸進最優路徑。最后進行路徑簡化，同時路徑多余節點剔除后進行平滑，縮短規劃路徑的長度，滿足機器人機械臂平穩工作的要求。

對于相同的起止點，進行改進前后算法對比，如圖3和圖4所示。

圖3 ?兩種RRT算法路徑搜索圖

其中多岔的細線搜索路線是傳統RRT算法規劃路徑，較粗的路徑是改進RRT算法規劃路徑。左下角為起始點，右上角為目標點。

圖4 ?改進RRT算法路徑搜索圖

從圖4可以看出，改進的算法在路徑長度上有明顯的改善，且在運行和搜索時間上有明顯優勢，通過對比可看出改進算法的高效性和優越性。

此外，經過驗證，在非柵格化狹窄空間中，改進算法路徑規劃也有明顯效果，如圖5所示。

圖5 ?狹窄環境下兩種算法路徑對比

其中較細的折線為傳統RRT算法，加粗曲線為改進后算法。左上角圓點為起始點，右下角圓點為目標點。通過仿真可明顯看出，改進后的算法剔除不必要的冗余節點，使規劃路徑更簡，總體搜索代價更低。

3 結語

本文針對基本RRT算法在避障規劃中的一些不足，對其進行了改進。改進算法剔除了大量冗余節點，并加入引導域指引新節點朝向目標方向搜索。通過兩種算法的仿真對比，可驗證改進后的算法減少了隨機性，能夠高效快速地規劃出可行路徑，同時在路徑長度和平滑方面更優，更符合機器人機械臂在運作過程中的平穩性，整體效果更佳。

參考文獻

[1] 胡嘉陽，韋巍.基于五次 NURBS 曲線的六軸機器人多目標軌跡優化[J].電子測量與儀器學報，2020，34（6）：198-203.

[2] 王洪斌，尹鵬衡，鄭維，等.基于改進的 A～*算法與動態窗口法的移動機器人路徑規劃[J].機器人，2020，42（3）：346-353

[3] 張玉偉， 左云波， 吳國新，等.基于改進Informed-RRT*算法的路徑規劃研究[J].組合機床與自動化加工技術，2020（7）：5.

[4] WU X， YAN M， WANG J.An improved path planning approach based on Particle Swarm Optimization[C]//International Conference on Hybrid Intelligent Systems.IEEE，2012：157-161.

[5] BB MENG， GAO X.UAV Path Planning Based on Bidirectional Sparse A* Search Algorithm[J].IEEE，2010：1106-1109.

[6] CHEN Y B， LUO G C， MEI Y S， et al.UAV path planning using artificial potential field method updated by optimal control theory[J].International Journal of Systems Science，2016，47（6）：1407-1420.

[7] 朱佑滔，何志琴，施文燁.多種群蟻群算法在機械手臂路徑規劃中的設計與應用[J].機械傳動，2021，45（4）：160-165.

[8] 張衛波，肖繼亮.改進 RRT 算法在復雜環境下智能車路徑規劃中的應用[J].中國公路學報，2021，34（3）：225-234.

[9] Faris Janjo?， Ron Reichart， Philipp Niermeyer.Smooth Path-Generation Around Obstacles Using Quartic Splines and RRTs[J]. IFAC-PapersOnLine，2017，50（1）：9108-9113.

[10] J D GAMMELL， S S SRINIVASA， BARFOT.Informed-RRT：Optimal sampling-base path focused via direct sampling of an admissible ellipsoidal heuristic[C].International Conference on Intelligent Robots and Systems IEEE，shanghai，2014：2997-3004.

[11] 尹高揚，周紹磊，吳青坡.基于改進 RRT 算法的無人機航跡規劃[J].電子學報，2017，45（7）：1764-1769.

[12] LAVALLE S M，KUFFNER J J. Randomized kinodynamic planning[C]∥Proc. of IEEE International Conference on Robotics and Automation. Piscataway，NJ：IEEE Press，1999：473-479.