基于改進(jìn)ＲＲＴ 算法的無(wú)人機(jī)路徑規(guī)劃

摘 要：無(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ù)（Ｒａｐｉｄｌｙ-ｅｘｐｌｏｒｉｎｇ Ｒａｎｄｏｍ Ｔｒｅｅ，ＲＲＴ）算法進(jìn)行無(wú)人機(jī)路徑規(guī)劃時(shí)搜索隨機(jī)性高、存在冗余路徑和路徑平滑性差的問(wèn)題，提出了一種面向無(wú)人機(jī)路徑規(guī)劃的改進(jìn)ＲＲＴ 算法。改進(jìn)ＲＲＴ算法在ＲＲＴ 算法的基礎(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é)合Ｂ 樣條曲線對(duì)路徑進(jìn)行平滑性處理，去除曲率突變的轉(zhuǎn)折點(diǎn)，形成一條平滑的適合無(wú)人機(jī)實(shí)際飛行的路徑。通過(guò)仿真軟件對(duì)Ａ* 算法、傳統(tǒng)ＲＲＴ 算法與改進(jìn)ＲＲＴ 算法進(jìn)行對(duì)比分析，仿真結(jié)果表明，提出的改進(jìn)ＲＲＴ 算法性能更高，在狹窄通道場(chǎng)景與復(fù)雜障礙物場(chǎng)景下相比于傳統(tǒng)ＲＲＴ 算法平均規(guī)劃時(shí)間各減少４９． ４４％ 和１７． ９７％ ，相比于Ａ* 算法平均規(guī)劃時(shí)間各減少了８０． ２３％ 和５２． ９３％ ，得到的路徑更短更為平緩，同時(shí)大幅降低了ＲＲＴ 算法路徑規(guī)劃失敗的可能性，驗(yàn)證了改進(jìn)ＲＲＴ 算法的可行性與有效性，解決了原算法隨機(jī)性高、存在冗余路徑和平滑性差的問(wèn)題。

關(guān)鍵詞：無(wú)人機(jī)；路徑規(guī)劃；改進(jìn)快速擴(kuò)展隨機(jī)樹(shù)算法；快速擴(kuò)展隨機(jī)樹(shù)算法；Ａ*算法；引力函數(shù)

中圖分類號(hào)：ＴＮ９１９． ２３ 文獻(xiàn)標(biāo)志碼：Ａ 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（ＯＳＩＤ）：

文章編號(hào)：１００３－３１１４（２０２４）０６－１１８４－０８

０ 引言

