高密度場(chǎng)景下基于改進(jìn)A* 算法的無(wú)人機(jī)路徑規(guī)劃

摘 要：針對(duì)無(wú)人機(jī)在高密度障礙物的城市環(huán)境飛行中路徑規(guī)劃實(shí)時(shí)性難以滿足的問(wèn)題，在Ａ* 算法基礎(chǔ)上結(jié)合跳點(diǎn)搜索（Ｊｕｍｐ Ｐｏｉｎｔ Ｓｅａｒｃｈ，ＪＰＳ）策略，提出一種Ｊｕｍｐ Ａ*（ＪＡ* ）算法。將Ａ* 算法進(jìn)行三維擴(kuò)展，并提出了一種三維對(duì)角距離精確表示了實(shí)際路徑代價(jià)，縮短了搜索時(shí)間。在二維ＪＰＳ 策略的基礎(chǔ)上拓展得到了三維ＪＰＳ 策略，代替了Ａ* 算法中的幾何鄰居擴(kuò)展，大大減少了擴(kuò)展結(jié)點(diǎn)數(shù)。對(duì)障礙物密度０． １ ～ ０． ４ 的復(fù)雜三維柵格地圖進(jìn)行了路徑規(guī)劃仿真。仿真結(jié)果表明，ＪＡ* 算法相較于Ａ*算法，在高密度多障礙物的近地城市環(huán)境下，路徑長(zhǎng)度幾乎不變，評(píng)估節(jié)點(diǎn)數(shù)大幅度減小，搜索速度具有顯著提升。

關(guān)鍵詞：路徑規(guī)劃；跳點(diǎn)搜索；Ａ*算法；三維柵格地圖；高密度障礙物

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

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

０ 引言

無(wú)人機(jī)作為先進(jìn)的飛行器，具有體積小、成本低等優(yōu)勢(shì)，已廣泛用于執(zhí)行識(shí)別、探測(cè)和監(jiān)控等任務(wù)。然而，要在復(fù)雜環(huán)境中成功完成任務(wù)，需要解決路徑規(guī)劃問(wèn)題。

根據(jù)對(duì)先驗(yàn)環(huán)境的已知程度，路徑規(guī)劃可以分為全局與局部路徑規(guī)劃［１－３］。局部路徑規(guī)劃通常采用人工勢(shì)場(chǎng)法［４］和動(dòng)態(tài)窗口法［５］等。本文主要研究了全局路徑規(guī)劃問(wèn)題，目前常用算法有Ａ* 算法［６］、Ｄｉｊｋｓｔｒａ 算法［７］、ＲＲＴ 算法［８］、蟻群算法［９］等。而根據(jù)使用方法和地圖的不同，可分為基于柵格地圖的路徑規(guī)劃算法、基于采樣的路徑規(guī)劃算法和智能仿真算法等。

在基于柵格地圖的路徑規(guī)劃算法中，Ａ* 算法被廣泛應(yīng)用。然而，它仍存在一些缺點(diǎn)，例如：由于大量操作優(yōu)先級(jí)隊(duì)列導(dǎo)致運(yùn)行速度緩慢，內(nèi)存占用大，以及在對(duì)稱路徑的環(huán)境中會(huì)耗費(fèi)更多時(shí)間。Ｈａｒａｂｏｒ等［１０］于２０１１ 年提出了跳點(diǎn)搜索（Ｊｕｍｐ Ｐｏｉｎｔ Ｓｅａｒｃｈ，ＪＰＳ）算法，針對(duì)Ａ*算法的冗余節(jié)點(diǎn)進(jìn)行了剪枝，減小了不必要的搜索，實(shí)現(xiàn)了節(jié)點(diǎn)間的長(zhǎng)距離跳躍，大幅度提升了運(yùn)行速度。此外，文獻(xiàn)［１１］提出一種六邊形柵格ＪＰＳ 策略，進(jìn)一步提升了搜索速度。

在啟發(fā)式函數(shù)方面，文獻(xiàn)［１２］提出了一種等同真實(shí)距離的啟發(fā)式函數(shù)，但缺少三維場(chǎng)景的擴(kuò)展。文獻(xiàn)［１３］提出了一種改進(jìn)Ａ*算法應(yīng)用于二維移動(dòng)機(jī)器人，解決了Ａ算法存在大量冗余節(jié)點(diǎn)的問(wèn)題，但缺少對(duì)應(yīng)的三維ＪＰＳ 策略。

