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

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

0 引言

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

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

綜上，首先為山區(qū)物流配送無人機(jī)建立了包括山體在內(nèi)的三維環(huán)境模型；然后構(gòu)造了基于航跡長度、障礙物碰撞和高度變化的適應(yīng)度函數(shù)，考慮引入航跡引導(dǎo)因子提出了一種改進(jìn)信息素更新規(guī)則的蟻群算法；最后通過仿真實(shí)驗(yàn)驗(yàn)證了新算法在任務(wù)規(guī)劃空間規(guī)劃出的航跡是合理和可行的。

1 模型建立

1.1 環(huán)境建模

對于無人機(jī)飛行環(huán)境中山區(qū)較高的天然山體，采用指數(shù)函數(shù)進(jìn)行描述[12]，如式(1)所示。

(1)

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

圖1 環(huán)境模型示意圖

1.2 航跡代價函數(shù)建模

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

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

(2)

式中：F表示航跡代價；fL表示航程代價；fC表示障礙物碰撞代價；fH表示高度變化代價；φ1、φ2、φ3為常數(shù)，代表不同成本的權(quán)重值，其權(quán)重比例值與無人機(jī)執(zhí)行的任務(wù)有關(guān)。

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

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

(3)

障礙物碰撞代價fC主要考慮無人機(jī)航跡節(jié)點(diǎn)與障礙物的距離。當(dāng)無人機(jī)飛行高度低于障礙物高度且與障礙物中心點(diǎn)的距離小于障礙物的半徑時，將發(fā)生碰撞。障礙物碰撞代價表示為：

(4)

(5)

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

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

(6)

式中：N表示航跡節(jié)點(diǎn)總數(shù)量；zk表示第k個航跡節(jié)點(diǎn)處的高度值。

2 蟻群算法及其改進(jìn)

2.1 基本蟻群算法

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

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

螞蟻根據(jù)轉(zhuǎn)移概率確定下一步前進(jìn)的方向，轉(zhuǎn)移概率表示為：

(7)

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

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

(8)

(9)

式中：ρ為信息素?fù)]發(fā)因子；Q為信息素常數(shù)；Lm為第m只螞蟻在本次循環(huán)中走過的路徑總長度；M為螞蟻總數(shù)。

2.2 改進(jìn)蟻群算法的航跡規(guī)劃

2.2.1添加航跡引導(dǎo)因子

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

(10)

式中：θi j為航跡引導(dǎo)因子；a，b均為常數(shù)，表示權(quán)重影響大小；s為起點(diǎn)，e為目標(biāo)點(diǎn)；dj,e表示節(jié)點(diǎn)j到目標(biāo)點(diǎn)e的距離；ds, j表示節(jié)點(diǎn)j到起點(diǎn)s的距離。

(11)

2.2.2信息素的更新方式

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

(12)

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

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

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

Riesenfeld等在1972年構(gòu)造了B樣條曲線，將Bernstein基函數(shù)用B樣條基函數(shù)來代替。B樣條曲線是分段組成的，每一段的參數(shù)區(qū)間為[0,1]，因此克服了貝塞爾曲線改變?nèi)我饪刂泣c(diǎn)時其曲線上所有點(diǎn)也改變的缺陷，使得樣條曲線具有局部修改的特性[20]，這種優(yōu)點(diǎn)使得B樣條曲線廣泛應(yīng)用于路徑規(guī)劃中。

設(shè)有n+1個控制點(diǎn)P0,P1,…,Pn，則k階B樣條曲線的數(shù)學(xué)表達(dá)式為

(13)

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

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

經(jīng)過考古數(shù)據(jù)的匯總，實(shí)物文本分析及比對，昂昂溪文化原始美術(shù)分布特點(diǎn)及整體的美術(shù)特征相關(guān)研究的結(jié)論如下：

(14)

(15)

式中：ui是一組被稱為節(jié)點(diǎn)矢量的非遞減序列的連續(xù)變化值。

2.4 改進(jìn)算法流程

步驟1根據(jù)式(1)創(chuàng)建三維環(huán)境，并設(shè)置無人機(jī)的起點(diǎn)和終點(diǎn)；

步驟2初始化。包括信息素初始化、啟發(fā)函數(shù)初始化以及蟻群規(guī)模、信息素?fù)]發(fā)因子等參數(shù)的初始化；