路徑規(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)題。例如Ｄｉｊｋｓｔｒａ算法［１］作為一種最短路徑算法，具有全局最優(yōu)性；遺傳算法［２］基于生物進(jìn)化論，通過(guò)選擇、交叉和變異的操作尋找全局最優(yōu)解；快速擴(kuò)展隨機(jī)樹(shù)（Ｒａｐｉｄｌｙ-ｅｘｐｌｏｒｉｎｇ Ｒａｎｄｏｍ Ｔｒｅｅ，ＲＲＴ）算法則利用隨機(jī)采樣快速探索高維空間中的可行路徑以及人工勢(shì)場(chǎng)法、速度障礙法［３］、粒子群算法［４］、Ａ* 算法、蟻群優(yōu)化（Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）算法［５］等，這些經(jīng)典算法在無(wú)人機(jī)路徑規(guī)劃中起到了重要的基底作用。文獻(xiàn)［６］運(yùn)用了Ｄｉｊｋｓｔｒａ 和紅外檢測(cè)合成的算法，使無(wú)人機(jī)能有效地避開(kāi)所有的障礙物，解決了局部離障礙物過(guò)近的問(wèn)題。文獻(xiàn)［７］提出了一種基于改進(jìn)自適應(yīng)蟻群（Ｉｍｐｒｏｖｅｄ Ａｄａｐｔｉｖｅ Ａｎｔ ＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎ，ＩＡＡＣＯ）算法的路徑規(guī)劃算法以解決傳統(tǒng)ＡＣＯ 算法存在的收斂速度慢、易陷入局部最優(yōu)等不足，同時(shí)規(guī)劃出的路徑更平滑、長(zhǎng)度更短。文獻(xiàn)［８］提出一種基于改進(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)［９］提出了基于管道模型預(yù)測(cè)控制（Ｔｕｂｅ-Ｍｏｄｅｌ ＰｒｅｄｉｃｔｉｖｅＣｏｎｔｒｏｌ，Ｔｕｂｅ-ＭＰＣ）和模型預(yù)測(cè)路徑積分（ＭｏｄｅｌＰｒｅｄｉｃｔｉｖｅ Ｐａｔｈ Ｉｎｔｅｇｒａｌ，ＭＰＰＩ）融合的多無(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ì)ＲＲＴ 算法的收斂速度慢、路徑曲折等問(wèn)題，研究者進(jìn)行了不同的優(yōu)化處理。文獻(xiàn)［１０］針對(duì)隨機(jī)樹(shù)擴(kuò)展時(shí)隨機(jī)性較大的問(wèn)題，加入人工勢(shì)場(chǎng)法約束，使得隨機(jī)樹(shù)偏向目標(biāo)點(diǎn)生長(zhǎng)，優(yōu)化了路徑。文獻(xiàn)［１１］針對(duì)ＲＲＴ 算法在路徑規(guī)劃中可能遇到的隨機(jī)性大、搜索時(shí)間長(zhǎng)、路徑曲折等問(wèn)題，提出了一種基于環(huán)境分區(qū)的蟻群優(yōu)化目標(biāo)偏差ＲＲＴ 算法，有效地消除了無(wú)用節(jié)點(diǎn)，減少了規(guī)劃時(shí)間。文獻(xiàn)［１２］提出了一種改進(jìn)的ＲＲＴ 算法，在擴(kuò)展隨機(jī)樹(shù)的過(guò)程中，引入ＡＣＯ 算法。優(yōu)化后的算法可以在ＲＲＴ 得到的路徑上設(shè)置信息素，并根據(jù)信息素濃度選擇下一個(gè)擴(kuò)展點(diǎn)。文獻(xiàn)［１３］提出了一種基于ＲＲＴ 算法的改進(jìn)路徑規(guī)劃算法，采用循環(huán)采樣策略提高采樣效率，設(shè)計(jì)了一種基于代價(jià)函數(shù)的擴(kuò)展隨機(jī)點(diǎn)規(guī)則來(lái)過(guò)濾隨機(jī)點(diǎn)。文獻(xiàn)［１４］針對(duì)ＲＲＴ 算法采樣隨機(jī)、效率低的問(wèn)題，提出了一種結(jié)合人工勢(shì)場(chǎng)法的改進(jìn)算法。在基本ＲＲＴ 算法的隨機(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ì)ＲＲＴ算法進(jìn)行了改進(jìn)，但改進(jìn)后的算法仍存在搜索隨機(jī)性高、存在冗余路徑和平滑性差的問(wèn)題。本文提出的改進(jìn)ＲＲＴ 算法是在ＲＲＴ 算法的基礎(chǔ)上首先結(jié)合人工勢(shì)場(chǎng)法中的引力函數(shù)使得隨機(jī)節(jié)點(diǎn)的產(chǎn)生具有導(dǎo)向性和目的性，從而減小了搜索隨機(jī)性；然后結(jié)合貪心算法［１５］對(duì)規(guī)劃所得路徑上的轉(zhuǎn)折點(diǎn)進(jìn)行剪枝優(yōu)化，去除了無(wú)用的冗余節(jié)點(diǎn)，減少了路徑上的轉(zhuǎn)折點(diǎn)，同時(shí)縮短了整體路徑長(zhǎng)度；最后采用３ 次Ｂ 樣條曲線擬合［１６］對(duì)剪枝后的路徑進(jìn)行平滑性處理，從而能夠生成一條路徑平滑的適合無(wú)人機(jī)實(shí)際飛行的路徑。

１ 系統(tǒng)模型和問(wèn)題描述

１． １ 系統(tǒng)模型

在進(jìn)行無(wú)人機(jī)路徑規(guī)劃前，首先需要建立一個(gè)無(wú)人機(jī)坐標(biāo)系統(tǒng)，然后將無(wú)人機(jī)各傳感器的信息傳遞到坐標(biāo)系統(tǒng)中，最后建立創(chuàng)建地圖所需的柵格地圖［１７］模型。

本文將無(wú)人機(jī)視為二維柵格地圖上的質(zhì)點(diǎn)，無(wú)人機(jī)的位置用柵格地圖的坐標(biāo)表示，Ｐｓ 表示無(wú)人機(jī)的起點(diǎn)，Ｐｇ 表示目標(biāo)點(diǎn)，如圖１ 所示。

柵格地圖模型將無(wú)人機(jī)飛行環(huán)境用若干連續(xù)的相同柵格表示，用兩種狀態(tài)表示環(huán)境中的可通行區(qū)域和障礙物區(qū)域。圖１ 中空白柵格表示無(wú)人機(jī)可以通過(guò)的空曠區(qū)域Ｐｆｒｅｅ，黑色柵格表示無(wú)人機(jī)不可以通過(guò)的障礙物區(qū)域。

