基于快速擴展隨機樹的工程機械路徑規劃研究

摘 要：針對復雜作業環境下的工程機械路徑規劃問題，提出了一種基于快速擴展隨機樹的路徑規劃方法。首先分別對路徑規劃的目的、約束條件、任務環境建模、路徑表述方法以及針對機械本體大小的障礙物膨化方法進行了分析論述，進而介紹了RRT算法的基本原理，并給出了基于RRT的路徑規劃算法步驟，最后通過仿真試驗驗證了所提方法的有效性和先進性。

關鍵詞：工程機械；路徑規劃；快速擴展隨機樹

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

0 前言

以推土機、挖掘機為代表的工程機械，通常在地面崎嶇、障礙物眾多的復雜環境進行土石方作業。傳統的人工駕駛方式是通過車載駕駛人員進行機械設備的現場操作，但是一些特殊領域，工作環境可能存在地面塌陷、山體垮塌等危險情況，會給駕駛人員的生命安全帶來威脅。智能化、精準化、無人化代表了工程機械行業未來的發展方向[1]。通過無人化設計，實現操作人員對設備的遠程遙控或者機械設備的任務級自主控制，能夠極大的提高工程施工的安全性、拓寬工程機械的應用場合。

路徑規劃是綜合考慮移動主體的運動學、動力學約束，以及任務環境的地形地貌、障礙分布等情況，為移動主體規劃出從起始位置到目標位置的可行路徑或最優路徑。路徑規劃是實現工程機械無人化作業的關鍵技術之一。常見的路徑規劃方法包括基于數學規劃的方法，基于群體智能的規劃方法、基于啟發式計算的方法等[1，2]。其中混合整數線性規劃為典型的數學規劃方法，具有嚴格的數學理論依據，但隨著規劃問題的增大，其計算量會急劇增加，因此只適合于小規模的路徑規劃問題。以蟻群算法、遺傳算法、粒子群算法為代表的群體智能優化方法具有內在的并行機制，全局優化能力強，但存在優化時間長，有時可能會規劃失敗等不足。人工勢場方法也是一種常見的路徑規劃方法，能夠在勢場引力和勢場斥力的綜合作用下，將路徑向著目標位置延伸，但也存在著存在引力和斥力相同的局部極小點問題，會導致規劃失敗。

快速擴展隨機樹算法 （Rapidly-exploring Random Tree，RRT）是一種基于空間采樣的路徑規劃方法，由美國學者LaValle于上個世紀末提出[3]。RRT在任務空間內采用節點生長的方式構造隨機樹，逐步構建出連通起始位置與目標位置的可行路徑。該算法具有參數少、結構簡單、收斂速度快等優點，自算法提出后，逐漸得到的學術界的認可，已有的研究表明，RRT算法具有比A*算法、隨機路線圖算法等原有的路徑規劃算法更高的優化效率[4]。

本文采用RRT算法求解復雜工作環境下的工程機械路徑規劃問題，包括路徑規劃問題描述與數學建模、算法設計、仿真試驗等內容。

1 問題描述

自動地規劃出工程機械的行駛路徑，是未來的智能化和無人化工程機械實現自主行進與施工作業的重要前提。該路徑規劃問題可以描述為：

（1）根據工作環境和任務要求，為工程機械生成從起始位置到目標位置的可行路徑。

（2）所得路徑應能夠避開已知的障礙物體或危險區域，保證設備的行進安全。

（3）所得路徑應滿足機械設備的運動學和動力學約束，比如路徑長度應小于工程機械的最大行程，轉彎半徑應符合工程機械的機動性能。

機械的行進路徑由任務區域中一系列的路徑節點組成，路徑節點的順序對應著工程機械的依次需要到達的行進位置。用直線段連接相鄰的路徑節點。假設工程機械的起始位置為，目標位置為，第個路徑節點表示為，其中分別為該路徑節點位置的縱橫向坐標，則從起始位置歷經個路徑節點到達目標位置的路徑可以表示為：

基于上述分析，可以采用二值化的任務環境建模方法。將障礙物、危險區域、機動性能受限區域等簡化為具有同等威脅程度的不可行區域，即整個工作環境區分為威脅區域（不可行區域）和可行區域兩種情況。威脅區域完全不可行，規劃所得路徑不能與威脅區域有重合。

