一種基于RRT-ConCon改進(jìn)的路徑規(guī)劃算法

王 凡， 馮 楠， 胡 小 鵬

( 1.大連理工大學(xué) 電子信息與電氣工程學(xué)部, 遼寧 大連 116024；2.中國(guó)人民解放軍65066部隊(duì)， 遼寧 大連 116100 )

?

一種基于RRT-ConCon改進(jìn)的路徑規(guī)劃算法

王 凡*1， 馮 楠1,2， 胡 小 鵬1

( 1.大連理工大學(xué) 電子信息與電氣工程學(xué)部, 遼寧 大連 116024；2.中國(guó)人民解放軍65066部隊(duì)， 遼寧 大連 116100 )

針對(duì)RRT算法缺乏穩(wěn)定性和收斂速度慢的問(wèn)題，基于RRT-ConCon算法和朝向目標(biāo)搜索的策略，提出了一種改進(jìn)的雙向搜索路徑規(guī)劃算法．該算法通過(guò)改變兩條搜索路徑的臨時(shí)擴(kuò)展目標(biāo)點(diǎn)，使搜索路徑不僅易于朝著目標(biāo)點(diǎn)方向生長(zhǎng)，而且提高了算法的穩(wěn)定性，同時(shí)可以保證規(guī)劃的路徑接近最優(yōu)解．改進(jìn)的RRT-ConCon算法利用隨機(jī)節(jié)點(diǎn)生成函數(shù)，使朝著目標(biāo)點(diǎn)生長(zhǎng)的搜索路徑避免陷入局部極小值．同時(shí)，為了測(cè)試各種仿真實(shí)驗(yàn)環(huán)境，還設(shè)計(jì)了一種仿真實(shí)驗(yàn)環(huán)境平臺(tái)，實(shí)驗(yàn)結(jié)果驗(yàn)證了本算法的有效性和穩(wěn)定性．

移動(dòng)機(jī)器人；路徑規(guī)劃；快速擴(kuò)展隨機(jī)樹(shù)(RRT)；雙向搜索樹(shù)(Bi-RRT)；RRT-ConCon算法

0 引 言

近年來(lái)移動(dòng)機(jī)器人的研究和開(kāi)發(fā)越來(lái)越受到各位學(xué)者的高度重視．在移動(dòng)機(jī)器人相關(guān)技術(shù)的研究中，路徑規(guī)劃問(wèn)題是其中的關(guān)鍵課題之一．所謂路徑規(guī)劃是指移動(dòng)機(jī)器人按照某一性能指標(biāo)(如距離、時(shí)間、能量等)搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或次優(yōu)路徑[1]．傳統(tǒng)的路徑規(guī)劃算法主要有人工勢(shì)場(chǎng)算法、模糊規(guī)則算法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)算法、模擬退火算法、蟻群優(yōu)化算法、粒子群算法等[2-4]，這些路徑規(guī)劃算法在處理普通的路徑規(guī)劃問(wèn)題時(shí)有一定的優(yōu)越性，但是當(dāng)機(jī)器人具有高自由度和工作環(huán)境更加復(fù)雜時(shí)，這些算法的計(jì)算復(fù)雜度會(huì)隨之提高，因此降低了求解速率[5-6]．

LaValle等提出了快速擴(kuò)展隨機(jī)樹(shù)(rapidly- exploring random trees，RRT)算法[7-8]．由于該算法不需要對(duì)空間建模，而且搜索速度快，適合解決高維空間和復(fù)雜環(huán)境中機(jī)器人的路徑規(guī)劃問(wèn)題[7-9]．近年來(lái)，RRT算法作為一種基于隨機(jī)采樣的單一查詢(xún)路徑規(guī)劃算法得到了廣泛的研究和應(yīng)用，但是其隨機(jī)性導(dǎo)致其只能概率完備[8]，其本身包含一些缺點(diǎn)：(1)不穩(wěn)定性，即對(duì)同一任務(wù)重復(fù)規(guī)劃時(shí)，會(huì)產(chǎn)生不同的路徑；(2)偏差性，即規(guī)劃出的路徑常常不是最優(yōu)路徑或次優(yōu)路徑；(3)無(wú)導(dǎo)向性，即搜索樹(shù)無(wú)任何偏向于目標(biāo)的導(dǎo)向，收斂速度可能是緩慢的．

