改進(jìn)RRT*的室內(nèi)機(jī)器人路徑規(guī)劃算法

楊 也,倪建軍,陳一楠,陳 顏

(河海大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 常州 213022)

0 引言

在過去的幾十年中，室內(nèi)機(jī)器人已經(jīng)越發(fā)的和人類生活息息相關(guān)[1]。它們?cè)诟鞣N企業(yè)、家庭中都日益占著較大的比重且有著不同的任務(wù)，例如目標(biāo)的探測(cè)、移物、清潔等。若想要完成這些任務(wù)，首先需要考慮的是如何成功到達(dá)目標(biāo)節(jié)點(diǎn)，這也是室內(nèi)機(jī)器人路徑規(guī)劃的核心問題[2]。它是確保室內(nèi)機(jī)器人可以充分利用先驗(yàn)信息，同時(shí)安全有效地完成任務(wù)的基礎(chǔ)。為了保證移動(dòng)機(jī)器人正確執(zhí)行各種任務(wù)，高效且實(shí)用的路徑規(guī)劃算法研究十分必要。

在室內(nèi)機(jī)器人的應(yīng)用領(lǐng)域，通常避障包含于路徑規(guī)劃問題。最佳路徑是起始點(diǎn)和目標(biāo)點(diǎn)之間的合理路徑[3-4]。為了獲得合理的路徑，算法需要考慮多方面因素。考慮多方面因素的目的是找到一種平衡各方因素的方法，這也是優(yōu)化算法可以實(shí)現(xiàn)的。優(yōu)化算法不僅可以確保任務(wù)的高效完成，還可以確保消耗的成本盡可能的少。因此，路徑規(guī)劃問題也可以轉(zhuǎn)化為具有約束條件的數(shù)學(xué)優(yōu)化問題。在這些優(yōu)化問題中，一些具有啟發(fā)式的算法，如RRT*算法，啟發(fā)式A*搜索法，PRM算法等，往往起著至關(guān)重要的作用。這些算法在一些較為簡(jiǎn)單的環(huán)境下都能較好的完成路徑規(guī)劃且結(jié)果都是比較優(yōu)良的路徑，但在復(fù)雜環(huán)境情況下，算法的收斂速度都急劇變差，更不說能否找尋到高質(zhì)量的路徑。

在上述算法中，很多路徑規(guī)劃算法如柵格法，可視圖法，A*，D*等算法雖然有各自的優(yōu)勢(shì)，但是難以考慮移動(dòng)機(jī)器人非完整約束限制?？焖匐S機(jī)搜索樹算法可以有效地考慮到移動(dòng)機(jī)器人的非完整約束限制并且可以有效的搜索整個(gè)解空間，從而快速得到路徑。RRT*算法是主要算法之一，也是完成度較高的一種算法。其作為一種基于RRT算法改進(jìn)的算法，RRT*算法保證了計(jì)算復(fù)雜度和漸進(jìn)最優(yōu)解，但RRT*的缺點(diǎn)任然很明顯：在快速找出初始路徑后，伴隨著采樣點(diǎn)的不斷增加，算法需要不停地進(jìn)行優(yōu)化，需要花費(fèi)大量的時(shí)間在算法收斂上。因此，它的算法收斂時(shí)間任然是一個(gè)較為突出的研究點(diǎn)，仍有優(yōu)化的空間。

為了在一定程度上克服此缺點(diǎn)，優(yōu)化該算法。本文算法替換了原算法的隨機(jī)采樣，使采樣點(diǎn)具有目的性，緊接著引進(jìn)人工勢(shì)場(chǎng)思想以及避障策略相結(jié)合引導(dǎo)隨機(jī)樹快速擴(kuò)展和生長(zhǎng)方向，同時(shí)我們采用曼哈頓距離代替歐幾里得距離作為代價(jià)估值函數(shù)。通過仿真實(shí)驗(yàn)進(jìn)行驗(yàn)證，本文算法比原算法擁有著更小的時(shí)間代價(jià)和更高的路徑質(zhì)量。

1 傳統(tǒng)RRT*算法