１． ２ ＲＲＴ 算法原理和模型

ＲＲＴ 算法的搜索過(guò)程可以看作是樹(shù)的樹(shù)枝不斷生長(zhǎng)、朝四周擴(kuò)展的過(guò)程。本文ＲＲＴ 算法以路徑起始點(diǎn)Ｐｓ 作為隨機(jī)樹(shù)Ｔ 的根節(jié)點(diǎn)，樹(shù)中節(jié)點(diǎn)Ｐｉ 用集合存儲(chǔ)，所有節(jié)點(diǎn)滿足Ｐｉ∈Ｐｆｒｅｅ，并設(shè)定整體隨機(jī)樹(shù)的最大迭代次數(shù)為Ｍ。在搜索過(guò)程中，隨機(jī)在空曠區(qū)域Ｐｆｒｅｅ 生成新節(jié)點(diǎn)，以引導(dǎo)樹(shù)的生長(zhǎng)方向，當(dāng)樹(shù)的某個(gè)葉子節(jié)點(diǎn)擴(kuò)展到目標(biāo)點(diǎn)Ｐｇ 時(shí)，ＲＲＴ 算法完成整個(gè)整個(gè)區(qū)域的搜索，并返回從目標(biāo)點(diǎn)到根節(jié)點(diǎn)之間的可行路徑連線。

ＲＲＴ 算法迭代模型如圖２ 所示，其每輪迭代中主要包含以下流程：

① 灰色點(diǎn)Ｐｒ 為ＲＡＮＤＯＭ 函數(shù)生成的隨機(jī)采樣點(diǎn)，其ｘ 和ｙ 軸坐標(biāo)分別為Ｍａｐ． ｘ·ＲＡＮＤＯＭ（１）和Ｍａｐ． ｙ·ＲＡＮＤＯＭ（１）。

② 遍歷當(dāng)前隨機(jī)樹(shù)為Ｐｒ 找到距離最近的父節(jié)點(diǎn)，遍歷Ｐｒ 和其父節(jié)點(diǎn)間的路徑，判斷是否存在障礙物，若存在則Ｐｒ 不可作為隨機(jī)樹(shù)節(jié)點(diǎn)。

③ 若Ｐｒ 符合以上條件，在Ｐｒ 與父節(jié)點(diǎn)間建立拓展步長(zhǎng)為ｕ 的新節(jié)點(diǎn)｛Ｐ１，Ｐ２，…，Ｐｎ｝并加入隨機(jī)樹(shù)Ｔ。

１． ３ 問(wèn)題描述

從前文可以得知ＲＲＴ 算法具有參數(shù)少、結(jié)構(gòu)簡(jiǎn)單、搜索能力強(qiáng)的優(yōu)點(diǎn)，然而從圖２ 迭代模型以及流程中也可以得知，當(dāng)ＲＲＴ 算法的起始隨機(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)ＲＲＴ 算法以解決ＲＲＴ 算法采樣隨機(jī)性較大、路徑冗長(zhǎng)、路徑不平滑的問(wèn)題。

２ 改進(jìn)ＲＲＴ 算法

２． １ 結(jié)合引力函數(shù)優(yōu)化搜索隨機(jī)性