針對(duì)基本RRT算法的不足，國(guó)內(nèi)外學(xué)者不斷對(duì)該算法進(jìn)行改進(jìn)以適應(yīng)應(yīng)用環(huán)境．如：為了提高搜索路徑的穩(wěn)定性，一些學(xué)者提出了ERRT、DRRT、MP-RRT算法等[10-14]；為了提高搜索效率，一些學(xué)者提出了偏向搜索樹(shù)、雙向搜索樹(shù)(bidirectional rapidly-exploring random trees，Bi-RRT)算法等，以及其他的相關(guān)改進(jìn)算法[15-19]．本文基于RRT-ConCon算法和朝向目標(biāo)搜索策略，提出一種改進(jìn)的雙向搜索路徑規(guī)劃算法，以保證規(guī)劃路徑接近最優(yōu)路徑．

1 RRT-ConCon算法

1.1 基本的雙向搜索樹(shù)(Bi-RRT)算法

基本的雙向搜索樹(shù)(Bi-RRT)算法[20]的主要思想是：從初始點(diǎn)和目標(biāo)點(diǎn)出發(fā)，并行構(gòu)建兩棵搜索樹(shù)；在每次迭代過(guò)程中，兩棵搜索樹(shù)總是彼此朝著對(duì)方擴(kuò)展，直至兩棵搜索樹(shù)相遇為止．基本的Bi-RRT構(gòu)建過(guò)程如下：在每次迭代中，先擴(kuò)展其中一棵搜索樹(shù)，然后嘗試將另一棵搜索樹(shù)擴(kuò)展到當(dāng)前搜索樹(shù)擴(kuò)展的新節(jié)點(diǎn)；兩棵搜索樹(shù)Tinit和Tgoal交替擴(kuò)展，直至兩棵搜索樹(shù)相遇為止．基本的Bi-RRT算法的偽代碼如下：

Algorithm1Bidirectional RRT Algorithm

Input:

T1: first RRT

T2: second RRT

l: number of attempts allowed to connectT1andT2

Output:

connected if the two RRTs are connected to each other; failure otherwise

1. fori=1 toldo

2.qrand← a randomly chosen free configuration

3.qnew,1← Extend RRT(T1,qrand)

4. ifqnew,1≠NIL then

5.qnew,2← Extend RRT(T2,qnew,1)

6. ifqnew,1=qnew,2then

7. returnPATH(T1,T2)

8. end if

9.SWAP(T1,T2)

10. end if

11. end for

12. return failure

Algorithm2Extend RRT Algorithm

Input:

T=(V,E): an RRT

q: a configuration toward which the treeTis grown

Output:

A new configurationqnewtowardq, or NIL in case of failure

1.qnear← closest neighbor ofqinT

2.qnew← progressqnearby step_size along the straight line betweenqnearandqrand

3. ifqnewis collision-free then

4.V←V∪{qnew}

5.E←E∪{(qnear,qnew)}

6. returnqnew

7. end if

8. return NIL

1.2 RRT-ConCon算法描述

基本的Bi-RRT算法比單棵RRT算法能產(chǎn)生更好的收斂性．為了進(jìn)一步提高搜索效率，Kuffner和LaValle提出了Connect算法[21]，使得每次節(jié)點(diǎn)擴(kuò)展操作更積極．Connect算法的偽代碼如下：

Algorithm3Connect Algorithm

Input:

T=(V,E): an RRT

q: a configuration toward which the treeTis grown

Output:

Connected ifqis connected toT; failure otherwise

1. repeat

2.S← Extend RRT(T,q)

3. until not (S=qnew)

4. returnS

分析可知，Connect算法是一種“貪婪算法”，通過(guò)迭代擴(kuò)展，使當(dāng)前節(jié)點(diǎn)一直朝著臨時(shí)目標(biāo)點(diǎn)擴(kuò)展．同時(shí)，Connect算法也是一種改進(jìn)的擴(kuò)展節(jié)點(diǎn)函數(shù)，它是通過(guò)重復(fù)調(diào)用擴(kuò)展節(jié)點(diǎn)函數(shù)Extend來(lái)實(shí)現(xiàn)的．

