馬智煥, 胡立坤*, 陶興華, 劉月洋, 胡正南

(1.廣西大學(xué)電氣工程學(xué)院, 廣西南寧530004;2.南寧學(xué)院智能制造學(xué)院, 廣西南寧530299)

0 引言

近年來,芯片制造技術(shù)、自動(dòng)化控制技術(shù)的日臻成熟和人工智能概念的興起,機(jī)器人的功能越來越強(qiáng)大,使用場(chǎng)景也愈加多元化,同時(shí)路徑規(guī)劃是機(jī)器人領(lǐng)域內(nèi)至關(guān)重要的研究方向之一。路徑規(guī)劃的需求是在明確了始發(fā)地和目標(biāo)位置的情況下,同時(shí)滿足路徑長(zhǎng)度短、規(guī)劃效率高等條件,并且搜索到與障礙物無碰撞的可行解。

常用的規(guī)劃算法包括Dijkstra算法[1]、A*算法[2]、人工勢(shì)場(chǎng)算法(artificial potential field, APF)[3]、遺傳算法[4]、人工魚群算法[5]、蟻群算法[6]、概率路線圖算法[7]和快速搜索隨機(jī)樹(rapidly exploring random trees, RRT)算法等。其中Dijkstra算法的主要特點(diǎn)是由中心向四周搜索,直到擴(kuò)展到終點(diǎn)位置為止,由于算法遍歷節(jié)點(diǎn)多,因此容易消耗大量的時(shí)間。A*算法采用啟發(fā)式的搜索,提高了全局的搜索效率,卻難以滿足路徑最優(yōu)的要求;APF算法可以獲取平滑安全的路徑,但是容易陷入局部最優(yōu)的困境。遺傳算法可以有效的搜索整個(gè)地圖環(huán)境,但是實(shí)時(shí)性較差。人工魚群算法種群數(shù)與路徑質(zhì)量成反比。蟻群算法雖然可以找到最優(yōu)路徑,但是收斂速度慢,容易發(fā)生死鎖現(xiàn)象。概率路線圖算法路徑的好壞取決于空間事先設(shè)置的采樣點(diǎn),當(dāng)采樣數(shù)量不多或者分布不均勻時(shí),很難找到路徑。