在軌跡平滑方面，文獻(xiàn)［１４］使用Ｔｈｅｔａ*算法在復(fù)雜三維場(chǎng)景中實(shí)現(xiàn)了路徑規(guī)劃，獲得了更加平滑的路徑。文獻(xiàn)［１５］對(duì)ＪＰＳ 搜索策略進(jìn)行了優(yōu)化，同時(shí)引入了３ 次Ｂ 樣條插值進(jìn)行路徑平滑，相較于Ｔｈｅｔａ*算法將規(guī)劃與軌跡平滑進(jìn)行了步驟分離。

在ＪＰＳ 搜索策略優(yōu)化方面，文獻(xiàn)［１６］用“對(duì)角優(yōu)先”方式改進(jìn)了ＪＰＳ 搜索策略，使對(duì)Ｏｐｅｎｌｉｓｔ 的操作大大減小。文獻(xiàn)［１７］采用向量叉積與尺度平衡因子相結(jié)合的方法優(yōu)化傳統(tǒng)ＪＰＳ 算法的啟發(fā)函數(shù)。

在對(duì)Ｏｐｅｎｌｉｓｔ 數(shù)據(jù)結(jié)構(gòu)優(yōu)化上，文獻(xiàn)［１８］使用最小堆的數(shù)據(jù)結(jié)構(gòu)對(duì)Ｏｐｅｎｌｉｓｔ 進(jìn)行了改進(jìn)，使其取最小值的速度大幅度提升。

在實(shí)際場(chǎng)景中，文獻(xiàn)［１９］將改進(jìn)Ａ* 算法部署在了農(nóng)業(yè)無(wú)人機(jī)上，大幅提升了路徑規(guī)劃的速度。文獻(xiàn)［２０］利用改進(jìn)ＲＲＴ 算法實(shí)現(xiàn)了無(wú)人機(jī)電力桿塔巡檢的路徑規(guī)劃。

針對(duì)傳統(tǒng)Ａ*算法在障礙物較多的三維場(chǎng)景中搜索效率較低的問(wèn)題，本文提出一種Ｊｕｍｐ Ａ*（ＪＡ*）算法，對(duì)Ａ* 算法的啟發(fā)式函數(shù)進(jìn)行了改進(jìn)，使其等于實(shí)際的最佳路徑代價(jià)。在二維ＪＰＳ 策略的基礎(chǔ)上拓展得到了三維ＪＰＳ 策略，代替了Ａ*算法中的幾何鄰居擴(kuò)展，大大減小了擴(kuò)展結(jié)點(diǎn)數(shù)。解決了在路徑對(duì)稱時(shí)Ａ* 算法造成的冗余問(wèn)題，提升了算法的運(yùn)行效率，滿足了無(wú)人機(jī)路徑規(guī)劃對(duì)實(shí)時(shí)性的要求。

１ 問(wèn)題描述

１． １ 環(huán)境模型建立

在無(wú)人機(jī)路徑規(guī)劃中，需要建立一個(gè)坐標(biāo)系統(tǒng)，通過(guò)傳感器信息建立一個(gè)能表示環(huán)境的地圖模型。本文使用三維柵格地圖來(lái)構(gòu)建環(huán)境地圖模型。為構(gòu)建精確的柵格地圖，將雙目深度相機(jī)獲取的三維點(diǎn)云地圖轉(zhuǎn)換為分辨率為０． ２ 的三維柵格地圖，將無(wú)人機(jī)視為一個(gè)方格，便于在占用柵格地圖中進(jìn)行計(jì)算。無(wú)人機(jī)的位置使用柵格地圖中的索引坐標(biāo)表示，空白地區(qū)為無(wú)障礙物地區(qū)，柵格為空閑狀態(tài)，有灰白色占用柵格的地區(qū)為障礙物地區(qū)，柵格為占用狀態(tài)，柵格地圖如圖１ 所示。