本小節(jié)將結(jié)合人工勢(shì)場(chǎng)法［１８］中引力勢(shì)場(chǎng)函數(shù)來(lái)解決ＲＲＴ 算法中節(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āng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的歐式距離。

式中：λ 為斥力系數(shù)，Ｄ０ 為障礙物斥力影響的范圍，當(dāng)距離大于Ｄ０ 時(shí)，障礙物的斥力對(duì)當(dāng)前節(jié)點(diǎn)不再具有影響。

新節(jié)點(diǎn)的生成過(guò)程如圖３ 所示。

圖３ 中，Ｐｒ 為隨機(jī)生成的新節(jié)點(diǎn)，Ｐｎ 為距離Ｐｒ最近的父節(jié)點(diǎn)，Ｐｎ＋１ 為Ｐｒ 加入引力函數(shù)后生成的拓展步長(zhǎng)為μ 的新節(jié)點(diǎn)，α 為引力系數(shù)。

加入引力函數(shù)生成的節(jié)點(diǎn)的坐標(biāo)見(jiàn)式（３）和式（４），再取距離Ｐｎ 拓展步長(zhǎng)為μ 即可得到新節(jié)點(diǎn)坐標(biāo)：

Ｐｘ ＝Ｐｎ． ｘ ＋αｃｏｓ θ＋μｃｏｓ γ ， （３）

Ｐｙ ＝Ｐｎ． ｙ ＋αｓｉｎ θ＋μｓｉｎ γ 。（４）

通過(guò)此方法得到的所有新節(jié)點(diǎn)都會(huì)受到來(lái)自目標(biāo)點(diǎn)的吸引力，因此能夠解決隨機(jī)生成的節(jié)點(diǎn)過(guò)于偏離最終目的點(diǎn)的問(wèn)題，并且解決了ＲＲＴ 算法存在大量冗余節(jié)點(diǎn)的問(wèn)題，在任何環(huán)境中進(jìn)行路徑規(guī)劃時(shí)能夠更快更穩(wěn)定地得到一條可行的路徑。

２． ２ 結(jié)合貪心算法剪枝優(yōu)化冗余路徑

ＲＲＴ 算法最終規(guī)劃得出的路徑均由隨機(jī)節(jié)點(diǎn)組成，且由于擴(kuò)展步長(zhǎng)的限制，路徑彎折，同時(shí)存在許多冗余節(jié)點(diǎn)和轉(zhuǎn)折點(diǎn)，如圖４ 所示，不符合無(wú)人機(jī)真實(shí)飛行時(shí)的軌跡，因此對(duì)路徑進(jìn)行剪枝優(yōu)化處理是非常有必要的。本小節(jié)將采用貪心算法對(duì)前文中結(jié)合引力函數(shù)后的算法規(guī)劃得出的路徑進(jìn)行剪枝優(yōu)化。

以目標(biāo)點(diǎn)Ｐｇ 為頭節(jié)點(diǎn)，選擇其父節(jié)點(diǎn)Ｐ６ 作為當(dāng)前節(jié)點(diǎn)，連接兩點(diǎn)。利用障礙物檢測(cè)函數(shù)檢測(cè)兩節(jié)點(diǎn)連線路徑上是否會(huì)遇到障礙物，如果未遇到障礙物，則對(duì)下一個(gè)父節(jié)點(diǎn)Ｐ５ 繼續(xù)進(jìn)行上述判斷，直到與起始點(diǎn)Ｐｓ 連接。如果兩節(jié)點(diǎn)連線路徑上有障礙物，則將上一個(gè)父節(jié)點(diǎn)Ｐ６ 與頭節(jié)點(diǎn)Ｐｇ 連接，并將節(jié)點(diǎn)Ｐ６ 作為新的頭節(jié)點(diǎn)重復(fù)上述判斷直到與Ｐｓ 連接。此時(shí)連接形成的新的路徑就是經(jīng)過(guò)貪心算法剪枝優(yōu)化后的路徑，如圖５ 所示，其中黑色虛線為剪枝優(yōu)化前的路徑，紅色實(shí)線為經(jīng)過(guò)貪心算法剪枝優(yōu)化后的路徑。

２． ３ 結(jié)合３ 次Ｂ 樣條曲線擬合轉(zhuǎn)折點(diǎn)

經(jīng)過(guò)剪枝處理后的改進(jìn)ＲＲＴ 算法所得路徑仍然存在曲率突變的轉(zhuǎn)折點(diǎn)，圖５ 中的Ｐ４ 節(jié)點(diǎn)不符合無(wú)人機(jī)的實(shí)際飛行軌跡，會(huì)降低無(wú)人機(jī)的運(yùn)行效率與穩(wěn)定性。Ｂ 樣條曲線具有很好的連續(xù)性，不僅結(jié)合了Ｂｅｚｉｅｒ 方法幾何不變性、仿射不變性等優(yōu)點(diǎn)，同時(shí)彌補(bǔ)了Ｂｅｚｉｅｒ 方法不具有局部性質(zhì)的缺陷，該曲線函數(shù)在路徑規(guī)劃中被廣泛地使用。為了提高無(wú)人機(jī)的運(yùn)行效率和運(yùn)行穩(wěn)定性，本節(jié)將采用３ 次Ｂ 樣條曲線對(duì)所得路徑曲率突變問(wèn)題進(jìn)行平滑處理。

設(shè)有Ｐ０、Ｐ１、Ｐ２、…、Ｐｎ 共ｎ＋１ 個(gè)控制點(diǎn)，這些點(diǎn)能夠確定Ｂ 樣條曲線的形狀和范圍，ｋ 階Ｂ 樣條曲線的定義可以通過(guò)控制點(diǎn)與基函數(shù)相乘的多項(xiàng)式形式來(lái)表達(dá)：

式中：Ｂｉ，ｋ（ｘ）為Ｂ 樣條基函數(shù)，ｉ 表示個(gè)數(shù)，ｋ 為階數(shù)，ｋ≥１，對(duì)應(yīng)的控制點(diǎn)為Ｐｉ，ｘ 為自變量。基函數(shù)Ｂｉ，ｋ（ｘ）的Ｃｏｘ-ｄｅＢｏｏｒ 遞推式如下：

式中：ｘｉ 為一組非遞減序列的連續(xù)變化值，序列為ｘｉ，ｘｉ＋１，…，ｘｉ＋ｋ，其節(jié)點(diǎn)矢量集合的元素的首尾值為０ 和１，同時(shí)區(qū)間［ｘｉ，ｘｉ＋ｋ ］定義為基函數(shù)的支撐區(qū)間。

在曲線方程中，ｎ＋１ 個(gè)控制點(diǎn)Ｐｉ 對(duì)應(yīng)ｎ＋１ 個(gè)基函數(shù)Ｂｉ，ｋ（ｘ），其節(jié)點(diǎn)集合為Ｚ ＝ ［ｘ０，ｘ１，…，ｘｎ，…，ｘｎ＋ｋ］。設(shè)起始點(diǎn)與目標(biāo)點(diǎn)的重復(fù)度為ｋ，使曲線方程滿足起始點(diǎn)和目標(biāo)點(diǎn)的約束時(shí)的節(jié)點(diǎn)矢量滿足以下條件：

為保證Ｂ 樣條曲線與控制點(diǎn)所形成的直線呈相切關(guān)系，需要對(duì)部分控制點(diǎn)進(jìn)行調(diào)整，以確保節(jié)點(diǎn)矢量滿足ｘｉ－ｋ，ｘｉ－ｋ＋１ ＝ｘｉ－ｋ＋２ ＝… ＝ｘｉ－１ ＝ｘｉ，ｘｉ＋ｋ 共線。

一般來(lái)說(shuō)，Ｂ 樣條曲線的階數(shù)越高，其導(dǎo)數(shù)的次數(shù)也會(huì)相應(yīng)增加，導(dǎo)致零點(diǎn)數(shù)量增多，這可能使得曲線出現(xiàn)較多的峰谷；反之，階數(shù)越低時(shí)，曲線能夠更有效地逼近控制點(diǎn)。３ 次Ｂ 樣條曲線能夠?qū)崿F(xiàn)二階導(dǎo)數(shù)的連續(xù)性，本文經(jīng)過(guò)多次實(shí)驗(yàn)分析確認(rèn)３ 次Ｂ樣條曲線對(duì)于路徑轉(zhuǎn)折點(diǎn)的擬合效果較好，故選擇３ 次Ｂ 樣條曲線用以擬合轉(zhuǎn)折點(diǎn)曲率突變。

