溫佳霖　梁豐　許雯

摘? 要：針對傳統(tǒng)蟻群算法（ACO）在無人機三維路徑規(guī)劃中存在的規(guī)劃路徑過長、容易陷入局部最優(yōu)解和收斂速度慢等問題，提出基于改進蟻群算法的無人機三維路徑規(guī)劃。在傳統(tǒng)蟻群算法啟發(fā)函數(shù)中引入高度因子，使蟻群搜索具有方向性。同時將信息素更新系數(shù)、信息啟發(fā)因子、期望啟發(fā)因子改為根據(jù)迭代次數(shù)進行動態(tài)變化，增加全局搜索能力和跳出局部最優(yōu)解的能力，加快收斂速度。通過柵格化的方法建立三維路徑規(guī)劃空間，經(jīng)仿真實驗驗證了基于改進蟻群算法的無人機三維路徑規(guī)劃的有效性。

關(guān)鍵詞：ACO算法；無人機；柵格化；三維路徑

中圖分類號：V279；V249；TP18 文獻標識碼：A 文章編號：2096-4706（2023）20-0084-05

Research on UAV 3D Path Planning Based on Improved Ant Colony Algorithm

WEN Jialin， LIANG Feng， XU Wen

（Zhejiang Wanli University， Ningbo? 315100， China）

Abstract： Aiming at the problems of traditional ACO algorithm in UAV 3D path planning， such as long planning path， easy falling into local optimal solution， and slow convergence speed， UAV 3D path planning based on improved ant colony algorithm is proposed. This paper introduces a height factor into the heuristic function of traditional ant colony algorithm to make the ant colony search directional. At the same time， the pheromone update coefficient， information heuristic factor， and expected heuristic factor are changed to dynamically change based on the number of iterations， increasing the global search ability and the ability to jump out of local optimal solutions， and accelerating convergence speed. 3D path planning space is established using rasterization method， and the effectiveness of UAV 3D path planning based on improved ant colony algorithm is verified through simulation experiments.

Keywords： ACO algorithm; UAV; rasterization; 3D path

0? 引? 言

隨著人工智能技術(shù)的飛速發(fā)展，無人機被廣泛應(yīng)用于民用領(lǐng)域（包括地理測繪、農(nóng)業(yè)植保、集群表演等領(lǐng)域）。無人機三維路徑規(guī)劃是指在指定的三維區(qū)域內(nèi)，規(guī)劃一條使無人機快速安全到達目的地的三維最優(yōu)路徑。

目前，國內(nèi)外學(xué)者在求解路徑優(yōu)化問題時常用的啟發(fā)式算法有模擬退火算法[1]、蟻群算法[2]、A*算法[3]、遺傳算法[4]、粒子群算法[5]等。一般的三維路徑規(guī)劃算法都存在計算過程復(fù)雜、無法大量存儲信息、不能直接完成全局規(guī)劃等問題。其中，A*算法的缺點是計算量隨著維度的增加而急劇增大，粒子群算法、遺傳算法和模擬退火算法只是準三維規(guī)劃算法。

蟻群算法憑借其優(yōu)良的適應(yīng)性和魯棒性，以及較易于與其他算法相互結(jié)合的特點而被廣泛應(yīng)用于無人機三維航跡規(guī)劃中。同時，蟻群算法存在收斂速度慢、易陷入局部最優(yōu)解、參數(shù)調(diào)節(jié)困難、規(guī)劃路徑過長的缺點。

基于傳統(tǒng)蟻群算法的上述缺點，代婷婷[6]等提出增加最優(yōu)路徑上的信息素濃度，減小最差路徑上的信息素濃度，從而提高了算法的收斂速度，但仍未解決易陷入死鎖的問題。Sangeetha[7]等將增益算法加入傳統(tǒng)蟻群算法中，發(fā)現(xiàn)這種做法可以有效地跳出局部最優(yōu)，算法的收斂速度明顯加快，但對于路徑最優(yōu)解的優(yōu)化并不明顯。熊自明[8]等引入偏航角對啟發(fā)信息進行改進，使蟻群算法能夠更加高效地搜索到最優(yōu)航跡。劉蓉[9]等在蟻群算法中引入混沌機制優(yōu)化信息素更新方法，將綜合代價較小路徑上的信息素濃度保留，提高了算法的迭代速度，避免在陷入局部最優(yōu)的同時又不會錯失最優(yōu)解。張博[10]提出將信息素揮發(fā)因子改為高斯分布動態(tài)變化指數(shù)，以此調(diào)節(jié)揮發(fā)因子的范圍。以上研究通過對蟻群算法的改進，解決了算法收斂速度慢的問題，但仍存在復(fù)雜環(huán)境中算法搜索效率低，容易陷入最優(yōu)解以及最優(yōu)路徑過長的問題。