無(wú)人機(jī)飛行過(guò)程中會(huì)存在不同的飛行方向，在不考慮障礙物以及地圖邊緣的情況下，可以向三維柵格中的２６ 個(gè)方向移動(dòng)，如圖２ 所示，不同的方向存在不一樣的路徑長(zhǎng)度。

１． ２ Ａ*算法及存在的問(wèn)題

Ａ*算法是一種啟發(fā)式的搜索算法，在Ｄｉｊｋｓｔｒａ算法的基礎(chǔ)上融合了貪心算法的思想，不同于Ｄｉｊｋｓｔｒａ 算法的隨機(jī)各方向擴(kuò)張，Ａ* 算法通過(guò)啟發(fā)式的搜索策略，可以更快地得到最優(yōu)路徑。在二維柵格中其搜索方向?yàn)椋?鄰域或８ 鄰域，如圖３ 所示。

三維柵格地圖中其擴(kuò)展方向?yàn)椋玻?鄰域或６ 鄰域，代價(jià)函數(shù)表達(dá)式為：

ｆ（ｎ）＝ ｇ（ｎ）＋ｈ（ｎ）， （１）

式中：ｆ（ｎ）為由起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的總代價(jià)函數(shù)，ｇ（ｎ）為由起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)ｎ 所產(chǎn)生的實(shí)際代價(jià)函數(shù)，ｈ（ｎ）為當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的預(yù)估代價(jià)函數(shù)。

式中：ｘｓ、ｙｓ、ｚｓ 為起始節(jié)點(diǎn)的坐標(biāo)，ｘｎ、ｙｎ、ｚｎ 為當(dāng)前節(jié)點(diǎn)的坐標(biāo)，ｇ（ｎ）為三維空間中起始點(diǎn)ｓ 與當(dāng)前節(jié)點(diǎn)ｎ 的真實(shí)距離。預(yù)估代價(jià)函數(shù)ｈ（ｎ）具有多種表達(dá)形式，一般有歐氏距離、曼哈頓距離：

式中：預(yù)估代價(jià)函數(shù)ｈ（ｎ）的取值決定了Ａ* 算法搜索效率，當(dāng)ｈ（ｎ）取值為０ 時(shí)將退化為Ｄｉｊｋｓｔｒａ 算法，而當(dāng)ｈ（ｎ）遠(yuǎn)大于實(shí)際路徑損耗時(shí)將退化為基于貪心算法思想的廣度優(yōu)先搜索。

傳統(tǒng)Ａ*算法在整個(gè)全局路徑規(guī)劃過(guò)程中占用了大量?jī)?nèi)存，在搜索過(guò)程中，需要維護(hù)一個(gè)隊(duì)列，隊(duì)列中可能會(huì)存儲(chǔ)大量節(jié)點(diǎn)信息，如果搜索的空間較大，內(nèi)存消耗也會(huì)較高。

２ ＪＡ*算法設(shè)計(jì)

為了解決上述問(wèn)題，本文針對(duì)評(píng)估函數(shù)進(jìn)行了改進(jìn)，并且融合了三維ＪＰＳ 策略對(duì)Ａ* 算法進(jìn)行改進(jìn)。

２． １ 改進(jìn)啟發(fā)式函數(shù)計(jì)算方式

恰當(dāng)?shù)膯l(fā)式函數(shù)能提高Ａ*算法的搜索效率，傳統(tǒng)Ａ*算法中通常使用歐氏距離與曼哈頓距離作為啟發(fā)式搜索函數(shù)，但在柵格地圖中，歐氏距離會(huì)小于實(shí)際的路徑距離，會(huì)導(dǎo)致拓展的節(jié)點(diǎn)數(shù)增加。

因此本文采用三維空間中的對(duì)角線距離作為啟發(fā)式搜索函數(shù)，對(duì)角線距離是指網(wǎng)格地圖中用于計(jì)算兩個(gè)節(jié)點(diǎn)之間的估價(jià)函數(shù)，常用于處理斜向移動(dòng)的情況。在實(shí)際最優(yōu)路徑中，沿著４５°角方向擴(kuò)展必然路徑長(zhǎng)度小于９０°角方向擴(kuò)展，因此二維空間下的對(duì)角線啟發(fā)函數(shù)為：