２． ４ 改進(jìn)ＲＲＴ 算法偽代碼

改進(jìn)ＲＲＴ 算法偽代碼如算法１ 所示。

算法１ 中ＲＡＮＤＯＭ 函數(shù)表示生成隨機(jī)采樣點(diǎn)，ＮＥＡＲＥＳＴ 函數(shù)表示為當(dāng)前節(jié)點(diǎn)找到隨機(jī)樹(shù)中距離最近的父節(jié)點(diǎn)，ＡＴＴＲＡＣＴ 函數(shù)表示結(jié)合引力函數(shù)生成新節(jié)點(diǎn)，ＯＢＳ＿ＮＯＴ＿ＦＲＥＥ 函數(shù)表示判斷節(jié)點(diǎn)間是否存在障礙物，ＮＥＷ＿ＳＴＡＴＥ 函數(shù)表示將新節(jié)點(diǎn)與父節(jié)點(diǎn)距離設(shè)置為拓展步長(zhǎng)，ａｄｄ＿ｎｏｄｅ 函數(shù)表示將新節(jié)點(diǎn)加入隨機(jī)樹(shù)中，ＰＲＵＮＥ 函數(shù)表示使用貪心算法對(duì)路徑節(jié)點(diǎn)集合進(jìn)行剪枝優(yōu)化，Ｂ-Ｓｐｌｉｎｅ Ｃｕｒｖｅ 函數(shù)表示使用Ｂ 樣條曲線擬合路徑轉(zhuǎn)折點(diǎn)。

３ 改進(jìn)ＲＲＴ 算法仿真與分析