本文針對復(fù)雜的三維環(huán)境及蟻群算法的缺點，進一步對算法進行改進。在啟發(fā)函數(shù)中引入高度因素和安全因素，提高尋找最優(yōu)路徑的能力，引導(dǎo)蟻群搜索方向。同時，提出根據(jù)迭代次數(shù)動態(tài)調(diào)整信息素更新系數(shù)、信息啟發(fā)因子、期望啟發(fā)因子的值，加快算法的收斂速度，提高全局搜索能力，增強算法跳出局部最優(yōu)解的能力，減小規(guī)劃路徑的長度。最后，通過合理的仿真實驗驗證了改進遺傳算法在無人機三維路徑規(guī)劃中的有效性。

1? 三維空間抽象建模

在三維地圖中建立抽象三維空間模型的方法如下：將三維地圖左下角的頂點作為三維坐標原點A，建立三維空間坐標系A(chǔ)-XYZ，x軸為沿經(jīng)度增加的方向，y軸為沿緯度增加的方向，z軸為垂直于海平面的方向。設(shè)定AB為最大長度，AA1為最大高度，AD為最大寬度。

所構(gòu)造的三維路徑規(guī)劃空間如圖1所示。沿著邊AB對空間ABCD-A1B1C1D1進行等分，可以得到n + 1個平面Πi（i = 1，2，…，n），接著對這n + 1個平面沿著AD和AA1的方向分別進行m等分和l等分，結(jié)果如圖2所示。由此得到（n + 1）×（m + 1）×（l + 1）個小正方體，即將三維空間離散化成一個三維點集合。

在算法中使用分層前進法和柵格平面法相結(jié)合的搜索方式。只允許螞蟻在劃分好的柵格間移動，且最大橫向移動距離為Ly， max，最大縱向移動距離為Lz， max，以此確定蟻群搜索節(jié)點的范圍。螞蟻從起點S出發(fā)，前進到第二個平面時，在Ly， max×Lz， max的范圍內(nèi)尋找最優(yōu)節(jié)點，直至到達終點E，如圖3所示。

2? 蟻群算法的改進

2.1? 傳統(tǒng)蟻群算法

蟻群算法是模擬蟻群在自然界中尋找食物時，會在它們經(jīng)過的路徑上釋放一種名為信息素的激素，能讓一定范圍內(nèi)的其他螞蟻有所感知。當(dāng)某條路徑上經(jīng)過的螞蟻越來越多的時候，信息素的濃度會非常高，導(dǎo)致蟻群選擇此路徑的概率很高，據(jù)此提出了基于信息正反饋原理的蟻群算法。

蟻群算法解決優(yōu)化問題的思路：用單個螞蟻經(jīng)過的路徑表示優(yōu)化問題的可行解，整個蟻群的全部經(jīng)過路徑構(gòu)成優(yōu)化問題的解空間。較短路徑上螞蟻釋放的信息素更多，隨著時間的推移，相對較短路徑上累積的信息素濃度逐漸升高，從而選擇該路徑的螞蟻數(shù)量也越來越多。最后，所有螞蟻會在正反饋的作用下集中在最短的路徑上，對應(yīng)了待優(yōu)化問題的最優(yōu)解。

2.2? 啟發(fā)函數(shù)改進

啟發(fā)函數(shù)的作用是引導(dǎo)螞蟻選擇最優(yōu)路徑，為了提高算法的效率，加入高度因素以引導(dǎo)螞蟻的搜索方向。螞蟻在搜索節(jié)點時應(yīng)該避開障礙物，因此加入避障因素以避免無人機與障礙物相互碰撞。

2.2.1? 高度因素

在啟發(fā)函數(shù)中引入高度因素，通過高度因子加強對算法搜索方向的引導(dǎo)。本文將下一個搜索節(jié)點與目標點的高度差作為影響啟發(fā)函數(shù)的因子，同時將距離目標點高度較近的節(jié)點作為較優(yōu)選擇點，使螞蟻在高度的選擇上也具有方向性。高度因子的計算式為：