式中：ｘｇ 與ｙｇ 為目標(biāo)點(diǎn)橫縱坐標(biāo)，ｘｎ 與ｙｎ 為當(dāng)前點(diǎn)的橫縱坐標(biāo)。

二維平面下的啟發(fā)式函數(shù)如圖４ 所示，綠色為二維曼哈頓距離，藍(lán)色為二維歐氏距離，黑色為二維對(duì)角線距離，顯然歐氏距離小于實(shí)際最優(yōu)距離，曼哈頓距離大于實(shí)際最優(yōu)距離，而對(duì)角線距離與實(shí)際最優(yōu)距離相等，因此通過(guò)對(duì)角線距離計(jì)算得到的代價(jià)值增強(qiáng)了算法啟發(fā)性的同時(shí)也能讓算法得到最優(yōu)路徑。

在二維對(duì)角線啟發(fā)式函數(shù)的基礎(chǔ)上，本文對(duì)其進(jìn)行拓展得到了三維對(duì)角線啟發(fā)式函數(shù)，如圖５ 所示，圖中分別顯示了點(diǎn)（０，０，－１）到（１，１，１）的距離。紅色為三維歐氏距離，藍(lán)色為三維對(duì)角線，綠色為距離三維曼哈頓距離，代價(jià)值依次為４、根號(hào)下６ 、根號(hào)下３ ＋１。顯然，對(duì)角線距離更符合真實(shí)無(wú)人機(jī)運(yùn)動(dòng)的鄰域擴(kuò)展，在２６ 鄰域的假設(shè)下，對(duì)角線距離與真實(shí)代價(jià)相等。因此，對(duì)角線距離更接近無(wú)人機(jī)真實(shí)運(yùn)動(dòng)的路徑代價(jià)。

ｄｘ＝ ｜ｘｇ －ｘｎ ｜， （６）

ｄｙ＝ ｜ｙｇ －ｙｎ ｜， （７）

ｄｚ＝ ｜ｚｇ －ｚｎ ｜， （８）

式中：ｄｚ、ｄｙ、ｄｚ 為目標(biāo)點(diǎn)坐標(biāo)與當(dāng)前點(diǎn)坐標(biāo)的絕對(duì)距離，需要對(duì)ｄｘ、ｄｙ、ｄｚ 進(jìn)行大小排序，假設(shè)從大到小依次為Ｖａｌ１、Ｖａｌ２、Ｖａｌ３。

式中：ｈ（ｎ）為２６ 鄰域下實(shí)際的路徑代價(jià)。在傳統(tǒng)的啟發(fā)式函數(shù)中，歐氏距離小于實(shí)際的路徑代價(jià)，因此能獲取更準(zhǔn)確的最優(yōu)路徑但同時(shí)耗費(fèi)的時(shí)間也會(huì)增加；而曼哈頓距離則大于實(shí)際的路徑代價(jià)，因此其耗時(shí)較少但同時(shí)不一定會(huì)得到最優(yōu)路徑。相對(duì)而言對(duì)角線距離在速度和最優(yōu)性方面達(dá)到了平衡。

２． ２ 三維ＪＰＳ 策略設(shè)計(jì)

ＪＰＳ 算法是在Ａ* 算法的基礎(chǔ)上提出的一種減少鄰域拓展過(guò)程中產(chǎn)生大量冗余中繼節(jié)點(diǎn)的優(yōu)化策略。本文拓展了二維ＪＰＳ 搜索策略，得到了三維空間下的修剪規(guī)則與跳躍規(guī)則，并與三維空間下的Ａ*算法結(jié)合。修剪的基本準(zhǔn)則是當(dāng)拓展至當(dāng)前節(jié)點(diǎn)ｎ 時(shí)，若ｘ 的鄰居節(jié)點(diǎn)可以從父節(jié)點(diǎn)不經(jīng)過(guò)ｘ 到達(dá)且代價(jià)更低時(shí)，則不考慮擴(kuò)展該節(jié)點(diǎn)。不同于Ａ*算法需要將幾何意義上的所有鄰居節(jié)點(diǎn)加入ＯｐｅｎＬｉｓｔ 中進(jìn)行評(píng)估，ＪＰＳ 算法在鄰居節(jié)點(diǎn)中進(jìn)行篩選，選取符合修剪規(guī)則的節(jié)點(diǎn)。符合修剪規(guī)則的節(jié)點(diǎn)，將其稱為自然鄰居節(jié)點(diǎn)，而障礙物不能被修剪的節(jié)點(diǎn)稱為強(qiáng)制鄰居節(jié)點(diǎn)。因此修剪規(guī)則根據(jù)當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)是否存在障礙物，分兩類(lèi)情況討論。