為了驗(yàn)證改進(jìn)后的ＲＲＴ 算法的有效性和高效性，在仿真軟件中設(shè)計(jì)了狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景進(jìn)行仿真，對(duì)Ａ、ＲＲＴ 與改進(jìn)ＲＲＴ 規(guī)劃所得路徑進(jìn)行對(duì)比分析。實(shí)驗(yàn)中將無(wú)人機(jī)視為一個(gè)質(zhì)點(diǎn)，考慮到無(wú)人機(jī)的真實(shí)體積，即使規(guī)劃路徑與障礙物沒(méi)有接觸，仍有可能發(fā)生碰撞，因此對(duì)障礙物進(jìn)行膨化處理，將障礙物外圍一層自由空間也視為障礙物區(qū)域。

３． １ 仿真驗(yàn)證

狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景仿真時(shí)的主要參數(shù)設(shè)置如表１ 和表２ 所示，Ａ*、ＲＲＴ 與改進(jìn)ＲＲＴ算法的仿真結(jié)果對(duì)比如圖６ 和圖７ 所示。其中，圖６（ｂ）和圖７（ｂ）中紅色曲線為改進(jìn)ＲＲＴ 算法最終規(guī)劃路徑，綠色曲線為ＲＲＴ 算法結(jié)合引力函數(shù)規(guī)劃路徑，藍(lán)色曲線為ＲＲＴ 算法結(jié)合引力函數(shù)與貪心算法剪枝優(yōu)化后路徑；圖６（ｃ）和圖７（ｃ）中紅色曲線為Ａ* 算法規(guī)劃路徑，藍(lán)色區(qū)域?yàn)橐?guī)劃過(guò)程探索的區(qū)域可等效為ＲＲＴ 算法的節(jié)點(diǎn)。

由圖６ 和圖７ 仿真結(jié)果對(duì)比可見(jiàn)，改進(jìn)ＲＲＴ 算法相對(duì)于ＲＲＴ 算法搜索能力大幅度提升，冗余節(jié)點(diǎn)大量減少，避障能力大幅提升，通過(guò)狹窄通道能力大幅提升，且與Ａ 算法對(duì)比可見(jiàn)ＲＲＴ 算法規(guī)劃所得路徑更具平滑性，符合無(wú)人機(jī)飛行的實(shí)際要求，確保了無(wú)人機(jī)的穩(wěn)定性。

３． ２ 數(shù)據(jù)分析

由于ＲＲＴ 算法具有隨機(jī)性，因此對(duì)每種場(chǎng)景進(jìn)行５０ 次路徑規(guī)劃仿真，對(duì)Ａ*、ＲＲＴ 和改進(jìn)ＲＲＴ 算法得到的仿真結(jié)果進(jìn)行數(shù)據(jù)統(tǒng)計(jì)，其中每個(gè)指標(biāo)的結(jié)果均為平均數(shù)值，仿真數(shù)據(jù)如表３ 和表４ 所示。

根據(jù)表３ 和表４，將狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景下仿真數(shù)據(jù)綜合分析可知：狹窄通道場(chǎng)景下改進(jìn)ＲＲＴ 算法總節(jié)點(diǎn)數(shù)量為７０９，平均規(guī)劃時(shí)間為６． ８２ ｓ；相較于ＲＲＴ 算法，總節(jié)點(diǎn)數(shù)量減少了３０． ０７％ ，平均規(guī)劃時(shí)間減少了４９． ４４％ ；相較于Ａ*算法，總節(jié)點(diǎn)數(shù)量減少了８１． ２２％ ，平均規(guī)劃時(shí)間減少了８０． ２３％ 。復(fù)雜障礙物場(chǎng)景下改進(jìn)ＲＲＴ 算法總節(jié)點(diǎn)數(shù)量為６５４，平均規(guī)劃時(shí)間為７． ６２ ｓ；相較于ＲＲＴ 算法，總節(jié)點(diǎn)數(shù)量減少了２４． ４８％ ，平均規(guī)劃時(shí)間減少了１７． ９７％ ；相較于Ａ* 算法，總節(jié)點(diǎn)數(shù)量減少了６． ８４％ ，平均規(guī)劃時(shí)間減少了５２． ９３％ 。值得注意的是，ＲＲＴ 算法在狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景下都有路徑規(guī)劃失?。ǚ抡鎸?shí)驗(yàn)中將規(guī)劃時(shí)間超過(guò)３０ ｓ 的案例視為失敗）的案例，其中在狹窄通道場(chǎng)景出現(xiàn)了９ 次失敗，在復(fù)雜障礙物場(chǎng)景出現(xiàn)了兩次失?。欢?算法與改進(jìn)ＲＲＴ 算法均沒(méi)有出現(xiàn)失敗的情況。根據(jù)上述分析可知，改進(jìn)ＲＲＴ 算法在各項(xiàng)指標(biāo)上都得到了顯著提升。

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

