基于變參數(shù)閾值的隨機(jī)擴(kuò)展樹算法路徑規(guī)劃研究

姜利光+甘屹+孫福佳

摘要：針對隨機(jī)擴(kuò)展樹算法在未知空間中進(jìn)行路徑規(guī)劃擴(kuò)展時隨機(jī)性大，且擴(kuò)展的樹節(jié)點在整個環(huán)境空間中搜索過于均勻等問題，提出一種基于變參數(shù)閾值的隨機(jī)擴(kuò)展樹算法。改進(jìn)后的算法在路徑規(guī)劃中，針對具體情況選取參數(shù)閾值作下一步擴(kuò)展，使得每次擴(kuò)展都有著一定的概率性偏向目標(biāo)；同時設(shè)定可變參數(shù)閾值，避免了陷入局部極小值，有效解決了隨機(jī)性大和搜索均勻問題。通過Matlab仿真實驗，驗證了該算法的可行性和有效性。

關(guān)鍵詞：隨機(jī)擴(kuò)展樹算法；路徑規(guī)劃；參數(shù)閾值

DOIDOI：10.11907/rjdk.171936

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）012-0067-03

Abstract：A stochastic extension tree algorithm based on variable parameter threshold is proposed to solve the large random of extension tree algorithm in the unknown space and the searching uniformity of extended tree nodes in the whole environment space. And then the improved algorithm is applied to the path planningto select the parameters for the next expansion aiming at the specific situation， so that each expansion has a certain probability of bias target； Meanwhile， the variable parameter threshold is set to avoid falling into the local minimum，which effectively solves the problem of large random and searching uniformity. Finally， the feasibility and validity of the algorithm are verified by MATLAB simulation experiment.

Key Words：stochastic expansion tree algorithm； path planning； parameter threshold

0 引言

路徑規(guī)劃技術(shù)是移動機(jī)器人研究領(lǐng)域的一個重要組成部分。其目的是機(jī)器人按照某一性能（時間、路程、耗能）搜索出一條由起始位置節(jié)點到目標(biāo)位置節(jié)點之間的最優(yōu)或次優(yōu)無碰路徑。路徑規(guī)劃主要分為：完全已知的全局路徑規(guī)劃、完全未知或部分未知的局部路徑規(guī)劃[1]。已有研究多是關(guān)于全局已知的靜態(tài)環(huán)境中的路徑規(guī)劃。但在實際工作中，環(huán)境中的障礙物位置、大小信息都是未知或部分已知，有時障礙物的位置還會隨著時間的變化而不斷移動，增加了路徑規(guī)劃中的建模難度[2]。

隨機(jī)擴(kuò)展樹（Rapidly-exploring Random Tree，RRT）算法采用隨機(jī)采樣的規(guī)劃方法，無需對環(huán)境空間進(jìn)行建模，避免了預(yù)處理[3]。但由于RRT算法是基于隨機(jī)采樣的機(jī)制，導(dǎo)致在路徑規(guī)劃時擴(kuò)展的樹節(jié)點均布于整個空間內(nèi)，產(chǎn)生大量的無效搜索。針對該問題，提出通過重復(fù)使用前一個周期的隨機(jī)樹信息對RRT算法進(jìn)行改進(jìn)，如ERRT算法[4]、DRRT算法[5]等均在一定程度上提高了RRT算法的穩(wěn)定性，但RRT算法所采用的固有規(guī)劃方式限制了其進(jìn)一步應(yīng)用。本研究采用RRT算法進(jìn)行機(jī)器人路徑規(guī)劃，以避免復(fù)雜的空間建模，并提出通過引入變參數(shù)閾值引導(dǎo)隨機(jī)樹在擴(kuò)展樹節(jié)點時以一定的概率偏向目標(biāo)點，避免了搜索點過于平均的問題。此外，參數(shù)閾值存在可變性，使得算法避免收斂于局部極小值。

1 RRT算法原理