在三維場(chǎng)景下，無(wú)障礙物的２６ 鄰域擴(kuò)展可分為３ 種情況：① 平移（代價(jià)為１）；② 對(duì)角線移動(dòng)（代價(jià)為槡２ ）；③ 斜上對(duì)角線移動(dòng)（代價(jià)為槡３ ）。將三維空間中的２７ 個(gè)節(jié)點(diǎn)分為３ 層，每層９ 個(gè)節(jié)點(diǎn)。紅色節(jié)點(diǎn)表示當(dāng)前拓展到的節(jié)點(diǎn)，黃色節(jié)點(diǎn)為其父節(jié)點(diǎn)，綠色節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)下一步考慮的擴(kuò)展節(jié)點(diǎn)，白色節(jié)點(diǎn)為下一步拓展中不再考慮的劣性節(jié)點(diǎn)，黑色節(jié)點(diǎn)為障礙物。

２． ２． １ 情況１：鄰居節(jié)點(diǎn)無(wú)障礙物

當(dāng)父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)為平行移動(dòng)時(shí)，如圖６ 所示。

當(dāng)父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)為對(duì)角線移動(dòng)時(shí)，如圖７ 所示。

當(dāng)父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)為斜對(duì)角線移動(dòng)時(shí)，如圖８ 所示。

２． ２． ２ 情況２：鄰居節(jié)點(diǎn)存在障礙物

當(dāng)父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)為平行移動(dòng)時(shí)，考慮中間層與頂層存在障礙物，如圖９ 所示。

當(dāng)父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)為對(duì)角線移動(dòng)時(shí)，考慮中間層與頂層存在障礙物，底層存在障礙物時(shí)不會(huì)產(chǎn)生強(qiáng)制鄰居節(jié)點(diǎn)，如圖１０ 所示。

當(dāng)父節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)為斜對(duì)角線移動(dòng)時(shí)，考慮底層存在障礙物，中間層與頂層存在礙物時(shí)不會(huì)產(chǎn)生強(qiáng)制鄰居節(jié)點(diǎn)，如圖１１ 所示。

２． ３ 算法流程

改進(jìn)Ａ*算法流程如算法１ 所示。

３ 算法仿真與分?jǐn)?shù)據(jù)分析

為了驗(yàn)證ＪＡ*算法的有效性，本文在三維環(huán)境中對(duì)Ｄｉｊｋｓｔｒａ 算法、Ａ* 算法和ＪＡ* 算法進(jìn)行了仿真分析。使用Ｕｂｕｎｔｕ １８． ０４ 操作系統(tǒng)和ＲＯＳ Ｍｅｌｏｄｉｃ 作為設(shè)備軟件配置，并搭配ＡＭＤ Ｒｙｚｅｎ ７ ５８００Ｈ 處理器。為了便于部署于真實(shí)無(wú)人機(jī)且用于可視化，本文使用了ｒｏｓ＋ｒｖｉｚ 作為仿真平臺(tái)。在仿真分析中，針對(duì)使用不同啟發(fā)式函數(shù)的Ａ*算法與相同地圖大小和不同障礙物密度的環(huán)境對(duì)算法進(jìn)行了比較。

３． １ 不同啟發(fā)式函數(shù)對(duì)比

如表１ 所示，在障礙物與柵格比例為０． ４ 的不同大小地圖中進(jìn)行Ａ* 算法路徑規(guī)劃時(shí)，對(duì)角線距離、歐式距離與曼哈頓距離的對(duì)比。