本文提出了一種改進(jìn)ＲＲＴ 算法，解決了傳統(tǒng)ＲＲＴ 算法在狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景中進(jìn)行路徑規(guī)劃時(shí)搜索隨機(jī)性高、存在冗余路徑以及平滑性差的問(wèn)題。通過(guò)兩種路徑規(guī)劃算法在狹窄通道場(chǎng)景和復(fù)雜障礙物場(chǎng)景的路徑規(guī)劃分析與對(duì)比，證明了改進(jìn)ＲＲＴ 算法的可行性和有效性。仿真結(jié)果表明，改進(jìn)ＲＲＴ 算法不僅很大程度減少了平均規(guī)劃時(shí)間和路徑規(guī)劃失敗的可能性，而且規(guī)劃所得的路徑更短、更為平緩，適合無(wú)人機(jī)在真實(shí)環(huán)境中飛行。雖然本文提出的改進(jìn)ＲＲＴ 算法在仿真中表現(xiàn)優(yōu)秀，但尚未將其使用于真實(shí)壞境中，后續(xù)將會(huì)在真實(shí)無(wú)人機(jī)的路徑規(guī)劃中驗(yàn)證其性能與可行性。

參考文獻(xiàn)

［１］ 鄭好，馮虢靚雯，蒲文杰，等． 基于Ｄｉｊｋｓｔｒａ 算法的封閉環(huán)境全局路徑規(guī)劃［Ｊ］． 汽車實(shí)用技術(shù)，２０２３，４８（１６）：７－１１．

［２］ 陳龍，鄭祥盤(pán)，唐曉騰． 基于遺傳算法的移動(dòng)機(jī)器人全覆蓋路徑規(guī)劃研究［Ｊ］． 閩江學(xué)院學(xué)報(bào)，２０２３，４４（５）：１８－２７．

［３］ 徐小強(qiáng)，楊家鼎，冒燕，等． 基于速度障礙和改進(jìn)人工勢(shì)場(chǎng)算法的無(wú)人艇路徑規(guī)劃研究［Ｊ］． 武漢理工大學(xué)學(xué)報(bào)，２０２２，４４（７）：９６－１０２．

［４］ 智瀚宇，賈新春，張學(xué)立． 無(wú)人機(jī)路徑規(guī)劃：一種粒子群和灰狼復(fù)合算法［Ｊ／ ＯＬ］． 控制工程：１－８（２０２３－１１－２８）［２０２４－０４－２４］． ｈｔｔｐｓ：∥ｄｏｉ． ｏｒｇ／１０． １４１０７ ／ ｊ． ｃｎｋｉ．ｋｚｇｃ． ２０２２１０５８．

［５］ 白瑋，王成，王彩玲，等． 基于蟻群數(shù)量動(dòng)態(tài)調(diào)整的改進(jìn)蟻群優(yōu)化算法［Ｊ］． 計(jì)算機(jī)應(yīng)用，２０２３，４３ （Ｓ１）：１６３－１６８．

［６］ 王超，王銀花． 一種改進(jìn)Ｄｉｊｋｓｔｒａ 算法的ＵＡＶ 路徑規(guī)劃［Ｊ］． 信息技術(shù)與信息化，２０２１（１０）：２１７－２１９．

［７］ 陳俠，毛海亮，劉奎武． 基于改進(jìn)自適應(yīng)蟻群算法的無(wú)人機(jī)航跡規(guī)劃研究［Ｊ］． 電光與控制，２０２２，２９ （９）：６－１０．

［８］ 郭華，郭小和． 改進(jìn)速度障礙法的無(wú)人機(jī)局部路徑規(guī)劃算法［Ｊ］． 航空學(xué)報(bào)，２０２３，４４（１１）：２７１－２８１．

［９］ 張學(xué)偉，田鯢苓，魯瀚辰，等． 面向復(fù)雜未知多障礙環(huán)境的多無(wú)人機(jī)分布式在線軌跡規(guī)劃［Ｊ］． 中國(guó)科學(xué)：信息科學(xué)，２０２２，５２（９）：１６２７－１６４１．

［１０］辛鵬，王艷輝，劉曉立，等． 優(yōu)化改進(jìn)ＲＲＴ 和人工勢(shì)場(chǎng)法的路徑規(guī)劃算法［Ｊ］． 計(jì)算機(jī)集成制造系統(tǒng)，２０２３，２９（９）：２８９９－２９０７．