另外由于工程機械具有自身的形狀和較大的外形尺寸，在實際的行駛時，需要避免車體與周圍物體的碰撞，不能簡單的將車體看作為沒有尺寸大小的質點。在路徑規劃過程中，可以采用障礙物膨脹的方法，將車體的外形尺寸進行等效處理，即根據工程機械的車體大小，將障礙物或危險區域進行等值的膨脹放大處理。經膨脹處理之后，不但解決了車體的碰撞問題，而且對于常見的推土機、挖掘機等低速運動的工程機械而言，其轉彎半徑、爬坡率等運動學約束也不用在規劃過程中單獨處理。

2 算法設計

RRT算法是一種以空間采樣的方式實現路徑搜索的規劃算法。假設任務區域為，表示其中的可行區域，表示威脅區域，和同為的子集，并且滿足和。路徑規劃的起始位置和目標位置，起始位置和目標位置位于同一連通區之內，路徑規劃的目的是得到從到的可行路徑。

RRT算法首先通過節點擴展的方式在構建隨機樹，在構建過程中，以為根節點，依照概率選擇目標位置或者空間中的隨意一個位置作為隨機目標點，并從原有的隨機樹上延伸一個步長，拓展出一個新節點，當隨機樹延伸到與足夠近的時候，通過反向搜索，可獲得從到的路徑。RRT算法的步驟如下：

（1）算法初始化；

（2）未到達目標位置則轉向步驟（3）；否則轉向步驟（7）；

（3）生成隨機數，若，則轉向步驟（4），否則轉向步驟（5）；

（4）以作為，確定臨近節點，進而得到，轉向步驟（6）；

（5）在任務區域內隨機生成，計算對應的；

（6）判斷與之間是否存在威脅，若無威脅則將添加到隨機樹之中，實現隨機樹的擴展，并轉向步驟2），若存在威脅則轉向步驟3）；

（7）從開始反向搜索父節點，直至找到起始節點，完成路徑規劃。

3 仿真試驗

采用RRT算法進行復雜任務環境中的路徑規劃仿真試驗，仿真軟件平臺為MATLAB2009。假設任務環境為的無量綱二維區域，任務環境內共有100個不可行的威脅區域。每個威脅區域的位置和覆蓋半徑都隨機產生。路徑規劃的起始位置坐標為（0，0），目標位置坐標為（100，100），設置RRT算法的參數為和。endprint

圖1為通過RRT算法得到路徑結果。由圖可知，所得路徑避開了所有的已知威脅區域，生成了從起始位置到目標位置的可行。在隨機樹在生長過程中產生了很多分支，這是由于對于復雜的任務環境，RRT算法必須通過不斷的在整個任務區域內容進行拓展搜索，以圖找到潛在的路徑。算法具有良好的時效性，仿真運行時間0.38秒，能夠滿足實際的工程機械路徑規劃的快速性要求。RRT算法在規劃過程中總共擴展出258個節點，其中所得路徑的長度175.3，這說明算法具有較好的方向性，沒有產生過多的迂回曲折。

4 結束語

以推土機、挖掘機、鏟車為代表的工程機械在工程施工領域有著不可替代的重要作用，隨著科技的發展，智能化、無人化代表了工程機械的發展方向。針對復雜作業環境下的工程機械路徑規劃問題，本文提出了一種基于快速擴展隨機樹的路徑規劃方法。首先對工程機械路徑規劃問題的目的、約束條件、任務環境建模、路徑表述以及障礙物膨化處理方法進行了分析論述，進而給出了基于RRT算法的路徑規劃方法，通過仿真試驗對所提方法的有效性和先進性進行了驗證。結果表明RRT算法是一種高效的路徑規劃方法，在工程機械路徑規劃領域有廣泛的應用前景。

參考文獻：

[1]朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010，25（07）：961-967.

[2]孫梅.移動機器人路徑規劃技術綜述[J].山東工業技術，2016（21）：164.

[3]LaValle S M，Kuffner J J.Donald B R，et al.Rapidly-exploring random trees：Progress and prospects[J].Algorithmic and Computational Robotics：New Directions，Wellesley，2001： 293-308.

[4]David B.Comparison of A*and RRT-connect motion planning techniques for self-reconfiguration planning[C]. International Conference on Intelligent Robots and Systems， Beijing，2006：892-897.

本論文來源于山東省重大科技創新工程項目，項目名稱《基于工業物聯網的工程機械智能裝配數據采集與處理關鍵技術研究與應用》，項目編號：2017CXGC0603

作者簡介：田從豐（1985-），男，山東微山人，工學碩士，工程師，研究方向：工程機械自動控制。endprint