以曼哈頓函數(shù)作為啟發(fā)式函數(shù)時(shí)，其計(jì)算接近于貪心算法，因此其評(píng)估節(jié)點(diǎn)數(shù)最少，搜索效率最高，但同時(shí)有概率獲取到非最優(yōu)路徑。歐式距離由于其計(jì)算復(fù)雜，導(dǎo)致效率較低。而對(duì)角線距離在具備遠(yuǎn)高于曼哈頓距離的搜索速度的同時(shí)，也能兼顧最優(yōu)的搜索路徑長(zhǎng)度。

圖１２ 和圖１３ 對(duì)比了３ 種啟發(fā)式函數(shù)下的算法在不同大小地圖上的規(guī)劃速度，可以看出，在規(guī)劃時(shí)間上對(duì)角線距離與曼哈頓距離接近，均遠(yuǎn)快于歐氏距離。

３． ２ 不同算法對(duì)比實(shí)驗(yàn)

圖１４ 為３ 種算法在不同障礙物密度的１０ ｍ×１０ ｍ×５ ｍ 隨機(jī)柵格地圖中進(jìn)行１０ 次仿真實(shí)驗(yàn)，設(shè)定起始點(diǎn)為坐標(biāo)（０，０，１）ｍ，設(shè)置地圖內(nèi)四角為固定終點(diǎn)。紅色柵格為ＪＡ*算法與Ａ*算法有部分重合，藍(lán)色柵格為Ｄｉｊｋｓｔｒａ 算法，綠色柵格為Ａ*算法。

在障礙物密度為０． ２ 的１０ ｍ×１０ ｍ×５ ｍ 地圖中進(jìn)行仿真對(duì)比，如圖１５ 所示，規(guī)劃數(shù)據(jù)如圖１６ 與表２ 所示。

對(duì)比Ａ*算法、Ｄｉｊｋｓｔｒａ 算法與ＪＡ*算法，ＪＡ*算法在大多數(shù)情況下具備最快的運(yùn)行速度，同時(shí)大大減少了拓展節(jié)點(diǎn)與內(nèi)存的占用。在障礙物密度為０．２ 時(shí)，ＪＡ*算法搜索速度較Ａ*算法提升了２８７． ６０％；障礙物密度為０． ４ 時(shí)，搜索速度提升了５７８． ２３％ 。在評(píng)估節(jié)點(diǎn)數(shù)量的對(duì)比上，ＪＡ*算法的評(píng)估節(jié)點(diǎn)數(shù)大大減小。仿真結(jié)果表明，在障礙物密度較大的情況下評(píng)估節(jié)點(diǎn)數(shù)量與搜索速度方面，ＪＡ* 算法遠(yuǎn)優(yōu)于傳統(tǒng)Ａ*算法。在障礙物密度較小時(shí)，ＪＡ*算法搜索速度會(huì)略低于Ａ*算法。

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

本文針對(duì)在密集障礙物環(huán)境無(wú)人機(jī)進(jìn)行路徑規(guī)劃中Ａ* 算法速度慢、冗余節(jié)點(diǎn)多的問(wèn)題，提出了一種ＪＡ*搜索算法，對(duì)Ａ*算法的啟發(fā)式函數(shù)進(jìn)行了改進(jìn)，融合了ＪＰＳ 算法的思想并進(jìn)行了三維拓展。通過(guò)對(duì)不同大小以及不同障礙物密度的地圖進(jìn)行了仿真分析與對(duì)比，證明了ＪＡ* 算法的有效性。仿真結(jié)果表明，在障礙物密度較大時(shí)，ＪＡ* 算法較于Ａ算法在不影響最優(yōu)路徑的情況下能大幅度提升搜索速度，大大減少了對(duì)隊(duì)列的操作次數(shù)。

本文算法也尚且存在不足之處，例如雖然ＪＡ*算法在復(fù)雜場(chǎng)景的搜索速度上具有巨大提升，但路徑不夠平滑。可以通過(guò)進(jìn)一步引入平滑函數(shù)來(lái)減小無(wú)人機(jī)加減速時(shí)的耗能。

參考文獻(xiàn)

［１］ 霍鳳財(cái)，遲金，黃梓健，等． 移動(dòng)機(jī)器人路徑規(guī)劃算法綜述［Ｊ］． 吉林大學(xué)學(xué)報(bào)（信息科學(xué)版），２０１８，３６（６）：６３９－６４７．

