基于DBSCAN算法的改進(jìn)RRT Connect路徑規(guī)劃研究

摘"要：針對(duì)雙向快速擴(kuò)展隨機(jī)樹（RRTConnect）算法收斂速度慢、路徑搜索效率低、路徑曲折的問題，提出了一種基于DBSCAN算法的改進(jìn)RRTConnect算法。在RRTConnect算法基礎(chǔ)上加入節(jié)點(diǎn)引力場(chǎng)引導(dǎo)新節(jié)點(diǎn)產(chǎn)生方向，使收斂速度變快；同時(shí)通過引入橢圓采樣方法，縮小采樣范圍，提高路徑規(guī)劃效率；最后在改進(jìn)RRTConnect的基礎(chǔ)上引入DBSCAN聚類算法，使得到的規(guī)劃路徑更加平滑可靠，增強(qiáng)算法的魯棒性。為了驗(yàn)證改進(jìn)后的算法優(yōu)化效果，分別在不同環(huán)境中與RRT算法、RRTConnect算法進(jìn)行仿真比較。仿真實(shí)驗(yàn)表明，改進(jìn)后的RRTConnect算法路徑規(guī)劃效果均要優(yōu)于其他兩種算法，不僅加快了路徑規(guī)劃速度，而且得到的路徑接近最優(yōu)解，具有普遍適用性、魯棒性高等特點(diǎn)。

關(guān)鍵詞：RRTConnect算法；DBSCAN算法；橢圓采樣；引力場(chǎng)；路徑規(guī)劃

中圖分類號(hào)：TP39""""""文獻(xiàn)標(biāo)識(shí)碼：A

Research"on"Improved"RRTConnect"Path"Planning"

Based"on"DBSCAN"Algorithm

LI"Liuyang，"WANG"Keqing，"JIAO"Sitao，"ZHOU"Qi"

（School"of"Automation，"Nanjing"University"of"Information"Science"and"Technology，Nanjing，Jiangsu"210044，China）

Abstract：Aiming"at"the"problems"of"slow"convergence"speed，"low"path"search"efficiency"and"tortuous"path"of"RRTConnect"algorithm，"an"improved"RRTConnect"algorithm"based"on"DBSCAN"algorithm"is"proposed."On"the"basis"of"the"RRTConnect"algorithm，"the"node"gravitational"field"is"added"to"guide"the"direction"of"the"new"node，"which"makes"the"convergence"speed"faster."At"the"same"time，"by"introducing"the"elliptical"sampling"method，"the"sampling"range"is"reduced"to"improve"the"efficiency"of"path"planning."Finally，"based"on"the"improved"RRTConnect，"the"DBSCAN"clustering"algorithm"is"introduced"to"make"the"obtained"planning"path"smoother"and"more"reliable，nbsp;and"enhance"the"robustness"of"the"algorithm."In"order"to"verify"the"optimization"effect"of"the"improved"algorithm，"it"is"simulated"and"compared"with"the"RRT"algorithm"and"the"RRTConnect"algorithm"in"different"environments."The"simulation"results"show"that"the"improved"RRTConnect"algorithm"has"better"path"planning"effect"than"the"other"two"algorithms."It"not"only"accelerates"the"path"planning"speed，"but"also"obtains"the"path"close"to"the"optimal"solution，"which"has"the"characteristics"of"universal"applicability"and"high"robustness.

Key"words：RRTConnect"algorithm;"DBSCAN"algorithm;"ellipse"sampling;"gravitational"field;"path"planning

路徑規(guī)劃是機(jī)器人技術(shù)和自動(dòng)化領(lǐng)域中的一個(gè)核心問題，它涉及在給定環(huán)境中，避免與障礙物碰撞的前提下，找到最優(yōu)路徑的任務(wù)[1]。路徑規(guī)劃在眾多實(shí)際應(yīng)用中發(fā)揮著重要作用，包括自動(dòng)駕駛[2]、機(jī)器人導(dǎo)航[3]、無人機(jī)航行[4]和運(yùn)輸[5]等領(lǐng)域。隨著技術(shù)的不斷發(fā)展和應(yīng)用的廣泛需求，路徑規(guī)劃算法的研究變得越來越關(guān)鍵。常見的路徑規(guī)劃算法有：A*算法[6]、蟻群算法[7]、人工勢(shì)場(chǎng)算法[8]、概率圖算法（PRM）[9]、D*算法[10]、快速探索隨機(jī)樹（RRT）。