RRT算法以機(jī)器人移動的開始點作為樹的初始根節(jié)點，利用隨機(jī)采樣原則，選定一個隨機(jī)節(jié)點。根據(jù)機(jī)器人移動約束條件（如步長、角度），在所選擇的節(jié)點上避開障礙物進(jìn)行擴(kuò)展，直到產(chǎn)生一個新節(jié)點，并將此新節(jié)點添加到搜索樹中，以此為樹節(jié)點作下一步擴(kuò)展，依次重復(fù)上述過程，直至找到所要尋找的目標(biāo)點才停止搜索。RRT算法擴(kuò)展方式如圖1所示。

圖1中，C表示擴(kuò)展環(huán)境空間，X0表示初始點，Xi表示隨機(jī)點，Xj表示離隨機(jī)點最近的一個樹節(jié)點，Xi為在Xi和Xj的連線上以步長Δ為單位截取的新節(jié)點。

該算法在搜索過程中要保證隨機(jī)采樣使得機(jī)器人向未知區(qū)域擴(kuò)展，并在搜索過程中不斷推進(jìn)搜索樹生長，同時使得樹節(jié)點與目標(biāo)點的距離不斷接近，最終該目標(biāo)點為樹上的一個節(jié)點或者在最后的節(jié)點附近（小于一個步長距離），即完成搜索任務(wù)[6]。

定義X0為初始位姿構(gòu)建隨機(jī)樹T，搜索步驟如下：①在空間C中，從初始點X0出發(fā)先建立一顆遍歷樹T；②在所處的區(qū)域內(nèi)隨機(jī)選擇一個位姿點Xi；③找出T中距離Xi最近的節(jié)點Xj，然后選擇控制輸入集U中的選擇輸入u∈U（如速度、角度等）作用在Xj，使得機(jī)器人沿著Xi直至Xj；④由Xj朝Xi方向擴(kuò)展一定的距離Δ到Xk（Δ為步長），并且Xk屬于該自由空間中的點；⑤選擇能使Xj到Xi距離最近的控制輸入u為最佳輸入，依次重復(fù)該過程直到新生成的某個點與目標(biāo)點（Xm）的距離小于該步長，至此隨機(jī)樹構(gòu)建完畢。

2 變參數(shù)閾值RRT算法

2.1 偏向目標(biāo)算法模型

RRT算法在全局規(guī)劃中隨機(jī)選取節(jié)點，能夠擴(kuò)大搜索空間，但這種隨機(jī)選擇也會導(dǎo)致路徑規(guī)劃中的盲目性，不僅使得路徑解發(fā)散，同時也會耗費相當(dāng)長的算法搜索時間。特別是在障礙物較少的局部空間中，隨機(jī)性會將路徑搜索點均勻遍布于空間內(nèi)，延長路徑解收斂時間。為了提升RRT算法效率，研究者[7-8]提出采用偏向目標(biāo)RRT算法（Bias-goal，Bg-RRT）。隨機(jī)函數(shù)生成樹節(jié)點之前，先按照平均概率分布方式隨機(jī)獲取一個概率值，以一定的概率性將目標(biāo)點作為牽引點，在一定程度上解決擴(kuò)展節(jié)點時隨機(jī)性大的問題。具體步驟為：取參數(shù)閾值q，表示該算法認(rèn)定目標(biāo)點Xm為隨機(jī)點Xi的幾率。如果q的值大于算法產(chǎn)生的概率值p，就選取目標(biāo)點Xm為Xi。如果q的值小于算法產(chǎn)生的概率值p，就由隨機(jī)函數(shù)Random_Configuration（）隨機(jī)產(chǎn)生Xi。經(jīng)過大量研究發(fā)現(xiàn)，加入?yún)?shù)閾值q后，該算法可以使得擴(kuò)展樹快速地向目標(biāo)點生長，但過多偏向目標(biāo)點時會使擴(kuò)展樹生長陷入局部最優(yōu)[9-10]。

2.2 Vpt-RRT算法

3 實驗仿真與分析

仿真實驗所用的計算機(jī)處理器為Intel（R） CORE（TM）i5-2400 CPU @ 3.10GHz 3.10GHz，顯卡為Intel（R） HD Graphics，內(nèi)存為4.00G，采用MATLABR2014a工具編程實現(xiàn)。