［１１］ＬＩＵ Ｔ，ＷＡＮＧ Ｘ Ｙ，ＫＡＮＧ Ｚ Ｑ． Ｐａｔｈ Ｐｌａｎｎｉｎｇ Ｕｓｉｎｇ Ａｎｔ Ｃｏｌｏｎｙ Ｂａｓｅｄ Ｅｎｖｉｒｏｎｍｅｎｔ Ｐａｒｔｉｔｉｏｎ Ｔａｒｇｅｔｂｉａｓｅｄ ＲＲＴ Ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｍｅａｓｕｒｅｍｅｎｔ Ｓｃｉｅｎｃｅ ａｎｄ Ｉｎ-ｓｔｒｕｍｅｎｔａｔｉｏｎ，２０２３，１４（１）：５５－６５．

［１２］ＹＡＮＧ Ｆ，ＦＡＮＧ Ｘ，ＧＡＯ Ｆ，ｅｔ ａｌ． Ｏｂｓｔａｃｌｅ Ａｖｏｉｄａｎｃｅ Ｐａｔｈ Ｐｌａｎｎｉｎｇ ｆｏｒ ＵＡＶ Ｂａｓｅｄ ｏｎ Ｉｍｐｒｏｖｅｄ ＲＲＴ Ａｌｇｏｒｉｔｈｍ ［Ｊ］． Ｄｉｓｃｒｅｔｅ Ｄｙｎａｍｉｃｓ ｉｎ Ｎａｔｕｒｅ ａｎｄ Ｓｏｃｉｅｔｙ，２０２２，２０２２：４５４４４９９．

［１３］ＨＵＡＮＧ Ｇ Ｈ，ＭＡ Ｑ Ｌ． Ｒｅｓｅａｒｃｈ ｏｎ Ｐａｔｈ Ｐｌａｎｎｉｎｇ Ａｌｇｏ-ｒｉｔｈｍ ｏｆ Ａｕｔｏｎｏｍｏｕｓ Ｖｅｈｉｃｌｅｓ Ｂａｓｅｄ ｏｎ Ｉｍｐｒｏｖｅｄ ＲＲＴ Ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｔｒａｎｓ-ｐｏｒｔａｔｉｏｎ Ｓｙｓｔｅｍｓ Ｒｅｓｅａｒｃｈ，２０２１，２０：１７０－１８０．

［１４］ＨＵＡＮＧ Ｓ Ｙ． Ｐａｔｈ Ｐｌａｎｎｉｎｇ Ｂａｓｅｄ ｏｎ Ｍｉｘｅｄ Ａｌｇｏｒｉｔｈｍ ｏｆ ＲＲＴ ａｎｄ Ａｒｔｉｆｉｃｉａｌ Ｐｏｔｅｎｔｉａｌ Ｆｉｅｌｄ Ｍｅｔｈｏｄ［Ｃ］∥２０２１ ４ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｒｏｂｏｔｉｃｓ ａｎｄ Ｃｏｎｔｒｏｌ Ｅｎｇｉｎｅｅｒｉｎｇ（ＩＲＣＥ）． Ｌａｎｚｈｏｕ：ＩＥＥＥ，２０２１：１４９－１５５．

［１５］杜傳勝，高煥兵，侯宇翔，等． 同根雙向擴(kuò)展的貪心ＲＲＴ 路徑規(guī)劃算法［Ｊ］． 計(jì)算機(jī)工程與應(yīng)用，２０２３，５９（２１）：３１２－３１８．

［１６］劉夢(mèng)奇，王維強(qiáng)，田良宇． 基于Ｂ 樣條曲線的無(wú)人駕駛車輛Ｉｎｆｏｒｍｅｄ ＲＲＴ 算法研究［Ｊ］． 智能計(jì)算機(jī)與應(yīng)用，２０２２，１２（４）：２５－２９．

［１７］鄭滋，楊圣慧，鄭永軍，等． 多旋翼無(wú)人機(jī)避障航跡規(guī)劃算法［Ｊ］． 農(nóng)業(yè)工程學(xué)報(bào)，２０２０，３６（２３）：５９－６９．

［１８］周蘭鳳，孔明月． 基于改進(jìn)人工勢(shì)場(chǎng)法的無(wú)人機(jī)三維避障［Ｊ］． 華東師范大學(xué)學(xué)報(bào)（自然科學(xué)版），２０２２（６）：５４－６７．

作者簡(jiǎn)介：

顧秋逸 男，（１９９９—），碩士研究生。主要研究方向：ＲＯＳ 無(wú)人機(jī)集群控制。

李大鵬 男，（１９８２—），博士，教授。主要研究方向：無(wú)線通信、移動(dòng)自組織網(wǎng)絡(luò)。