其中，最常用的算法是基于采樣的方法。RRT算法憑借其搜索路徑效率高、適用于高維空間的優(yōu)點(diǎn)，在路徑規(guī)劃算法中得到快速發(fā)展和應(yīng)用。傳統(tǒng)的RRT算法采用隨機(jī)采樣的方法進(jìn)行搜索，具有較強(qiáng)的搜索能力，但RRT的隨機(jī)性也導(dǎo)致其搜索效率有提升的空間，同時(shí)規(guī)劃路徑的質(zhì)量方面也不能達(dá)到最優(yōu)，特別是在復(fù)雜環(huán)境和高維空間中。為了提高RRT算法的搜索效率和路徑質(zhì)量問題，很多學(xué)者對(duì)其進(jìn)行了改進(jìn)。Kuffner等[11]在2000年提出RRTConnect算法，通過起點(diǎn)和目標(biāo)點(diǎn)同時(shí)生成隨機(jī)擴(kuò)展樹來提高算法的搜索效率，但是規(guī)劃的路徑比較曲折，在應(yīng)用于空間機(jī)械臂避障路徑規(guī)劃時(shí)，存在盲采樣點(diǎn)大、無效點(diǎn)多等問題[12]。Karaman等[13]在2011年提出RRT*算法，該算法隨著樣本數(shù)量的增加而不斷優(yōu)化隨機(jī)樹，由于其漸進(jìn)優(yōu)化的特性，RRT*算法理論上可以得到最優(yōu)解，但是收斂速度過慢。趙超力等[14]將引力場(chǎng)思想引入RRTConnect算法，引導(dǎo)隨機(jī)樹生長(zhǎng)，并且在路徑起點(diǎn)和終點(diǎn)之間設(shè)置第三節(jié)點(diǎn)，由兩棵隨機(jī)樹變?yōu)樗目秒S機(jī)樹，大大加快搜索效率，但存在獲取路徑曲折問題。游達(dá)章等[15]提出一種基于橢球子集采樣的RRTConnect算法，縮小采樣空間，同時(shí)引入目標(biāo)偏執(zhí)采樣策略，提高路徑規(guī)劃效率，最后基于三角不等式的路徑修剪策略來優(yōu)化路徑質(zhì)量。Zhu等[16]提出將Dijkstra算法與RRTConnect算法相結(jié)合，去除冗余路徑節(jié)點(diǎn)，縮短路徑長(zhǎng)度，引用人工勢(shì)場(chǎng)思想，減少路徑盲目搜索，最后利用B樣條曲線對(duì)規(guī)劃路徑進(jìn)行平滑處理，獲得連續(xù)軌跡。

通過對(duì)上面的文獻(xiàn)總結(jié)得知，RRTConnect算法優(yōu)點(diǎn)還是比較突出的，相較于RRT算法和RRT*算法，它采用兩棵隨機(jī)擴(kuò)展樹來搜索路徑，使搜索效率大大提升，但是RRTConnect算法的缺點(diǎn)也很明顯，比如擴(kuò)展路徑曲折、隨機(jī)盲目擴(kuò)展等問題。為了解決以上問題，以RRTConnect算法為基礎(chǔ)，在路徑起點(diǎn)以及目標(biāo)點(diǎn)上疊加引力場(chǎng)引導(dǎo)隨機(jī)樹擴(kuò)展方向，使收斂速度變快，實(shí)現(xiàn)路徑平滑的效果；同時(shí)引入橢圓采樣策略，將采樣空間限制在一個(gè)橢圓空間內(nèi)，以減少路徑搜索的盲目性，提高路徑規(guī)劃效率；最后針對(duì)路徑曲折問題，在改進(jìn)RRTConnect算法的基礎(chǔ)上采用DBSCAN聚類算法，對(duì)以往的仿真數(shù)據(jù)進(jìn)行聚類分析，就可以直接、有效地通過已有的歷史數(shù)據(jù)提取出重要且有意義的路徑點(diǎn)，使得到的路徑更接近最優(yōu)解，算法普適性和魯棒性更高。通過仿真實(shí)驗(yàn)，驗(yàn)證改進(jìn)算法的有效性和可行性。

