改進ACO算法的UAV航跡規劃在山區物流配送中的應用研究

巫 茜，黃 浩，曾 青，王成睿，鄺 茜

(重慶理工大學 計算機科學與工程學院， 重慶 400054)

0 引言

無人機(unmanned aerial vehicle,UAV)是一種不搭載飛行員并配有自動飛行駕駛系統的飛行器[1]。它具有體積小、風險低、使用方便等特點，在軍用和民用領域應用廣泛[2]。隨著電商行業的迅速發展，物流末端配送的壓力也隨之增大[3]，尤其是在山區，人口分散、地形復雜等因素導致物流成本過高，配送時間較長，針對這種情況，物流無人機應運而生[4]。

目前，對物流無人機航跡規劃的研究較少。無人機航跡規劃是為順利完成飛行任務，在綜合權衡地形地貌、各類威脅、能源油耗等諸多因素下給無人機規劃出的一條令人滿意的空間飛行航跡[5]。目前有多種航跡規劃優化算法，如粒子群算法、蟻群算法、魚群算法、人工勢場法等[6]。其中，蟻群算法(ant colony optimization,ACO)因魯棒性強、搜索速度快而得到廣泛應用，但存在搜索效率低、易陷入局部最優等缺點[7]。為了解決路徑的平滑問題，文獻[8]在啟發函數中考慮了無人機轉彎次數的影響，增強了算法的全局搜索能力，提高了路徑的平滑性，但改進后的算法仍存在初期收斂速度慢、易陷入局部最優的缺點。文獻[9]基于最短路徑的目標，提出了一種改進信息素更新規則的蟻群算法，在運行時間和收斂速度方面性能均有所提升，但只考慮了路徑最短，沒有綜合考慮無人機航跡的安全性、平滑性等其他因素。文獻[10]提出了一種考慮節點到目標節點以及節點到起始節點距離的引導因子，通過改進算法的引導因子增強啟發函數的引導作用，但由于受信息素初始分布的影響，該算法易陷入局部最優。文獻[11]提出了一種利用幾何優化的方法，采用自適應參數調整方法提高蟻群算法的搜索能力和個體間的交互能力，有效改進了傳統蟻群算法收斂速度慢、易陷入局部最優的問題，但是在算法初期仍存在搜索速度慢的問題。

綜上，首先為山區物流配送無人機建立了包括山體在內的三維環境模型；然后構造了基于航跡長度、障礙物碰撞和高度變化的適應度函數，考慮引入航跡引導因子提出了一種改進信息素更新規則的蟻群算法；最后通過仿真實驗驗證了新算法在任務規劃空間規劃出的航跡是合理和可行的。

1 模型建立

1.1 環境建模

對于無人機飛行環境中山區較高的天然山體，采用指數函數進行描述[12]，如式(1)所示。

(1)

式中：N表示山峰總個數；(xoi，yoi)是第i座小山坡的中心坐標；hi表示第i座小山坡的高度；xsi、ysi分別是第i座小山坡的坡度。三維環境建模的效果如圖1所示。建模空間為220 km×220 km×80 km，其中包含2座山峰。山峰的相關參數設置：hi=[74,78]，xoi=[55,155]，yoi=[65,125]，xsi=[25,18]，ysi=[20,25]。

圖1 環境模型示意圖

1.2 航跡代價函數建模

航跡代價函數用于計算可飛航跡的代價，比較不同航跡的代價值以找到最優航跡。綜合考慮航跡長度、障礙物碰撞以及高度變化的影響，無人機航跡代價函數模型表示為：

F=φ1fL+φ2fC+φ3fH

(2)

式中：F表示航跡代價；fL表示航程代價；fC表示障礙物碰撞代價；fH表示高度變化代價；φ1、φ2、φ3為常數，代表不同成本的權重值，其權重比例值與無人機執行的任務有關。

航程代價fL主要考慮無人機從起點到終點的飛行航跡長度，如果總航跡由n個航點組成，經插值法平滑后整個航跡由N個航點組成，(xi,yi,zi)和(xi+1,yi+1,zi+1)分別表示第i個航點與相鄰下一航點的三維坐標，則航程代價表示為：

i∈[1,2,…,N-1]

(3)

障礙物碰撞代價fC主要考慮無人機航跡節點與障礙物的距離。當無人機飛行高度低于障礙物高度且與障礙物中心點的距離小于障礙物的半徑時，將發生碰撞。障礙物碰撞代價表示為：

(4)

(5)

式中：T表示障礙物的個數；N表示航跡平滑后的節點總數量；Ci, j表示第i個障礙物和第j個航跡節點間的距離；Robsi表示障礙物i的半徑。