2.2.2? 避障因素

在三維環(huán)境中，會存在障礙物影響無人機路徑的情況，為了使螞蟻在尋找路徑時避開障礙物，在啟發(fā)函數(shù)中引入避障因子 。定義三維空間內(nèi)某節(jié)點? 的避障因子計算式為：

其中，Num表示此節(jié)點搜索區(qū)域內(nèi)所有節(jié)點的數(shù)量，Unum表示搜索區(qū)域內(nèi)不可達節(jié)點的數(shù)量。為三維空間模型中的所有節(jié)點定義安全值，當(dāng)節(jié)點可達時，安全值賦1，當(dāng)節(jié)點不可達時，安全值賦0。這樣可以使螞蟻在選擇路徑時有效地避開障礙物，但由于在選擇下一個節(jié)點時需要對搜索區(qū)域內(nèi)各個節(jié)點的安全值進行計算，這就增加了算法的復(fù)雜度。因此，需要在建模階段提前計算好三維空間中各節(jié)點的安全值。

2.4? 信息素濃度更新系數(shù)ρ的改進

在蟻群算法中，信息素濃度是影響螞蟻搜索的重要因素，信息素位置設(shè)定以及更新方式對蟻群尋優(yōu)具有重大意義。

在三維空間抽象建模中已經(jīng)將整個搜索空間離散為一個個三維離散點，這些離散點就是蟻群算法進行搜索的節(jié)點。因此，針對搜索空間中所有離散點預(yù)先設(shè)置好一個信息素濃度值，將各離散點信息素濃度值的大小作為對螞蟻的吸引程度，信息素濃度在每只螞蟻經(jīng)過后更新。

信息素全局更新是指在螞蟻完成一條路徑的搜索后，會以該路徑長度作為影響值，從路徑集合中選出最短的路徑，并且增加最短路徑中各個節(jié)點的信息素濃度。信息素濃度的更新規(guī)則如下：

其中，K表示常數(shù)，La表示第a只螞蟻經(jīng)過的路徑長度，ρ表示信息素濃度的更新系數(shù)。

更新系數(shù)ρ是影響搜索路徑上信息素濃度的重要因素之一，當(dāng)ρ取值過大時，較優(yōu)路徑與其他路徑上的信息素濃度有較大差距，縮小了蟻群的搜索范圍，使蟻群快速聚集在較優(yōu)路徑上，但容易陷入局部最優(yōu)。當(dāng)ρ取值過小時，信息素衰減慢，路徑上殘留的信息素濃度大，擴大了蟻群的搜索范圍，導(dǎo)致算法收斂速度慢。在算法初期搜索中，為較快得到較優(yōu)解，ρ應(yīng)取較大值；當(dāng)算法處于停滯狀態(tài)時，有可能陷入局部最優(yōu)解，這時應(yīng)該減小ρ值，擴大蟻群的搜索范圍，便于跳出局部最優(yōu)解。綜合以上分析，ρ取值計算式為：

其中，c表示最優(yōu)解連續(xù)未進化的循環(huán)次數(shù)，cmax表示常數(shù)，ρmin表示ρ的最小取值，限制ρ的最小取值是為了避免ρ過小導(dǎo)致算法性能下降。

2.5? 改進蟻群算法步驟

1）建立柵格地圖模型，設(shè)置蟻群算法的迭代次數(shù)、螞蟻個數(shù)、信息素更新系數(shù)、信息啟發(fā)因子、期望啟發(fā)因子、信息素強度等初始參數(shù)。

2）構(gòu)建解空間。

3）將蟻群放置在起點開始尋找節(jié)點。

4）蟻群根據(jù)啟發(fā)函數(shù)搜索下一個節(jié)點并選擇轉(zhuǎn)移節(jié)點。

5）對比更新路徑。

6）全局信息素更新。

7）判斷是否達到最大迭代次數(shù)，若達到最大迭代次數(shù)則完成路徑規(guī)劃，輸出最優(yōu)路徑。反之，則返回步驟4）。

本文最終的算法流程如圖4所示。

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