如果將基本的Bi-RRT算法(Algorithm 1)視為RRT-ExtExt算法，那么通過(guò)用Connect函數(shù)替換Extend 函數(shù)衍生出RRT-ExtCon、RRT-ConCon 等多種算法．用Connect函數(shù)替換RRT-ExtExt算法中的第1個(gè)Extend函數(shù)，目的是使節(jié)點(diǎn)更積極地?cái)U(kuò)展到狀態(tài)空間．用Connect函數(shù)替換RRT-ExtExt算法中的第2個(gè)Extend函數(shù)，目的是在每次迭代中，算法能夠積極地嘗試連接兩棵搜索樹(shù)．RRT-ConCon算法就是將RRT-ExtExt 算法中的兩個(gè)Extend函數(shù)都用Connect函數(shù)替換．與其他變形的多種規(guī)劃算法相比，RRT-ConCon算法具有較高的規(guī)劃效率．圖1為RRT-ConCon構(gòu)建過(guò)程，圖中，搜索樹(shù)Tgoal利用Connect函數(shù)擴(kuò)展到隨機(jī)采樣點(diǎn)qtarget，同時(shí)將該點(diǎn)作為另一棵搜索樹(shù)Tinit擴(kuò)展的子目標(biāo)點(diǎn)；在搜索樹(shù)Tinit上找到離子目標(biāo)點(diǎn)qtarget最近的節(jié)點(diǎn)qnear，然后通過(guò)Connect函數(shù)找到新的節(jié)點(diǎn)qnew添加到搜索樹(shù)S(xS,yS)上．兩棵搜索樹(shù)按照交換原則擴(kuò)展．

圖1 RRT-ConCon構(gòu)建過(guò)程

2 一種基于RRT-ConCon改進(jìn)的路徑規(guī)劃算法

2.1 改進(jìn)的路徑規(guī)劃算法描述

RRT-ConCon算法雖然比基本的Bi-RRT算法的收斂性能更好，但該算法生成的路徑仍具有隨機(jī)性和不穩(wěn)定性．綜上，本文提出一種基于RRT-ConCon算法和朝向目標(biāo)搜索的改進(jìn)路徑規(guī)劃算法．改進(jìn)的RRT-ConCon構(gòu)建過(guò)程如圖2所示，虛線(xiàn)箭頭方向表示當(dāng)前節(jié)點(diǎn)的擴(kuò)展方向．改進(jìn)的RRT-ConCon算法與原算法相比有兩處不同：一是在改進(jìn)的算法中，搜索路徑Tinit的臨時(shí)目標(biāo)點(diǎn)一直是終點(diǎn)qgoal，保證了算法的穩(wěn)定性，搜索樹(shù)Tgoal的臨時(shí)目標(biāo)點(diǎn)是另一條搜索路徑Tinit擴(kuò)展得到的新節(jié)點(diǎn)；二是在改進(jìn)的算法中，引入了隨機(jī)節(jié)點(diǎn)生成函數(shù)．

圖2 改進(jìn)的RRT-ConCon構(gòu)建過(guò)程

如果S(xS,yS)表示移動(dòng)機(jī)器人初始點(diǎn)，G(xG,yG)表示移動(dòng)機(jī)器人目標(biāo)點(diǎn)，那么本文所提出的改進(jìn)路徑規(guī)劃算法具體步驟如下：

Step1對(duì)搜索路徑PATH初始化，PATH開(kāi)始只包含初始點(diǎn)S和目標(biāo)點(diǎn)G．

Step2如果初始點(diǎn)S和目標(biāo)點(diǎn)G的距離小于一個(gè)給定閾值T，則認(rèn)為搜索路徑到達(dá)了目標(biāo)點(diǎn)，返回搜索路徑PATH={(S,G)}；否則進(jìn)入Step4．

Step3如果T1與T2相遇，則返回搜索路徑PATH={T1,T2}．