文獻(xiàn)[8]提出了基于采樣的RRT算法,因?yàn)槠浣Y(jié)構(gòu)簡(jiǎn)單、路徑搜索效率高、擁有完整的概率完備性等特點(diǎn),所以被運(yùn)用在各類路徑規(guī)劃場(chǎng)景中,但是,RRT算法沒有考慮路徑節(jié)點(diǎn)的代價(jià),導(dǎo)致生成的路徑通常是曲折的,無法保證路徑最優(yōu)。RRT*算法[9]為新點(diǎn)在一定范圍之中尋找最佳的父節(jié)點(diǎn),同時(shí)將此范圍內(nèi)的路徑點(diǎn)與新點(diǎn)重新連接,從而使得算法在采樣點(diǎn)數(shù)量接近無窮大時(shí)可以找到最佳路徑,但無法在短時(shí)間內(nèi)找到最優(yōu)解。Informed-RRT*[10]通過將采樣點(diǎn)的生成范圍削減到一個(gè)超橢球狀態(tài)子集內(nèi)來提升算法求解路徑的效率,但在狹窄通道、迷宮等復(fù)雜環(huán)境中通過性較差。譚建豪等[11]將啟發(fā)式思想運(yùn)用到隨機(jī)采樣過程中,利用節(jié)點(diǎn)刪除策略對(duì)每一個(gè)路徑節(jié)點(diǎn)賦予相應(yīng)的權(quán)重,使得算法可以保留權(quán)重更大的路徑節(jié)點(diǎn),提高了算法的尋路性能。文獻(xiàn)[12]通過改變樹的生長(zhǎng)策略,利用三角不等式原理減少了路徑的長(zhǎng)度,同時(shí)在選擇最佳父節(jié)點(diǎn)時(shí)考慮相鄰節(jié)點(diǎn)的父節(jié)點(diǎn),從而提出了收斂速度更快的Quick-RRT*算法。文獻(xiàn)[13]提出一種基于三角不等式改變樹中已存在節(jié)點(diǎn)連接方式,并利用轉(zhuǎn)角約束增強(qiáng)路徑的平滑度的RRT-Connect算法,在縮短尋找路徑時(shí)間的同時(shí),還通過重新選擇祖節(jié)點(diǎn)減少路徑長(zhǎng)度。雖然RRT-Connect顯示出良好的搜索環(huán)境的能力,但與RRT算法相似,其路徑質(zhì)量并不穩(wěn)定,并且不能保證最佳。欒添添等[14]將地圖劃分四級(jí)采樣區(qū)域,并利用概率目標(biāo)偏置改變隨機(jī)點(diǎn)的生成方向,同時(shí)設(shè)置安全距離且利用轉(zhuǎn)角限制和B樣條曲線擬合平滑路徑。Liao等[15]提出了F-RRT*算法,通過創(chuàng)造一個(gè)新節(jié)點(diǎn)使得路徑質(zhì)量變得更優(yōu)。陳俠等[16]利用人工勢(shì)場(chǎng)算法削弱了RRT算法采樣時(shí)的隨機(jī)性,障礙物產(chǎn)生斥力,而終點(diǎn)產(chǎn)生引力,二者結(jié)合為隨機(jī)點(diǎn)提供擴(kuò)展方向;但是由于人工勢(shì)場(chǎng)算法計(jì)算量較大,而且容易陷入局部陷阱,因此可能使得采樣點(diǎn)陷入局部最優(yōu)。荊澤成等[17]在RRT算法中加入目標(biāo)偏置來加速算法搜索速度,但是對(duì)于復(fù)雜的環(huán)境目標(biāo)偏置反而有可能限制樹的生長(zhǎng)。

基于對(duì)傳統(tǒng)RRT采樣過程的分析,研究發(fā)現(xiàn)隨機(jī)采樣效率低,ε-DT-RRT利用ε-動(dòng)態(tài)三角采樣區(qū)域劃分采樣空間,通過限制采樣區(qū)域減少無效節(jié)點(diǎn)的數(shù)量和在無價(jià)值區(qū)域的重復(fù)采樣。除此之外,通過對(duì)RRT算法結(jié)果的觀察,雖然采樣點(diǎn)是在整個(gè)地圖空間隨機(jī)生成的;但是很難生成最優(yōu)路徑上的最佳節(jié)點(diǎn),因此采用創(chuàng)造過渡節(jié)點(diǎn)的方法解決了此問題。在此基礎(chǔ)上,通過遞歸回溯祖節(jié)點(diǎn)進(jìn)一步去除路徑中冗余點(diǎn),縮短路徑長(zhǎng)度。

1 傳統(tǒng)RRT算法

RRT算法把已知的初始狀態(tài)起點(diǎn)選取為隨機(jī)樹的源節(jié)點(diǎn),在定義的地圖中隨機(jī)產(chǎn)生一個(gè)采樣點(diǎn),根據(jù)采樣點(diǎn)生成一個(gè)新的子節(jié)點(diǎn),不斷重復(fù)此過程直至子節(jié)點(diǎn)到達(dá)終點(diǎn)時(shí)擴(kuò)展終止。最后采取不斷尋找節(jié)點(diǎn)的父節(jié)點(diǎn)的方式即可尋找到一條完整路徑?；A(chǔ)RRT算法主要步驟如下：

步驟1：初始化空間信息,生成隨機(jī)樹T。

步驟2：在空間中均勻采樣生成Xran,并搜索最近點(diǎn)Xnea。

步驟3：利用最近點(diǎn)和隨機(jī)點(diǎn),依據(jù)公式(1)合成Xnew。

步驟4：如果Xnew可以直接加入樹中進(jìn)行步驟5,反之返回步驟2。