在MATLAB R2020a環(huán)境下，搭建無人機三維路徑規(guī)劃仿真環(huán)境，在大小為21 km×21 km×2 km的三維空間，設(shè)定某些高度的地形為無人機前往目標點的障礙物。規(guī)定x軸、y軸方向每個節(jié)點的間隔為1 km，z軸方向每個節(jié)點的間隔為200 m。路徑規(guī)劃出發(fā)點坐標為（1，10，4），目標點為（21，8，6）。設(shè)置最大迭代次數(shù)N = 300，信息素更新系數(shù)ρ = 0.8、ρmin = 0.2、cmax = 10、K = 100，最大橫向移動距離Ly， max = 2 km，最大縱向移動距離Lz， max = 2 km。根據(jù)上述參數(shù)進行三維路徑規(guī)劃仿真。

如圖5所示為傳統(tǒng)蟻群算法路徑規(guī)劃圖，其中顯示的規(guī)劃路徑節(jié)點較為分散，且航跡不夠平滑。如圖6所示為改進蟻群算法的路徑規(guī)劃圖，其中顯示的規(guī)劃路徑航跡平滑。證明改進的蟻群算法能尋找到更安全、更平滑的路徑。圖7、圖8分別為普通蟻群算法和改進蟻群算法的最佳適應(yīng)度變化曲線。從圖中可以看出，改進后的算法收斂迅速且降低了適應(yīng)度值（即路徑長度），同時能夠及時跳出局部最優(yōu)解，找到更優(yōu)解，有效解決了傳統(tǒng)蟻群算法規(guī)劃路徑過長、容易陷入局部最優(yōu)解和收斂速度慢的問題。

4? 結(jié)? 論

針對傳統(tǒng)蟻群算法中常見的收斂速度慢、較容易陷入局部最優(yōu)解、參數(shù)調(diào)節(jié)困難、規(guī)劃路徑過長等缺點，本文對三維空間環(huán)境下無人機的路徑規(guī)劃問題進行了優(yōu)化研究。在傳統(tǒng)蟻群算法的基礎(chǔ)上，通過增加高度因素，使改進蟻群算法中的蟻群搜索更具方向性。對信息素更新系數(shù)進行動態(tài)調(diào)節(jié)，有助于蟻群選擇出更優(yōu)的路徑。仿真實驗結(jié)果表明，本文所提出的改進蟻群算法三維路徑規(guī)劃效果較優(yōu)，路徑長度明顯縮短，較好地驗證了改進蟻群算法在該問題中的有效性及實用性。

參考文獻：

[1] 禹建麗，程思雅，孫增圻，等.一種移動機器人三維路徑規(guī)劃優(yōu)化算法 [J].中南大學(xué)學(xué)報：自然科學(xué)版，2009，40（2）：471-477.

[2] 孔維立，王峰，周平華，等.改進蟻群算法的無人機三維路徑規(guī)劃 [J].電光與控制，2023，30（3）：63-69.

[3] 支琛博，張愛軍，杜新陽，等.改進A*算法的移動機器人全局路徑規(guī)劃研究 [J].計算機仿真，2023，40（2）：486-491.

[4] 呂倩，孫憲坤，熊玉潔.改進遺傳算法的無人機路徑規(guī)劃 [J].導(dǎo)航定位學(xué)報，2020，8（5）：42-48.

[5] 辛守庭，趙冠宇，王曉光，等.基于改進粒子群算法的旋翼無人機三維航跡規(guī)劃 [J].飛行力學(xué)，2022，40（5）：47-52+73.

[6] 代婷婷，朱桂玲，胡曉飛.改進蟻群算法及其應(yīng)用 [J].洛陽理工學(xué)院學(xué)報：自然科學(xué)版，2021，31（3）：80-84.

[7] SANGEETHA V，RAVICHANDRAN K S，SHEKHAR S，et al. An Intelligent Gain-based Ant Colony Optimisation Method for Path Planning of Unmanned Ground Vehicles [J].Defence Science Journal，2019，69（2）：167-172.

[8] 熊自明，萬剛，吳本材.基于改進蟻群算法的無人機低空突防三維航跡規(guī)劃 [J].電光與控制，2011，18（12）：44-48.

[9] 劉蓉，楊帆，張衡.基于改進混沌蟻群算法的無人機航路規(guī)劃 [J].指揮信息系統(tǒng)與技術(shù)，2018，9（6）：41-48.

[10] 張博.基于改進蟻群算法的無人機航跡規(guī)劃研究 [D].西安：西安科技大學(xué)，2020.

作者簡介：溫佳霖（1998—），男，漢族，江西贛州人，碩士研究生在讀，研究方向：物流信息技術(shù)應(yīng)用。

收稿日期：2023-04-11