高度變化代價fH主要考慮無人機因避開障礙物飛行高度的變化，用航跡高度的方差來刻畫。高度變化代價表示為：

(6)

式中：N表示航跡節點總數量；zk表示第k個航跡節點處的高度值。

2 蟻群算法及其改進

2.1 基本蟻群算法

基本蟻群算法是受螞蟻覓食過程中尋找路徑啟發而產生的一種群智能仿生算法。該算法求解優化問題的基本思想是：用螞蟻的行走路徑表示待優化問題的可行解，整個螞蟻群體的所有路徑構成待優化問題的解空間[13]。信息素的含量是由路徑的長短決定的，路徑越長信息素的含量越低。螞蟻對路徑的選擇取決于信息素的含量，含量越高，該路徑被選擇的幾率越大。隨著時間的推移，大部分螞蟻最終都會集中在較短的路徑上，那么該路徑就是該優化問題的最優解[14-15]。

每只螞蟻前進的方向主要和2個因素有關，一個是信息素，另一個是啟發式信息。路徑上信息素的含量越高，螞蟻選擇該路徑的可能性越大；而啟發式信息是指導每只螞蟻確定下一步前進的方向。因此，蟻群算法的優劣關鍵在于信息素更新模型和啟發式函數的構建[16-17]。

螞蟻根據轉移概率確定下一步前進的方向，轉移概率表示為：

(7)

式中：ηi, j(t)為啟發函數，通常取ηi, j(t)= 1/di j(d為兩節點i，j中心的歐式距離)；τi， j(t)為信息素；allowedi為節點i處可行鄰接節點的集合；m為螞蟻標號；i為當前位置節點標號；j為待轉移的下一位置節點標號；t為當前迭代次數；α、β分別表示信息素和啟發式因素的相對重要性。

信息素是構建蟻群算法的關鍵，螞蟻走過的路徑越短，信息素濃度越高，越能起到對螞蟻的引導作用。隨著時間的推移，信息素也會蒸發，故需要建立信息素更新模型。常見的信息素更新模型有蟻周模型、蟻量模型和蟻密模型[18]。本文中使用蟻周模型，如式(8)和式(9)所示。

(8)

(9)

式中：ρ為信息素揮發因子；Q為信息素常數；Lm為第m只螞蟻在本次循環中走過的路徑總長度；M為螞蟻總數。

2.2 改進蟻群算法的航跡規劃

2.2.1添加航跡引導因子

為了提高算法初期搜索路徑的效率和搜索速度，在啟發式函數中引入航跡引導因子，見式(10)。航跡引導因子是當前節點與起點節點的偏移量以及當前節點與目標節點的偏移量和的加權倒數。這可使螞蟻在算法初期確定可行解的大致方向，使螞蟻朝該方向行進，減少算法的迭代時間，提高算法的收斂速度。

(10)

式中：θi j為航跡引導因子；a，b均為常數，表示權重影響大小；s為起點，e為目標點；dj,e表示節點j到目標點e的距離；ds, j表示節點j到起點s的距離。

(11)

2.2.2信息素的更新方式

傳統信息素更新方式為蟻周模型，在該模型中，信息素的更新只考慮路徑的長度。但在實際需求中，最優航跡不僅要求航跡短，平滑性和安全性也不可缺少。因此，本文在信息素的更新方式上進行改進，改進后信息素的更新方式見式(8)和式(12)所示，分別表示為：

(12)

式(12)中:Fm為在第t次迭代中第m只螞蟻路徑的航跡代價函數值，其數值越小，航跡越優。其他字符含義同式(9)。

2.3 基于B樣條曲線的航跡平滑算法

由于無人機的航跡是通過航跡點的連線構成，算法最終搜索出來的航跡一般是曲折、不平滑的，考慮無人機自身的機動性能限制，需要對搜索出來的航跡進行平滑處理。而B樣條曲線具有連續性、局部可調整性等優點，使得該曲線在路徑規劃中被廣泛使用[19]。因此，提出基于三次B樣條曲線的航跡優化處理，與算法相結合生成一條平穩光滑的航跡，確保無人機飛行的連續性和平穩性。

Riesenfeld等在1972年構造了B樣條曲線，將Bernstein基函數用B樣條基函數來代替。B樣條曲線是分段組成的，每一段的參數區間為[0,1]，因此克服了貝塞爾曲線改變任意控制點時其曲線上所有點也改變的缺陷，使得樣條曲線具有局部修改的特性[20]，這種優點使得B樣條曲線廣泛應用于路徑規劃中。

設有n+1個控制點P0,P1,…,Pn，則k階B樣條曲線的數學表達式為