步驟5：循環(huán)執(zhí)行以上步驟,直到找到完整路徑。

(1)

從以上步驟可以看出,RRT算法結(jié)構(gòu)簡(jiǎn)單,但是也面臨以下問題：首先,隨機(jī)點(diǎn)是在整個(gè)地圖空間上隨機(jī)均勻選取的,地圖環(huán)境越大,隨機(jī)采樣點(diǎn)的選擇性越多,生成無用路徑點(diǎn)的數(shù)量與概率也隨之增多,消耗了大量的算法時(shí)間;其次,當(dāng)Xnew與Xnea之間是直接連接,并沒有經(jīng)過優(yōu)化,導(dǎo)致算法生成的路徑曲折;最后,Xnew與Xnea之間存在障礙物時(shí),算法會(huì)舍棄Xnew,而二者之間往往會(huì)有最優(yōu)路徑點(diǎn),可能導(dǎo)致算法不能尋找到最優(yōu)路徑。

2 ε-DTSR-RRT算法設(shè)計(jì)

2.1 ε-動(dòng)態(tài)三角采樣區(qū)域

傳統(tǒng)RRT算法中,因?yàn)樵谡麄€(gè)地圖中隨機(jī)采樣生成Xran,所以會(huì)產(chǎn)生大量無用的采樣點(diǎn)。針對(duì)此類問題,提出動(dòng)態(tài)三角采樣區(qū)域的改進(jìn)措施。首先,在生成Xran前,在樹中尋找距離目標(biāo)點(diǎn)最近的節(jié)點(diǎn)1,根據(jù)新點(diǎn)1的坐標(biāo)將采樣區(qū)域分為已探索區(qū)域和未探索區(qū)域。已探索區(qū)域?yàn)榈貓D中小于新點(diǎn)1坐標(biāo)的區(qū)域,其余區(qū)域則記為未探索區(qū)域。其次,在未探索區(qū)域生成節(jié)點(diǎn)2,由于節(jié)點(diǎn)1和節(jié)點(diǎn)2是動(dòng)態(tài)變化的,故節(jié)點(diǎn)1、節(jié)點(diǎn)2和終點(diǎn)構(gòu)成的動(dòng)態(tài)三角采樣區(qū)域,如圖1所示。最后,引入強(qiáng)化學(xué)習(xí)中ε-greedy動(dòng)作選擇策略,隨機(jī)生成一個(gè)0～1的數(shù)記為rand,當(dāng)rand小于ε(小于1的正數(shù))時(shí),從整個(gè)地圖空間中隨機(jī)生成采樣點(diǎn);反之,則在三角區(qū)域中隨機(jī)生成采用點(diǎn),如公式(2)所示。

圖1 動(dòng)態(tài)三角采樣區(qū)域Fig.1 Dynamic triangular sampling region

(2)

2.2 創(chuàng)建過渡節(jié)點(diǎn)

針對(duì)RRT算法中,當(dāng)Xnea和Xnew之間存在障礙物時(shí),便會(huì)放棄Xnew,重新生成采樣點(diǎn)的問題,如圖2(a)所示,提出了創(chuàng)造過渡節(jié)點(diǎn)的方法。而在這種情況下,Xnew往往處于未探索區(qū)域中,為了加快對(duì)地圖空間的搜索,需要聯(lián)通最近點(diǎn)和新點(diǎn),同時(shí)將新點(diǎn)添加到路徑中。以Xnea和Xnew為對(duì)角頂點(diǎn)構(gòu)造矩形[18]。在矩形另外兩端點(diǎn)中任選一個(gè)處于可行區(qū)域中的點(diǎn)作為臨時(shí)過渡節(jié)點(diǎn)Xt,并利用二分法優(yōu)化調(diào)整Xt的位置,如圖 2(b)所示。當(dāng)優(yōu)化完成時(shí),進(jìn)一步利用三角不等式遞歸回溯Xt的無碰撞祖節(jié)點(diǎn)Xanc,并將Xanc作為Xt的父節(jié)點(diǎn)、Xt作為Xnew的父節(jié)點(diǎn)插入樹中,最終路徑如圖2(c)所示。由圖2可知,構(gòu)建的過渡節(jié)點(diǎn)Xt既保留了原算法中被舍棄的Xnew,又增加了算法獲取最佳路徑節(jié)點(diǎn)的機(jī)會(huì),并聯(lián)通了新的探索區(qū)域。

