基于改進(jìn)蟻群算法的無(wú)人機(jī)三維航跡規(guī)劃研究*

趙冬梅 周 波 宋 陽(yáng) 周國(guó)軍

（海軍大連艦艇學(xué)院基礎(chǔ)部 大連 116018）

1 引言

無(wú)人機(jī)（UAV）結(jié)構(gòu)簡(jiǎn)單，價(jià)格低廉，安全性好，適用于執(zhí)行偵察、攻擊和評(píng)估等軍事任務(wù)。2020年1 月3 日，美國(guó)出動(dòng)無(wú)人機(jī)在巴格達(dá)機(jī)場(chǎng)附近暗殺前伊斯蘭革命衛(wèi)隊(duì)圣城軍指揮官蘇萊曼尼［1］。隨著無(wú)人機(jī)技術(shù)的發(fā)展，在未來(lái)戰(zhàn)場(chǎng)上，無(wú)人機(jī)將大顯身手，成為陸、海、空戰(zhàn)的主力。航跡規(guī)劃是無(wú)人機(jī)完成任務(wù)的前提，是無(wú)人機(jī)技術(shù)研究的關(guān)鍵環(huán)節(jié)。航跡規(guī)劃的目的是在復(fù)雜的戰(zhàn)場(chǎng)環(huán)境中，在滿足一定的約束條件下，尋找一條從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑［2］。目前，國(guó)內(nèi)外學(xué)者圍繞無(wú)人機(jī)的航跡規(guī)劃算法開(kāi)展了大量研究［3］，主要分為Dijkstra算法［4］、模擬退火算法［5］和人工勢(shì)場(chǎng)法［6～7］等傳統(tǒng)經(jīng)典算法和遺傳算法［8］、粒子群優(yōu)化算法［9］和蟻群優(yōu)化算法［10～11］等現(xiàn)代智能算法。

相比于經(jīng)典算法，智能優(yōu)化算法以其概念簡(jiǎn)明、實(shí)現(xiàn)方便、參數(shù)設(shè)置少、魯棒性強(qiáng)［12］等優(yōu)點(diǎn)越來(lái)越受到研究學(xué)者的青睞。文獻(xiàn)［13］采用基于時(shí)間和空間的信息素?fù)]發(fā)因子自適應(yīng)更新策略改進(jìn)蟻群算法，保證搜索范圍的同時(shí)加快了收斂速度；文獻(xiàn)［14］提出改進(jìn)變步長(zhǎng)蟻群算法，兼顧較大的搜索區(qū)域和較少的迭代次數(shù)，提高算法的全局尋優(yōu)能力；文獻(xiàn)［15］將起始點(diǎn)和目的點(diǎn)的直線連線作為對(duì)角線劃定矩形區(qū)域，區(qū)別初始化區(qū)域內(nèi)和區(qū)域外的信息素濃度，利于減小搜索初期的盲目性，但沒(méi)有進(jìn)一步細(xì)化信息素差異；文獻(xiàn)［16］提出一種新的信息素更新機(jī)制，在迭代后期將每代最優(yōu)路徑長(zhǎng)度引入信息素增量公式中，區(qū)分不同搜索時(shí)期的信息素更新，但以固定的迭代次數(shù)作為劃分依據(jù)，降低算法的靈活性；文獻(xiàn)［17］根據(jù)最優(yōu)解增加最優(yōu)路徑上的信息素，根據(jù)最差解減弱最差路徑上的信息素，提高了蟻群算法的收斂速度，但沒(méi)有解決易陷入局部最優(yōu)問(wèn)題。

綜合上述文獻(xiàn)對(duì)蟻群算法改進(jìn)的優(yōu)缺點(diǎn)，提出一種新的改進(jìn)思路：初始化信息素時(shí)增大出發(fā)點(diǎn)和目標(biāo)點(diǎn)連線附近的濃度，同時(shí)根據(jù)距離遠(yuǎn)近設(shè)置濃度差異，使螞蟻在搜索初期就能沿著目標(biāo)點(diǎn)方向選擇路徑，提高搜索的指向性；為提高搜索效率，改進(jìn)啟發(fā)函數(shù)，增加待選點(diǎn)和目標(biāo)點(diǎn)的距離信息以及相鄰航跡的轉(zhuǎn)角信息；隨著算法的進(jìn)程，優(yōu)質(zhì)路徑的優(yōu)勢(shì)逐漸顯現(xiàn)，故在搜索后期進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)，采用概率選擇和確定性選擇相融合的策略，進(jìn)一步提高算法的收斂速度；完善信息素更新機(jī)制，根據(jù)迭代次數(shù)動(dòng)態(tài)調(diào)整信息素總量，自適應(yīng)地進(jìn)行信息素更新，以平衡算法收斂速度和陷入局部最優(yōu)之間的矛盾。最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證算法的優(yōu)越性。