［２］ 朱磊，樊繼壯，趙杰，等． 基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障［Ｊ］． 中南大學(xué)學(xué)報(bào)（自然科學(xué)版），２０１１，４２（１１）：３４２１－３４２８．

［３］ 王春穎，劉平，秦洪政． 移動(dòng)機(jī)器人的智能路徑規(guī)劃算法綜述［Ｊ］． 傳感器與微系統(tǒng)，２０１８，３７（８）：５－８．

［４］ 張建英，趙志萍，劉暾． 基于人工勢(shì)場(chǎng)法的機(jī)器人路徑規(guī)劃［Ｊ］． 哈爾濱工業(yè)大學(xué)學(xué)報(bào)，２００６，３８ （８ ）：１３０６－１３０９．

［５］ ＦＯＸ Ｄ，ＢＵＲＧＡＲＤ Ｗ，ＴＨＲＵＮ Ｓ． Ｔｈｅ Ｄｙｎａｍｉｃ Ｗｉｎｄｏｗ Ａｐｐｒｏａｃｈ ｔｏ Ｃｏｌｌｉｓｉｏｎ Ａｖｏｉｄａｎｃｅ ［Ｊ］． ＩＥＥＥ Ｒｏｂｏｔｉｃｓ ＆Ａｕｔｏｍａｔｉｏｎ Ｍａｇａｚｉｎｅ，１９９７，４（１）：２３－３３．

［６］ ＥＶＥＲＳＯＮ Ｌ Ｒ，ＳＡＰＡＴＮＥＫＡＲ Ｓ Ｓ，ＫＩＭ Ｃ Ｈ． Ａ Ｔｉｍｅｂａｓｅｄ Ｉｎｔｒａｍｅｍｏｒｙ Ｃｏｍｐｕｔｉｎｇ Ｇｒａｐｈ Ｐｒｏｃｅｓｓｏｒ Ｆｅａｔｕｒｉｎｇ Ａ Ｗａｖｅｆｒｏｎｔ Ｅｘｐａｎｓｉｏｎ ａｎｄ ２Ｄ Ｇｒａｄｉｅｎｔ Ｃｏｎｔｒｏｌ［Ｊ］．ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｆ Ｓｏｌｉｄｓｔａｔｅ Ｃｉｒｃｕｉｔｓ，２０２１，５６ （７ ）：２２８１－２２９０．

［７］ ＰＲＩＭ Ｒ Ｃ． Ｓｈｏｒｔｅｓｔ Ｃｏｎｎｅｃｔｉｏｎ Ｎｅｔｗｏｒｋｓ ａｎｄ Ｓｏｍｅ Ｇｅｎｅｒａｌｉｚａｔｉｏｎｓ［Ｊ］． Ｔｈｅ Ｂｅｌｌ Ｓｙｓｔｅｍ Ｔｅｃｈｎｉｃａｌ Ｊｏｕｒｎａｌ，１９５７，３６（６）：１３８９－１４０１．

［８］ ＤＡ ＳＩＬＶＡ Ｃ Ｌ，ＴＯＮＩＤＡＮＤＥＬ Ｆ． ＤＶＧ＋ Ａ ａｎｄ ＲＲＴ Ｐａｔｈｐｌａｎｎｅｒｓ：Ａ Ｃｏｍｐａｒｉｓｏｎ ｉｎ ａ Ｈｉｇｈｌｙ Ｄｙｎａｍｉｃ Ｅｎｖｉｒｏｎｍｅｎｔ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ ＆ Ｒｏｂｏｔｉｃ Ｓｙｓｔｅｍｓ，２０２１，１０１：５８．

［９］ ＤＯＲＩＧＯ Ｍ，ＧＡＭＢＡＲＤＥＬＬＡ Ｌ Ｍ． Ａｎｔ Ｃｏｌｏｎｙ Ｓｙｓｔｅｍ：Ａ Ｃｏｏｐｅｒａｔｉｖｅ Ｌｅａｒｎｉｎｇ Ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，１９９７，１（１）：５３－６６．