(a) 生成Xnew

2.3 遞歸回溯祖節(jié)點(diǎn)

針對(duì)RRT算法中頂點(diǎn)利用率低、局部最小值等情況,提出了遞歸回溯祖節(jié)點(diǎn)的方法優(yōu)化路徑。在Xnew作為可行路徑點(diǎn)被添加樹中之前,對(duì)最近點(diǎn)進(jìn)行祖節(jié)點(diǎn)溯源。通過循環(huán)溯源操作直至擇出可以與Xnew直接連接的路徑點(diǎn)記作Xanc,將其父節(jié)點(diǎn)記作Xp,如圖3(a)所示。由于新點(diǎn)和Xp之間存在障礙物,不可直接加入路徑,利用Xanc,Xnew和Xp建立一個(gè)連通路徑的過渡節(jié)點(diǎn)Xt。首先,在Xanc與新點(diǎn)之間搭建臨時(shí)點(diǎn);其次,在臨時(shí)點(diǎn)和Xp之間生成Xt,如圖3(b)所示。在此基礎(chǔ)上,為了進(jìn)一步刪除拐點(diǎn)數(shù)量和削減路徑代價(jià),繼續(xù)從樹中搜集Xt可以直接連接的路徑點(diǎn)Xtp,并加入樹中。由圖3(c)所示,經(jīng)過遞歸回溯祖節(jié)點(diǎn)之后的路徑質(zhì)量明顯優(yōu)于初始路徑。

(a) 回溯祖節(jié)點(diǎn)

2.4 改進(jìn)連接終點(diǎn)判別方式

傳統(tǒng)RRT算法找到路徑的標(biāo)準(zhǔn)是Xnew與終點(diǎn)的距離小于閾值條件即可,其局限在于不能保證新點(diǎn)是一直沿著終點(diǎn)方向拓展的,并且閾值大小也不好確定,可能會(huì)在重復(fù)的地點(diǎn)來回搜索,導(dǎo)致路徑出現(xiàn)震蕩。綜合起點(diǎn)與終點(diǎn)的長(zhǎng)度并乘以系數(shù),記作THR。如果新點(diǎn)與終點(diǎn)的距離小于THR,啟動(dòng)終點(diǎn)直連環(huán)節(jié),若能直接連接,說明算法已經(jīng)找到路徑。相對(duì)于在地圖中盲目拓展的時(shí)間而言,直接連接環(huán)節(jié)消耗的時(shí)間可以忽略。

2.5 ε-DTSR-RRT算法實(shí)現(xiàn)

ε-DT-RRT算法具體步驟如下：

步驟1：初始化地圖,設(shè)置起始點(diǎn)、目標(biāo)點(diǎn)、步長(zhǎng)等參數(shù)。

步驟2：動(dòng)態(tài)三角采樣區(qū)域中生成隨機(jī)點(diǎn)Xran,在已知樹中找到Xnea,并生成新點(diǎn)Xnew。

步驟3：判斷Xnea和Xnew之間是否有障礙物。如果有跳至步驟7,否則進(jìn)行步驟4。

步驟4：尋找Xnea祖節(jié)點(diǎn)中與Xnew沒有碰撞的節(jié)點(diǎn)Xanc、Xanc父節(jié)點(diǎn)Xp。

步驟5：基于Xp和Xnew之間創(chuàng)造過渡節(jié)點(diǎn)Xt,利用二分法優(yōu)化Xt。

步驟6：尋找Xp祖節(jié)點(diǎn)中可以直接與Xt相連的路徑點(diǎn)Xtp,將相關(guān)節(jié)點(diǎn)插入樹中。

