馬小陸，袁書生，王兵，吳紫恒

（1.安徽工業(yè)大學(xué) 電氣與信息工程學(xué)院，安徽馬鞍山 243032；2.特種重載機(jī)器人安徽省重點(diǎn)實(shí)驗(yàn)室，安徽馬鞍山 243032）

RRT*算法是在快速擴(kuò)展隨機(jī)樹（Rapidlyexploring random tree,RRT）算法[1]上衍生出來的算法。RRT 算法從根節(jié)點(diǎn)出發(fā)，通過在規(guī)劃路徑的空間隨機(jī)采樣獲取新節(jié)點(diǎn)并進(jìn)行判斷，若新節(jié)點(diǎn)可用，則將隨機(jī)樹擴(kuò)展到該點(diǎn)，隨機(jī)樹通過這個(gè)方式進(jìn)行擴(kuò)展，最終得到一條規(guī)劃的路徑。但因RRT 算法使用隨機(jī)方法獲取新節(jié)點(diǎn)，樹的擴(kuò)展方向具有隨機(jī)性，因此規(guī)劃出的路徑不是最優(yōu)路徑。針對(duì)RRT 算法的缺點(diǎn)，Karamen 與Frazzoli 提出了RRT*算法[2]，RRT*算法對(duì)新加入隨機(jī)樹的節(jié)點(diǎn)進(jìn)行了最優(yōu)路徑的判斷，依據(jù)判斷結(jié)果確定是否對(duì)隨機(jī)樹重新布線，進(jìn)而得到一條較優(yōu)路徑。由于RRT*中的概率采樣算法成熟且無需對(duì)環(huán)境進(jìn)行建模，因此該方法被廣泛地應(yīng)用在機(jī)器人的路徑規(guī)劃中，文獻(xiàn)[3-4]將RRT*算法和運(yùn)動(dòng)學(xué)、動(dòng)力學(xué)條件約束進(jìn)行結(jié)合，提高了路徑規(guī)劃的速度和質(zhì)量，并將其應(yīng)用在了機(jī)器人多自由度機(jī)械臂的路徑規(guī)劃中；文獻(xiàn)[5-6]對(duì)基于RRT*算法的路徑規(guī)劃進(jìn)行了平滑處理，并將其應(yīng)用在無人機(jī)的立體空間飛行軌跡規(guī)劃中；文獻(xiàn)[7]利用RRT*算法不用對(duì)空間環(huán)境建模的特點(diǎn)，規(guī)劃出了一條粗糙的路徑，再通過Dijkstra 算法對(duì)其進(jìn)行了優(yōu)化，并應(yīng)用在無人汽車泊車場(chǎng)景中；文獻(xiàn)[8]通過人工勢(shì)場(chǎng)法優(yōu)化了RRT*算法的采樣過程，減少了計(jì)算量，加速了RRT*算法的收斂速度。

RRT*算法是一個(gè)漸進(jìn)最優(yōu)算法，若想獲得較優(yōu)路徑，則需增加采樣點(diǎn)，采樣點(diǎn)的增加會(huì)使RRT*算法計(jì)算量增加，因此規(guī)劃路徑的時(shí)間會(huì)變長[9]。如何提高RRT*算法的收斂速度，成為RRT*算法的研究熱點(diǎn)。Jordan 和Perez 借鑒RRT-Connect 算法雙向擴(kuò)展的特性，在2013 年提出了 B-RRT*算法[10]，即雙向擴(kuò)展RRT*；潘思宇等通過引入啟發(fā)式樣本代價(jià)函數(shù)，在2017 年提出了RRT*算法的改進(jìn)算法[11]，提高了路徑規(guī)劃的速度和質(zhì)量；Qureshi 等提出IBRRT*算法[12]，該算法通過加入智能采樣函數(shù)加快了B-RRT*算法的收斂速度。

針對(duì)RRT*算法收斂速度慢的問題，本文提出了一種均勻Logistic 混沌序列采樣的RRT*路徑規(guī)劃算法。該方法使用了均勻分布Logistic 混沌序列采樣方法，增加了采樣點(diǎn)的遍歷性，提高了通過障礙物區(qū)域的概率，加速了隨機(jī)樹重布線的效率，減少了路徑規(guī)劃時(shí)間。

