摘 要：無人機(jī)路徑規(guī)劃源于機(jī)器人運(yùn)動規(guī)劃，是當(dāng)下無人機(jī)應(yīng)用研究的核心內(nèi)容，對提高無人機(jī)系統(tǒng)在復(fù)雜環(huán)境中的作業(yè)能力起著關(guān)鍵作用。針對快速擴(kuò)展隨機(jī)樹（Ｒａｐｉｄｌｙ-ｅｘｐｌｏｒｉｎｇ Ｒａｎｄｏｍ Ｔｒｅｅ，ＲＲＴ）算法進(jìn)行無人機(jī)路徑規(guī)劃時搜索隨機(jī)性高、存在冗余路徑和路徑平滑性差的問題，提出了一種面向無人機(jī)路徑規(guī)劃的改進(jìn)ＲＲＴ 算法。改進(jìn)ＲＲＴ算法在ＲＲＴ 算法的基礎(chǔ)上結(jié)合人工勢場法中的引力函數(shù)使得隨機(jī)節(jié)點(diǎn)的產(chǎn)生具有目標(biāo)導(dǎo)向性，限制了隨機(jī)樹的拓展方向，從而降低了搜索的隨機(jī)性；結(jié)合貪心算法對規(guī)劃所得路徑進(jìn)行剪枝優(yōu)化，去除冗余節(jié)點(diǎn)，縮短了路徑長度；結(jié)合Ｂ 樣條曲線對路徑進(jìn)行平滑性處理，去除曲率突變的轉(zhuǎn)折點(diǎn)，形成一條平滑的適合無人機(jī)實際飛行的路徑。通過仿真軟件對Ａ* 算法、傳統(tǒng)ＲＲＴ 算法與改進(jìn)ＲＲＴ 算法進(jìn)行對比分析，仿真結(jié)果表明，提出的改進(jìn)ＲＲＴ 算法性能更高，在狹窄通道場景與復(fù)雜障礙物場景下相比于傳統(tǒng)ＲＲＴ 算法平均規(guī)劃時間各減少４９． ４４％ 和１７． ９７％ ，相比于Ａ* 算法平均規(guī)劃時間各減少了８０． ２３％ 和５２． ９３％ ，得到的路徑更短更為平緩，同時大幅降低了ＲＲＴ 算法路徑規(guī)劃失敗的可能性，驗證了改進(jìn)ＲＲＴ 算法的可行性與有效性，解決了原算法隨機(jī)性高、存在冗余路徑和平滑性差的問題。

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

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

文章編號：１００３－３１１４（２０２４）０６－１１８４－０８

０ 引言

路徑規(guī)劃技術(shù)近些年發(fā)展迅速，已經(jīng)被應(yīng)用于各行各業(yè)，尤其是在無人機(jī)領(lǐng)域。無人機(jī)路徑規(guī)劃是無人機(jī)應(yīng)用研究的核心內(nèi)容，對提高無人機(jī)系統(tǒng)在復(fù)雜未知環(huán)境的作業(yè)能力起著關(guān)鍵作用。無人機(jī)路徑規(guī)劃的核心任務(wù)是在已知起始點(diǎn)和目標(biāo)點(diǎn)的情況下，找出一條既能避開沿途障礙物又趨向于距離最短的可行路徑。

各國學(xué)者已經(jīng)提出了多種經(jīng)典路徑規(guī)劃算法，以應(yīng)對不同場景下的路徑優(yōu)化問題。例如Ｄｉｊｋｓｔｒａ算法［１］作為一種最短路徑算法，具有全局最優(yōu)性；遺傳算法［２］基于生物進(jìn)化論，通過選擇、交叉和變異的操作尋找全局最優(yōu)解；快速擴(kuò)展隨機(jī)樹（Ｒａｐｉｄｌｙ-ｅｘｐｌｏｒｉｎｇ Ｒａｎｄｏｍ Ｔｒｅｅ，ＲＲＴ）算法則利用隨機(jī)采樣快速探索高維空間中的可行路徑以及人工勢場法、速度障礙法［３］、粒子群算法［４］、Ａ* 算法、蟻群優(yōu)化（Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）算法［５］等，這些經(jīng)典算法在無人機(jī)路徑規(guī)劃中起到了重要的基底作用。文獻(xiàn)［６］運(yùn)用了Ｄｉｊｋｓｔｒａ 和紅外檢測合成的算法，使無人機(jī)能有效地避開所有的障礙物，解決了局部離障礙物過近的問題。文獻(xiàn)［７］提出了一種基于改進(jìn)自適應(yīng)蟻群（Ｉｍｐｒｏｖｅｄ Ａｄａｐｔｉｖｅ Ａｎｔ ＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎ，ＩＡＡＣＯ）算法的路徑規(guī)劃算法以解決傳統(tǒng)ＡＣＯ 算法存在的收斂速度慢、易陷入局部最優(yōu)等不足，同時規(guī)劃出的路徑更平滑、長度更短。文獻(xiàn)［８］提出一種基于改進(jìn)速度障礙法的局部路徑避障規(guī)劃算法，將傳統(tǒng)速度障礙法拓展到三維空間中，解決了無人機(jī)在動態(tài)環(huán)境中基于環(huán)境感知進(jìn)行局部路徑重規(guī)劃時面臨的實時性與安全性問題。文獻(xiàn)［９］提出了基于管道模型預(yù)測控制（Ｔｕｂｅ-Ｍｏｄｅｌ ＰｒｅｄｉｃｔｉｖｅＣｏｎｔｒｏｌ，Ｔｕｂｅ-ＭＰＣ）和模型預(yù)測路徑積分（ＭｏｄｅｌＰｒｅｄｉｃｔｉｖｅ Ｐａｔｈ Ｉｎｔｅｇｒａｌ，ＭＰＰＩ）融合的多無人機(jī)分布式在線軌跡規(guī)劃框架與方法，同時采用并行蒙特卡洛隨機(jī)采樣技術(shù)，將多無人機(jī)軌跡優(yōu)化問題的求解過程轉(zhuǎn)化為對大量采樣軌跡的期望求解過程，避免了傳統(tǒng)方法對代價函數(shù)和約束條件的連續(xù)性及凸性要求的限制，從而實現(xiàn)了對復(fù)雜非線性環(huán)境中多無人機(jī)軌跡的高效優(yōu)化與規(guī)劃。