步驟7：如果可以建立過渡節(jié)點(diǎn)Xt進(jìn)行下一步,不能跳至步驟2。

步驟8：利用二分法在障礙物邊緣生成Xt,并在樹中尋找可以直接與Xt相連的路徑點(diǎn),并插入樹中。

步驟9：判斷Xnew與目標(biāo)點(diǎn)之間的距離是否大于設(shè)置閾值,若大于則返回步驟2,否則,結(jié)束程序并輸出路徑。

3 仿真與驗(yàn)證

為了驗(yàn)證ε-DT-RRT算法路徑規(guī)劃效果,利用MATLAB軟件仿真對(duì)比原算法和RRT類相關(guān)算法中所得路徑的指標(biāo)。算法的運(yùn)行環(huán)境配置為筆記本電腦,操作系統(tǒng)版本為Windows 10 64位;CPU為i5;主頻為2.5 GHz。RRT算法得到的路徑都存在或多或少的差異,這是因?yàn)槠渚哂泻軓?qiáng)的不確定性。為了減少算法的不確定性帶來的實(shí)驗(yàn)誤差,在不同的空間中運(yùn)行RRT、Bias-RRT、RRT*、ε-DT-RRT算法各50次,整理實(shí)驗(yàn)結(jié)果對(duì)比分析。

3.1 地圖1的仿真驗(yàn)證

地圖1設(shè)定為的狹窄環(huán)境地圖(180×180),用于驗(yàn)證算法狹窄環(huán)境下的路徑指標(biāo)。設(shè)置左上角為坐標(biāo)原點(diǎn),起始點(diǎn)坐標(biāo)為[10,10],目標(biāo)點(diǎn)坐標(biāo)為[180,180]。選取RRT、Bias-RRT、RRT*、ε-DT-RRT算法最優(yōu)路徑規(guī)劃結(jié)果如圖4所示。虛線為迭代過程,實(shí)線段為最終路徑。為了更直觀地對(duì)比,將50次實(shí)驗(yàn)所得4種算法數(shù)據(jù)列于表1。

表1 地圖1的4種算法數(shù)據(jù)對(duì)比Tab.1 Four algorithm data comparison in Map 1

(a) RRT算法

從表1可以得到,ε-DT-RRT算法在狹窄通道中的采樣次數(shù)相較于RRT算法、Bias-RRT算法分別由原來的1 062.82、1 735.06縮減到225.80,分別減少了78.75%、86.99%。路徑長(zhǎng)度參數(shù)雖然與RRT*算法相差不大,但是在時(shí)間消耗和拐點(diǎn)數(shù)量方面各自減少了96.23%和58.00%?？梢钥闯鲈诘貓D1環(huán)境下,改進(jìn)算法性能均優(yōu)于對(duì)比算法。

結(jié)合表1數(shù)據(jù)和路徑規(guī)劃結(jié)果,改進(jìn)算法在快速尋找到最優(yōu)路徑有一定的優(yōu)勢(shì),這是因?yàn)樗崴惴ㄊ褂昧甩?動(dòng)態(tài)三角采樣區(qū)域一方面限制了采樣點(diǎn)的隨機(jī)性,另一方面指出了最優(yōu)路徑點(diǎn)可能存在范圍,減少了生成低價(jià)值節(jié)點(diǎn)的時(shí)間,進(jìn)而提升了算法的效率。

3.2 地圖2的仿真驗(yàn)證

地圖2設(shè)置為局部陷阱環(huán)境(500×500),用于驗(yàn)證算法跳出局部陷阱環(huán)境的能力。設(shè)置左上角為坐標(biāo)原點(diǎn),起始點(diǎn)坐標(biāo)為[10,10],目標(biāo)點(diǎn)坐標(biāo)為[500,500]。選取RRT、Bias-RRT、RRT*、ε-DT-RRT算法最優(yōu)路徑規(guī)劃結(jié)果如圖5所示。虛線為迭代過程,實(shí)線段為最終路徑。為了更直觀地對(duì)比,將50次實(shí)驗(yàn)所得4種算法數(shù)據(jù)于表2。