1"傳統(tǒng)算法

1.1"RRT算法

RRT算法作為一種隨機(jī)性算法，在搜索空間中隨機(jī)生成節(jié)點(diǎn)，并將新節(jié)點(diǎn)連接到樹中已有的節(jié)點(diǎn)，從而構(gòu)建一棵隨機(jī)生長(zhǎng)的樹，直到找到目標(biāo)節(jié)點(diǎn)為止。RRT算法憑借其快速、簡(jiǎn)單且易于實(shí)現(xiàn)的特點(diǎn)在路徑規(guī)劃問題中得到廣泛的研究和應(yīng)用。

RRT算法通過在起始點(diǎn)構(gòu)建一棵只包含根節(jié)點(diǎn)的樹，定義起始節(jié)點(diǎn)為n"init，見圖1，在可搜索空間中隨機(jī)采樣一個(gè)點(diǎn)n"rand，再根據(jù)定義的搜索步長(zhǎng)λ在樹中搜索最近的節(jié)點(diǎn)n"near，如果n"rand和n"near之間的直線上有障礙物，則舍棄該采樣點(diǎn)并重新生成一個(gè)新的采樣點(diǎn)；如果沒有障礙物，則根據(jù)搜索步長(zhǎng)λ逐步連接n"rand和n"near。重復(fù)上面的步驟直到到達(dá)目標(biāo)點(diǎn)n"goal或設(shè)定好的迭代次數(shù)。最后通過回溯隨機(jī)樹在上述過程中生成的節(jié)點(diǎn)，獲取從起始點(diǎn)到終點(diǎn)的路徑。

1.2"RRTConnect算法

RRTConnect算法在RRT算法的基礎(chǔ)上將起始點(diǎn)和目標(biāo)點(diǎn)構(gòu)建為兩棵隨機(jī)樹，分別向彼此的方向擴(kuò)展，同時(shí)引入節(jié)點(diǎn)貪婪擴(kuò)展策略，在每次迭代生成節(jié)點(diǎn)時(shí)，盡量將另一棵樹的最近節(jié)點(diǎn)作為該樹的擴(kuò)展方向，使兩棵樹快速相交。另外，如果在擴(kuò)展過程中沒有遇到障礙物，算法繼續(xù)在該方向上擴(kuò)展節(jié)點(diǎn)；如遇到障礙物，該算法使用交換函數(shù)，讓另一個(gè)隨機(jī)樹擴(kuò)展，這樣避免算法陷入局部最優(yōu)困境。相較于RRT算法，搜索路徑效率得到了極大提升。RRTConnect算法擴(kuò)展過程如圖2所示。

2"改進(jìn)算法

RRTConnect算法相較于RRT算法在搜索效率以及路徑規(guī)劃質(zhì)量方面雖然有所提升，但是本身的盲目搜索特性還有路徑曲折問題依然存在，所以我們就根據(jù)RRTConnect算法所存在的問題，提出針對(duì)性的算法優(yōu)化。針對(duì)盲目搜索問題，引入節(jié)點(diǎn)引力場(chǎng)概念，給起始點(diǎn)和目標(biāo)點(diǎn)各疊加一個(gè)引力場(chǎng)，引導(dǎo)隨機(jī)樹向目標(biāo)節(jié)點(diǎn)生長(zhǎng)；同時(shí)引入橢圓采樣策略，將隨機(jī)采樣空間限制在一個(gè)橢圓空間內(nèi)，進(jìn)一步降低路徑盲目搜索性；針對(duì)規(guī)劃路徑曲折問題，采用DBSCAN聚類算法去除路徑冗余點(diǎn)，優(yōu)化路徑質(zhì)量，提高算法適用性和魯棒性。