Step4對(duì)于搜索樹(shù)T1，調(diào)用擴(kuò)展節(jié)點(diǎn)函數(shù)，朝著目標(biāo)點(diǎn)方向擴(kuò)展搜索樹(shù)，直至搜索路徑遇到障礙物或T1與T2相遇為止；將擴(kuò)展節(jié)點(diǎn)函數(shù)的返回節(jié)點(diǎn)添加到搜索樹(shù)T1中．

Step5當(dāng)T1遇到障礙物時(shí)，調(diào)用隨機(jī)節(jié)點(diǎn)生成函數(shù)，生成一個(gè)隨機(jī)節(jié)點(diǎn)，將該節(jié)點(diǎn)添加到搜索樹(shù)T1中．

Step6對(duì)于搜索樹(shù)T2，調(diào)用擴(kuò)展節(jié)點(diǎn)函數(shù)，朝著T1擴(kuò)展得到的新節(jié)點(diǎn)擴(kuò)展，直至搜索路徑遇到障礙物或T1與T2相遇為止；將擴(kuò)展節(jié)點(diǎn)函數(shù)的返回節(jié)點(diǎn)添加到搜索樹(shù)T2中．

Step7當(dāng)T2遇到障礙物時(shí)，調(diào)用隨機(jī)節(jié)點(diǎn)生成函數(shù)，生成一個(gè)隨機(jī)節(jié)點(diǎn)，將該節(jié)點(diǎn)添加到搜索樹(shù)T2中．

Step8返回到Step3．

為了使該算法可控，在Step8中加入循環(huán)次數(shù)上限．如果在限制次數(shù)內(nèi)搜索樹(shù)無(wú)法到達(dá)目標(biāo)點(diǎn)或目標(biāo)區(qū)域，則算法返回失?。倪M(jìn)的RRT-ConCon算法的偽代碼如下：

Algorithm4Improved RRT-ConCon Algorithm

Input:

T1: first RRT

T2: second RRT

l: number of attempts allowed to connectT1andT2

Output:

Connected if the two RRTs are connected to each other; failure otherwise

1. fori=1 toldo

2.qnew,1← Connect (T1,G)

3.qnew,1← RandomNode (qnew,1,ρ)

4. ifqnew,1≠NIL then

5.qnew,2← Connect (T2,qnew,1)

6. ifqnew,1=qnew,2then

7. returnPATH(T1,T2)

8. elseqnew,2← RandomNode (qnew,2,ρ)

9. end if

10. end if

11. end for

12. return failure

2.2 改進(jìn)的Connect函數(shù)

RRT-ConCon中調(diào)用擴(kuò)展函數(shù)Connect (T,q)，其中T是搜索樹(shù)Tinit或搜索樹(shù)Tgoal，q是自由空間中選擇的臨時(shí)目標(biāo)點(diǎn)．對(duì)于改進(jìn)的RRT-ConCon算法，從初始點(diǎn)生成的搜索樹(shù)T1調(diào)用的擴(kuò)展節(jié)點(diǎn)函數(shù)為Connect (T1,G)，其中G是目標(biāo)點(diǎn)；從目標(biāo)點(diǎn)生成的搜索樹(shù)T2調(diào)用的擴(kuò)展節(jié)點(diǎn)函數(shù)為Connect (T2,qnew,1)，其中qnew,1是搜索樹(shù)T1擴(kuò)展的一個(gè)新節(jié)點(diǎn)．

與Connect函數(shù)相同，改進(jìn)的Connect函數(shù)也是通過(guò)重復(fù)調(diào)用擴(kuò)展函數(shù)Extend來(lái)實(shí)現(xiàn)的．改進(jìn)的Extend函數(shù)的偽代碼如下：

Algorithm5EXTEND Algorithm

Input:

P: a configuration in Route

Q: a free configuration

Output:

A new configurationqnewis obtained by movingPby step_size towardQ, or NIL in case of failure

1.qnew← progressPby step_size along the straight line betweenPandQ

2. ifqnewis collision-free then

3.V←V∪{qnew}

4.E←E∪{(P,qnew)}

5. returnqnew

6. end if

7. return NIL