表2 地圖2的4種算法數(shù)據(jù)對(duì)比Tab.2 Four algorithm data comparison in Map 2

從表2可以看出,ε-DT-RRT算法采取動(dòng)態(tài)三角區(qū)域采樣的方式加快了算法的尋路速度,原算法需要3.14 s才能找到路徑,而相對(duì)較快的Bias-RRT也需要2.09 s,但改進(jìn)算法僅需要1.76 s,分別提升了43.95%和15.89%。同時(shí)從迭代次數(shù)中也可以觀察到ε-DT-RRT算法的有效性,相較對(duì)比算法分別減少了51.21%、66.21%、60.46%,而迭代次數(shù)越少,也說明算法效率越高。

地圖2的作用是驗(yàn)證算法逃離陷阱的能力,由圖5可以看出,RRT算法、Bias-RRT算法、RRT*算法在面對(duì)地圖左上角半包圍型障礙物時(shí)均有不同程度地陷入其中,導(dǎo)致生成大量的冗余節(jié)點(diǎn),消耗了算法的大量時(shí)間,而改進(jìn)算法利用動(dòng)態(tài)區(qū)域采樣迅速逃離局部陷阱,提升了算法的效率。從圖5(d)中,可以看出改進(jìn)算法所得路徑長(zhǎng)度短,這是由于在隨機(jī)樹擴(kuò)展的過程中和遞歸回溯祖節(jié)點(diǎn)生成了過渡節(jié)點(diǎn),而過渡節(jié)點(diǎn)則有極大的概率是最優(yōu)路徑上的節(jié)點(diǎn)。

3.3 地圖3的仿真驗(yàn)證

將地圖3設(shè)定為復(fù)雜環(huán)境地圖(500×500),除地圖環(huán)境設(shè)置以外,其余設(shè)置同上,4種算法路徑對(duì)比如圖6所示。虛線為迭代過程,實(shí)線段為最終路徑,將50次實(shí)驗(yàn)所得4種算法數(shù)據(jù)列于表3。

表3 地圖3的4種算法數(shù)據(jù)對(duì)比Tab.3 Four algorithm data comparison in Map 3

(a) RRT算法

從表3可知,ε-DT-RRT算法有效地剔除了冗余節(jié)點(diǎn),相較于RRT算法、Bias-RRT算法及RRT*算法分別減少了72.29%、71.01%、65.70%,同時(shí)迭代次數(shù)也收縮了64.91%、77.48%、70.62%。最佳路徑代價(jià)和平均路徑代價(jià)分別為841.96、888.84 m,比原算法減少了16.76%和26.27%。搜索時(shí)間也由原來的2.19 s縮短到1.35 s,減少了38.36%。

地圖3為復(fù)雜環(huán)境,其中設(shè)計(jì)了狹窄通道,局部陷阱等復(fù)雜地形。由表3可知,改進(jìn)算法在復(fù)雜地形環(huán)境平均僅用了440次迭代就達(dá)到了遠(yuǎn)低于具有最優(yōu)性的RRT*算法1 500次迭代的效果。這是因?yàn)?ε-動(dòng)態(tài)三角采樣區(qū)域結(jié)合將地圖劃分為最優(yōu)區(qū)域和次優(yōu)區(qū)域,最優(yōu)區(qū)域中的點(diǎn)往往是最優(yōu)節(jié)點(diǎn),可以快速通過狹窄通道和逃離局部陷阱。從圖6中算法的路徑對(duì)比可以看出,改進(jìn)算法通過在障礙物附近創(chuàng)造過渡節(jié)點(diǎn),通過連接過渡節(jié)點(diǎn)避開障礙物,使得路徑更短;進(jìn)一步利用遞歸回溯祖節(jié)點(diǎn)的方式,去除路徑上的冗余節(jié)點(diǎn),減少了路徑上的轉(zhuǎn)折點(diǎn),從而得到平直的路徑,進(jìn)一步減少移動(dòng)機(jī)器人轉(zhuǎn)彎時(shí)的能耗。