3.1 參數(shù)閾值設(shè)定

Bg-RRT算法中，參數(shù)閾值q的值域為[0，1]。以q=0.1取值間隔為0.1，進(jìn)行不同參數(shù)閾值q的路徑規(guī)劃仿真實驗。仿真實驗中選取相同的步長，以仿真結(jié)果中擴(kuò)展的總節(jié)點數(shù)、路徑平均規(guī)劃時間作為性能指標(biāo)。對每一個參數(shù)閾值q，分別做多次實驗，通過統(tǒng)計分析實驗到第10次時結(jié)果趨于收斂；故取10次實驗的平均值作為該q值的Bg-RRT算法運(yùn)行結(jié)果，仿真實驗結(jié)果如圖3、圖4所示。

由圖3可知，隨著參數(shù)閾值q值的增大，Bg-RRT算法中隨機(jī)樹擴(kuò)展的總節(jié)點數(shù)先減小后增大再減小，總體呈現(xiàn)下降趨勢。由圖4可知，路徑規(guī)劃時間總體上隨著參數(shù)閾值q的增大先減小后增大。通過分析圖3、圖4可知，參數(shù)閾值q對Bg-RRT算法而言十分重要，直接影響路徑規(guī)劃相關(guān)性能指標(biāo)。q值選取得是否合理直接影響最終路徑規(guī)劃的優(yōu)劣。q值較小時，隨機(jī)樹擴(kuò)展的樹節(jié)點增多，說明規(guī)劃中偏向目標(biāo)搜索的趨勢不明顯，隨機(jī)樹會向其它空白區(qū)域進(jìn)行無效擴(kuò)展。q取值較大時，隨機(jī)樹以較大的概率選取目標(biāo)節(jié)點進(jìn)行擴(kuò)展，更傾向朝著目標(biāo)點生長，擴(kuò)展的樹節(jié)點較少；但由于隨機(jī)節(jié)點選擇單一，規(guī)避障礙物的能力減弱，甚至陷入局部極小值。因此需要花費更多的時間躲避障礙，進(jìn)而增加了規(guī)劃時間。

通過以上仿真分析可知，本文中的qmax可取0.7，此時擴(kuò)展樹有較大的偏目標(biāo)趨勢，且路徑規(guī)劃時間相對較少，在無障礙空間內(nèi)能以較大的概率朝著目標(biāo)搜索。而對于qmin，取0.1時，算法規(guī)劃時間、擴(kuò)展的樹節(jié)點相對較多。在路徑規(guī)劃中，q值的選取根據(jù)定義視具體情況而定，合理完成RRT算法的路徑規(guī)劃。

3.2 仿真實驗

機(jī)器人移動的仿真環(huán)境范圍設(shè)置為100*100單位格，整個環(huán)境空間分為障礙區(qū)域和非障礙區(qū)域，其中空白處表示無障礙區(qū)域，黑色圓表示障礙物。仿真環(huán)境中設(shè)定機(jī)器人移動的起始點坐標(biāo)為（5，5），目標(biāo)點坐標(biāo)為（95，95）。

采用RRT算法、Bg-RRT算法和Vpt-RRT算法分別在大型障礙物環(huán)境、存有狹窄通道環(huán)境、復(fù)雜障礙環(huán)境下進(jìn)行對比實驗。各種環(huán)境中的障礙物大小、數(shù)量均隨機(jī)生成。

圖5為3種算法在大型障礙物環(huán)境下的路徑規(guī)劃結(jié)果，其中“+”表示隨機(jī)樹在規(guī)劃過程中擴(kuò)展的樹節(jié)點，線條表示由起始點到目標(biāo)點的路徑規(guī)劃擬合線。圖6為狹窄通道環(huán)境下3種算法的路徑規(guī)劃結(jié)果，仿真過程設(shè)定迭代次數(shù)為500次時，RRT算法會出現(xiàn)無法成功規(guī)劃的現(xiàn)象，Vpt-RRT算法則能夠在每次仿真中快速找到一條有效路徑。復(fù)雜障礙物環(huán)境下的路徑規(guī)劃如圖7所示。