步驟3將所有螞蟻放在起始點(diǎn)上，構(gòu)建禁忌表(禁忌表用來存放螞蟻已經(jīng)走過的節(jié)點(diǎn)，避免已經(jīng)走過的節(jié)點(diǎn)再次被螞蟻選擇)；

步驟4根據(jù)式(11)計算轉(zhuǎn)移概率來確定螞蟻下一個要走的節(jié)點(diǎn)，將走過的節(jié)點(diǎn)放入禁忌表中。當(dāng)螞蟻到達(dá)目標(biāo)節(jié)點(diǎn)時，即完成一次搜索。

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

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

步驟7將每次迭代的經(jīng)過數(shù)據(jù)插值處理后的最優(yōu)航跡進(jìn)行比較，找到當(dāng)前的最優(yōu)航跡；

步驟8判斷迭代次數(shù)是否達(dá)到設(shè)定的最大值，若達(dá)到最大，則輸出最優(yōu)航跡；否則，繼續(xù)進(jìn)行迭代。

3 算法仿真及評價

3.1 仿真環(huán)境及參數(shù)選取

采用Matlab R2021a仿真軟件對傳統(tǒng)蟻群算法、多啟發(fā)因素改進(jìn)蟻群算法和本文改進(jìn)算法在相同條件下進(jìn)行仿真對比。仿真實(shí)驗(yàn)在Win10 64位操作系統(tǒng)、AMD Ryzen 5 4500U處理器、8GB RAM配置下的計算機(jī)上運(yùn)行。

建模任務(wù)空間為220 km×220 km×80 km，包含了4個山峰。起點(diǎn)坐標(biāo)為[12,22,10]，終點(diǎn)坐標(biāo)為[150,180,45]。

傳統(tǒng)蟻群算法、多啟發(fā)因素改進(jìn)蟻群算法以及本文算法的參數(shù)設(shè)置如表1所示。

表1 算法參數(shù)設(shè)置

根據(jù)上述條件，使用傳統(tǒng)蟻群算法、多啟發(fā)因素改進(jìn)蟻群算法和本文算法分別進(jìn)行離線航跡規(guī)劃，仿真次數(shù)為100次。記錄3種算法各自的算法用時、轉(zhuǎn)彎次數(shù)和綜合指標(biāo)等數(shù)據(jù)。

3.2 仿真結(jié)果及其分析

將本文算法、傳統(tǒng)蟻群算法和多啟發(fā)因素改進(jìn)蟻群算法在220 km×220 km×80 km的三維地圖環(huán)境上進(jìn)行對比實(shí)驗(yàn)，仿真結(jié)果如表2和圖2—5所示。

表2 實(shí)驗(yàn)指標(biāo)相關(guān)數(shù)據(jù)

如圖2所示，實(shí)線為本文改進(jìn)蟻群算法的最優(yōu)航跡，點(diǎn)畫線為多啟發(fā)因素改進(jìn)算法的最優(yōu)航跡，虛線為傳統(tǒng)蟻群算法的最優(yōu)航跡。可以看出，實(shí)線的轉(zhuǎn)彎次數(shù)更少，平滑性更好，路徑更短。

圖2 最優(yōu)航跡仿真結(jié)果示意圖

圖3為不同迭代次數(shù)時，3種算法的最優(yōu)航跡長度曲線?？梢钥闯?，傳統(tǒng)蟻群算法的航跡長度一直都是最長的。在開始時，虛線的航跡長度比點(diǎn)畫線的航跡長度短。但是在進(jìn)行迭代之后，點(diǎn)畫線很快找到了最優(yōu)航跡，在相同迭代次數(shù)下，點(diǎn)畫線的航跡一直是最佳的。

圖3 最優(yōu)航跡長度曲線

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

圖4 最優(yōu)航跡的高度方差曲線

圖5為不同迭代次數(shù)時，3種算法的最優(yōu)航跡的綜合指標(biāo)曲線。綜合指標(biāo)用適應(yīng)度函數(shù)來刻畫，適應(yīng)度函數(shù)值越低，即綜合指標(biāo)值越低，則算法越優(yōu)。從圖5可以看出，虛線的綜合指標(biāo)開始時低于點(diǎn)畫線的綜合指標(biāo)，隨著迭代次數(shù)的增加，點(diǎn)畫線的綜合指標(biāo)明顯低于虛線的綜合指標(biāo)。

圖5 最優(yōu)航跡的綜合指標(biāo)曲線

4 結(jié)論

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