1 均勻分布Logistic 混沌序列

混沌是非線性動(dòng)力學(xué)中一種特有的運(yùn)動(dòng)形式，混沌具有規(guī)律性、遍歷性和隨機(jī)性的特點(diǎn)。產(chǎn)生混沌變量的Logistic 混沌模型映射公式為：

式中：i為迭代時(shí)間步，i=0,1,···,n；xi是混沌變量，取值(0,1)；μ是混沌系統(tǒng)的李雅普諾夫(Lyapunov)指數(shù)，即控制參數(shù)，取值(0,4]；Logistic 映射分叉圖如圖1 所示。

圖1 Logistic 映射分叉圖

由圖1 可以看出，隨著控制參數(shù)μ的增加，混沌變量xi的取值從確定值增加到兩倍、四倍周期分叉，最后進(jìn)入到混沌狀態(tài)。

文獻(xiàn)[13]對(duì)基本Logistic 混沌序列的隨機(jī)性進(jìn)行了研究，當(dāng)μ取(3.99,4]時(shí)，隨機(jī)性較好，將μ值設(shè)定為4，x0初值設(shè)定為0.630 時(shí)，迭代40 000 次，由公式（1）得到的Logistic 混沌序列統(tǒng)計(jì)直方圖如圖2 所示。

圖2 非均勻分布的Logistic 混沌序列統(tǒng)計(jì)直方圖

由圖2 可見，產(chǎn)生的混沌序列在（0,1）區(qū)間分布不均勻。依據(jù)文獻(xiàn)[14]將式（1）得到的序列經(jīng)式（2）處理后得到Logistic 混沌序列的統(tǒng)計(jì)直方圖如圖3 所示。

圖3 均勻分布的Logistic 混沌序列統(tǒng)計(jì)直方圖

由圖3 可以看出，該序列的取值在(0,1)區(qū)間內(nèi)分布均勻，此時(shí)，混沌序列的每個(gè)序列值出現(xiàn)的概率基本相同。

因此，本文的算法中使用式（1）和式（2）生成均勻分布Logistic 混沌序列，同時(shí)為了保證生成混沌序列的混沌性和均勻性，將生成的序列前面一些數(shù)值舍去。

2 RRT＊算法

RRT 通過狀態(tài)空間的隨機(jī)采樣點(diǎn)，在空白區(qū)域內(nèi)繼續(xù)搜索，最終規(guī)劃出到一條從起始點(diǎn)到目標(biāo)點(diǎn)的路徑。RRT 算法的隨機(jī)樹擴(kuò)展模型如圖4 所示。

圖4 RRT 算法擴(kuò)展模型

圖4 中，RRT 算法在規(guī)劃空間里隨機(jī)采樣一個(gè)點(diǎn)xrand，然后在隨機(jī)樹中尋找與點(diǎn)xrand距離最近的點(diǎn)xnear，并和該點(diǎn)進(jìn)行連線，在這條線的方向上尋找步長為l的點(diǎn)xnew，若點(diǎn)xnew可?。床辉谡系K物內(nèi)）且連接可行，則連接點(diǎn)xnew，并將其加入到隨機(jī)樹中。通過這樣擴(kuò)展的方式，能夠獲得一條從起點(diǎn)到終點(diǎn)的規(guī)劃路徑。

RRT*算法在樹的擴(kuò)展方式上和RRT 一樣，不同之處是RRT*對(duì)xnew父節(jié)點(diǎn)的選取增加了重寫操作，然后又對(duì)隨機(jī)樹進(jìn)行了重新布線操作。圖5 為RRT*算法父節(jié)點(diǎn)重寫的過程。

圖5 RRT*算法的父節(jié)點(diǎn)重寫