針對ＲＲＴ 算法的收斂速度慢、路徑曲折等問題，研究者進(jìn)行了不同的優(yōu)化處理。文獻(xiàn)［１０］針對隨機(jī)樹擴(kuò)展時隨機(jī)性較大的問題，加入人工勢場法約束，使得隨機(jī)樹偏向目標(biāo)點(diǎn)生長，優(yōu)化了路徑。文獻(xiàn)［１１］針對ＲＲＴ 算法在路徑規(guī)劃中可能遇到的隨機(jī)性大、搜索時間長、路徑曲折等問題，提出了一種基于環(huán)境分區(qū)的蟻群優(yōu)化目標(biāo)偏差ＲＲＴ 算法，有效地消除了無用節(jié)點(diǎn)，減少了規(guī)劃時間。文獻(xiàn)［１２］提出了一種改進(jìn)的ＲＲＴ 算法，在擴(kuò)展隨機(jī)樹的過程中，引入ＡＣＯ 算法。優(yōu)化后的算法可以在ＲＲＴ 得到的路徑上設(shè)置信息素，并根據(jù)信息素濃度選擇下一個擴(kuò)展點(diǎn)。文獻(xiàn)［１３］提出了一種基于ＲＲＴ 算法的改進(jìn)路徑規(guī)劃算法，采用循環(huán)采樣策略提高采樣效率，設(shè)計了一種基于代價函數(shù)的擴(kuò)展隨機(jī)點(diǎn)規(guī)則來過濾隨機(jī)點(diǎn)。文獻(xiàn)［１４］針對ＲＲＴ 算法采樣隨機(jī)、效率低的問題，提出了一種結(jié)合人工勢場法的改進(jìn)算法。在基本ＲＲＴ 算法的隨機(jī)樹展開步驟中引入一個概率值，加快隨機(jī)樹向目標(biāo)節(jié)點(diǎn)的收斂，并在隨機(jī)樹中添加引力分量，引導(dǎo)樹向目標(biāo)點(diǎn)生長，加快搜索過程，該方法在迭代時間、路徑長度和迭代次數(shù)等方面得到了顯著優(yōu)化。

上述算法從采樣方式、拓展方式等方面對ＲＲＴ算法進(jìn)行了改進(jìn)，但改進(jìn)后的算法仍存在搜索隨機(jī)性高、存在冗余路徑和平滑性差的問題。本文提出的改進(jìn)ＲＲＴ 算法是在ＲＲＴ 算法的基礎(chǔ)上首先結(jié)合人工勢場法中的引力函數(shù)使得隨機(jī)節(jié)點(diǎn)的產(chǎn)生具有導(dǎo)向性和目的性，從而減小了搜索隨機(jī)性；然后結(jié)合貪心算法［１５］對規(guī)劃所得路徑上的轉(zhuǎn)折點(diǎn)進(jìn)行剪枝優(yōu)化，去除了無用的冗余節(jié)點(diǎn)，減少了路徑上的轉(zhuǎn)折點(diǎn)，同時縮短了整體路徑長度；最后采用３ 次Ｂ 樣條曲線擬合［１６］對剪枝后的路徑進(jìn)行平滑性處理，從而能夠生成一條路徑平滑的適合無人機(jī)實際飛行的路徑。

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

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

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

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

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

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

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

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

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

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

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

１． ３ 問題描述

從前文可以得知ＲＲＴ 算法具有參數(shù)少、結(jié)構(gòu)簡單、搜索能力強(qiáng)的優(yōu)點(diǎn)，然而從圖２ 迭代模型以及流程中也可以得知，當(dāng)ＲＲＴ 算法的起始隨機(jī)節(jié)點(diǎn)偏離目標(biāo)點(diǎn)，算法運(yùn)算到后期會出現(xiàn)大量冗余節(jié)點(diǎn)，產(chǎn)生較大的隨機(jī)性，使得運(yùn)算速度變慢，最終得到的路徑平滑性差，不適合無人機(jī)真實飛行場景。本文將介紹一種改進(jìn)ＲＲＴ 算法以解決ＲＲＴ 算法采樣隨機(jī)性較大、路徑冗長、路徑不平滑的問題。

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

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

本小節(jié)將結(jié)合人工勢場法［１８］中引力勢場函數(shù)來解決ＲＲＴ 算法中節(jié)點(diǎn)隨機(jī)性較大、冗余節(jié)點(diǎn)量大、收斂速度慢的問題。

人工勢場法是一種局部路徑規(guī)劃方法，最早是針對移動機(jī)器人進(jìn)行避障使用的，具有如下的引力勢函數(shù)和斥力勢函數(shù)：

式中：α 為引力系數(shù)，Ｄ（Ｐ，Ｐｇ）為當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的歐式距離。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

３． １ 仿真驗證

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

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

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

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

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

４ 結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

作者簡介：

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

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