RRT*算法是MIT的Sertac和Emilio在2010年提出的一種基于隨機(jī)采樣漸進(jìn)最優(yōu)的快速路徑規(guī)劃方法，其也是RRT(快速擴(kuò)展隨機(jī)樹)算法的改進(jìn)版[5-7]。盡管RRT算法是一個(gè)相對(duì)高效率，同時(shí)可以較好的處理帶有非完整約束的路徑規(guī)劃問題的算法，并且在很多方面有很大的優(yōu)勢(shì)，但是RRT算法并不能保證所得出的可行路徑是相對(duì)優(yōu)化的。因此許多關(guān)于RRT算法的改進(jìn)也致力于解決路徑優(yōu)化的問題，RRT*算法就是其中一個(gè)。RRT*算法的主要特征是能快速的找出初始路徑，之后隨著采樣點(diǎn)的增加，不斷地進(jìn)行優(yōu)化直到找到目標(biāo)點(diǎn)或者達(dá)到設(shè)定的最大循環(huán)次數(shù)。RRT*算法是漸進(jìn)最優(yōu)化的，也就是隨著迭代次數(shù)的增加，得出的路徑是越來越優(yōu)化的，而且永遠(yuǎn)不可能在有限的時(shí)間中得出最優(yōu)的路徑。而RRT*算法與RRT算法相比貢獻(xiàn)主要在于新節(jié)點(diǎn)的父節(jié)點(diǎn)重選過程以及對(duì)新節(jié)點(diǎn)領(lǐng)域內(nèi)節(jié)點(diǎn)重布線隨機(jī)樹的過程。

RRT*的主要思想是通過隨機(jī)采樣生成一個(gè)隨機(jī)擴(kuò)展樹，在新產(chǎn)生的節(jié)點(diǎn)nnew附近以規(guī)定的范圍內(nèi)尋找“鄰居”，這些“鄰居”作為替換nnew的候選節(jié)點(diǎn)。依次計(jì)算候選節(jié)點(diǎn)到起點(diǎn)的路徑代價(jià)，同時(shí)加上nnew到每個(gè)候選節(jié)點(diǎn)的路徑代價(jià)。選出候選節(jié)點(diǎn)中作為nnew父節(jié)點(diǎn)后，路徑代價(jià)相對(duì)最小的節(jié)點(diǎn)，更換nnew的父節(jié)點(diǎn)。

重選父節(jié)點(diǎn)的具體步驟如下文所示，如下圖1(a)、(b)所示，分別為新節(jié)點(diǎn)c重選父節(jié)點(diǎn)和新節(jié)點(diǎn)鄰域內(nèi)節(jié)點(diǎn){a,b,e}重布線過程，其中ninit為起始起點(diǎn)，nnear為距離隨機(jī)點(diǎn)最近的隨機(jī)樹節(jié)點(diǎn)。計(jì)算新節(jié)點(diǎn)c的原來路徑代價(jià)，即新節(jié)點(diǎn)c通過節(jié)點(diǎn)d再到初始節(jié)點(diǎn)的路徑代價(jià)，由圖1(a)可以得到原來路徑代價(jià)為14。再分別計(jì)算c節(jié)點(diǎn)以鄰域內(nèi)其它節(jié)點(diǎn)a,b,e為父節(jié)點(diǎn)到初始節(jié)點(diǎn)的路徑，由圖1(a)回溯法可以計(jì)算出c節(jié)點(diǎn)通過a節(jié)點(diǎn)再到達(dá)初始節(jié)點(diǎn)的路徑代價(jià)為11；c節(jié)點(diǎn)通過b節(jié)點(diǎn)回溯到初始節(jié)點(diǎn)的路徑代價(jià)為12；c節(jié)點(diǎn)通過e節(jié)點(diǎn)再回溯到初始節(jié)點(diǎn)的路徑代價(jià)為16。所以新節(jié)點(diǎn)c將和d節(jié)點(diǎn)斷開連接并以a節(jié)點(diǎn)為新的父節(jié)點(diǎn)進(jìn)行連接。新節(jié)點(diǎn)c重選父節(jié)點(diǎn)后的連接圖如圖1(b)所示。每當(dāng)生成新節(jié)點(diǎn)后，通過重選父節(jié)點(diǎn)，是否能使得某些節(jié)點(diǎn)的路徑代價(jià)變小，其意義便是減小路徑代價(jià)。

圖1 nnew節(jié)點(diǎn)重選父節(jié)點(diǎn)過程

在nnew節(jié)點(diǎn)更換新的父節(jié)點(diǎn)后，為進(jìn)一步使得隨機(jī)樹節(jié)點(diǎn)之間的代價(jià)小，需要為隨機(jī)樹重新布線。即若nnew節(jié)點(diǎn)附近的“鄰居”節(jié)點(diǎn)以新節(jié)點(diǎn)為父節(jié)點(diǎn)可以減小路徑代價(jià)，則進(jìn)行重布線。重布線過程如下圖2(a)、(b)所示。