2.1"節(jié)點(diǎn)引力場(chǎng)

將目標(biāo)節(jié)點(diǎn)引力思想[17，18]引入RRTConnect算法中，分別對(duì)雙向隨機(jī)樹中的每個(gè)節(jié)點(diǎn)n都疊加一個(gè)目標(biāo)引力函數(shù)G（n）"，這個(gè)節(jié)點(diǎn)是由起始節(jié)點(diǎn)（或目標(biāo)接點(diǎn)）向外擴(kuò)展的第n個(gè)節(jié)點(diǎn)，表達(dá)式為：

F（n）=R（n）+G（n）""""（1）

方程（1）表示節(jié)點(diǎn)"n"到目標(biāo)點(diǎn)的生長(zhǎng)指導(dǎo)函數(shù)"F（n）"是由隨機(jī)生長(zhǎng)函數(shù)"R（n）"和目標(biāo)引力函數(shù)"G（n）"組成的。生長(zhǎng)指導(dǎo)函數(shù)F（n）"是指導(dǎo)節(jié)點(diǎn)n向目標(biāo)點(diǎn)生長(zhǎng)的總力量。隨機(jī)生長(zhǎng)函數(shù)R（n）表示從初始節(jié)點(diǎn)到節(jié)點(diǎn)n的隨機(jī)生長(zhǎng)力量，它模擬了隨機(jī)的生長(zhǎng)過程。目標(biāo)引力函數(shù)G（n）則代表了目標(biāo)點(diǎn)對(duì)節(jié)點(diǎn)n的引力，它使節(jié)點(diǎn)"n"被引導(dǎo)向目標(biāo)點(diǎn)。

新節(jié)點(diǎn)的隨機(jī)生長(zhǎng)函數(shù)R（n）的計(jì)算公式為：

R（n）=λ*nrand-nnearnrand-nnear（2）

其中λ為步長(zhǎng)。目標(biāo)引力函數(shù)G（n）為：

G（n）=λ*γ*ngoal-nnear2（3）

其中γ為引力系數(shù)，ngoal-nnear2為目標(biāo)點(diǎn)到隨機(jī)生長(zhǎng)樹上最近點(diǎn)的歐氏距離的平方，這樣離目標(biāo)點(diǎn)越遠(yuǎn)，引力越大。

將式（2）和式（3）代入式（1）得：

F（n）=λ*nrand-nnearnrand-nnear+

λ*γ*ngoal-nnear2（4）

根據(jù)式（4）可得到疊加引力場(chǎng)后的新節(jié)點(diǎn)產(chǎn)生方式為：

nnew=nnear+λ*nrand-nnearnrand-nnear+

γ*ngoal-nnear2（5）

在疊加引力場(chǎng)之后，每個(gè)節(jié)點(diǎn)在雙向隨機(jī)樹中都使用相同的生長(zhǎng)指導(dǎo)函數(shù)F（n），該函數(shù)綜合考慮了引力分量和自由空間的因素。引力分量使節(jié)點(diǎn)朝向目標(biāo)方向生長(zhǎng)，而自由空間的概念確保節(jié)點(diǎn)在生長(zhǎng)過程中避免碰撞或穿越障礙物。這種一致性的生長(zhǎng)指導(dǎo)函數(shù)確保了樹的協(xié)調(diào)和一致性，使得雙向隨機(jī)樹能夠高效地搜索路徑并找到目標(biāo)點(diǎn)。引力場(chǎng)下影響節(jié)點(diǎn)擴(kuò)展示意圖如圖3所示。

2.2"橢圓采樣

在規(guī)劃路徑時(shí)，由于起始點(diǎn)和目標(biāo)點(diǎn)都是已知的，兩點(diǎn)連線是成本最低的路徑。將隨機(jī)點(diǎn)限制在最小路徑周圍生成的橢圓區(qū)域內(nèi)，而不是在自由空間中任意搜索，這樣既能提高收斂速度，又能克服一定的隨機(jī)性。

為了將采樣空間限制在橢圓子集中，引用以起始點(diǎn)和目標(biāo)點(diǎn)為焦點(diǎn)的橢圓。Cmin是起始點(diǎn)和目標(biāo)點(diǎn)之間的歐氏距離，橢球的短軸為C2best-C2min，橢球的長(zhǎng)軸為Cbest，見圖4。

該采樣過程需要在子集Xellipse～U（Xellipse）內(nèi)均勻地分布樣本。通過將樣本均勻分布在半徑為n的球上，然后將它們轉(zhuǎn)移到橢圓子集XBall～U（Xball）來實(shí)現(xiàn)。

xellipse=Lxball+xcenter""（6）

xcenter=xf1+xf22"""（7）