2 航跡規(guī)劃問(wèn)題建模

2.1 問(wèn)題描述

無(wú)人機(jī)在100km×100km×8km的空間區(qū)域內(nèi)從基地出發(fā)，到達(dá)目標(biāo)點(diǎn)執(zhí)行攻擊任務(wù)，這就需要規(guī)劃出一條避開(kāi)障礙物、路徑較短、高度起伏和轉(zhuǎn)彎較小的最優(yōu)航跡。

2.2 三維環(huán)境地形建模

采取隨機(jī)地形和典型地形相結(jié)合的方式建立環(huán)境地形模型。通過(guò)式（1）設(shè)置隨機(jī)地形的高度，模擬較平坦的地形。

式（2）用于模擬典型地形山峰或山谷，n 為山峰或山谷的個(gè)數(shù)，（xi0，yi0）為山峰或山谷的中心坐標(biāo)，hi為高度值，通過(guò)xis和yis設(shè)置峰谷的陡峭程度。

取隨機(jī)地形和典型地形的較大值為坐標(biāo)點(diǎn)（x，y）對(duì)應(yīng)的實(shí)際高度值z(mì)，如式（3）所示。

2.3 三維空間抽象建模

參考文獻(xiàn)［18］，在三維坐標(biāo)系下，沿x 軸取經(jīng)度方向，沿y 軸取緯度方向，沿z 軸取海拔高度方向。當(dāng)無(wú)人機(jī)執(zhí)行任務(wù)的搜索空間確定后，其在三維坐標(biāo)系下的路徑空間也隨之建立。以xGrid、yGrid、zGrid為步長(zhǎng)分別對(duì)x、y、z 三個(gè)方向進(jìn)行等分，從而確定航跡規(guī)劃空間內(nèi)離散化的三維點(diǎn)集合。無(wú)人機(jī)航跡規(guī)劃可以抽象為在這些三維點(diǎn)中進(jìn)行航跡點(diǎn)選擇，確定從出發(fā)點(diǎn)S（xs，ys，zs）到目標(biāo)點(diǎn)T（xt，yt，zt）的最優(yōu)航跡。

2.4 搜索區(qū)域規(guī)則

為降低航跡規(guī)劃的復(fù)雜度，規(guī)定經(jīng)度方向?yàn)槲浵佉苿?dòng)的主方向，即無(wú)人機(jī)沿x 軸方向以xGrid的固定步長(zhǎng)移動(dòng)，同時(shí)設(shè)置螞蟻沿緯度和高度方向均有最大允許移動(dòng)距離，分別為Dymax和Dzmax，這就為螞蟻選擇下一航跡點(diǎn)提供了一個(gè)較小的可搜索空間，進(jìn)一步提高算法的運(yùn)行效率。

3 改進(jìn)蟻群算法

3.1 蟻群算法原理

螞蟻從出發(fā)點(diǎn)開(kāi)始，根據(jù)信息素τij(t)和啟發(fā)函數(shù)ηij(t)按照式（4）的概率選擇下一個(gè)節(jié)點(diǎn)，直至到達(dá)目標(biāo)點(diǎn)并計(jì)算航跡距離。

式（4）中，allowm為螞蟻m 待訪問(wèn)節(jié)點(diǎn)的集合，α和β分別為信息素和啟發(fā)函數(shù)重要程度參數(shù)，體現(xiàn)蟻群先驗(yàn)知識(shí)和未探知航跡的權(quán)重大小。

隨著時(shí)間的推移，信息素濃度會(huì)逐漸揮發(fā)，ρ為揮發(fā)因子，當(dāng)所有螞蟻尋找到一條從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的航跡后，信息素按式（5）進(jìn)行更新。

重復(fù)上述計(jì)算轉(zhuǎn)移概率、確定下一節(jié)點(diǎn)、計(jì)算各個(gè)螞蟻路徑長(zhǎng)度、更新信息素濃度的步驟，直至迭代結(jié)束，得到最優(yōu)航跡BestPath。

3.2 非均勻初始化信息素

信息素是吸引螞蟻移動(dòng)的主要因素之一，合理設(shè)置信息素的初始值和更新方法是蟻群算法有效實(shí)現(xiàn)的重要保證。傳統(tǒng)蟻群算法設(shè)置濃度相同的信息素初始值，信息素的均勻分布增加了螞蟻搜索初期的難度，使算法不易收斂。為引導(dǎo)螞蟻從出發(fā)點(diǎn)朝著目標(biāo)點(diǎn)方向移動(dòng)，設(shè)置非均勻分布的信息素初始值。