(13)

式中：Ni,k(u)是第i個k階B樣條基函數，u是自變量。

基函數具有如式(14)和式(15)的Cox-deBoor遞推式。

經過考古數據的匯總，實物文本分析及比對，昂昂溪文化原始美術分布特點及整體的美術特征相關研究的結論如下：

(14)

(15)

式中：ui是一組被稱為節點矢量的非遞減序列的連續變化值。

2.4 改進算法流程

步驟1根據式(1)創建三維環境，并設置無人機的起點和終點；

步驟2初始化。包括信息素初始化、啟發函數初始化以及蟻群規模、信息素揮發因子等參數的初始化；

步驟3將所有螞蟻放在起始點上，構建禁忌表(禁忌表用來存放螞蟻已經走過的節點，避免已經走過的節點再次被螞蟻選擇)；

步驟4根據式(11)計算轉移概率來確定螞蟻下一個要走的節點，將走過的節點放入禁忌表中。當螞蟻到達目標節點時，即完成一次搜索。

步驟5通過三次B樣條曲線的數據插值處理，對含有n個航跡點的航跡進行平滑，得到一條包含N個航跡點的航跡。計算每只螞蟻的路徑代價函數值，找出本次迭代的最優路徑；

步驟6根據式(8)和式(12)對信息素的含量進行更新；

步驟7將每次迭代的經過數據插值處理后的最優航跡進行比較，找到當前的最優航跡；

步驟8判斷迭代次數是否達到設定的最大值，若達到最大，則輸出最優航跡；否則，繼續進行迭代。

3 算法仿真及評價

3.1 仿真環境及參數選取

采用Matlab R2021a仿真軟件對傳統蟻群算法、多啟發因素改進蟻群算法和本文改進算法在相同條件下進行仿真對比。仿真實驗在Win10 64位操作系統、AMD Ryzen 5 4500U處理器、8GB RAM配置下的計算機上運行。

建模任務空間為220 km×220 km×80 km，包含了4個山峰。起點坐標為[12,22,10]，終點坐標為[150,180,45]。

傳統蟻群算法、多啟發因素改進蟻群算法以及本文算法的參數設置如表1所示。

表1 算法參數設置

根據上述條件，使用傳統蟻群算法、多啟發因素改進蟻群算法和本文算法分別進行離線航跡規劃，仿真次數為100次。記錄3種算法各自的算法用時、轉彎次數和綜合指標等數據。

3.2 仿真結果及其分析

將本文算法、傳統蟻群算法和多啟發因素改進蟻群算法在220 km×220 km×80 km的三維地圖環境上進行對比實驗，仿真結果如表2和圖2—5所示。

表2 實驗指標相關數據

如圖2所示，實線為本文改進蟻群算法的最優航跡，點畫線為多啟發因素改進算法的最優航跡，虛線為傳統蟻群算法的最優航跡。可以看出，實線的轉彎次數更少，平滑性更好，路徑更短。

圖2 最優航跡仿真結果示意圖

圖3為不同迭代次數時，3種算法的最優航跡長度曲線。可以看出，傳統蟻群算法的航跡長度一直都是最長的。在開始時，虛線的航跡長度比點畫線的航跡長度短。但是在進行迭代之后，點畫線很快找到了最優航跡，在相同迭代次數下，點畫線的航跡一直是最佳的。

圖3 最優航跡長度曲線

圖4為不同迭代次數時，3種算法的最優航跡的高度方差曲線。可以看出，在相同的迭代次數下，點畫線的高度方差一直低于實線和虛線，說明點畫線的航跡相較于其他2種算法更具平穩性。

圖4 最優航跡的高度方差曲線

圖5為不同迭代次數時，3種算法的最優航跡的綜合指標曲線。綜合指標用適應度函數來刻畫，適應度函數值越低，即綜合指標值越低，則算法越優。從圖5可以看出，虛線的綜合指標開始時低于點畫線的綜合指標，隨著迭代次數的增加，點畫線的綜合指標明顯低于虛線的綜合指標。

圖5 最優航跡的綜合指標曲線

4 結論

提出一種改進的蟻群算法。為了提高蟻群算法初期的搜索效率和速度，促使算法跳出局部最優，對轉移概率和信息素更新方式進行改善，引入了航跡引導因子，將當前節點到起點節點以及當前節點到目標節點的距離作為啟發函數的影響因子之一，并將航跡的綜合評價考慮進信息素更新方式中。仿真實驗表明，與傳統蟻群算法和多啟發因素改進蟻群算法相比，本文算法可以更快地搜索最優航跡，航跡更短、更平滑，所需代價更小。