圖5a）為隨機(jī)樹擴(kuò)展過程中的某一時(shí)刻，圖5a）中節(jié)點(diǎn)的序號(hào)大小表示節(jié)點(diǎn)產(chǎn)生的先后順序，初始節(jié)點(diǎn)為0 號(hào)節(jié)點(diǎn)，產(chǎn)生的最新節(jié)點(diǎn)為9 號(hào)節(jié)點(diǎn)（xnew），與xnew節(jié)點(diǎn)相連接的4 號(hào)節(jié)點(diǎn)是xnew節(jié)點(diǎn)的父節(jié)點(diǎn)，節(jié)點(diǎn)和節(jié)點(diǎn)間連線上數(shù)字代表歐式距離即路徑代價(jià)。以9 號(hào)節(jié)點(diǎn)為圓心，以事先規(guī)定好的半徑，將xnew節(jié)點(diǎn)附近圈起來，圖5a）中5 號(hào)、6 號(hào)和8 號(hào)節(jié)點(diǎn)為9 號(hào)節(jié)點(diǎn)的備選父節(jié)點(diǎn)。分別計(jì)算從起始節(jié)點(diǎn)經(jīng)過這3 個(gè)備選父節(jié)點(diǎn)再到xnew節(jié)點(diǎn)路徑的代價(jià)，并和經(jīng)過原來父節(jié)點(diǎn)的路徑代價(jià)進(jìn)行比較，得到一條代價(jià)最小的路徑，即將該路徑的備選父節(jié)點(diǎn)作為xnew的父節(jié)點(diǎn)，再將原本的父節(jié)點(diǎn)斷開，即可得到了圖5b）所示的隨機(jī)樹。

重寫xnew的父節(jié)點(diǎn)之后，再通過重新布線隨機(jī)樹進(jìn)一步減小xnew附近的節(jié)點(diǎn)到起始點(diǎn)的代價(jià)。重新布線的操作過程如圖6 所示。

圖6 RRT*算法的隨機(jī)樹重新布線

圖6a）中9 號(hào)節(jié)點(diǎn)（xnew）為最新生成的節(jié)點(diǎn)，4 號(hào)、6 號(hào)和8 號(hào)節(jié)點(diǎn)為其鄰近的節(jié)點(diǎn)，它們父節(jié)點(diǎn)分別為節(jié)點(diǎn)0、4 和5。路徑分別為0→4、0→4→6、0→1→5→8，路徑代價(jià)分別為10、15 和9。若將9 號(hào)節(jié)點(diǎn)設(shè)置為4 號(hào)節(jié)點(diǎn)的父節(jié)點(diǎn)，則路徑變?yōu)?→1→5→9→4，路徑代價(jià)為15，比原來的路徑代價(jià)10 大，因此不對(duì)節(jié)點(diǎn)4 進(jìn)行改寫父節(jié)點(diǎn)操作。同理若將節(jié)點(diǎn)9 號(hào)節(jié)點(diǎn)設(shè)置為8 號(hào)節(jié)點(diǎn)的父節(jié)點(diǎn)，路徑代價(jià)為14；若節(jié)點(diǎn)9 號(hào)節(jié)點(diǎn)設(shè)置為6 號(hào)節(jié)點(diǎn)的父節(jié)點(diǎn)，路徑代價(jià)為12。因而對(duì)節(jié)點(diǎn)6 進(jìn)行改寫父節(jié)點(diǎn)操作，其隨機(jī)樹如圖6b）所示。

可見，重新布線會(huì)讓某些節(jié)點(diǎn)到起點(diǎn)間的代價(jià)變小，因此得到的路徑更短。雖然最終生成的從起點(diǎn)到終點(diǎn)的路徑不會(huì)包含每一個(gè)重新布線的節(jié)點(diǎn)，但每一次的重新布線會(huì)優(yōu)化路徑規(guī)劃。