xcenter為橢球的中心，xf1、xf2為橢圓子集的焦點(diǎn)，Xball是單位r球內(nèi)的樣本。

Xball=x∈Xx2≤１}""（8）

使用超橢球內(nèi)迭代采樣方法，初始路徑長(zhǎng)度與后續(xù)迭代生成的路徑長(zhǎng)度相比較，后者較短。隨著迭代次數(shù)的增加，超橢球的體積逐漸縮小，導(dǎo)致路徑長(zhǎng)度不斷減小。最終，算法能夠找到最優(yōu)路徑。橢圓采樣在高維空間中展現(xiàn)出更顯著的優(yōu)勢(shì)，是因?yàn)樗哂懈斓氖諗克俣群透叩乃阉餍省?/p>

2.3"DBSCAN聚類算法

經(jīng)過RRTConnect算法的多次規(guī)劃，雖然可以避開障礙物并到達(dá)目的地，但每個(gè)規(guī)劃路徑過程都是相互獨(dú)立的，雖然有些路徑能夠安全到達(dá)目標(biāo)點(diǎn)，但它們遠(yuǎn)不是最優(yōu)路徑，如果將規(guī)劃結(jié)果直接應(yīng)用到真實(shí)的場(chǎng)景中，可能會(huì)付出高昂的代價(jià)。引進(jìn)的DBSCAN算法不需要事先確定簇?cái)?shù)，對(duì)野值不敏感，操作簡(jiǎn)單，計(jì)算速度快。DBSCAN算法是一種典型的基于密度分布的聚類算法。該算法將聚類定義為密度連接的最大點(diǎn)集，可以將密度足夠大的區(qū)域劃分為聚類，也可以在噪聲空間數(shù)據(jù)庫中找到任意形狀的聚類。該算法需要預(yù)先定義半徑區(qū)域和最小點(diǎn)。

半徑區(qū)域：DBSCAN算法用來判斷數(shù)據(jù)點(diǎn)的相似度、接近度以及是否屬于同一類別的標(biāo)準(zhǔn)距離。

最小點(diǎn)：標(biāo)準(zhǔn)用于選擇聚類中心。如果附近點(diǎn)的數(shù)量小于N，則該點(diǎn)被標(biāo)記為噪聲點(diǎn)。如果附近點(diǎn)的數(shù)量大于或等于N，則將該點(diǎn)和附近點(diǎn)組合以形成聚類。然后標(biāo)記點(diǎn)，采用遞歸算法不斷擴(kuò)展聚類。

DBSCAN算法根據(jù)每個(gè)數(shù)據(jù)點(diǎn)的空間分布，將點(diǎn)集劃分為核心點(diǎn)、邊界點(diǎn)和離群點(diǎn)。核心點(diǎn)均在半徑范圍內(nèi)，其他數(shù)據(jù)點(diǎn)包含的點(diǎn)數(shù)超過最小值;邊界點(diǎn)在半徑內(nèi)，其他數(shù)據(jù)點(diǎn)包含少于最小數(shù)量的點(diǎn);離群點(diǎn)既不是核心點(diǎn)，也不是邊界點(diǎn)。