圖2 nnew節(jié)點(diǎn)附近重布線過程

如圖2(a)中所示，c節(jié)點(diǎn)為新節(jié)點(diǎn)，{d,e,b}為新節(jié)點(diǎn)c鄰域內(nèi)節(jié)點(diǎn)。初始節(jié)點(diǎn)到達(dá)d節(jié)點(diǎn)的路徑代價(jià)為10；初始節(jié)點(diǎn)到達(dá)b節(jié)點(diǎn)的路徑代價(jià)為9；初始節(jié)點(diǎn)到達(dá)e節(jié)點(diǎn)的路徑代價(jià)為15。分別計(jì)算d，e，b節(jié)點(diǎn)以c節(jié)點(diǎn)為父節(jié)點(diǎn)后的路徑代價(jià)，d節(jié)點(diǎn)通過c節(jié)點(diǎn)回溯到初始節(jié)點(diǎn)的路徑代價(jià)為15；b節(jié)點(diǎn)通過c節(jié)點(diǎn)回溯到初始節(jié)點(diǎn)的路徑代價(jià)為14；e節(jié)點(diǎn)通過c節(jié)點(diǎn)回溯到初始節(jié)點(diǎn)的路徑代價(jià)為12。通過上述計(jì)算可知存在e節(jié)點(diǎn)以c節(jié)點(diǎn)為父節(jié)點(diǎn)可以減小路徑代價(jià)，對(duì)e節(jié)點(diǎn)進(jìn)行重布線。重布線結(jié)果如圖2(b)所示。

重新選則父節(jié)點(diǎn)作用是使新生成的節(jié)點(diǎn)路徑代價(jià)盡可能的小，重布線是使生成新節(jié)點(diǎn)后減少隨機(jī)樹的冗余分支，減小搜索路徑代價(jià)。如果以整體的眼光看，并不是每一個(gè)重新布線的節(jié)點(diǎn)都會(huì)出現(xiàn)在最終生成的路徑中，但在生成隨機(jī)樹的過程中，每一次的重布線都盡可能的為最終路徑代價(jià)減小創(chuàng)造機(jī)會(huì)。

2 改進(jìn)RRT*算法

雖然RRT*漸進(jìn)最優(yōu)且?guī)в袉l(fā)式搜索，但該算法在收斂時(shí)間上仍然代價(jià)較大[8]。針對(duì)這一突出問題，本文改變了原算法中的隨機(jī)采樣方法，并將人工勢(shì)場(chǎng)思想和避障且不影響隨機(jī)樹擴(kuò)展的策略相結(jié)合，使隨機(jī)樹擴(kuò)展速度加快且具有方向性，減少算法收斂時(shí)間。

2.1 采樣點(diǎn)的選取

RRT*中采樣點(diǎn)的生成一般依賴于隨機(jī)高斯采樣，仍然具有很大的隨機(jī)性，這也是該算法可以優(yōu)化的一點(diǎn)。本文算法將更具目的性的選取采樣點(diǎn)。因?yàn)樵诘貓D中，起始點(diǎn)和目標(biāo)點(diǎn)都屬于先驗(yàn)知識(shí)[9]。因此在此基礎(chǔ)上，本文算法直接定義起始點(diǎn)和目標(biāo)點(diǎn)的中間點(diǎn)為我們所需要的臨時(shí)隨機(jī)點(diǎn)。緊接著需要判斷該臨時(shí)節(jié)點(diǎn)處是否恰好存在障礙物，即碰撞檢測(cè)。若不存在障礙物，則該臨時(shí)隨機(jī)點(diǎn)就設(shè)為隨機(jī)點(diǎn)nrand。若存在障礙物，則需要重新選取采樣點(diǎn)。通過上述臨時(shí)采樣點(diǎn)做垂直于起點(diǎn)和終點(diǎn)連接線的直線L，在直線上兩端分別取距離上述臨時(shí)點(diǎn)為m*s的點(diǎn)為新的采樣點(diǎn)，其中s為步長(zhǎng)，m為整數(shù)(超出障礙物的最小整數(shù))，如圖3所示。

圖3 采樣點(diǎn)的選取