綜上，在RRT*算法中，重選父節(jié)點(diǎn)會(huì)在隨機(jī)樹上選擇一條從起始節(jié)點(diǎn)到最新節(jié)點(diǎn)間的最小代價(jià)路徑，并將最新節(jié)點(diǎn)插入到隨機(jī)樹中；重布線會(huì)對(duì)隨機(jī)樹進(jìn)行重新布局進(jìn)而減少了隨機(jī)樹中節(jié)點(diǎn)到起點(diǎn)的冗余通路，優(yōu)化重新布線路徑。RRT*算法通過這兩個(gè)操作來減小路徑代價(jià)，但RRT*算法仍是一種漸進(jìn)最優(yōu)的方法，若想得到較優(yōu)路徑，需要增加采樣點(diǎn)，但每增加一個(gè)采樣點(diǎn)，需要對(duì)多個(gè)點(diǎn)進(jìn)行父節(jié)點(diǎn)重寫和重布線，因此，隨著采樣點(diǎn)的增加，計(jì)算量會(huì)成倍的增加，因此RRT*算法的存在收斂時(shí)間過長的問題。

3 均勻Logistic 混沌序列采樣的RRT＊算法

RRT*算法在規(guī)劃的空間中獲取新節(jié)點(diǎn)方法是隨機(jī)采樣方法，得到的新節(jié)點(diǎn)具有隨機(jī)性，但不能保證規(guī)劃空間中樣點(diǎn)的遍歷性，特別在規(guī)劃的空間中樣點(diǎn)少的情況下更加的明顯。為了解決此問題，本文提出一種基于均勻分布Logistic 混沌序列采樣的RRT*算法，使得獲取新節(jié)點(diǎn)時(shí)不僅具有隨機(jī)性，還具有遍歷性，該方法能提高RRT*算法的收斂速度，具體分析如下。

3.1 障礙物區(qū)域算法穩(wěn)定

使用RRT*算法在進(jìn)行全局路徑規(guī)劃時(shí)，路徑在延伸擴(kuò)展過程中，經(jīng)常會(huì)出現(xiàn)路徑被障礙物圈住的情況，如圖7 所示。

圖7 RRT*算法路徑擴(kuò)展陷入障礙物模型

圖7 中xinit為起點(diǎn)，xgoal為目標(biāo)點(diǎn)，周圍深色矩形表示障礙物，隨機(jī)樹在從起點(diǎn)向終點(diǎn)擴(kuò)展的過程中，會(huì)出現(xiàn)如圖7 所示的被障礙物圍住的情況。在這種情況下，采樣點(diǎn)只有落在圖7 虛線所圍成的角度范圍內(nèi)，才能保證隨機(jī)樹跳出周圍障礙物并繼續(xù)向后擴(kuò)展。

若只考慮在角度上的采樣，將圖7 中M點(diǎn)周圍以固定的角度劃分為m個(gè)扇形區(qū)域，劃分的模型可以簡(jiǎn)化為圖8 所示。

圖8 兩種方法角度上采樣簡(jiǎn)化模型

圖8a)和8b)分別表示隨機(jī)數(shù)采樣和均勻分布Logistic 混沌序列采樣在角度上采樣的簡(jiǎn)化模型，假設(shè)采樣點(diǎn)落在每個(gè)角度范圍內(nèi)是等可能的，那么在第一次采樣時(shí)，基于隨機(jī)數(shù)采樣和基于均勻分布Logistic 混沌序列采樣落在圖7 中θ角(即跳出被圍困區(qū)域)的概率為Pθ1和此時(shí)即

若第1 次采樣時(shí)，兩種方法都沒有讓路徑擴(kuò)展跳出圍困區(qū)域，因基于均勻分布Logistic 混沌序列的采樣的遍歷會(huì)表現(xiàn)在角度上，若圖8b)中的陰影區(qū)域表示已落在該區(qū)域的采樣點(diǎn)，那么該區(qū)域不再考慮。因此第2 次采樣時(shí)，兩者的概率分別為：

可見，Pθ2的數(shù)值依然不變，而則會(huì)變大。假設(shè)在前i-1 次的采樣中，均沒有跳出被圍困區(qū)域，那么第i(i≤m)次采樣時(shí)，基于隨機(jī)數(shù)的采樣概率依然不變，而基于均勻分布Logistic 混沌序列的概率為

此時(shí)跳出被圍困區(qū)域的概率會(huì)隨著采樣次數(shù)i的增加而變大。

