顧海蛟， 宋 宇

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

0 引 言

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

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

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

1 RRT算法概述

RRT算法是一種基于隨機采樣的樹結(jié)構(gòu)搜索算法，以空間給定的起點qstart出發(fā)，通過在給定的封閉空間中隨機采樣,并且引導(dǎo)搜索樹的生長。當(dāng)樹的節(jié)點進入目標區(qū)域內(nèi),并且找到終點qgoal時算法結(jié)束，然后回溯到起始節(jié)點,即可得到所規(guī)劃的路徑。用有向圖表示路徑G=(u,E)，一條規(guī)劃的路徑就是一系列坐標點的順序連接(u1,u2,u3,…,un)，u1=qstart,un=qgoal。同時(ui,ui+1)∈E,1≤i≤n-1表示邊。實質(zhì)就是使用采樣點來擴展圖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的坐標點集只有初始節(jié)點qstart，邊集E為空集。然后進入迭代,即進入While循環(huán)，迭代次數(shù)為N，設(shè)置為新的擴展圖G′，Sample(i)用來采樣一個新的點qrand，利用新的點來拓展圖G，最后到達目標點qgoal，結(jié)束循環(huán)，此時,通過RRT算法找到從出發(fā)點到目標點的規(guī)劃路徑[4-7]。

2 RRT-Connect算法概述

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

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

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

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

3 算法”改線“機制

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

圖3 三角形三邊原理

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

4 仿真實驗

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

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

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

圖4 部分采樣點生成路徑規(guī)劃

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

圖5 全部采樣點生成路徑規(guī)劃

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

4.1 改線仿真實驗

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

圖6 改線后的路徑規(guī)劃

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

4.2 仿真數(shù)據(jù)對比

算法結(jié)果對比見表1。

表1 算法結(jié)果對比

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

5 結(jié) 語

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