采樣點(diǎn)選取的具體策略為，起始點(diǎn)坐標(biāo)為(xinit,yinit)，終點(diǎn)坐標(biāo)為(xgoal,ygoal)，垂直于起點(diǎn)和終點(diǎn)連線的直線L公式為：

(1)

本文算法中新的采樣點(diǎn)的選取比原算法更具有目標(biāo)性，也多了約束性，可以更容易的確定隨機(jī)點(diǎn)，減少了算法的隨機(jī)性，同時(shí)也加快了算法的收斂。

2.2 新節(jié)點(diǎn)的生成

人工勢(shì)場(chǎng)算法的基本思想是，移動(dòng)機(jī)器人在虛擬的環(huán)境力場(chǎng)中朝著目標(biāo)運(yùn)動(dòng)[10]。目標(biāo)點(diǎn)對(duì)移動(dòng)機(jī)器人有著吸引力的作用，而障礙物對(duì)其有著排斥力作用，在二者的合力作用下使機(jī)器人向著目標(biāo)點(diǎn)方向移動(dòng)[11]。

本文算法將人工勢(shì)場(chǎng)與避障策略的思想融入新節(jié)點(diǎn)的生成策略，引導(dǎo)隨機(jī)樹往目標(biāo)點(diǎn)方向擴(kuò)展[12]。以此來減少RRT*算法隨機(jī)樹擴(kuò)展、搜索的隨機(jī)性，減少不必要的冗余計(jì)算和路徑規(guī)劃所需要的時(shí)間代價(jià)。

當(dāng)采樣點(diǎn)為起始點(diǎn)和目標(biāo)點(diǎn)中點(diǎn)時(shí)，即所取采樣點(diǎn)處不存在障礙物，隨機(jī)樹直接往采樣點(diǎn)方向以步長(zhǎng)s擴(kuò)展；當(dāng)采樣點(diǎn)不在起始點(diǎn)與目標(biāo)點(diǎn)的中點(diǎn)時(shí)，引入目標(biāo)點(diǎn)具有吸引力的思想后，隨機(jī)樹的生長(zhǎng)方向?qū)⒉辉賰H僅由隨機(jī)點(diǎn)決定，而是由最近隨機(jī)樹節(jié)點(diǎn)nnear到目標(biāo)點(diǎn)的方向以及其到隨機(jī)點(diǎn)方向共同決定，以此來引導(dǎo)隨機(jī)樹往目標(biāo)點(diǎn)擴(kuò)展。如圖4所示，其中nrand為隨機(jī)點(diǎn)，ngoal為目標(biāo)點(diǎn)，s為隨機(jī)樹擴(kuò)展步長(zhǎng)，g是大于零的引力系數(shù)，nnew為目標(biāo)點(diǎn)和隨機(jī)點(diǎn)共同作用下生成的新節(jié)點(diǎn)。新節(jié)點(diǎn)明顯具有向目標(biāo)點(diǎn)靠近的偏向性。

圖4 帶目標(biāo)引力的新節(jié)點(diǎn)生長(zhǎng)

若隨機(jī)點(diǎn)nrand為起始點(diǎn)ninit與目標(biāo)點(diǎn)ngoal連線的中點(diǎn)，即采樣點(diǎn)所處位置不存在障礙物，則新節(jié)點(diǎn)nnew節(jié)點(diǎn)的坐標(biāo)公式僅由隨機(jī)點(diǎn)確定，其沿隨機(jī)點(diǎn)方向分布的新節(jié)點(diǎn)公式如下所示：

(2)

若隨機(jī)點(diǎn)nrand不在起始點(diǎn)ninit與目標(biāo)點(diǎn)ngoal的連線上，對(duì)于本文算法引入目標(biāo)點(diǎn)對(duì)新節(jié)點(diǎn)引力作用后，可以得到新節(jié)點(diǎn)的公式如下所示：

(3)

由上述圖4和式(3)能看出快速擴(kuò)展隨機(jī)樹的生長(zhǎng)具有著一定的方向性，從而加快隨機(jī)樹的生長(zhǎng)與搜索。