綜上可見，基于隨機(jī)數(shù)采樣在跳出障礙物圍困區(qū)域完全基于隨機(jī)性；而基于均勻分布Logistic 混沌序列采樣在隨機(jī)性的情況下，其遍歷性會(huì)讓隨機(jī)的概率變大，在被障礙物圍困的情況下，增加了其跳出的被圍困區(qū)域的概率，加速了隨機(jī)樹的擴(kuò)展，從而提高了算法的收斂速度。

3.2 隨機(jī)樹重新布線高效

圖9 所示為RRT*算法規(guī)劃出一條從xinit到xgoal的一條路徑，圖9 中各個(gè)節(jié)點(diǎn)虛線為重布線時(shí)考慮的半徑范圍，圖9 中原始路徑為xinit→A→B；但在采樣過程中經(jīng)過C點(diǎn)時(shí)路徑的距離更短，隨機(jī)樹重寫成xinit→C→B。對(duì)于一條除首尾節(jié)點(diǎn)外有n個(gè)節(jié)點(diǎn)的隨機(jī)樹，則存在n個(gè)可能重寫隨機(jī)樹的區(qū)域。

圖9 隨機(jī)樹重新布線概率模型

圖9 中，假設(shè)從左至右有4 個(gè)節(jié)點(diǎn)，出現(xiàn)可能改寫區(qū)域的面積分別為S1、S2、S3、S4，整個(gè)區(qū)域內(nèi)的面積為S，假設(shè)采樣點(diǎn)占據(jù)空間大小為Ssample。則在第1 次采樣的時(shí)候出現(xiàn)對(duì)隨機(jī)樹的改寫的概率P1為

假設(shè)第1 次未對(duì)隨機(jī)樹進(jìn)行重新布線，而在第2 次采樣的時(shí)候RRT*算法對(duì)隨機(jī)樹的重新布線概率P2為

由式（8）和式（9）可見，隨機(jī)樹的重新布線概率相同。

而基于均勻分布Logistic 混沌序列采樣因?yàn)槌司邆潆S機(jī)性外還具備遍歷性，在第1 次采樣的時(shí)候出現(xiàn)對(duì)隨機(jī)樹的改寫的概率P1同樣如式（8）所示，但第2 次采樣時(shí)重寫隨機(jī)樹的概率P2會(huì)變?yōu)?/p>

若一直都是未重新采樣，則重寫概率會(huì)越來越大?？梢姡诰鶆蚍植糒ogistic 混沌序列采樣的RRT*算法對(duì)隨機(jī)樹的重新布線的概率除第1 次相等外，其余都比基本RRT*算法的概率要高，且這個(gè)概率隨著采樣次數(shù)的增加在不斷增大，因此其更加合理高效，提高了路徑規(guī)劃的質(zhì)量，從而提高了算法的收斂速度。

4 算法仿真

4.1 仿真平臺(tái)

為了驗(yàn)證基于均勻分布Logistic 混沌序列采樣的可行性，本文使用仿真對(duì)其進(jìn)行驗(yàn)證，仿真試驗(yàn)地圖如圖10 所示。

圖10 仿真試驗(yàn)用地圖

圖10 為500×500 像素的地圖，圖中黑色區(qū)域代表障礙物，路徑規(guī)劃的起點(diǎn)為(10,10)，終點(diǎn)的位置為(490,490)，在仿真試驗(yàn)地圖上分別使用RRT*算法和基于均勻分布Logistic 混沌序列采樣的RRT*算法規(guī)劃路徑。

4.2 仿真過程和結(jié)果分析

為方便描述，將基于均勻分布Logistic混沌序列采樣的RRT*算法簡(jiǎn)稱為改進(jìn)的RRT*算法，分別對(duì)RRT*算法和改進(jìn)的RRT*算法設(shè)置相同的采用次數(shù)，試驗(yàn)30 次，分別對(duì)試驗(yàn)規(guī)劃成功的次數(shù)、路徑長度及規(guī)劃時(shí)間進(jìn)行記錄，試驗(yàn)采樣從1 500 次開始，每次增加100 次一直到2 000 次，重復(fù)試驗(yàn)。通過對(duì)獲取的試驗(yàn)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)得到的數(shù)據(jù)分別如表1～ 表5 所示。

