基于改進RRT算法的垃圾收集車路徑規劃研究

顧海蛟， 宋 宇

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

0 引 言

隨著現代技術的發展，無人化時代已然來臨，原本需要人工才能完成的簡單和危險的工作被機器所代替，比如現在快遞業的無人寄取、大疆科技的無人機，以及常見的無人售貨機等。就無人駕駛的垃圾回收車而言，決定其性能優劣的實質是內部的動力驅動系統和外部的路徑規劃問題。其中路徑規劃問題直接決定著工作效率和是否能夠完成所要執行任務的關鍵。因此，一種合理與高效的路徑規劃算法是實現其工作性能最大化的保證。

常用的路徑規劃算法有圖搜索法、人工勢場法、遺傳算法、RRT算法等。圖搜索法是在已知環境和障礙物信息構造從起點到目標點的可行路徑[1]，主要分為深度優先和廣度優先兩個方向。在Prim和Dijkstar最短路徑算法中采用了廣度優先的思想，但規劃效果對啟發式函數依賴性太強，較好的啟發函數需要靠試湊來獲得[2]。人工勢場法是將整體抽象成一個引力場，目標點對移動物體產生“引力”，障礙物對移動物體產生“斥力”，最后通過“合力”控制物體的運動方向，但規劃效果得到的往往不是全局最優路徑[3]。遺傳算法是一種仿生物算法，隨著一代又一代的“遺傳”,逐漸找到最優路徑，容易出現過早的收斂和停滯現象。RRT算法是一種增量式采樣的搜索方法，在應用中不需要任何參數，具備良好的使用性能，它利用增量遞增方法構建搜索樹，逐漸提高分辨能力，而無需設置任何參數與函數。

文中主要對垃圾回收車的路徑規劃進行研究，假設在高檔小區每個家庭的垃圾都在對應規定的地方投放，而無人回收垃圾車在預先標記的垃圾點自主地將垃圾收集到一起處理，就會考慮到小車路徑規劃問題，只要將小車路徑規劃好，效率就會大大提高。在路徑規劃算法中,RRT算法在應用中需要參數少，具有良好的使用功能，容易實現。借鑒改進RRT算法的基礎上，提出一種新的、易于實現的改進RRT算法的路徑規劃方法。傳統RRT算法在設定好出發點和目標點的位置后，只需要在一定的迭代次數后就會找到一條從出發點到目標點的路徑，但速度會比較慢，而在改進后的雙向隨機搜索樹是從起始點和目標點并行生成兩棵RRT樹，直至兩棵樹相遇，這樣會縮短搜索過程用時，減少計算機的計算用時，但會在規劃的路徑中出現障礙盲區，在實際允許的情形下加入“改線”機制，改進后的算法縮短了路徑長度，達到節省能耗的目的。

1 RRT算法概述

RRT算法是一種基于隨機采樣的樹結構搜索算法，以空間給定的起點qstart出發，通過在給定的封閉空間中隨機采樣,并且引導搜索樹的生長。當樹的節點進入目標區域內,并且找到終點qgoal時算法結束，然后回溯到起始節點,即可得到所規劃的路徑。用有向圖表示路徑G=(u,E)，一條規劃的路徑就是一系列坐標點的順序連接(u1,u2,u3,…,un)，u1=qstart,un=qgoal。同時(ui,ui+1)∈E,1≤i≤n-1表示邊。實質就是使用采樣點來擴展圖G，之后就是一條從起點到終點的路徑。

RRT算法流程如下：

1.U←{qstart}，E←φ，i←0

2.While i

3.G′←(u,E)

4.qrand←Sample(i)，i←i+1

5.(U,E)←extend(G′,qrand)

6.G←(G′,qrand)

7.end while

RRT算法的簡易圖解如圖1所示。

圖1 RRT算法的簡易圖解

最初，擴展圖G的坐標點集只有初始節點qstart，邊集E為空集。然后進入迭代,即進入While循環，迭代次數為N，設置為新的擴展圖G′，Sample(i)用來采樣一個新的點qrand，利用新的點來拓展圖G，最后到達目標點qgoal，結束循環，此時,通過RRT算法找到從出發點到目標點的規劃路徑[4-7]。

2 RRT-Connect算法概述

RRT-Connect算法是在RRT算法的基礎上加上了雙樹雙向抖索的引導策略，并且在擴展路徑的方式基礎上加入了貪婪策略,用來加快搜索速度。

RRT-Connect算法的簡易圖解如圖2所示。

圖2 RRT-Connect算法的簡易圖解

圖2中RRT-Connect算法在搜索路徑時，從起始點與目標點兩端同時進行路徑的搜索，直到兩段路徑相遇，即全局搜索路徑結束，得到規劃路徑軌跡。

3 算法”改線“機制

經過RRT-Connect算法規劃得到的路線將會在障礙物的邊緣出現障礙盲區，這一部分盲區主要是由起始點與目標點之間進行雙向的樹形搜索存在的不足引起的，不能同時兼顧搜索時間短與路徑長度短的優點，針對上述問題引入”改線機制“，其原理是三角形的三邊原理，如圖3所示。

圖3 三角形三邊原理

假設三角形的三條邊長度分別為a，b，c，其中a，b兩邊的夾角為α，其對應的邊為c。三角形兩邊之和大于第三邊，a+b>c。文中就是利用這一原理，在規劃的路徑中引入改線機制，使得規劃后的路徑實際運動距離更短。

4 仿真實驗

仿真是在Matlab2014上進行的，在采樣點給定次數4 000次進行的實驗。

起點坐標(5，5)，終點坐標(95，95)通過RRT-Connect算法找到路徑。

采樣次數2 000次時，部分采樣點下生成的路徑規劃如圖4所示。

圖4 部分采樣點生成路徑規劃

采樣次數4 000次時，全部采樣點下生成的路徑規劃如圖5所示。

圖5 全部采樣點生成路徑規劃

全部采樣點生成的路徑長度比部分采樣點生成的路徑長度少4.25%。

4.1 改線仿真實驗

在控制其它變量不變，只改變采樣點數的情況下進行仿真實驗，下面將進行改線，其中改線是在圖5障礙盲區的路徑段進行改線，改線后在滿足垃圾收集車實際運動軌跡的情形下路徑規劃如圖6所示。

圖6 改線后的路徑規劃

圖6相較于圖5，生成的路徑長度減少4.45%。

4.2 仿真數據對比

算法結果對比見表1。

表1 算法結果對比

改進后的算法路徑在保證采樣點數，運行時間一樣的情況下長度減少了。達到了減少實際運行路徑長度的目的。

5 結 語

提出的基于改進RRT-Connect算法的垃圾收集車路徑規劃算法，通過利用三角形三邊定理進行“改線”，得出的實際運行路徑長度相較于原始算法更短，能達到減少耗能的目的。仿真結果表明，改進后的算法路徑長度相較于原始算法的路徑長度縮短了4.45%，有很大的利用價值。