通過在不同地圖上測(cè)試分析,ε-DT-RRT算法在所選取的路徑指標(biāo)中均優(yōu)于基礎(chǔ)RRT、Bias-RRT、和RRT*。在相同的地圖環(huán)境中,改進(jìn)算法能夠生成更為簡(jiǎn)潔的規(guī)劃軌跡,路徑搜索時(shí)間更短,路徑迭代效率更高,路徑規(guī)劃效果更為顯著。

3.4 算法的概率完備性

諸多學(xué)者已經(jīng)論證過RRT算法是概率完備的,即在任意存在路徑的地圖中,只要RRT算法迭代的次數(shù)足夠多,Xnew總會(huì)進(jìn)入到終點(diǎn)目標(biāo)范圍內(nèi),即找到一條無碰撞的路徑。所提算法在傳統(tǒng)RRT算法上改進(jìn),提出ε-動(dòng)態(tài)三角采樣區(qū)域來限制采樣點(diǎn)的區(qū)域,利用過渡節(jié)點(diǎn)創(chuàng)造無障礙路徑,采用遞歸回溯的方式消除路徑的轉(zhuǎn)折點(diǎn),使得算法可以更快地找到路徑。改進(jìn)算法以ε的概率探索未知的區(qū)域,1-ε的概率探索最優(yōu)區(qū)域,在采樣點(diǎn)足夠多的情況下,采樣點(diǎn)可以遍歷整個(gè)地圖,故ε-DTSR-RRT算法依舊是概率完備的。

4 結(jié)論

為了解決傳統(tǒng)RRT在路徑規(guī)劃存在的問題,提出了一種ε-DT-RRT算法,通過理論分析和實(shí)驗(yàn)仿真,得出以下結(jié)論：

①通過ε-動(dòng)態(tài)三角區(qū)域劃分地圖采樣空間,限制隨機(jī)采樣點(diǎn)的生成位置,從而減少次優(yōu)區(qū)域的搜索次數(shù)和無效節(jié)點(diǎn)的數(shù)量,提升了采樣效率,同時(shí)兼顧了采樣點(diǎn)的全局性和最優(yōu)性,加快了算法的收斂速度。

②針對(duì)傳統(tǒng)RRT算法在Xnea和Xnew之間存在障礙物時(shí)舍棄Xnew的問題,提出了創(chuàng)造過渡節(jié)點(diǎn)的方法。過渡節(jié)點(diǎn)通常是最優(yōu)路徑上的節(jié)點(diǎn),能夠靠近障礙物并保持安全的距離,提升了獲取最優(yōu)路徑節(jié)點(diǎn)的概率,有效地縮短了路徑長(zhǎng)度。

③運(yùn)用遞歸回溯祖節(jié)點(diǎn)的方法,通過連接新點(diǎn)和祖節(jié)點(diǎn)達(dá)到縮短路徑長(zhǎng)度和減少冗余點(diǎn)的效果。在此基礎(chǔ)上,為無碰撞祖節(jié)點(diǎn)的父節(jié)點(diǎn)和新點(diǎn)之間創(chuàng)造過渡節(jié)點(diǎn),能夠進(jìn)一步改善路徑質(zhì)量。

從上述的仿真實(shí)驗(yàn)結(jié)果來看,在3種不同的地圖中,相比于RRT算法、Bias-RRT算法及RRT*算法,改進(jìn)算法減少了路徑中節(jié)點(diǎn)的數(shù)量,優(yōu)化了路徑的長(zhǎng)度,得到了更短的路徑;同時(shí)減少了迭代次數(shù),縮短搜索的時(shí)間。通過上述的數(shù)據(jù)對(duì)比可以看出,ε-DT-RRT算法極大地提高了算法搜索路徑的速度、質(zhì)量和效率,證明了其在路徑規(guī)劃方面具有很強(qiáng)的優(yōu)越性。