由圖5-圖7可看出，本文提出的Vpt-RRT算法在不同的障礙環(huán)境中都能合理地規(guī)劃出一條有效路徑。

為了更清楚地體現(xiàn)變參數(shù)閾值RRT算法的優(yōu)越性，在以上3組實驗中分別用RRT算法、Bg-RRT算法和Vpt-RRT算法各進(jìn)行100次仿真實驗，取平均值作對比。表1和表2分別為路徑規(guī)劃過程中的總節(jié)點數(shù)和有效節(jié)點數(shù)。

由表1、表2可知，Vpt-RRT算法在3種不同環(huán)境下路徑規(guī)劃過程中擴(kuò)展的總節(jié)點數(shù)和有效節(jié)點數(shù)均優(yōu)于其它兩種算法，特別是在存有狹窄通道的環(huán)境下，這說明Vpt-RRT算法能夠大大減少擴(kuò)展的樹節(jié)點，并且該算法具有很好的避障性能和尋優(yōu)能力。

4 結(jié)語

本文針對基本隨機(jī)擴(kuò)展樹算法在路徑規(guī)劃中隨機(jī)性大、搜索方式過于平均、搜索效率低下等問題，分析其原因在于隨機(jī)點在全空間分布過于均勻。鑒于此，提出了Vpt-RRT算法，在原算法中通過增加變參數(shù)閾值，視具體環(huán)境確定閾值大??；引導(dǎo)擴(kuò)展中樹節(jié)點的選取，使節(jié)點有偏向目標(biāo)點的趨勢，避免了擴(kuò)展中的無效搜索，使得隨機(jī)樹能夠朝著目標(biāo)點快速地擴(kuò)展生長，解決了隨機(jī)點分布過于平均的缺點；并且由于每次擴(kuò)展時參數(shù)閾值都具有可變性，因而避免了陷入局部極小值。最后在3種不同環(huán)境下，分別對RRT算法、Bg-RRT算法與本文提出的Vpt-RRT算法進(jìn)行仿真實驗。結(jié)果表明，在不同的仿真環(huán)境中，本文提出的算法均具有更好的可行性和有效性。

參考文獻(xiàn)：

[1] 魏唯.智能規(guī)劃方法中啟發(fā)式搜索策略的研究[D].長春：吉林大學(xué)，2013.

[2] 朱大奇，顏明重.移動機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010，25（7）：961-967.

[3] 張煜，任保安，陳璟.基于改進(jìn)RRT算法的預(yù)警機(jī)實時航跡規(guī)劃[J].計算機(jī)仿真，2016（9）：106-112.

[4] 馮林，賈菁輝.基于對比優(yōu)化的RRT路徑規(guī)劃改進(jìn)算法[J].計算機(jī)工程與應(yīng)用，2011，47（3）：210-213，228.

[5] 宋金澤，戴斌，單恩忠，等.一種改進(jìn)的RRT路徑規(guī)劃算法[J].電子學(xué)報，2010，38：225-228.

[6] 杜明博，梅濤，陳佳佳，等.復(fù)雜環(huán)境下基于RRT的智能車輛運(yùn)動規(guī)劃算法[J].機(jī)器人，2015（4）：443-450.

[7] 黃炳強(qiáng)，曹廣益.基于人工勢場法的移動機(jī)器人路徑規(guī)劃研究[J].計算機(jī)工程與應(yīng)用，2006（27）：26-28.

[8] FRAGKOPOULO CHRISTOS，GRAESER AXEL.Extended algorithm with dynamic N-dimensional cuboid domains[C].Proceedings of the International Conference on Optimisation of Electrical and Electronic Equipment，OPTIM，2010：851-857.

[9] GARRIDO SANTIAGO，BLANCO DOLORES，MORENO LUIS，et al.Improving RRT motion trajectories using VFM [C].IEEE 2009 International Conference on Mechatronics，ICM，2009.

[10] 王濱，金明河，謝宗武，等.基于啟發(fā)式的快速擴(kuò)展隨機(jī)樹路徑規(guī)劃算法[J].機(jī)械制造，2007，45（12）：1-4.

（責(zé)任編輯：孫 娟）