摘 要:無(wú)人機(jī)路徑規(guī)劃源于機(jī)器人運(yùn)動(dòng)規(guī)劃,是當(dāng)下無(wú)人機(jī)應(yīng)用研究的核心內(nèi)容,對(duì)提高無(wú)人機(jī)系統(tǒng)在復(fù)雜環(huán)境中的作業(yè)能力起著關(guān)鍵作用。針對(duì)快速擴(kuò)展隨機(jī)樹(shù)(Rapidly-exploring Random Tree,RRT)算法進(jìn)行無(wú)人機(jī)路徑規(guī)劃時(shí)搜索隨機(jī)性高、存在冗余路徑和路徑平滑性差的問(wèn)題,提出了一種面向無(wú)人機(jī)路徑規(guī)劃的改進(jìn)RRT 算法。改進(jìn)RRT算法在RRT 算法的基礎(chǔ)上結(jié)合人工勢(shì)場(chǎng)法中的引力函數(shù)使得隨機(jī)節(jié)點(diǎn)的產(chǎn)生具有目標(biāo)導(dǎo)向性,限制了隨機(jī)樹(shù)的拓展方向,從而降低了搜索的隨機(jī)性;結(jié)合貪心算法對(duì)規(guī)劃所得路徑進(jìn)行剪枝優(yōu)化,去除冗余節(jié)點(diǎn),縮短了路徑長(zhǎng)度;結(jié)合B 樣條曲線對(duì)路徑進(jìn)行平滑性處理,去除曲率突變的轉(zhuǎn)折點(diǎn),形成一條平滑的適合無(wú)人機(jī)實(shí)際飛行的路徑。通過(guò)仿真軟件對(duì)A* 算法、傳統(tǒng)RRT 算法與改進(jìn)RRT 算法進(jìn)行對(duì)比分析,仿真結(jié)果表明,提出的改進(jìn)RRT 算法性能更高,在狹窄通道場(chǎng)景與復(fù)雜障礙物場(chǎng)景下相比于傳統(tǒng)RRT 算法平均規(guī)劃時(shí)間各減少49. 44% 和17. 97% ,相比于A* 算法平均規(guī)劃時(shí)間各減少了80. 23% 和52. 93% ,得到的路徑更短更為平緩,同時(shí)大幅降低了RRT 算法路徑規(guī)劃失敗的可能性,驗(yàn)證了改進(jìn)RRT 算法的可行性與有效性,解決了原算法隨機(jī)性高、存在冗余路徑和平滑性差的問(wèn)題。
關(guān)鍵詞:無(wú)人機(jī);路徑規(guī)劃;改進(jìn)快速擴(kuò)展隨機(jī)樹(shù)算法;快速擴(kuò)展隨機(jī)樹(shù)算法;A*算法;引力函數(shù)
中圖分類號(hào):TN919. 23 文獻(xiàn)標(biāo)志碼:A 開(kāi)放科學(xué)(資源服務(wù))標(biāo)識(shí)碼(OSID):
文章編號(hào):1003-3114(2024)06-1184-08
0 引言
路徑規(guī)劃技術(shù)近些年發(fā)展迅速,已經(jīng)被應(yīng)用于各行各業(yè),尤其是在無(wú)人機(jī)領(lǐng)域。無(wú)人機(jī)路徑規(guī)劃是無(wú)人機(jī)應(yīng)用研究的核心內(nèi)容,對(duì)提高無(wú)人機(jī)系統(tǒng)在復(fù)雜未知環(huán)境的作業(yè)能力起著關(guān)鍵作用。無(wú)人機(jī)路徑規(guī)劃的核心任務(wù)是在已知起始點(diǎn)和目標(biāo)點(diǎn)的情況下,找出一條既能避開(kāi)沿途障礙物又趨向于距離最短的可行路徑。
各國(guó)學(xué)者已經(jīng)提出了多種經(jīng)典路徑規(guī)劃算法,以應(yīng)對(duì)不同場(chǎng)景下的路徑優(yōu)化問(wèn)題。例如Dijkstra算法[1]作為一種最短路徑算法,具有全局最優(yōu)性;遺傳算法[2]基于生物進(jìn)化論,通過(guò)選擇、交叉和變異的操作尋找全局最優(yōu)解;快速擴(kuò)展隨機(jī)樹(shù)(Rapidly-exploring Random Tree,RRT)算法則利用隨機(jī)采樣快速探索高維空間中的可行路徑以及人工勢(shì)場(chǎng)法、速度障礙法[3]、粒子群算法[4]、A* 算法、蟻群優(yōu)化(Ant Colony Optimization,ACO)算法[5]等,這些經(jīng)典算法在無(wú)人機(jī)路徑規(guī)劃中起到了重要的基底作用。文獻(xiàn)[6]運(yùn)用了Dijkstra 和紅外檢測(cè)合成的算法,使無(wú)人機(jī)能有效地避開(kāi)所有的障礙物,解決了局部離障礙物過(guò)近的問(wèn)題。文獻(xiàn)[7]提出了一種基于改進(jìn)自適應(yīng)蟻群(Improved Adaptive Ant ColonyOptimization,IAACO)算法的路徑規(guī)劃算法以解決傳統(tǒng)ACO 算法存在的收斂速度慢、易陷入局部最優(yōu)等不足,同時(shí)規(guī)劃出的路徑更平滑、長(zhǎng)度更短。文獻(xiàn)[8]提出一種基于改進(jìn)速度障礙法的局部路徑避障規(guī)劃算法,將傳統(tǒng)速度障礙法拓展到三維空間中,解決了無(wú)人機(jī)在動(dòng)態(tài)環(huán)境中基于環(huán)境感知進(jìn)行局部路徑重規(guī)劃時(shí)面臨的實(shí)時(shí)性與安全性問(wèn)題。文獻(xiàn)[9]提出了基于管道模型預(yù)測(cè)控制(Tube-Model PredictiveControl,Tube-MPC)和模型預(yù)測(cè)路徑積分(ModelPredictive Path Integral,MPPI)融合的多無(wú)人機(jī)分布式在線軌跡規(guī)劃框架與方法,同時(shí)采用并行蒙特卡洛隨機(jī)采樣技術(shù),將多無(wú)人機(jī)軌跡優(yōu)化問(wèn)題的求解過(guò)程轉(zhuǎn)化為對(duì)大量采樣軌跡的期望求解過(guò)程,避免了傳統(tǒng)方法對(duì)代價(jià)函數(shù)和約束條件的連續(xù)性及凸性要求的限制,從而實(shí)現(xiàn)了對(duì)復(fù)雜非線性環(huán)境中多無(wú)人機(jī)軌跡的高效優(yōu)化與規(guī)劃。
針對(duì)RRT 算法的收斂速度慢、路徑曲折等問(wèn)題,研究者進(jìn)行了不同的優(yōu)化處理。文獻(xiàn)[10]針對(duì)隨機(jī)樹(shù)擴(kuò)展時(shí)隨機(jī)性較大的問(wèn)題,加入人工勢(shì)場(chǎng)法約束,使得隨機(jī)樹(shù)偏向目標(biāo)點(diǎn)生長(zhǎng),優(yōu)化了路徑。文獻(xiàn)[11]針對(duì)RRT 算法在路徑規(guī)劃中可能遇到的隨機(jī)性大、搜索時(shí)間長(zhǎng)、路徑曲折等問(wèn)題,提出了一種基于環(huán)境分區(qū)的蟻群優(yōu)化目標(biāo)偏差RRT 算法,有效地消除了無(wú)用節(jié)點(diǎn),減少了規(guī)劃時(shí)間。文獻(xiàn)[12]提出了一種改進(jìn)的RRT 算法,在擴(kuò)展隨機(jī)樹(shù)的過(guò)程中,引入ACO 算法。優(yōu)化后的算法可以在RRT 得到的路徑上設(shè)置信息素,并根據(jù)信息素濃度選擇下一個(gè)擴(kuò)展點(diǎn)。文獻(xiàn)[13]提出了一種基于RRT 算法的改進(jìn)路徑規(guī)劃算法,采用循環(huán)采樣策略提高采樣效率,設(shè)計(jì)了一種基于代價(jià)函數(shù)的擴(kuò)展隨機(jī)點(diǎn)規(guī)則來(lái)過(guò)濾隨機(jī)點(diǎn)。文獻(xiàn)[14]針對(duì)RRT 算法采樣隨機(jī)、效率低的問(wèn)題,提出了一種結(jié)合人工勢(shì)場(chǎng)法的改進(jìn)算法。在基本RRT 算法的隨機(jī)樹(shù)展開(kāi)步驟中引入一個(gè)概率值,加快隨機(jī)樹(shù)向目標(biāo)節(jié)點(diǎn)的收斂,并在隨機(jī)樹(shù)中添加引力分量,引導(dǎo)樹(shù)向目標(biāo)點(diǎn)生長(zhǎng),加快搜索過(guò)程,該方法在迭代時(shí)間、路徑長(zhǎng)度和迭代次數(shù)等方面得到了顯著優(yōu)化。
上述算法從采樣方式、拓展方式等方面對(duì)RRT算法進(jìn)行了改進(jìn),但改進(jìn)后的算法仍存在搜索隨機(jī)性高、存在冗余路徑和平滑性差的問(wèn)題。本文提出的改進(jìn)RRT 算法是在RRT 算法的基礎(chǔ)上首先結(jié)合人工勢(shì)場(chǎng)法中的引力函數(shù)使得隨機(jī)節(jié)點(diǎn)的產(chǎn)生具有導(dǎo)向性和目的性,從而減小了搜索隨機(jī)性;然后結(jié)合貪心算法[15]對(duì)規(guī)劃所得路徑上的轉(zhuǎn)折點(diǎn)進(jìn)行剪枝優(yōu)化,去除了無(wú)用的冗余節(jié)點(diǎn),減少了路徑上的轉(zhuǎn)折點(diǎn),同時(shí)縮短了整體路徑長(zhǎng)度;最后采用3 次B 樣條曲線擬合[16]對(duì)剪枝后的路徑進(jìn)行平滑性處理,從而能夠生成一條路徑平滑的適合無(wú)人機(jī)實(shí)際飛行的路徑。
1 系統(tǒng)模型和問(wèn)題描述
1. 1 系統(tǒng)模型
在進(jìn)行無(wú)人機(jī)路徑規(guī)劃前,首先需要建立一個(gè)無(wú)人機(jī)坐標(biāo)系統(tǒng),然后將無(wú)人機(jī)各傳感器的信息傳遞到坐標(biāo)系統(tǒng)中,最后建立創(chuàng)建地圖所需的柵格地圖[17]模型。
本文將無(wú)人機(jī)視為二維柵格地圖上的質(zhì)點(diǎn),無(wú)人機(jī)的位置用柵格地圖的坐標(biāo)表示,Ps 表示無(wú)人機(jī)的起點(diǎn),Pg 表示目標(biāo)點(diǎn),如圖1 所示。
柵格地圖模型將無(wú)人機(jī)飛行環(huán)境用若干連續(xù)的相同柵格表示,用兩種狀態(tài)表示環(huán)境中的可通行區(qū)域和障礙物區(qū)域。圖1 中空白柵格表示無(wú)人機(jī)可以通過(guò)的空曠區(qū)域Pfree,黑色柵格表示無(wú)人機(jī)不可以通過(guò)的障礙物區(qū)域。
1. 2 RRT 算法原理和模型
RRT 算法的搜索過(guò)程可以看作是樹(shù)的樹(shù)枝不斷生長(zhǎng)、朝四周擴(kuò)展的過(guò)程。本文RRT 算法以路徑起始點(diǎn)Ps 作為隨機(jī)樹(shù)T 的根節(jié)點(diǎn),樹(shù)中節(jié)點(diǎn)Pi 用集合存儲(chǔ),所有節(jié)點(diǎn)滿足Pi∈Pfree,并設(shè)定整體隨機(jī)樹(shù)的最大迭代次數(shù)為M。在搜索過(guò)程中,隨機(jī)在空曠區(qū)域Pfree 生成新節(jié)點(diǎn),以引導(dǎo)樹(shù)的生長(zhǎng)方向,當(dāng)樹(shù)的某個(gè)葉子節(jié)點(diǎn)擴(kuò)展到目標(biāo)點(diǎn)Pg 時(shí),RRT 算法完成整個(gè)整個(gè)區(qū)域的搜索,并返回從目標(biāo)點(diǎn)到根節(jié)點(diǎn)之間的可行路徑連線。
RRT 算法迭代模型如圖2 所示,其每輪迭代中主要包含以下流程:
① 灰色點(diǎn)Pr 為RANDOM 函數(shù)生成的隨機(jī)采樣點(diǎn),其x 和y 軸坐標(biāo)分別為Map. x·RANDOM(1)和Map. y·RANDOM(1)。
② 遍歷當(dāng)前隨機(jī)樹(shù)為Pr 找到距離最近的父節(jié)點(diǎn),遍歷Pr 和其父節(jié)點(diǎn)間的路徑,判斷是否存在障礙物,若存在則Pr 不可作為隨機(jī)樹(shù)節(jié)點(diǎn)。
③ 若Pr 符合以上條件,在Pr 與父節(jié)點(diǎn)間建立拓展步長(zhǎng)為u 的新節(jié)點(diǎn){P1,P2,…,Pn}并加入隨機(jī)樹(shù)T。
1. 3 問(wèn)題描述
從前文可以得知RRT 算法具有參數(shù)少、結(jié)構(gòu)簡(jiǎn)單、搜索能力強(qiáng)的優(yōu)點(diǎn),然而從圖2 迭代模型以及流程中也可以得知,當(dāng)RRT 算法的起始隨機(jī)節(jié)點(diǎn)偏離目標(biāo)點(diǎn),算法運(yùn)算到后期會(huì)出現(xiàn)大量冗余節(jié)點(diǎn),產(chǎn)生較大的隨機(jī)性,使得運(yùn)算速度變慢,最終得到的路徑平滑性差,不適合無(wú)人機(jī)真實(shí)飛行場(chǎng)景。本文將介紹一種改進(jìn)RRT 算法以解決RRT 算法采樣隨機(jī)性較大、路徑冗長(zhǎng)、路徑不平滑的問(wèn)題。
2 改進(jìn)RRT 算法
2. 1 結(jié)合引力函數(shù)優(yōu)化搜索隨機(jī)性
本小節(jié)將結(jié)合人工勢(shì)場(chǎng)法[18]中引力勢(shì)場(chǎng)函數(shù)來(lái)解決RRT 算法中節(jié)點(diǎn)隨機(jī)性較大、冗余節(jié)點(diǎn)量大、收斂速度慢的問(wèn)題。
人工勢(shì)場(chǎng)法是一種局部路徑規(guī)劃方法,最早是針對(duì)移動(dòng)機(jī)器人進(jìn)行避障使用的,具有如下的引力勢(shì)函數(shù)和斥力勢(shì)函數(shù):
式中:α 為引力系數(shù),D(P,Pg)為當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的歐式距離。
式中:λ 為斥力系數(shù),D0 為障礙物斥力影響的范圍,當(dāng)距離大于D0 時(shí),障礙物的斥力對(duì)當(dāng)前節(jié)點(diǎn)不再具有影響。
新節(jié)點(diǎn)的生成過(guò)程如圖3 所示。
圖3 中,Pr 為隨機(jī)生成的新節(jié)點(diǎn),Pn 為距離Pr最近的父節(jié)點(diǎn),Pn+1 為Pr 加入引力函數(shù)后生成的拓展步長(zhǎng)為μ 的新節(jié)點(diǎn),α 為引力系數(shù)。
加入引力函數(shù)生成的節(jié)點(diǎn)的坐標(biāo)見(jiàn)式(3)和式(4),再取距離Pn 拓展步長(zhǎng)為μ 即可得到新節(jié)點(diǎn)坐標(biāo):
Px =Pn. x +αcos θ+μcos γ , (3)
Py =Pn. y +αsin θ+μsin γ 。(4)
通過(guò)此方法得到的所有新節(jié)點(diǎn)都會(huì)受到來(lái)自目標(biāo)點(diǎn)的吸引力,因此能夠解決隨機(jī)生成的節(jié)點(diǎn)過(guò)于偏離最終目的點(diǎn)的問(wèn)題,并且解決了RRT 算法存在大量冗余節(jié)點(diǎn)的問(wèn)題,在任何環(huán)境中進(jìn)行路徑規(guī)劃時(shí)能夠更快更穩(wěn)定地得到一條可行的路徑。
2. 2 結(jié)合貪心算法剪枝優(yōu)化冗余路徑
RRT 算法最終規(guī)劃得出的路徑均由隨機(jī)節(jié)點(diǎn)組成,且由于擴(kuò)展步長(zhǎng)的限制,路徑彎折,同時(shí)存在許多冗余節(jié)點(diǎn)和轉(zhuǎn)折點(diǎn),如圖4 所示,不符合無(wú)人機(jī)真實(shí)飛行時(shí)的軌跡,因此對(duì)路徑進(jìn)行剪枝優(yōu)化處理是非常有必要的。本小節(jié)將采用貪心算法對(duì)前文中結(jié)合引力函數(shù)后的算法規(guī)劃得出的路徑進(jìn)行剪枝優(yōu)化。
以目標(biāo)點(diǎn)Pg 為頭節(jié)點(diǎn),選擇其父節(jié)點(diǎn)P6 作為當(dāng)前節(jié)點(diǎn),連接兩點(diǎn)。利用障礙物檢測(cè)函數(shù)檢測(cè)兩節(jié)點(diǎn)連線路徑上是否會(huì)遇到障礙物,如果未遇到障礙物,則對(duì)下一個(gè)父節(jié)點(diǎn)P5 繼續(xù)進(jìn)行上述判斷,直到與起始點(diǎn)Ps 連接。如果兩節(jié)點(diǎn)連線路徑上有障礙物,則將上一個(gè)父節(jié)點(diǎn)P6 與頭節(jié)點(diǎn)Pg 連接,并將節(jié)點(diǎn)P6 作為新的頭節(jié)點(diǎn)重復(fù)上述判斷直到與Ps 連接。此時(shí)連接形成的新的路徑就是經(jīng)過(guò)貪心算法剪枝優(yōu)化后的路徑,如圖5 所示,其中黑色虛線為剪枝優(yōu)化前的路徑,紅色實(shí)線為經(jīng)過(guò)貪心算法剪枝優(yōu)化后的路徑。
2. 3 結(jié)合3 次B 樣條曲線擬合轉(zhuǎn)折點(diǎn)
經(jīng)過(guò)剪枝處理后的改進(jìn)RRT 算法所得路徑仍然存在曲率突變的轉(zhuǎn)折點(diǎn),圖5 中的P4 節(jié)點(diǎn)不符合無(wú)人機(jī)的實(shí)際飛行軌跡,會(huì)降低無(wú)人機(jī)的運(yùn)行效率與穩(wěn)定性。B 樣條曲線具有很好的連續(xù)性,不僅結(jié)合了Bezier 方法幾何不變性、仿射不變性等優(yōu)點(diǎn),同時(shí)彌補(bǔ)了Bezier 方法不具有局部性質(zhì)的缺陷,該曲線函數(shù)在路徑規(guī)劃中被廣泛地使用。為了提高無(wú)人機(jī)的運(yùn)行效率和運(yùn)行穩(wěn)定性,本節(jié)將采用3 次B 樣條曲線對(duì)所得路徑曲率突變問(wèn)題進(jìn)行平滑處理。
設(shè)有P0、P1、P2、…、Pn 共n+1 個(gè)控制點(diǎn),這些點(diǎn)能夠確定B 樣條曲線的形狀和范圍,k 階B 樣條曲線的定義可以通過(guò)控制點(diǎn)與基函數(shù)相乘的多項(xiàng)式形式來(lái)表達(dá):
式中:Bi,k(x)為B 樣條基函數(shù),i 表示個(gè)數(shù),k 為階數(shù),k≥1,對(duì)應(yīng)的控制點(diǎn)為Pi,x 為自變量。基函數(shù)Bi,k(x)的Cox-deBoor 遞推式如下:
式中:xi 為一組非遞減序列的連續(xù)變化值,序列為xi,xi+1,…,xi+k,其節(jié)點(diǎn)矢量集合的元素的首尾值為0 和1,同時(shí)區(qū)間[xi,xi+k ]定義為基函數(shù)的支撐區(qū)間。
在曲線方程中,n+1 個(gè)控制點(diǎn)Pi 對(duì)應(yīng)n+1 個(gè)基函數(shù)Bi,k(x),其節(jié)點(diǎn)集合為Z = [x0,x1,…,xn,…,xn+k]。設(shè)起始點(diǎn)與目標(biāo)點(diǎn)的重復(fù)度為k,使曲線方程滿足起始點(diǎn)和目標(biāo)點(diǎn)的約束時(shí)的節(jié)點(diǎn)矢量滿足以下條件:
為保證B 樣條曲線與控制點(diǎn)所形成的直線呈相切關(guān)系,需要對(duì)部分控制點(diǎn)進(jìn)行調(diào)整,以確保節(jié)點(diǎn)矢量滿足xi-k,xi-k+1 =xi-k+2 =… =xi-1 =xi,xi+k 共線。
一般來(lái)說(shuō),B 樣條曲線的階數(shù)越高,其導(dǎo)數(shù)的次數(shù)也會(huì)相應(yīng)增加,導(dǎo)致零點(diǎn)數(shù)量增多,這可能使得曲線出現(xiàn)較多的峰谷;反之,階數(shù)越低時(shí),曲線能夠更有效地逼近控制點(diǎn)。3 次B 樣條曲線能夠?qū)崿F(xiàn)二階導(dǎo)數(shù)的連續(xù)性,本文經(jīng)過(guò)多次實(shí)驗(yàn)分析確認(rèn)3 次B樣條曲線對(duì)于路徑轉(zhuǎn)折點(diǎn)的擬合效果較好,故選擇3 次B 樣條曲線用以擬合轉(zhuǎn)折點(diǎn)曲率突變。
2. 4 改進(jìn)RRT 算法偽代碼
改進(jìn)RRT 算法偽代碼如算法1 所示。
算法1 中RANDOM 函數(shù)表示生成隨機(jī)采樣點(diǎn),NEAREST 函數(shù)表示為當(dāng)前節(jié)點(diǎn)找到隨機(jī)樹(shù)中距離最近的父節(jié)點(diǎn),ATTRACT 函數(shù)表示結(jié)合引力函數(shù)生成新節(jié)點(diǎn),OBS_NOT_FREE 函數(shù)表示判斷節(jié)點(diǎn)間是否存在障礙物,NEW_STATE 函數(shù)表示將新節(jié)點(diǎn)與父節(jié)點(diǎn)距離設(shè)置為拓展步長(zhǎng),add_node 函數(shù)表示將新節(jié)點(diǎn)加入隨機(jī)樹(shù)中,PRUNE 函數(shù)表示使用貪心算法對(duì)路徑節(jié)點(diǎn)集合進(jìn)行剪枝優(yōu)化,B-Spline Curve 函數(shù)表示使用B 樣條曲線擬合路徑轉(zhuǎn)折點(diǎn)。
3 改進(jìn)RRT 算法仿真與分析
為了驗(yàn)證改進(jìn)后的RRT 算法的有效性和高效性,在仿真軟件中設(shè)計(jì)了狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景進(jìn)行仿真,對(duì)A、RRT 與改進(jìn)RRT 規(guī)劃所得路徑進(jìn)行對(duì)比分析。實(shí)驗(yàn)中將無(wú)人機(jī)視為一個(gè)質(zhì)點(diǎn),考慮到無(wú)人機(jī)的真實(shí)體積,即使規(guī)劃路徑與障礙物沒(méi)有接觸,仍有可能發(fā)生碰撞,因此對(duì)障礙物進(jìn)行膨化處理,將障礙物外圍一層自由空間也視為障礙物區(qū)域。
3. 1 仿真驗(yàn)證
狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景仿真時(shí)的主要參數(shù)設(shè)置如表1 和表2 所示,A*、RRT 與改進(jìn)RRT算法的仿真結(jié)果對(duì)比如圖6 和圖7 所示。其中,圖6(b)和圖7(b)中紅色曲線為改進(jìn)RRT 算法最終規(guī)劃路徑,綠色曲線為RRT 算法結(jié)合引力函數(shù)規(guī)劃路徑,藍(lán)色曲線為RRT 算法結(jié)合引力函數(shù)與貪心算法剪枝優(yōu)化后路徑;圖6(c)和圖7(c)中紅色曲線為A* 算法規(guī)劃路徑,藍(lán)色區(qū)域?yàn)橐?guī)劃過(guò)程探索的區(qū)域可等效為RRT 算法的節(jié)點(diǎn)。
由圖6 和圖7 仿真結(jié)果對(duì)比可見(jiàn),改進(jìn)RRT 算法相對(duì)于RRT 算法搜索能力大幅度提升,冗余節(jié)點(diǎn)大量減少,避障能力大幅提升,通過(guò)狹窄通道能力大幅提升,且與A 算法對(duì)比可見(jiàn)RRT 算法規(guī)劃所得路徑更具平滑性,符合無(wú)人機(jī)飛行的實(shí)際要求,確保了無(wú)人機(jī)的穩(wěn)定性。
3. 2 數(shù)據(jù)分析
由于RRT 算法具有隨機(jī)性,因此對(duì)每種場(chǎng)景進(jìn)行50 次路徑規(guī)劃仿真,對(duì)A*、RRT 和改進(jìn)RRT 算法得到的仿真結(jié)果進(jìn)行數(shù)據(jù)統(tǒng)計(jì),其中每個(gè)指標(biāo)的結(jié)果均為平均數(shù)值,仿真數(shù)據(jù)如表3 和表4 所示。
根據(jù)表3 和表4,將狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景下仿真數(shù)據(jù)綜合分析可知:狹窄通道場(chǎng)景下改進(jìn)RRT 算法總節(jié)點(diǎn)數(shù)量為709,平均規(guī)劃時(shí)間為6. 82 s;相較于RRT 算法,總節(jié)點(diǎn)數(shù)量減少了30. 07% ,平均規(guī)劃時(shí)間減少了49. 44% ;相較于A*算法,總節(jié)點(diǎn)數(shù)量減少了81. 22% ,平均規(guī)劃時(shí)間減少了80. 23% 。復(fù)雜障礙物場(chǎng)景下改進(jìn)RRT 算法總節(jié)點(diǎn)數(shù)量為654,平均規(guī)劃時(shí)間為7. 62 s;相較于RRT 算法,總節(jié)點(diǎn)數(shù)量減少了24. 48% ,平均規(guī)劃時(shí)間減少了17. 97% ;相較于A* 算法,總節(jié)點(diǎn)數(shù)量減少了6. 84% ,平均規(guī)劃時(shí)間減少了52. 93% 。值得注意的是,RRT 算法在狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景下都有路徑規(guī)劃失?。ǚ抡鎸?shí)驗(yàn)中將規(guī)劃時(shí)間超過(guò)30 s 的案例視為失敗)的案例,其中在狹窄通道場(chǎng)景出現(xiàn)了9 次失敗,在復(fù)雜障礙物場(chǎng)景出現(xiàn)了兩次失?。欢?算法與改進(jìn)RRT 算法均沒(méi)有出現(xiàn)失敗的情況。根據(jù)上述分析可知,改進(jìn)RRT 算法在各項(xiàng)指標(biāo)上都得到了顯著提升。
4 結(jié)束語(yǔ)
本文提出了一種改進(jìn)RRT 算法,解決了傳統(tǒng)RRT 算法在狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景中進(jìn)行路徑規(guī)劃時(shí)搜索隨機(jī)性高、存在冗余路徑以及平滑性差的問(wèn)題。通過(guò)兩種路徑規(guī)劃算法在狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景的路徑規(guī)劃分析與對(duì)比,證明了改進(jìn)RRT 算法的可行性和有效性。仿真結(jié)果表明,改進(jìn)RRT 算法不僅很大程度減少了平均規(guī)劃時(shí)間和路徑規(guī)劃失敗的可能性,而且規(guī)劃所得的路徑更短、更為平緩,適合無(wú)人機(jī)在真實(shí)環(huán)境中飛行。雖然本文提出的改進(jìn)RRT 算法在仿真中表現(xiàn)優(yōu)秀,但尚未將其使用于真實(shí)壞境中,后續(xù)將會(huì)在真實(shí)無(wú)人機(jī)的路徑規(guī)劃中驗(yàn)證其性能與可行性。
參考文獻(xiàn)
[1] 鄭好,馮虢靚雯,蒲文杰,等. 基于Dijkstra 算法的封閉環(huán)境全局路徑規(guī)劃[J]. 汽車實(shí)用技術(shù),2023,48(16):7-11.
[2] 陳龍,鄭祥盤(pán),唐曉騰. 基于遺傳算法的移動(dòng)機(jī)器人全覆蓋路徑規(guī)劃研究[J]. 閩江學(xué)院學(xué)報(bào),2023,44(5):18-27.
[3] 徐小強(qiáng),楊家鼎,冒燕,等. 基于速度障礙和改進(jìn)人工勢(shì)場(chǎng)算法的無(wú)人艇路徑規(guī)劃研究[J]. 武漢理工大學(xué)學(xué)報(bào),2022,44(7):96-102.
[4] 智瀚宇,賈新春,張學(xué)立. 無(wú)人機(jī)路徑規(guī)劃:一種粒子群和灰狼復(fù)合算法[J/ OL]. 控制工程:1-8(2023-11-28)[2024-04-24]. https:∥doi. org/10. 14107 / j. cnki.kzgc. 20221058.
[5] 白瑋,王成,王彩玲,等. 基于蟻群數(shù)量動(dòng)態(tài)調(diào)整的改進(jìn)蟻群優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用,2023,43 (S1):163-168.
[6] 王超,王銀花. 一種改進(jìn)Dijkstra 算法的UAV 路徑規(guī)劃[J]. 信息技術(shù)與信息化,2021(10):217-219.
[7] 陳俠,毛海亮,劉奎武. 基于改進(jìn)自適應(yīng)蟻群算法的無(wú)人機(jī)航跡規(guī)劃研究[J]. 電光與控制,2022,29 (9):6-10.
[8] 郭華,郭小和. 改進(jìn)速度障礙法的無(wú)人機(jī)局部路徑規(guī)劃算法[J]. 航空學(xué)報(bào),2023,44(11):271-281.
[9] 張學(xué)偉,田鯢苓,魯瀚辰,等. 面向復(fù)雜未知多障礙環(huán)境的多無(wú)人機(jī)分布式在線軌跡規(guī)劃[J]. 中國(guó)科學(xué):信息科學(xué),2022,52(9):1627-1641.
[10]辛鵬,王艷輝,劉曉立,等. 優(yōu)化改進(jìn)RRT 和人工勢(shì)場(chǎng)法的路徑規(guī)劃算法[J]. 計(jì)算機(jī)集成制造系統(tǒng),2023,29(9):2899-2907.
[11]LIU T,WANG X Y,KANG Z Q. Path Planning Using Ant Colony Based Environment Partition Targetbiased RRT Algorithm[J]. Journal of Measurement Science and In-strumentation,2023,14(1):55-65.
[12]YANG F,FANG X,GAO F,et al. Obstacle Avoidance Path Planning for UAV Based on Improved RRT Algorithm [J]. Discrete Dynamics in Nature and Society,2022,2022:4544499.
[13]HUANG G H,MA Q L. Research on Path Planning Algo-rithm of Autonomous Vehicles Based on Improved RRT Algorithm[J]. International Journal of Intelligent Trans-portation Systems Research,2021,20:170-180.
[14]HUANG S Y. Path Planning Based on Mixed Algorithm of RRT and Artificial Potential Field Method[C]∥2021 4th International Conference on Intelligent Robotics and Control Engineering(IRCE). Lanzhou:IEEE,2021:149-155.
[15]杜傳勝,高煥兵,侯宇翔,等. 同根雙向擴(kuò)展的貪心RRT 路徑規(guī)劃算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2023,59(21):312-318.
[16]劉夢(mèng)奇,王維強(qiáng),田良宇. 基于B 樣條曲線的無(wú)人駕駛車輛Informed RRT 算法研究[J]. 智能計(jì)算機(jī)與應(yīng)用,2022,12(4):25-29.
[17]鄭滋,楊圣慧,鄭永軍,等. 多旋翼無(wú)人機(jī)避障航跡規(guī)劃算法[J]. 農(nóng)業(yè)工程學(xué)報(bào),2020,36(23):59-69.
[18]周蘭鳳,孔明月. 基于改進(jìn)人工勢(shì)場(chǎng)法的無(wú)人機(jī)三維避障[J]. 華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2022(6):54-67.
作者簡(jiǎn)介:
顧秋逸 男,(1999—),碩士研究生。主要研究方向:ROS 無(wú)人機(jī)集群控制。
李大鵬 男,(1982—),博士,教授。主要研究方向:無(wú)線通信、移動(dòng)自組織網(wǎng)絡(luò)。