表1 成功規(guī)劃路徑的平均長度 m

表2 成功規(guī)劃路徑的平均時(shí)間 s

表3 成功規(guī)劃路徑次數(shù)

表4 成功規(guī)劃路徑最短路徑長度 m

表5 成功規(guī)劃路徑最大路徑長度 m

由表1 數(shù)據(jù)繪制出的成功規(guī)劃路徑的平均長度隨采樣數(shù)變化的折線圖，如圖11 所示。

圖11 成功規(guī)劃路徑的平均長度變化折線圖

由圖11 可以看出，在采樣次數(shù)相同的情況下，改進(jìn)的RRT*算法規(guī)劃出的平均路徑長度要比基本RRT*算法規(guī)劃出的路徑要短。仿真結(jié)果說明了在獲取相同長度的路徑的情況下，改進(jìn)的RRT*算法的采樣次數(shù)更少，且更加穩(wěn)定，因此改進(jìn)的RRT*能夠提前收斂。

由表2 數(shù)據(jù)繪制出的成功規(guī)劃路徑的平均時(shí)間隨采樣數(shù)變化的折線圖，如圖12 所示。

圖12 成功規(guī)劃路徑的平均時(shí)間變化折線圖

由圖12 可以看出，隨著采樣次數(shù)的增加，兩種算法消耗的時(shí)間都在增加，改進(jìn)的RRT*算法和RRT*算法規(guī)劃路徑的時(shí)間相差不大，因而改進(jìn)的RRT*算法并不會(huì)增加時(shí)間的消耗。

由表3 數(shù)據(jù)繪制出的30 次規(guī)劃路徑成功率的變化折線圖，如圖13 所示。

圖13 規(guī)劃路徑成功率變化折線圖

由圖13 可以看出，隨著采樣次數(shù)的增加，改進(jìn)的RRT*算法規(guī)劃路徑的成功率也在穩(wěn)定地增加；而RRT*算法的成功率波動(dòng)較大，算法不穩(wěn)定。

由表4 數(shù)據(jù)繪制出的30 次規(guī)劃路徑成功出的最短路徑長度變化折線圖，如圖14 所示。

圖14 成功規(guī)劃路徑最短路徑長度變化曲線圖

由圖14 可以看出，隨著采樣次數(shù)的增加，兩種算法規(guī)劃出的最短路徑長度都在減小，但相對(duì)于RRT*來說，改進(jìn)RRT*算法的最短路徑穩(wěn)定性更好，路徑更短。

由表5 數(shù)據(jù)繪制出的30 次規(guī)劃路徑成功出的最長路徑長度變化折線圖，如圖15 所示。

圖15 成功規(guī)劃路徑最長路徑長度變化曲線圖

由圖15 可以看出，RRT*算法規(guī)劃出的最大路徑長度波動(dòng)較大，而改進(jìn)RRT*的規(guī)劃出的最大路徑長度隨著采樣次數(shù)的增加趨于收斂，算法較為穩(wěn)定。

在仿真試驗(yàn)中，分別對(duì)RRT*算法和改進(jìn)RRT*算法分別進(jìn)行一次15 萬次采樣的試驗(yàn)，耗費(fèi)時(shí)間約為35 分鐘，兩次規(guī)劃的路徑長度分別為952.709 m和951.987 m，兩種算法規(guī)劃出的總路徑長度相差不大，由于采樣的次數(shù)已達(dá)到十萬級(jí)別，可以將生成的路徑近似當(dāng)作理想的最優(yōu)路徑。規(guī)劃出的路徑基本沿著障礙物邊緣，如圖16 所示。

圖16 理想狀態(tài)的路徑