對(duì)于輸入的當(dāng)前節(jié)點(diǎn)P、臨時(shí)目標(biāo)點(diǎn)Q，算法從當(dāng)前節(jié)點(diǎn)P出發(fā)，朝著臨時(shí)目標(biāo)點(diǎn)Q的方向嘗試擴(kuò)展路徑．如果Extend函數(shù)返回值是一個(gè)新節(jié)點(diǎn)qnew，則將qnew添加到搜索路徑PATH中；如果Extend函數(shù)返回值是空，也就是說(shuō)探測(cè)節(jié)點(diǎn)與障礙物發(fā)生碰撞，那么下一步將調(diào)用隨機(jī)節(jié)點(diǎn)生成函數(shù)來(lái)躲避障礙物．

2.3 隨機(jī)節(jié)點(diǎn)生成函數(shù)——RandomNode函數(shù)

由于在本文算法中，從初始點(diǎn)生成的搜索樹(shù)T1采用了朝向目標(biāo)的擴(kuò)展策略，雖然提高了算法的收斂速度，但也容易使搜索路徑陷入一個(gè)局部極小值．為了避免這個(gè)問(wèn)題，本文在搜索樹(shù)遇到障礙物時(shí)，考慮隨機(jī)生成一個(gè)節(jié)點(diǎn)來(lái)躲避障礙物．

函數(shù)RandomNode (P,ρ)的作用是生成隨機(jī)節(jié)點(diǎn)．如圖3所示，灰色圓表示障礙物，圓點(diǎn)P表示機(jī)器人當(dāng)前位置節(jié)點(diǎn)，虛線(xiàn)圓表示移動(dòng)機(jī)器人下一步可能到達(dá)的位置軌跡，那么該圓的半徑為移動(dòng)機(jī)器人的規(guī)劃步長(zhǎng)；該虛線(xiàn)圓上的每一個(gè)無(wú)碰撞節(jié)點(diǎn)(如節(jié)點(diǎn)A、B、N)都是移動(dòng)機(jī)器人下一步可能到達(dá)的節(jié)點(diǎn)，而虛線(xiàn)圓與障礙物發(fā)生碰撞的點(diǎn)(如節(jié)點(diǎn)C)都是移動(dòng)機(jī)器人不能到達(dá)的節(jié)點(diǎn)．設(shè)節(jié)點(diǎn)N是移動(dòng)機(jī)器人下一步將要到達(dá)的節(jié)點(diǎn)，那么節(jié)點(diǎn)N由函數(shù)RandomNode (P,ρ)隨機(jī)生成．隨機(jī)節(jié)點(diǎn)N(xN,yN)滿(mǎn)足以下3個(gè)條件：(1)節(jié)點(diǎn)N滿(mǎn)足方程(xN-xP)2+(yN-yP)2=ρ2；(2)節(jié)點(diǎn)N是無(wú)碰撞節(jié)點(diǎn)；(3)節(jié)點(diǎn)N能成功與節(jié)點(diǎn)P連接．隨機(jī)節(jié)點(diǎn)生成函數(shù)算法的偽代碼如下：

Algorithm6RandomNode Algorithm

Input:

P: a configuration in Route

ρ: step_size

Output:

A randomly chosen free configuration

1. while (connect(P,N)=0) do

2.N← a randomly chosen free configuration inO(P,ρ)

3. if connect (P,N) then

4. returnN

5. end if

對(duì)于輸入的當(dāng)前節(jié)點(diǎn)P和機(jī)器人規(guī)劃步長(zhǎng)ρ，在P為圓心、ρ為半徑的圓周上隨機(jī)地計(jì)算一個(gè)節(jié)點(diǎn)N．判斷N是否與環(huán)境中的障礙物發(fā)生碰撞并且判斷節(jié)點(diǎn)P和N是否成功連接，如果這兩項(xiàng)檢測(cè)結(jié)果都成功，那么返回節(jié)點(diǎn)N．

圖3 隨機(jī)節(jié)點(diǎn)生成過(guò)程

3 仿真實(shí)驗(yàn)

3.1 仿真實(shí)驗(yàn)環(huán)境平臺(tái)