使用最近鄰的思想，Minkowski（閔可夫斯基）距離用于測(cè)量最近距離，其表示如下：

D（x，y）=p（|x1-y1|）p+（|x2-y2|）p+…+xm-ymp=p∑mi=1xi-yip（9）

本文采用曼哈頓距離來度量樣本距離，其表示如下：

D（x，y）=x1-y1+x2-y2+…+

xm-ym=∑mi=1xi-yi（10）

每個(gè)聚類基于密度進(jìn)行分離，用每個(gè)聚類的樣本均值表示聚類的質(zhì)心。

改進(jìn)后的RRTConnect算法偽代碼如下;

其中，center為橢圓的中心點(diǎn)；semi_major_axis為橢圓的半長(zhǎng)軸；semi_minor_axis為橢圓的半短軸；theta_min和theta_max為橢圓上采樣點(diǎn)的角度范圍；random"value"between"0"and"1為在區(qū)間"[0，"1]"內(nèi)生成一個(gè)隨機(jī)值；sqrt為平方根函數(shù)；empty"list為空列表；append為將元素添加到列表的末尾；eps為領(lǐng)域半徑，用于確定點(diǎn)的鄰域；minpts為鄰域中所需的最小點(diǎn)數(shù)。

3"仿真結(jié)果與分析

相關(guān)仿真實(shí)驗(yàn)在MATLAB"R2020a軟件中完成，實(shí)驗(yàn)環(huán)境配置如下：11th"Gen"Intel（R）"Core（TM）"i711800H@2.3GHz，RAM16GB。

為了驗(yàn)證改進(jìn)后的算法的適用性和有效性，進(jìn)行仿真實(shí)驗(yàn)，與RRT算法、RRTConnect算法規(guī)劃的路徑結(jié)果相比較。并且應(yīng)用于三種仿真環(huán)境，比較三種算法的生成節(jié)點(diǎn)數(shù)、路徑長(zhǎng)度以及規(guī)劃時(shí)間三個(gè)參數(shù)。為了各算法實(shí)驗(yàn)參數(shù)的一致性，三種算法相關(guān)參數(shù)設(shè)置和步長(zhǎng)設(shè)置一致。

3.1"少障礙物環(huán)境

本環(huán)境地圖采用15×15，起點(diǎn)位置為[3，3]，終點(diǎn)位置為[13，13]。三種算法在該環(huán)境下路徑搜索及規(guī)劃路徑（紅色路線為最終規(guī)劃路徑，灰色路線為搜索路徑）見圖5。

搜索及規(guī)劃路徑

在該環(huán)境下，分別用三種算法進(jìn)行50次仿真實(shí)驗(yàn)，對(duì)路徑生成過程中的節(jié)點(diǎn)數(shù)、路徑長(zhǎng)度以及規(guī)劃時(shí)間三個(gè)參數(shù)做記錄取平均值，生成表2。

由圖5和表2可得，本文改進(jìn)的算法相較于RRT算法和RRTConnect算法，得到的規(guī)劃路徑更加平滑，搜索路徑節(jié)點(diǎn)更少。在生成節(jié)點(diǎn)數(shù)方面，改進(jìn)算法只有RRT算法的17.8%，RRTConnect算法的75%；改進(jìn)算法在路徑長(zhǎng)度方面比RRT算法縮短27.3%，比RRTConnect算法縮短9.8%；規(guī)劃時(shí)間也相應(yīng)減短59.6%、13.1%。在三個(gè)參數(shù)方面以及生成路徑平滑度均有提升效果。

3.2"適度障礙物環(huán)境

本環(huán)境地圖采用20×20，起點(diǎn)位置為[2，2]，終點(diǎn)位置為[19，19]。三種算法在該環(huán)境下路徑搜索及規(guī)劃路徑（紅色路線為最終規(guī)劃路徑，灰色路線為搜索路徑）見圖6。

路徑搜索及規(guī)劃路徑

在該環(huán)境下，分別用三種算法進(jìn)行50次仿真實(shí)驗(yàn)，對(duì)路徑生成過程中的節(jié)點(diǎn)數(shù)、路徑長(zhǎng)度以及規(guī)劃時(shí)間三個(gè)參數(shù)做記錄取平均值，生成表3。

由圖6和表3可得，在生成節(jié)點(diǎn)數(shù)方面，改進(jìn)算法只有RRT算法的15.1%，RRTConnect算法的73.5%；改進(jìn)算法在路徑長(zhǎng)度方面比RRT算法縮短31.5%，比RRTConnect算法縮短11.1%；規(guī)劃時(shí)間也相應(yīng)減短63.2%、15.1%。同樣在三個(gè)參數(shù)方面以及生成路徑平滑度均有提升效果。

3.3"多障礙物環(huán)境

本環(huán)境地圖采用25×25，起點(diǎn)位置為[2，2]，終點(diǎn)位置為[24，24]。三種算法在該環(huán)境下路徑搜索及規(guī)劃路徑（紅色路線為最終規(guī)劃路徑，灰色路線為搜索路徑）見圖7。

路徑搜索及規(guī)劃路徑

在該環(huán)境下，分別用三種算法進(jìn)行50次仿真實(shí)驗(yàn)，對(duì)路徑生成過程中的節(jié)點(diǎn)數(shù)、路徑長(zhǎng)度以及規(guī)劃時(shí)間三個(gè)參數(shù)做記錄取平均值，生成表4。

由圖7和表4可得，在生成節(jié)點(diǎn)數(shù)方面，改進(jìn)算法只有RRT算法的14.5%，RRTConnect算法的68.1%；改進(jìn)算法在路徑長(zhǎng)度方面比RRT算法縮短28.6%，比RRTConnect算法縮短13.6%；規(guī)劃時(shí)間也相應(yīng)減短69.7%、21.2%。在三個(gè)參數(shù)方面以及生成路徑平滑度均有提升效果。

從以上仿真數(shù)據(jù)可以看出，改進(jìn)后的算法相較于RRT算法、RRTConnect算法數(shù)值方面均有提升，尤其是在環(huán)境復(fù)雜度較高的時(shí)候，能夠逐步提升規(guī)劃時(shí)間，且最終規(guī)劃路徑均取得不錯(cuò)的效果。

4"結(jié)"論

通過對(duì)RRTConnect算法的改進(jìn)，解決了擴(kuò)展路徑曲折以及隨機(jī)盲目擴(kuò)展等問題。通過在路徑起始點(diǎn)和目標(biāo)點(diǎn)上引入引力場(chǎng)，以及橢圓采樣策略，引導(dǎo)隨機(jī)樹在橢圓區(qū)域向目標(biāo)點(diǎn)方向擴(kuò)展，減少無用擴(kuò)展，加快路徑規(guī)劃效率。通過DBSCAN聚類算法對(duì)歷史采樣點(diǎn)數(shù)據(jù)進(jìn)行聚類分析，去除冗余點(diǎn)，增強(qiáng)算法魯棒性，使得到的路徑接近最優(yōu)解。通過在三種環(huán)境下與RRT算法、RRTConnect算法的比較，驗(yàn)證了改進(jìn)算法的有效性和適用性。

參考文獻(xiàn)

［１］"湯云峰．改進(jìn)智能算法在移動(dòng)機(jī)器人路徑規(guī)劃中的研究［D］．南京："南京郵電大學(xué)，2021.

［2］"李學(xué)鋆．基于UTMD的汽車自動(dòng)駕駛的路徑規(guī)劃尋優(yōu)算法［J］．"汽車安全與節(jié)能學(xué)報(bào)，2018，9（4）：449-455.

［3］"陳敏，李笑，武交峰．基于改進(jìn)RRT算法的差動(dòng)機(jī)器人路徑規(guī)劃［J］．"計(jì)算機(jī)應(yīng)用與軟件，2019，36（9）"："276-280.

［4］"尹高揚(yáng)，周紹磊，吳青坡．基于改進(jìn)RRT算法的無人機(jī)航跡規(guī)劃［J］．"電子學(xué)報(bào)，2017，45（7）：1764-1769．

［5］"LIU"C"L，"PAI"T"W，"CHANG"C"T"，et"al."Pathplanning"algorithms"for"public"transportation"systems［C］//2001"IEEE"Intelligent"Transportation"Systems."Proceedings"（Cat."No.01TH8585），"Oakland，"CA，"2001：1061-1066.

［6］"DING"H，"LI"Y，"CHAI"Y，"et"al."Path"planning"for"2DOF"manipulator"based"on"Bezier"curve"and"A*"algorithm[C]//2018"Chinese"Automation."Chinese"Automation"Congress"（CAC）."IEEE，2018：670-674.

［7］"LIU"T，"SONG"C，"JIANG"J."Robotic"path"planning"based"on"improved"ant"colony"algorithm[C]//International"Symposium"on"Neural"Networks."Springer，"Cham，"2019："351-358.

［8］"BOUNINI"F，"GINGRAS"D，"POLLART"H，"et"al."Modified"artificial"potential"field"method"for"online"path"planning"applications［C］//2017"IEEE"Intelligent"Vehicles"Symposium"（IV），"2017：180-185.

［9］"KAVRAKI"L"E，"SVESTKA"P，"LATOMBE"J"C，"et"al."Probabilistic"roadmapsnbsp;for"path"planning"in"highdimensional"configuration"spaces[J]."IEEE"Transactions"on"Robotics"and"Automation"1996，12（4）：566-580.

［10］KOENIG"S，"LIKHACHEV"M."D*"lite［J］."Journal"of"Artificial"Intelligence"Research，2002，17：1-5.

［11］KUFFNER"J"J，"LAVALLE，"S"M.RRTconnect："An"efficient"approach"to"singlequery"path"planning［C］//IEEE"International"Conference"on"Robotics"and"Automation."IEEE，"2000，"2："995-1001.

［12］CAO"Y，"ZHANG"Y"B，"ZHOU"Y."Research"on"obstacle"avoidance"path"planning"of"spatial"manipulator"based"on"improved"RRTconnect[J]."Machine"Tool"amp;"Hydraulics，"2020，48"（12）：177-183.

［13］KARAMAN"S，"FRAZZOLI"E."Samplingbased"algorithms"for"optimal"motion"planning[J]."The"International"Journal"of

Robotics"Research，"2011，"30（7）：846-894.

［14］趙超力，馬行，張春濤，等.基于引力場(chǎng)引導(dǎo)的RRTConnect路徑規(guī)劃算法[J].電子測(cè)量技術(shù)，2021，44（22）：44-49.

［15］游達(dá)章，楊智杰，張業(yè)鵬.基于改進(jìn)RRTConnect算法的機(jī)械臂運(yùn)動(dòng)規(guī)劃[J].電子測(cè)量技術(shù)，2023，46（8）：112-119.

［16］ZHU"Y，"TANG"Y，"ZHANG"Y，"et"al."Path"planning"of"manipulator"based"on"improved"RRTConnect"algorithm［C］//2021"2nd"International"Conference"on"Big"Data"amp;"Artificial"Intelligence"amp;"Software"Engineering"（ICBASE），"Zhuhai，"China，"2021：44-47.

［17］GAMMELL"J"D，"SRINIVASA"S"S，"BARFOOT"T"D."Informed"RRT*：optimal"samplingbased"path"planning"focused"via"direct"sampling"of"an"admissible"ellipsoidal"heuristic[C]//Proc."IEEE/RSJ"Int."Conf."Intell."Robots"Syst.，"2014："2997-3004.

［18］LUCHI"D，"LOUREIROS"R"A，"Miguel"Varejo"F."Sampling"approaches"for"applying"DBSCAN"to"large"datasets[J]."Pattern"Recogn"Lett，2019，117：90-96.