圖17 為多次RRT*算法規(guī)劃出最長路徑時(shí)的路徑分布，對(duì)比圖16 可以看到路徑并沒有從最后一個(gè)窄道通過，且在實(shí)驗(yàn)中發(fā)現(xiàn)規(guī)劃出較長路徑基本都存在這種情況，而改進(jìn)的RRT*算法不存在這種情況?？梢?，基于均勻分布Logistic 混沌序列采樣的RRT*算法由于采樣點(diǎn)的合理性使得路徑通過窄道的穩(wěn)定性更高。

圖17 RRT*算法規(guī)劃出的最長路徑

綜上可見，基于均勻分布Logistic 混沌序列采樣的RRT*算法比RRT*算法需要更少的采樣點(diǎn)且算法穩(wěn)定。

5 試驗(yàn)驗(yàn)證

5.1 試驗(yàn)平臺(tái)

試驗(yàn)平臺(tái)為實(shí)際應(yīng)用的移動(dòng)機(jī)器人底盤，其系統(tǒng)架構(gòu)如圖18 所示。

圖18 移動(dòng)機(jī)器人底盤系統(tǒng)架構(gòu)圖

由圖18 可以看出，系統(tǒng)主要分為3 個(gè)部分：底盤運(yùn)動(dòng)控制部分、中間決策部分、監(jiān)測(cè)部分(上層命令下發(fā)等)。底盤運(yùn)動(dòng)控制部分，主要采用STM32單片機(jī)來處理來自決策部分的控制命令，主要有機(jī)器人速度的控制，編碼器、IMU 等各種傳感器數(shù)據(jù)的采集以及上傳，底盤運(yùn)動(dòng)控制部分和中間層通過RS232 來進(jìn)行數(shù)據(jù)的交換。中間決策部分是一塊搭載了Ubuntu16.04 的x86 工控機(jī)。在該系統(tǒng)上已搭建好ROS 環(huán)境，主要負(fù)責(zé)機(jī)器人的實(shí)時(shí)定位、路徑規(guī)劃等運(yùn)算量比較大的部分。上層監(jiān)測(cè)部分使用的是一臺(tái)已經(jīng)搭建好ROS 環(huán)境的筆記本電腦，該電腦通過無線網(wǎng)絡(luò)接入系統(tǒng)，這樣可通過遠(yuǎn)程的方式對(duì)決策部分下發(fā)命令，同時(shí)可以實(shí)時(shí)監(jiān)控導(dǎo)航的效果。移動(dòng)機(jī)器人的底盤的外部和內(nèi)部實(shí)物圖分別如圖19 和圖20 所示。

圖19 機(jī)器人底盤實(shí)物外部

圖20 底盤實(shí)物圖內(nèi)部

5.2 試驗(yàn)方法和試驗(yàn)結(jié)果

試驗(yàn)的場(chǎng)地為所在的實(shí)驗(yàn)室，其掃描出的地圖如圖21 所示。

圖21 試驗(yàn)用地圖

不像A*算法那一類的最優(yōu)算法，能夠找到一條最優(yōu)路徑。RRT*算法和改進(jìn) RRT*都是于基于概率采樣得到的路徑，屬于漸進(jìn)最優(yōu)的算法，盡管隨著采樣次數(shù)的不斷增多能夠無限趨近于最優(yōu)路徑，但是獲得的路徑與所付出的計(jì)算資源完全不成正比。因而在使用這類算法時(shí)，只需得到一條相對(duì)較優(yōu)的路徑的前提下占用的資源較少即可。

在應(yīng)用改進(jìn)RRT*算法和RRT*算法時(shí)，規(guī)劃出來的路徑相對(duì)其它算法來說隨機(jī)性較高，無法確保實(shí)驗(yàn)的重復(fù)性，即無法保證兩次規(guī)劃出的路徑重合。并且在試驗(yàn)場(chǎng)景相對(duì)簡(jiǎn)單的情況下，仿真試驗(yàn)中性能對(duì)比的結(jié)果并不是特別明顯。所以在實(shí)際的機(jī)器人上試驗(yàn)時(shí)，使用了大多數(shù)路徑規(guī)劃性能比對(duì)的方案，即以規(guī)劃出的路徑長度和規(guī)劃的時(shí)間來衡量算法的性能。為了排除采樣算法的偶然性，試驗(yàn)方案選取同一個(gè)起點(diǎn)和同一終點(diǎn)間進(jìn)行多次（30 次）的路徑規(guī)劃，對(duì)規(guī)劃出的時(shí)間，路徑長度以及采樣點(diǎn)數(shù)量進(jìn)行了統(tǒng)計(jì)，然后取均值進(jìn)行比較。