為了建立各種障礙物環(huán)境，本文結(jié)合改進(jìn)的RRT-ConCon算法，設(shè)計(jì)了一種仿真實(shí)驗(yàn)環(huán)境平臺(tái)，該平臺(tái)的主要功能是繪制所需的仿真環(huán)境．仿真實(shí)驗(yàn)環(huán)境平臺(tái)用Matlab開(kāi)發(fā)，窗口界面主要包括參數(shù)配置和工作空間．在參數(shù)配置中可以選擇障礙物圖形(如矩形、圓形)和障礙物圖形半徑，可以設(shè)置起始點(diǎn)和目標(biāo)點(diǎn)坐標(biāo)．在工作空間中，環(huán)境設(shè)為30×30下的矩形區(qū)域．在設(shè)置仿真環(huán)境時(shí)，先配置好參數(shù)，然后在工作空間中單擊鼠標(biāo)，便可生成一個(gè)障礙物．該平臺(tái)還提供了一個(gè)開(kāi)放的算法接口，以便將仿真實(shí)驗(yàn)環(huán)境應(yīng)用于各類(lèi)型的路徑規(guī)劃算法，拓展了平臺(tái)的使用范圍．圖4(a)所示為該仿真實(shí)驗(yàn)環(huán)境平臺(tái)的窗口界面，圖4(b)所示為一個(gè)繪制的仿真實(shí)驗(yàn)環(huán)境．

3.2 仿真實(shí)驗(yàn)實(shí)例

為了驗(yàn)證本文算法的有效性，實(shí)驗(yàn)環(huán)境用Matlab開(kāi)發(fā)，運(yùn)行于PC機(jī)上，CPU主頻為2.4 GHz．仿真實(shí)驗(yàn)環(huán)境基于上述實(shí)驗(yàn)環(huán)境平臺(tái)建立，設(shè)置初始點(diǎn)坐標(biāo)為(0,0)，目標(biāo)點(diǎn)坐標(biāo)為(30,30)．實(shí)驗(yàn)?zāi)繕?biāo)為規(guī)劃一條從初始點(diǎn)到目標(biāo)點(diǎn)的有效路徑．

圖5顯示了本文算法在不同環(huán)境(隨機(jī)環(huán)境、通道環(huán)境、柵格環(huán)境、狹窄環(huán)境)中的路徑規(guī)劃．圖5(a)中的障礙物是隨機(jī)設(shè)置的，圖5(b)～(d)中的障礙物是按需要設(shè)置的．

不失一般性，使用圖5(a)設(shè)置的隨機(jī)環(huán)境來(lái)測(cè)試本文算法的穩(wěn)定性．如圖6所示，當(dāng)重復(fù)規(guī)劃一條路徑時(shí)，本文算法基本保證了路徑的穩(wěn)定性．

(a) 窗口界面

(b) 繪制實(shí)例

圖4 仿真實(shí)驗(yàn)環(huán)境平臺(tái)

Fig.4 Simulation experimental environment platform

圖5 不同環(huán)境中的路徑規(guī)劃

表1為本文算法與基本RRT算法在圖6仿真實(shí)驗(yàn)環(huán)境下，進(jìn)行仿真實(shí)驗(yàn)得到的數(shù)據(jù)比較．從表1中可以看出，相對(duì)于基本RRT算法來(lái)說(shuō)，本文算法路徑更優(yōu)，運(yùn)行時(shí)間更短，并且可以保證規(guī)劃的路徑接近最優(yōu)路徑．

圖6 重復(fù)規(guī)劃路徑比較

表1 仿真實(shí)驗(yàn)環(huán)境下的數(shù)據(jù)比較

4 結(jié) 語(yǔ)

