改進(jìn)ACO算法的UAV航跡規(guī)劃在山區(qū)物流配送中的應(yīng)用研究

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

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

0 引言

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

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

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

1 模型建立

1.1 環(huán)境建模

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

(1)

式中：N表示山峰總個(gè)數(shù)；(xoi，yoi)是第i座小山坡的中心坐標(biāo)；hi表示第i座小山坡的高度；xsi、ysi分別是第i座小山坡的坡度。三維環(huán)境建模的效果如圖1所示。建?？臻g為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 航跡代價(jià)函數(shù)建模

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

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

(2)

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

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

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

(3)

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

(4)

(5)

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

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

(6)

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

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

2.1 基本蟻群算法

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

每只螞蟻前進(jìn)的方向主要和2個(gè)因素有關(guān)，一個(gè)是信息素，另一個(gè)是啟發(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)號(hào)；i為當(dāng)前位置節(jié)點(diǎn)標(biāo)號(hào)；j為待轉(zhuǎn)移的下一位置節(jié)點(diǎn)標(biāo)號(hào)；t為當(dāng)前迭代次數(shù)；α、β分別表示信息素和啟發(fā)式因素的相對(duì)重要性。

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

(8)

(9)

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

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

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

為了提高算法初期搜索路徑的效率和搜索速度，在啟發(fā)式函數(shù)中引入航跡引導(dǎo)因子，見(jiàn)式(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)，減少算法的迭代時(shí)間，提高算法的收斂速度。

(10)

式中：θi j為航跡引導(dǎo)因子；a，b均為常數(shù)，表示權(quán)重影響大?。籹為起點(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)信息素更新方式為蟻周模型，在該模型中，信息素的更新只考慮路徑的長(zhǎng)度。但在實(shí)際需求中，最優(yōu)航跡不僅要求航跡短，平滑性和安全性也不可缺少。因此，本文在信息素的更新方式上進(jìn)行改進(jìn)，改進(jìn)后信息素的更新方式見(jiàn)式(8)和式(12)所示，分別表示為：

(12)

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

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

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

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

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

(13)

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

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

經(jīng)過(guò)考古數(shù)據(jù)的匯總，實(shí)物文本分析及比對(duì)，昂昂溪文化原始美術(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è)置無(wú)人機(jī)的起點(diǎn)和終點(diǎn)；

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

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

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

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

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

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

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

3 算法仿真及評(píng)價(jià)

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

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

建模任務(wù)空間為220 km×220 km×80 km，包含了4個(gè)山峰。起點(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種算法各自的算法用時(shí)、轉(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)行對(duì)比實(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ù)時(shí)，3種算法的最優(yōu)航跡長(zhǎng)度曲線。可以看出，傳統(tǒng)蟻群算法的航跡長(zhǎng)度一直都是最長(zhǎng)的。在開(kāi)始時(shí)，虛線的航跡長(zhǎng)度比點(diǎn)畫線的航跡長(zhǎng)度短。但是在進(jìn)行迭代之后，點(diǎn)畫線很快找到了最優(yōu)航跡，在相同迭代次數(shù)下，點(diǎn)畫線的航跡一直是最佳的。

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

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

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

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

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

4 結(jié)論

提出一種改進(jìn)的蟻群算法。為了提高蟻群算法初期的搜索效率和速度，促使算法跳出局部最優(yōu)，對(duì)轉(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ù)的影響因子之一，并將航跡的綜合評(píng)價(jià)考慮進(jìn)信息素更新方式中。仿真實(shí)驗(yàn)表明，與傳統(tǒng)蟻群算法和多啟發(fā)因素改進(jìn)蟻群算法相比，本文算法可以更快地搜索最優(yōu)航跡，航跡更短、更平滑，所需代價(jià)更小。