圖22 所示為試驗(yàn)中選取兩點(diǎn)規(guī)劃出比較好的路徑截圖，圖22a）、圖22b）中起點(diǎn)、目標(biāo)點(diǎn)1 和目標(biāo)點(diǎn)2 用橢圓標(biāo)出，從起點(diǎn)到目標(biāo)點(diǎn)1 和目標(biāo)點(diǎn)2 之間的線條即為規(guī)劃出的路徑。

圖22 路徑規(guī)劃試驗(yàn)結(jié)果圖

當(dāng)以目標(biāo)點(diǎn)1 作為終點(diǎn)時(shí)，RRT*算法和改進(jìn)的RRT*算法路徑規(guī)劃數(shù)據(jù)（30 次試驗(yàn)的平均數(shù)據(jù)）如表6 所示。

表6 目標(biāo)點(diǎn)1 下兩種算法性能比較

由表6 可以看出，當(dāng)以目標(biāo)點(diǎn)1 為終點(diǎn)時(shí)，RRT*算法采樣點(diǎn)個(gè)數(shù)為435，而改進(jìn)RRT*算法采樣點(diǎn)個(gè)數(shù)為296，采樣點(diǎn)數(shù)減少了31.95%，因采樣點(diǎn)數(shù)有所減少，路徑規(guī)劃時(shí)間減少了42.29%，路徑長度減少了2.2%。

當(dāng)以目標(biāo)點(diǎn)2 作為終點(diǎn)時(shí)，RRT*算法和改進(jìn)的RRT*算法路徑規(guī)劃數(shù)據(jù)（30 次試驗(yàn)的平均數(shù)據(jù)）如表7 所示。

表7 目標(biāo)點(diǎn)2 下兩種算法性能比較

由表7 可以看出，當(dāng)以目標(biāo)點(diǎn)2 為終點(diǎn)時(shí)，RRT*算法采樣點(diǎn)個(gè)數(shù)為404，而改進(jìn)RRT*算法采樣點(diǎn)個(gè)數(shù)為297，采樣點(diǎn)數(shù)減少了26.49%，路徑規(guī)劃時(shí)間減少了64.52%，路徑長度增加了1.9%。

試驗(yàn)結(jié)果表明，改進(jìn)的RRT*算法能夠加快路徑向最優(yōu)路徑的收斂速度。在規(guī)劃出相同長度路徑的情況下，改進(jìn)的RRT*算法所需要的采樣點(diǎn)數(shù)更少，規(guī)劃出路徑的時(shí)間更短。即在采樣點(diǎn)相同的情況下，改進(jìn)的RRT*算法能夠獲得更短的路徑。

6 結(jié)論

本文提出了一種基于均勻分布Logistic 混沌序列采樣的RRT*路徑規(guī)劃算法，該方法通過采用Logistic混沌方法代替隨機(jī)數(shù)方法生成RRT*算法采樣點(diǎn)，不僅保證了采樣點(diǎn)的隨機(jī)性，也增加了采樣點(diǎn)遍歷性，使得采樣點(diǎn)在分布上更具合理性和有效，提高了通過障礙物區(qū)域的概率，加速了隨機(jī)樹重布線的效率，加速了RRT*算法的收斂速度。通過仿真和實(shí)驗(yàn)驗(yàn)證均表明基于均勻分布Logistic 混沌序列采樣的RRT*算法能夠提高路徑規(guī)劃的收斂速度。相對(duì)傳統(tǒng)的RRT*算法，在相同的路徑長度，改進(jìn)的RRT*算法所需要的采樣點(diǎn)數(shù)更少，規(guī)劃路徑的時(shí)間更短，穩(wěn)定性更高。