［１０］ＨＡＲＡＢＯＲ Ｄ，ＧＲＡＳＴＩＥＮ Ａ． Ｏｎｌｉｎｅ Ｇｒａｐｈ Ｐｒｕｎｉｎｇ ｆｏｒ Ｐａｔｈｆｉｎｄｉｎｇ ｏｎ Ｇｒｉｄ Ｍａｐｓ［ＥＢ／ ＯＬ］． ［２０２４－０２－２０］． ｈｔｔｐｓ：∥ｃｄｎ． ａａａｉ． ｏｒｇ／ ｏｊｓ／７９９４ ／７９９４－１３ －１１５２２ －１ －２ －２０２０１２２８． ｐｄｆ．

［１１］王文明，杜佳璐． 基于正六邊形柵格ＪＰＳ 算法的智能體路徑規(guī)劃［Ｊ］． 系統(tǒng)工程與電子技術(shù)，２０２１，４３（１２）：３６３５－３６４２．

［１２］張慶，劉旭，彭力，等． 融合ＪＰＳ 和改進(jìn)Ａ* 算法的移動(dòng)機(jī)器人路徑規(guī)劃［Ｊ］． 計(jì)算機(jī)科學(xué)與探索，２０２１，１５（１１）：２２３３－２２４０．

［１３］趙曉，王錚，黃程侃，等． 基于改進(jìn)Ａ* 算法的移動(dòng)機(jī)器人路徑規(guī)劃［Ｊ］． 機(jī)器人，２０１８，４０（６）：９０３－９１０．

［１４］林思偉，席萬(wàn)強(qiáng)，李青云，等． 復(fù)雜環(huán)境下的無(wú)人機(jī)三維路徑規(guī)劃［Ｊ］． 電光與控制，２０２３，３０（２）：３１－３５．

［１５］趙衛(wèi)東，唐顧杰，宋江一． 基于改進(jìn)ＪＰＳ 與三次Ｂ 樣條插值的路徑規(guī)劃算法［Ｊ］． 安徽工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），２０２２，３９（２）：１８９－１９５．

［１６］宋曉茹，任怡悅． 面向移動(dòng)機(jī)器人快速全局路徑規(guī)劃的改進(jìn)跳點(diǎn)搜索算法［Ｊ］． 科學(xué)技術(shù)與工程，２０２０，２０（２９）：１１９９２－１１９９９．

［１７］胡士強(qiáng)，武美萍，施健，等． 融合向量叉積與跳點(diǎn)搜索策略的改進(jìn)Ａ 算法研究［Ｊ／ ＯＬ］． 機(jī)械科學(xué)與技術(shù)，２０２３：１－１０（２０２３－０１－０６）［２０２４－０３－０２］． ｈｔｔｐｓ：∥ｄｏｉ．ｏｒｇ／１０． １３４３３ ／ ｊ． ｃｎｋｉ． １００３－８７２８． ２０２３００１７．

［１８］謝春麗，高勝寒，孫學(xué)志． 融合改進(jìn)Ａ* 算法和貝塞爾曲線優(yōu)化的路徑規(guī)劃算法［Ｊ］． 重慶理工大學(xué)學(xué)報(bào)（自然科學(xué)），２０２２，３６（７）：１７７－１８７．

［１９］田茹，曹茂永，馬鳳英，等． 基于改進(jìn)Ａ*算法的農(nóng)用無(wú)人機(jī)路徑規(guī)劃［Ｊ］． 現(xiàn)代電子技術(shù)，２０２２，４５（４）：１８２－１８６．

［２０］羅隆福，李冬，鐘杭． 基于改進(jìn)ＲＲＴ 的無(wú)人機(jī)電力桿塔巡檢路徑規(guī)劃［Ｊ］． 湖南大學(xué)學(xué)報(bào)（自然科學(xué)版），２０１８，４５（１０）：８０－８６．

作者簡(jiǎn)介：

趙烈海 男，（１９９９—），碩士研究生。主要研究方向：無(wú)人機(jī)避障與路徑規(guī)劃。

（*通信作者）李大鵬 男，（１９８２—），博士，教授，博士生導(dǎo)師。主要研究方向：無(wú)人機(jī)群體智能、分布式網(wǎng)絡(luò)技術(shù)、無(wú)人機(jī)集群控制。