緊接著再將避障策略融入新節(jié)點(diǎn)的生成中。在原算法中，將隨機(jī)點(diǎn)nnear與新節(jié)點(diǎn)nnew的連線進(jìn)行碰撞檢測(cè)。若不能規(guī)避障礙物，則進(jìn)行重新選擇新的隨機(jī)點(diǎn)，再進(jìn)行新的節(jié)點(diǎn)生成；若可以成功規(guī)避障礙物，則隨機(jī)樹進(jìn)行擴(kuò)展。這就導(dǎo)致隨機(jī)樹的新節(jié)點(diǎn)和隨機(jī)樹的擴(kuò)展速度緩慢。本文算法對(duì)原算法新節(jié)點(diǎn)的選取的加入了避障策略，如圖5所示，其中s為步長(zhǎng)。

圖5 新節(jié)點(diǎn)的生成與避障策略

當(dāng)新節(jié)點(diǎn)nnew與最鄰近節(jié)點(diǎn)nnear的連線與障礙物進(jìn)行碰撞檢測(cè)后，若檢測(cè)結(jié)果為不存在障礙物，直接按照文章上述方法，將最近鄰節(jié)點(diǎn)nnear作為新節(jié)點(diǎn)nnew的父節(jié)點(diǎn)直接進(jìn)行隨機(jī)樹擴(kuò)展；若檢測(cè)結(jié)果為存在障礙物，則做以臨時(shí)新節(jié)點(diǎn)nnew為圓心，h*s為半徑的半圓(h為順利通過碰撞檢測(cè)的最小正整數(shù))，并且半圓的直徑垂直于最近鄰節(jié)點(diǎn)與臨時(shí)新節(jié)點(diǎn)的連線。將半圓平均劃分為6等份，分別選取圓周上五個(gè)采樣點(diǎn)nnew 1、nnew 2、nnew 3、nnew 4、nnew 5作為候選新節(jié)點(diǎn)。分別將這五個(gè)候選新節(jié)點(diǎn)與最近鄰節(jié)點(diǎn)nnear的連線與障礙物進(jìn)行碰撞檢測(cè)，選取候選新節(jié)點(diǎn)中無碰撞且最靠近最近鄰節(jié)點(diǎn)nnear的采樣點(diǎn)為新的新節(jié)點(diǎn)nnew。 若這五個(gè)候選新節(jié)點(diǎn)在與障礙物進(jìn)行碰撞檢測(cè)后，任然處于會(huì)碰撞狀態(tài)，則將初始值為1的h自動(dòng)加1，直到這五個(gè)候選節(jié)點(diǎn)中出現(xiàn)可以順利通過碰撞檢測(cè)的節(jié)點(diǎn)，此時(shí)將該候選新節(jié)點(diǎn)設(shè)置為新的新節(jié)點(diǎn)nnew。緊接著便按照原算法中的方法將最近鄰節(jié)點(diǎn)作為新節(jié)點(diǎn)的父節(jié)點(diǎn)進(jìn)行隨機(jī)樹擴(kuò)展。

此后，新節(jié)點(diǎn)的選取就按上述方法進(jìn)行，比原算法中先返回重選隨機(jī)點(diǎn)階段再選取新節(jié)點(diǎn)要更加的快速性。

2.3 改進(jìn)估價(jià)函數(shù)

RRT*算法中將啟發(fā)式函數(shù)用作估值函數(shù)減少不必要的采樣。本文算法在這將曼哈頓距離代替歐氏距離作為代價(jià)函數(shù)。由式(4)、(5)分別可知點(diǎn)p(x1,y1)與點(diǎn)q(x2,y2)歐氏距離表示該兩點(diǎn)之間的直線距離，曼哈頓距離表示該兩點(diǎn)橫縱坐標(biāo)之差絕對(duì)值的和，由公式的計(jì)算方法即可看出曼哈頓距離在計(jì)算方便方面比歐式距離更加出眾，也可以避免浮點(diǎn)運(yùn)算，從而加快運(yùn)算速度。

(4)

dis=|x1-x2|+|y1-y2|

(5)

將上述2.1節(jié)、2.2節(jié)、2.3節(jié)的改進(jìn)方法帶到RRT*算法中，具體凡人算法步驟如下所示：

1)初始化起點(diǎn)、終點(diǎn)以及障礙物。

2)按本文算法中采樣點(diǎn)選取方法選取采樣點(diǎn)nrand。

3)找到距離采樣點(diǎn)最近的節(jié)點(diǎn)nnear。

4)按文中2.2節(jié)中節(jié)點(diǎn)生成的方法生成新節(jié)點(diǎn)nnew。

5)通過最小路徑代價(jià)判斷新節(jié)點(diǎn)是否需要重選父節(jié)點(diǎn)(規(guī)定范圍內(nèi))。