針對(duì)RRT算法缺乏穩(wěn)定性和收斂速度慢的問(wèn)題，本文提出了一種基于RRT-ConCon算法和朝向目標(biāo)搜索的雙向搜索路徑規(guī)劃算法．改進(jìn)的RRT-ConCon算法通過(guò)改變一條搜索路徑(Tinit)的臨時(shí)擴(kuò)展目標(biāo)點(diǎn)提高了算法的穩(wěn)定性，同時(shí)可以保證規(guī)劃的路徑接近最優(yōu)解．由于本文算法結(jié)合了朝向目標(biāo)搜索的策略，使得搜索路徑易于陷入局部極小值的問(wèn)題能夠通過(guò)隨機(jī)節(jié)點(diǎn)生成函數(shù)得到解決．同時(shí)，為了測(cè)試各種環(huán)境，本文設(shè)計(jì)了一個(gè)仿真實(shí)驗(yàn)環(huán)境平臺(tái)，可以簡(jiǎn)單地繪制所需的仿真實(shí)驗(yàn)環(huán)境．通過(guò)與本文算法結(jié)合的仿真實(shí)驗(yàn)結(jié)果，驗(yàn)證了本文所提出的改進(jìn)算法在穩(wěn)定性、導(dǎo)向性及獲得最優(yōu)路徑方面都優(yōu)于RRT算法．但本文中仍存在一些有待完善的地方，下一步，嘗試改進(jìn)隨機(jī)節(jié)點(diǎn)生成函數(shù)，以便確定一條更優(yōu)的路徑，同時(shí)將該算法應(yīng)用于實(shí)際工程領(lǐng)域以更好地展示其有效性．

[1] LaValle S M.PlanningAlgorithms[M]. Cambridge:Cambridge University Press, 2006.

[2] 康 亮,趙春霞,郭劍輝. 未知環(huán)境下改進(jìn)的基于RRT算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 模式識(shí)別與人工智能, 2009,22(3):337-343.

KANG Liang, ZHAO Chun-xia, GUO Jian-hui. Improved path planning based on rapidly-exploring random tree for mobile robot in unknown environment [J].PR&AI, 2009,22(3):337-343. (in Chinese)

[3] 付 濤,王大鎮(zhèn),弓清忠,等. 改進(jìn)神經(jīng)網(wǎng)絡(luò)自適應(yīng)滑?？刂频臋C(jī)器人軌跡跟蹤控制[J]. 大連理工大學(xué)學(xué)報(bào), 2014,54(5):523-530.

FU Tao, WANG Da-zhen, GONG Qing-zhong,etal. Robot trajectory tracking control of improved neural network adaptive sliding mode control [J].JournalofDalianUniversityofTechnology, 2014,54(5):523-530. (in Chinese)

[4] 徐望寶,陳雪波,趙 杰. 個(gè)體機(jī)器人局部路徑規(guī)劃的人工力矩方法[J]. 大連理工大學(xué)學(xué)報(bào), 2012,52(3):418-425.

XU Wang-bao, CHEN Xue-bo, ZHAO Jie. Artificial moment method for local path planning of single robot [J].JournalofDalianUniversityofTechnology, 2012,52(3):418-425. (in Chinese)

[5] 王 勇,蔡自興,周育人,等. 約束優(yōu)化進(jìn)化算法[J]. 軟件學(xué)報(bào), 2009,20(1):11-29.

WANG Yong, CAI Zi-xing, ZHOU Yu-ren,etal. Constrained optimization evolutionary algorithms [J].JournalofSoftware, 2009,20(1):11-29. (in Chinese)

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

WANG Bin, JIN Ming-he, XIE Zong-wu,etal. Algorithm of path planning of rapidly-exploring random tree based on heuristics [J].Machinery, 2007,45(12):1-4. (in Chinese)

[7] LaValle S M. Rapidly-exploring random trees:A new tool for path planning, TR98-11 [R]. Ames:Department of Computer Science, Iowa State University, 1998.

[8] LaValle S M, Kuffner J J Jr. Rapidly-exploring random trees:Progress and prospects [C] //TheFourthInternationalWorkshoponAlgorithmicFoundationsofRobotics(WAFR). Natick:A. K. Peters, 2000:293-308.

[9] Mezura-Montes E, Coello Coello C A. A simple multimembered evolution strategy to solve constrained optimization problems [J].IEEETransactionsonEvolutionaryComputation, 2005,9(1):1-17.

[10] 張國(guó)亮. 動(dòng)態(tài)環(huán)境中移動(dòng)機(jī)器人路徑規(guī)劃研究綜述[J]. 機(jī)床與液壓, 2013,41(1):157-162.