以無(wú)人機(jī)出發(fā)點(diǎn)和目標(biāo)點(diǎn)的連線ST 為中心，向四周空間輻射的信息素濃度逐漸減小。設(shè)計(jì)方法為計(jì)算空間中任一航跡點(diǎn)到直線ST 的垂直距離d，該航跡點(diǎn)信息素的初始值τ與距離d 服從指數(shù)分布，二者關(guān)系為

其中，τ0為ST上航跡點(diǎn)的信息素初始值，也是信息素初始值的最大值。

根據(jù)上述設(shè)計(jì)，信息素初始值呈現(xiàn)以出發(fā)點(diǎn)和目標(biāo)點(diǎn)連線為中心的指數(shù)遞減分布，突出了搜索初期從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的引導(dǎo)性，極大提高了算法的效率和準(zhǔn)確性。

3.3 基于距離和轉(zhuǎn)角的啟發(fā)信息

啟發(fā)信息是吸引螞蟻移動(dòng)的另一重要因素，文獻(xiàn)［20］將目標(biāo)節(jié)點(diǎn)信息加入啟發(fā)因子中，利于算法收斂，但忽略了局部最短路徑，易出現(xiàn)折線路徑。為此，本文將待選航跡點(diǎn)與目標(biāo)點(diǎn)距離和相鄰航跡間的轉(zhuǎn)角兩項(xiàng)因素融入啟發(fā)函數(shù)中，降低螞蟻轉(zhuǎn)彎的概率，進(jìn)一步縮短航跡，減小無(wú)人機(jī)能耗。

其中，γ1、γ2、γ3為上述三個(gè)因素的權(quán)重因素，代表它們各自的重要程度。

1）相鄰航跡點(diǎn)距離

Dij的計(jì)算公式如下：

式中，（xi，yi，zi）為當(dāng)前航跡點(diǎn)的坐標(biāo)值，（xj，yj，zj）為待選航跡點(diǎn)的坐標(biāo)值，該啟發(fā)信息的設(shè)置有利于螞蟻選取距離較短的航跡點(diǎn)。

2）待選航跡點(diǎn)與目標(biāo)點(diǎn)距離

Qij的計(jì)算公式如下：

式中，（xj，yj，zj）為待選航跡點(diǎn)的坐標(biāo)值，（xt，yt，zt）為目標(biāo)點(diǎn)的坐標(biāo)值，該啟發(fā)信息的設(shè)置有利于螞蟻選取距離目標(biāo)較近的航跡點(diǎn)。

3）相鄰航跡線的轉(zhuǎn)角信息

式中，ε是值大于0 的轉(zhuǎn)角調(diào)整系數(shù)，目的是防止Φij的分母為0，該啟發(fā)信息的設(shè)置有助于螞蟻選取轉(zhuǎn)角較小的航跡點(diǎn)。

3.4 融入確定性選擇的狀態(tài)轉(zhuǎn)移策略

選擇下一節(jié)點(diǎn)j的方法為

其中，q 為0～1 之間的隨機(jī)數(shù)，q0為0～1 之間的可調(diào)參數(shù)，表示使用確定性節(jié)點(diǎn)轉(zhuǎn)移策略的概率。

3.5 動(dòng)態(tài)調(diào)整的信息素更新機(jī)制

改變傳統(tǒng)蟻群算法信息素總量Q 固定不變的機(jī)制，以算法迭代次數(shù)為變量控制Q的取值。在搜索初期，由于螞蟻主要根據(jù)非均勻初始化的信息素濃度尋找航跡，可設(shè)置較大的Q 值，有助于提高搜索效率；隨著算法的推進(jìn)，經(jīng)過(guò)一定次數(shù)的迭代，各航跡上的信息素?cái)?shù)值較大，為避免阻塞和停滯，應(yīng)適當(dāng)降低Q 值，利于螞蟻進(jìn)行全局搜索；在算法后期，螞蟻已基本找到最優(yōu)航跡，為加快算法收斂，可再適當(dāng)增加Q 值。因此，設(shè)計(jì)信息素總量Q 隨迭代次數(shù)服從倒置的高斯分布，表達(dá)式為

其中，l為迭代次數(shù)，c取值為最大迭代次數(shù)的1/2，σ取值為最大迭代次數(shù)的1/4，設(shè)置信息素總量Q 的取值范圍在［Qmin，Qmax］區(qū)間內(nèi)。

對(duì)于信息素更新公式（5），為平衡算法的全局搜索能力和收斂速度，采取參考文獻(xiàn)［21］提出的自適應(yīng)信息素更新策略，公式為

其中，φm=a·l，和迭代次數(shù)l成正比，a為常數(shù)。

3.6 航跡評(píng)價(jià)函數(shù)