6)同理，通過最小路徑代價(jià)判斷，新節(jié)點(diǎn)鄰域內(nèi)的“鄰居”節(jié)點(diǎn)是否需要重布線。

7)判斷新節(jié)點(diǎn)與目標(biāo)點(diǎn)之間的距離是否小于步長(zhǎng)s。是，路徑規(guī)劃到此結(jié)束；否，重新回到步驟2)。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文算法對(duì)RRT*改進(jìn)的有效性，本文仿真實(shí)驗(yàn)在Windows10環(huán)境中使用8G RAM和i7-7700HQ 2.80 GHz CPU 64位操作系統(tǒng)的筆記本電腦上進(jìn)行了實(shí)驗(yàn)。文中算法采用MATLAB編程實(shí)現(xiàn)。

3.1 仿真結(jié)果圖分析

為了驗(yàn)證本文對(duì)算法的改進(jìn)是否有著較為直觀的體現(xiàn)。本文以簡(jiǎn)單環(huán)境和復(fù)雜環(huán)境兩種布局結(jié)構(gòu)作為仿真地圖，方形區(qū)域?yàn)闄C(jī)器人不可行走的障礙物區(qū)域，空白區(qū)域?yàn)闄C(jī)器人的可行區(qū)域。由圖6的(a)圖、(b)圖可以明顯的看出，在較為簡(jiǎn)單的環(huán)境背景下，本文算法顯然比原算法在冗余樹枝方面明顯減少，且樹枝具有一定的方向擴(kuò)展性；而且從路徑質(zhì)量上能看出，本文算法更加平滑更加最優(yōu)。

圖6 簡(jiǎn)單環(huán)境下算法改進(jìn)前后對(duì)比

同理，由圖7中的(a)圖、(b)圖，可以較明顯的發(fā)現(xiàn)改進(jìn)后的算法比原算法的隨機(jī)樹擴(kuò)展更具有目的性，冗余樹枝的數(shù)量明顯較少，這在一定程度上可以減少搜索時(shí)間，從而加快算法的收斂速度，并且路徑的質(zhì)量也有明顯的提高。

圖7 復(fù)雜環(huán)境下算法改進(jìn)前后對(duì)比

3.2 算法定量比較分析

下面統(tǒng)計(jì)上述改進(jìn)后算法的實(shí)際運(yùn)行時(shí)間以及最終規(guī)劃的路徑長(zhǎng)度，以此來做一個(gè)定量的比較。兩種環(huán)境下，每個(gè)算法運(yùn)行5次進(jìn)行試驗(yàn)。由表1在簡(jiǎn)單的背景環(huán)境下的對(duì)比可以看出本文算法所需要的時(shí)間比原算法所需時(shí)間平均減少了60%；在路徑長(zhǎng)度方面，本文算法也比原算法要短。

表1 簡(jiǎn)單環(huán)境下算法的定量比較

表2 復(fù)雜環(huán)境下算法的定量比較

由表2中在復(fù)雜環(huán)境背景下的對(duì)比數(shù)據(jù)可以看出本文算法的運(yùn)行時(shí)間明顯比原算法運(yùn)行時(shí)間要小很多，粗略算一下可得本文算法在復(fù)雜環(huán)境下所需時(shí)間比原算法所需時(shí)間要減小了50%左右；而在路徑長(zhǎng)度方面，本文算法最終規(guī)劃的路徑要比原算法規(guī)劃得到的路徑要短。

4 結(jié)束語(yǔ)

本文所研究的RRT*路徑規(guī)劃算法，針對(duì)RRT*算法存在的局限性，對(duì)該算法進(jìn)行了改進(jìn)。首先改變隨機(jī)點(diǎn)的隨機(jī)性，有目的性的設(shè)置采樣點(diǎn)；在隨機(jī)樹新節(jié)點(diǎn)生成中，加入目標(biāo)對(duì)其的吸引作用和新節(jié)點(diǎn)避障策略，減少因?yàn)殡S機(jī)性和隨機(jī)樹慢速生長(zhǎng)而提高的時(shí)間成本；文中啟發(fā)式代價(jià)估值函數(shù)采用曼哈頓距離可以加快運(yùn)算。實(shí)驗(yàn)結(jié)果表明，本文算法不僅加快了算法的收斂時(shí)間，且規(guī)劃的路徑質(zhì)量得到保障，是一種有效的路徑規(guī)劃算法。