ZHANG Guo-liang. Survey on path planning for mobile robot under dynamic environment [J].MachineTool&Hydraulics, 2013,41(1):157-162. (in Chinese)

[11] Bruce J, Veloso M. Real-time randomized path planning for robot navigation [C] //IEEEInternationalConferenceonIntelligentRobotsandSystems(IROS). Piscataway:IEEE, 2002:2383-2388.

[12] Ferguson D, Kalra N, Stentz A. Replanning with RRTs [C] //Proceedings2006IEEEInternationalConferenceonRoboticsandAutomation,ICRA2006. Piscataway:IEEE, 2006:1243-1248.

[13] Zucker M, Kuffner J, Branicky M. Multipartite RRTs for rapid replanning in dynamic environments [C] //2007IEEEInternationalConferenceonRoboticsandAutomation,ICRA′07. Piscataway:IEEE, 2007:1603-1609.

[14] FENG Lin, JIA Jing-hui. Improved algorithm of RRT path planning based on comparison optimization [J].ComputerEngineeringandApplications, 2011,47(3):210-213.

[15] Shi K, Denny J, Amato N M. Spark PRM:Using RRTs within PRMs to efficiently explore narrow passages [C] //2014IEEEInternationalConferenceonRoboticsandAutomation,ICRA2014. Piscataway:IEEE, 2014:4659-4666.

[16] Denny J, Morales M, Rodriguez S,etal. Adapting RRT growth for heterogeneous environments [C] //IEEEInternationalConferenceonIntelligentRobotsandSystems(IROS). Piscataway:IEEE, 2013:1-7.

[17] Lee J, Kwon O, ZHANG Liang-jun,etal. SR-RRT:Selective retraction-based RRT planner [C] //2012IEEEInternationalConferenceonRoboticsandAutomation,ICRA2012. Piscataway:IEEE, 2012:2543-2550.

[18] Karaman S, Frazzoli E. Sampling-based algorithms for optimal motion planning [J].InternationalJournalofRoboticsResearch, 2011,30(7):846-894.

[19] PAN Jia, ZHANG Liang-jun, Manocha D. Retraction-based RRT planner for articulated models [C] //2010IEEEInternationalConferenceonRoboticsandAutomation,ICRA2010. Piscataway:IEEE, 2010:2529-2536.

[20] Laumond J P, Sekhavat S, Lamiraux F.GuidelinesinNonholonomicMotionPlanningforMobileRobots[M]. Berlin:Springer Berlin Heidelberg, 1998.

[21] Kuffner J J Jr, LaValle S M. RRT-Connect:An efficient approach to single query path planning [J].Proceedings-IEEEInternationalConferenceonRoboticsandAutomation, 2000,2:995-1001.

AnimprovedpathplanningalgorithmbasedonRRT-ConCon

WANG Fan*1, FENG Nan1,2, HU Xiao-peng1

( 1.Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China；2.Troops 65066, The Chinese People′s Liberation Army, Dalian 116100, China )

Aiming at the lack of stability and slow convergence for RRT algorithm, based on RRT-ConCon algorithm and towards goal search strategy, an improved bidirectional search path planning algorithm is proposed. By changing the temporary extension target for two search paths, the algorithm not only can make the search path grow easily towards the direction of target, but also can improve the stability of the algorithm, at the same time can guarantee the planning path close to the optimal solution. The improved RRT-ConCon algorithm uses random node generating function to avoid the search path growing towards the target point falling into local minimum. Meanwhile, in order to test a variety of simulation experimental environments, a simulation experimental environment platform is designed, and experimental results demonstrate the effectiveness and stability of the proposed algorithm.

mobile robot; path planning; rapidly-exploring random trees (RRT); bidirectional rapidly-exploring random trees (Bi-RRT); RRT-ConCon algorithm

1000-8608(2014)06-0637-07

2014-03-07；

: 2014-06-12．

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272523).

王 凡*(1975-)，女，博士，碩士生導(dǎo)師，E-mail:wangfan@dlut.edu.cn； 馮 楠(1981-)，女，碩士生，E-mail:fengnanbangbang@163.com.

TP24

：Adoi:10.7511/dllgxb201406007