航跡評(píng)價(jià)函數(shù)體現(xiàn)無(wú)人機(jī)航跡規(guī)劃的優(yōu)劣程度。本文設(shè)計(jì)基于航程距離代價(jià)、海拔高度代價(jià)和相鄰航線轉(zhuǎn)角代價(jià)的航跡評(píng)價(jià)函數(shù)，表達(dá)式如下：

其中，ωD、ωH和ωθ分別為航程、海拔和轉(zhuǎn)角代價(jià)的權(quán)重因子。

上述評(píng)價(jià)指標(biāo)兼顧了飛行距離、高度和轉(zhuǎn)角，能夠引導(dǎo)螞蟻選擇出長(zhǎng)度較短、高度起伏較緩和轉(zhuǎn)動(dòng)角度較小的最優(yōu)航跡。

4 算法流程

應(yīng)用改進(jìn)蟻群算法進(jìn)行無(wú)人機(jī)三維航跡規(guī)劃的流程如圖1所示。

圖1 改進(jìn)蟻群算法流程圖

5 仿真實(shí)驗(yàn)與結(jié)果分析

為檢驗(yàn)本文提出的改進(jìn)蟻群算法的有效性，進(jìn)行如下仿真實(shí)驗(yàn)。設(shè)置螞蟻數(shù)量為20，出發(fā)點(diǎn)和目標(biāo)點(diǎn)坐標(biāo)分別為（1，20，4）和（100，80，5），最大迭代次數(shù)NC=400。環(huán)境建模參數(shù)如表1所示。

表1 三維環(huán)境建模參數(shù)

傳統(tǒng)蟻群算法和改進(jìn)蟻群算法規(guī)劃的航跡如圖2所示。

圖2 傳統(tǒng)蟻群算法和改進(jìn)蟻群算法規(guī)劃航跡對(duì)比圖

由圖2 可見(jiàn)，傳統(tǒng)蟻群算法規(guī)劃的航跡轉(zhuǎn)彎點(diǎn)較多，增加了無(wú)人機(jī)的飛行距離；而改進(jìn)算法規(guī)劃的轉(zhuǎn)彎點(diǎn)較少，航跡較平滑，提高了無(wú)人機(jī)的飛行性能。

傳統(tǒng)算法和改進(jìn)算法的航跡評(píng)價(jià)函數(shù)值隨迭代次數(shù)變化的曲線如圖3所示。

圖3 傳統(tǒng)蟻群算法和改進(jìn)蟻群算法航跡評(píng)價(jià)函數(shù)值對(duì)比圖

隨機(jī)選取3 次實(shí)驗(yàn)，記錄兩種算法在航跡長(zhǎng)度、轉(zhuǎn)角和、迭代次數(shù)和運(yùn)行時(shí)間等方面的結(jié)果如表2所示。

表2 傳統(tǒng)蟻群算法和改進(jìn)蟻群算法的性能對(duì)比

綜上所述，與傳統(tǒng)蟻群算法相比，改進(jìn)后的算法在搜索初期具有較強(qiáng)的收斂性，整體迭代次數(shù)更少，規(guī)劃的航跡長(zhǎng)度更短，航跡轉(zhuǎn)角和更小，這充分說(shuō)明改進(jìn)蟻群算法的優(yōu)越性。

6 結(jié)語(yǔ)

本文采用改進(jìn)的蟻群算法進(jìn)行無(wú)人機(jī)航跡規(guī)劃。為克服初始階段螞蟻搜索的盲目性，加強(qiáng)起點(diǎn)和終點(diǎn)連線附近的信息素濃度，并由近及遠(yuǎn)形成遵循指數(shù)衰減分布的濃度梯度，極大提高了第一代蟻群的搜索效率。設(shè)計(jì)基于相鄰航跡點(diǎn)長(zhǎng)度、待選航跡點(diǎn)與目標(biāo)點(diǎn)長(zhǎng)度和相鄰航線轉(zhuǎn)動(dòng)角度三個(gè)要素的啟發(fā)函數(shù)，進(jìn)一步平滑航跡，縮短航程，減小無(wú)人機(jī)油耗。在搜索后期進(jìn)行航跡點(diǎn)選擇時(shí)，采用概率選擇和確定性選擇相融合的策略，進(jìn)一步提高算法的收斂速度。改進(jìn)信息素更新機(jī)制，根據(jù)迭代次數(shù)自適應(yīng)調(diào)整信息素總量和更新信息素，以兼顧算法收斂速度快和全局搜索能力。仿真實(shí)驗(yàn)表明：改進(jìn)后的算法具有較強(qiáng)的全局搜索能力，有效減小了迭代次數(shù)，較大程度提高了航跡規(guī)劃的質(zhì)量。