陳 俠， 毛海亮， 劉奎武

(沈陽(yáng)航空航天大學(xué)，沈陽(yáng) 110000)

0 引言

近年來(lái)，無(wú)人機(jī)技術(shù)逐漸成為航空領(lǐng)域最具挑戰(zhàn)性和高潛力的技術(shù)之一。同時(shí)，航跡規(guī)劃正在成為無(wú)人機(jī)的關(guān)鍵技術(shù)之一，受到世界各國(guó)學(xué)者的廣泛關(guān)注。無(wú)人機(jī)航跡規(guī)劃的主要任務(wù)是在已知起點(diǎn)和終點(diǎn)的情況下，找到一條可以避開障礙的可行路徑[1]。

近年來(lái)，各國(guó)學(xué)者提出了許多航跡規(guī)劃方法，如經(jīng)典的Dijkstra算法、遺傳算法[2]、快速隨機(jī)搜索樹算法[3]、粒子群算法[4]、A*算法[5]、蟻群 (ACO) 算法等。ACO算法自從被意大利學(xué)者DORIGO提出后，逐漸被應(yīng)用于物流、路徑規(guī)劃等領(lǐng)域。該算法是根據(jù)蟻群覓食原理設(shè)計(jì)出的一種群智能算法，具有魯棒性強(qiáng)、信息反饋好等優(yōu)點(diǎn)，有利于解決復(fù)雜路徑規(guī)劃的問(wèn)題，被廣泛應(yīng)用于無(wú)人機(jī)航跡規(guī)劃[6]。但ACO算法在執(zhí)行任務(wù)過(guò)程中存在收斂速度慢、效率低等缺點(diǎn)，于是，有關(guān)學(xué)者開始對(duì)其不斷改進(jìn)來(lái)滿足無(wú)人機(jī)的飛行要求。文獻(xiàn)[7]利用幾何優(yōu)化方法對(duì)螞蟻進(jìn)行引導(dǎo)，加快了收斂速度，但存在個(gè)別螞蟻迷失的現(xiàn)象；文獻(xiàn)[8]對(duì)狀態(tài)轉(zhuǎn)移函數(shù)和信息素更新規(guī)則進(jìn)行改進(jìn)，加快了算法前期的搜索速度，通過(guò)引入信息素調(diào)節(jié)因子，避免算法后期取得局部最優(yōu)解，但該算法收斂速度仍然較慢；文獻(xiàn)[9]將自適應(yīng)與ACO算法相結(jié)合，提高算法尋找全局最優(yōu)值的能力，通過(guò)自適應(yīng)并行策略和自適應(yīng)信息更新策略，提升算法全局搜尋能力，但該算法規(guī)劃的航跡仍不平滑；文獻(xiàn)[10]提出了多啟發(fā)式改進(jìn)蟻群 (IACO) 算法，并提出基于路徑長(zhǎng)度、轉(zhuǎn)彎次數(shù)、梯度平滑度3個(gè)因素的改進(jìn)啟發(fā)式函數(shù)，綜合計(jì)算轉(zhuǎn)移概率，然后根據(jù)3個(gè)因素綜合指標(biāo)在每個(gè)路徑上分配信息素量，引導(dǎo)螞蟻以最佳整體性能接近路徑，IACO算法被應(yīng)用于機(jī)器人路徑規(guī)劃。雖然上述文獻(xiàn)對(duì)ACO算法進(jìn)行了改進(jìn)，取得了一些研究成果，但基于改進(jìn)蟻群的無(wú)人機(jī)航跡規(guī)劃算法仍有提升空間，需要提高算法的效率，以滿足空戰(zhàn)的實(shí)際需求。

受到以上研究的啟發(fā)，本文提出了一種基于改進(jìn)自適應(yīng)蟻群(IAACO)算法的無(wú)人機(jī)航跡規(guī)劃方法。改進(jìn)傳統(tǒng)ACO算法中的啟發(fā)式信息、狀態(tài)轉(zhuǎn)換概率、信息素更新規(guī)則，強(qiáng)化了算法的全局搜索能力并加快了收斂速度，提高了無(wú)人機(jī)的航跡規(guī)劃效率。仿真表明，本文提出的改進(jìn)算法可以滿足無(wú)人機(jī)航跡規(guī)劃中的要求，收斂速度快，能夠生成安全、平滑且長(zhǎng)度較短的路徑。

1 改進(jìn)的自適應(yīng)蟻群(IAACO)算法

1.1 ACO算法基本原理

算法的數(shù)學(xué)表達(dá)：在初始時(shí)刻，將M只螞蟻隨機(jī)置于地圖中，并設(shè)置所有節(jié)點(diǎn)的初始信息素，根據(jù)節(jié)點(diǎn)的信息素求出螞蟻從i點(diǎn)到j(luò)點(diǎn)的概率，其表達(dá)式為

(1)

式中：τi j(t)為當(dāng)前時(shí)刻從i點(diǎn)到j(luò)點(diǎn)的信息素濃度；ηi j為與(i，j)相關(guān)聯(lián)的啟發(fā)式信息；α，β分別為τi j(t)，ηi j的權(quán)重參數(shù)；N為所有節(jié)點(diǎn)數(shù)量；T為禁忌表；k表示第k只螞蟻。

ACO算法迭代過(guò)程中信息素濃度值的更新表達(dá)式為

τi j(t+1)=(1-ρ)·τi j(t)+Δτi j

(2)

(3)

式中：ρ為信息素?fù)]發(fā)系數(shù)；Δτi j(t)為當(dāng)前循環(huán)中螞蟻在t時(shí)刻向路徑li j釋放的信息素；Q為常數(shù)；Lk(t)為螞蟻在本次循環(huán)中爬行長(zhǎng)度。

1.2 改進(jìn)的啟發(fā)式信息

基本ACO算法的啟發(fā)式信息值與從下一個(gè)節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離成反比，從而驅(qū)動(dòng)螞蟻選擇短距離路徑。然而，在不考慮當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)位置的情況下，所選路徑不一定是最短路徑，因此在后期搜索階段，為了加快收斂速度，啟發(fā)式信息對(duì)路徑選擇的影響應(yīng)被削弱。本文引入了自適應(yīng)調(diào)整因子來(lái)削弱后期搜索階段啟發(fā)式信息ηi j對(duì)路徑選擇的影響，其表達(dá)式為

(4)

式中：djG為j點(diǎn)到目標(biāo)點(diǎn)G的距離；自適應(yīng)調(diào)整因子ε可以表示為

(5)

式中：Nc為當(dāng)前迭代次數(shù)；Nmax為最大迭代次數(shù)；e為自然常數(shù)。

1.3 改進(jìn)的狀態(tài)轉(zhuǎn)移規(guī)則

為了提高算法的搜索效率，本節(jié)在ACO算法的轉(zhuǎn)移概率中引入角度導(dǎo)向因子，改進(jìn)的轉(zhuǎn)移概率可以表示為

(6)

式中：μi j(t)為角度導(dǎo)向因子；γ為角度導(dǎo)向因子的權(quán)重。μi j(t)可以表示為

μi j(t)=acos θ·χ

(7)

(8)

其中：a為常數(shù)；χ為調(diào)整因子。

螞蟻在當(dāng)前節(jié)點(diǎn)位置直線移動(dòng)到下一行節(jié)點(diǎn)與螞蟻在當(dāng)前節(jié)點(diǎn)位置直線移動(dòng)到目標(biāo)點(diǎn)(終點(diǎn))之間的夾角角度示意圖見圖1。

圖1 角度示意圖Fig.1 Schematic diagram of angle

圖1中，i為當(dāng)前點(diǎn)，j為下一步可行的點(diǎn)，θ為當(dāng)前點(diǎn)i(xi,yi)至下一可行點(diǎn)j(xj,yj)的連線與當(dāng)前點(diǎn)i(xi,yi)至目標(biāo)點(diǎn)G(xG,yG)的連線所成夾角，取值范圍為[0°,180°]。根據(jù)實(shí)際情況，角度θ越小，可行點(diǎn)所在路徑越接近于理想路徑，此時(shí)，角度導(dǎo)向因子μi j(t)越大，螞蟻選擇該路徑上的點(diǎn)的概率越大，從而提高了算法的收斂速度。

為了避免螞蟻在迭代初期盲目搜索，根據(jù)參數(shù)自適應(yīng)偽隨機(jī)比例規(guī)則進(jìn)行狀態(tài)轉(zhuǎn)移，其表達(dá)式為

(9)

式中：q為[0,1]之間的隨機(jī)數(shù)；q0為自適應(yīng)轉(zhuǎn)換概率的閾值，即

(10)

式中，δ0為比例系數(shù)。在迭代初期，q0的值較大，若q≤q0，根據(jù)式(6)，螞蟻會(huì)選擇轉(zhuǎn)移概率最大的節(jié)點(diǎn)，避免了迭代初期盲目搜索；在迭代后期，q0的值較小，若q>q0，根據(jù)式(6)，螞蟻會(huì)利用輪盤賭選擇下一步要前往的節(jié)點(diǎn)，從而提高了全局搜索能力。

1.4 改進(jìn)的信息素更新規(guī)則

為了使螞蟻的搜索范圍集中在最優(yōu)路徑的鄰域，在每次迭代后，本文算法只更新到達(dá)目標(biāo)點(diǎn)的螞蟻?zhàn)哌^(guò)路徑上的信息素，從而避免信息素的盲目更新。

傳統(tǒng)的信息素濃度更新公式僅與路徑長(zhǎng)度有關(guān)，本文將目標(biāo)函數(shù)作為信息素更新的變量，改善的信息素濃度更新算式為

τi j(t+1)=(1-ρ)·τi j(t)+ρ·Δτi ji，j∈pbest

(11)

(12)

其中，Jk為螞蟻k當(dāng)前迭代路徑的性能指標(biāo)。

在每次迭代后，為了增強(qiáng)最優(yōu)螞蟻?zhàn)哌^(guò)路徑的信息素、削弱最差螞蟻?zhàn)哌^(guò)路徑的信息素，對(duì)信息素更新規(guī)則進(jìn)行改進(jìn)，即

τi j(t+1)=(1-ρ)·τi j(t)+ρ·Q·Jbesti，j∈pbest

(13)

τi j(t+1)=(1-ρ)·τi j(t)-ρ·Q·Jworsti，j∈pworst

(14)

其中：Jbest為當(dāng)前迭代最優(yōu)路徑性能指標(biāo)值；Jworst為當(dāng)前迭代最差路徑的性能指標(biāo)值；pbest為當(dāng)前迭代的最優(yōu)路徑；pworst為當(dāng)前迭代的最差路徑。

2 目標(biāo)函數(shù)的建立

首先定義了長(zhǎng)度指標(biāo)函數(shù)和角度指標(biāo)函數(shù)，然后通過(guò)兩個(gè)指標(biāo)函數(shù)構(gòu)建航跡優(yōu)化的目標(biāo)函數(shù)，最后實(shí)現(xiàn)了滿足無(wú)人機(jī)航跡規(guī)劃要求的全局優(yōu)化。

1) 長(zhǎng)度指標(biāo)函數(shù)。

長(zhǎng)度指標(biāo)函數(shù)L(p)可以表示為

(15)

(16)

其中:n為無(wú)人機(jī)經(jīng)過(guò)的路徑點(diǎn)總數(shù)；pi為路徑上的第i個(gè)點(diǎn)；(xi,yi)為pi的坐標(biāo)值；d(pi,pi+1)為從pi到pi+1的歐幾里德距離。

2) 角度指標(biāo)函數(shù)。

本文將路徑轉(zhuǎn)彎角度作為角度指標(biāo)的主要影響因素，角度指標(biāo)函數(shù)E(p)可以定義為

(17)

式中：h為無(wú)人機(jī)的轉(zhuǎn)彎次數(shù)；α(li,li+1)為無(wú)人機(jī)從當(dāng)前航線進(jìn)入下一點(diǎn)的轉(zhuǎn)彎角度，其取值范圍為[0°,180°]，如圖2所示。

圖2 轉(zhuǎn)彎角度示意圖Fig.2 Schematic diagram of turning angle

進(jìn)而，根據(jù)長(zhǎng)度指標(biāo)函數(shù)和角度指標(biāo)函數(shù)，可以將無(wú)人機(jī)航跡優(yōu)化的目標(biāo)函數(shù)J(p)定義為

J(p)=kL·L(p)+kE·E(p)

(18)

式中，kL和kE分別為長(zhǎng)度指標(biāo)和角度指標(biāo)的權(quán)重，且滿足kL+kE=1。在算法完成所有迭代后，得到使目標(biāo)函數(shù)J(p)達(dá)到最大值maxJ(p)的路徑，并將其視為最優(yōu)路徑。

3 算法流程

將本文提出的算法應(yīng)用于無(wú)人機(jī)航跡規(guī)劃問(wèn)題，其算法流程如下所述。

1) 將二維空間柵格化，得到二維搜索空間的模擬圖，可沿X軸將二維空間m等分，沿Y軸將二維空間l等分，所以二維空間可由m×l個(gè)柵格來(lái)描述，每一個(gè)柵格對(duì)應(yīng)一個(gè)空間節(jié)點(diǎn)。若m=10，l=10，則可將空間劃分為100個(gè)柵格，如圖3所示。

圖3 二維搜索空間模型示意圖Fig.3 Schematic diagram of 2D searching space model

2) 確定起點(diǎn)、終點(diǎn)、地圖障礙信息及算法參數(shù)初始化。

3) 將第k只螞蟻放入初始柵格，k=1,2,…,M。

4) 由式(4)和式(7)分別計(jì)算啟發(fā)式信息及角度信息，螞蟻根據(jù)式(6)和式(9)選擇下一步到達(dá)的節(jié)點(diǎn)，并且將已訪問(wèn)的節(jié)點(diǎn)加入禁忌表。

5) 判斷螞蟻k是否到達(dá)終點(diǎn)或無(wú)節(jié)點(diǎn)可選，若是，則進(jìn)行6)，否則，轉(zhuǎn)到4)。

6) 清空禁忌表，判斷螞蟻數(shù)量是否小于數(shù)量上限M，若是，則將k加1，轉(zhuǎn)到3)，否則，進(jìn)行7)。

7) 統(tǒng)計(jì)到達(dá)目標(biāo)點(diǎn)的螞蟻?zhàn)哌^(guò)路徑的長(zhǎng)度和角度，根據(jù)式(18)建立目標(biāo)函數(shù)，選擇最優(yōu)螞蟻和最差螞蟻，并根據(jù)式(11)，(13)，(14)更新信息素。

8) 若當(dāng)前迭代次數(shù)小于上限Nmax，將當(dāng)前迭代次數(shù)加1，并轉(zhuǎn)到3)，否則，進(jìn)行9)。

9) 對(duì)航跡進(jìn)行平滑處理并輸出最優(yōu)路徑，算法結(jié)束。

4 仿真與結(jié)果分析

算法的重要參數(shù)如下：最大迭代次數(shù)Nmax為30，螞蟻數(shù)量M為8，信息素因子權(quán)重α為1，啟發(fā)值因子權(quán)重β為10，角度導(dǎo)向因子權(quán)重γ為4，式(7)常數(shù)a為2，增強(qiáng)系數(shù)Q為1，比例系數(shù)δ0為0.5，調(diào)整系數(shù)κ為0.5，長(zhǎng)度指標(biāo)的權(quán)重kL為0.6，角度指標(biāo)的權(quán)重kE為0.4，信息素?fù)]發(fā)系數(shù)ρ為0.3。

4.1 目標(biāo)函數(shù)優(yōu)化

在目標(biāo)函數(shù)中，不同權(quán)重的取值會(huì)導(dǎo)致規(guī)劃出的航跡不同，為了找到適合的權(quán)重，通過(guò)分析不同取值下規(guī)劃出的路徑長(zhǎng)度和轉(zhuǎn)彎次數(shù)來(lái)確定權(quán)重的取值，如表1所示。

表1 目標(biāo)函數(shù)權(quán)重系數(shù)優(yōu)化Table 1 Optimization of objective function weight coefficient

圖4所示為不同權(quán)重系數(shù)下的航跡規(guī)劃。

當(dāng)kL=1,kE=0時(shí)，得到最短長(zhǎng)度的路徑，如圖4中藍(lán)色帶圓圈的虛線所示；當(dāng)kL=0,kE=1時(shí)，得到轉(zhuǎn)彎次數(shù)最少的路徑，如圖4中綠色帶*的虛線所示；本文旨在規(guī)劃出路徑更短且轉(zhuǎn)彎次數(shù)相對(duì)較少的航跡，因此,最終選取kL=0.6，kE=0.4，得到綜合最優(yōu)路徑，如圖4中紅線所示。

圖4 不同權(quán)重系數(shù)下的航跡規(guī)劃Fig.4 Track planning with different weight coefficients

4.2 算法的比較分析

為了驗(yàn)證本文提出算法的有效性，在Matlab中分別將ACO算法、文獻(xiàn)[10]的IACO算法以及本文IAACO算法應(yīng)用于無(wú)人機(jī)航跡規(guī)劃進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為簡(jiǎn)單的9個(gè)障礙物環(huán)境和復(fù)雜的15個(gè)障礙物環(huán)境。

簡(jiǎn)單環(huán)境可以被劃分為30 km×30 km的地圖，如圖5所示，起點(diǎn)坐標(biāo)為(1 km,30 km)，終點(diǎn)坐標(biāo)為(30 km,1 km)。

圖5 簡(jiǎn)單環(huán)境下仿真Fig.5 Simulation in simple environment

從圖5中的飛行軌跡和收斂曲線可以看出，相比于ACO算法和IACO算法，本文提出的IAACO算法收斂速度更快，規(guī)劃的路徑更為平滑且更短。

復(fù)雜環(huán)境可以被劃分為50 km×50 km的地圖，相對(duì)于簡(jiǎn)單環(huán)境規(guī)模更大，且障礙物更多，復(fù)雜環(huán)境的起點(diǎn)坐標(biāo)為(1 km,50 km)，終點(diǎn)坐標(biāo)為(50 km,1 km)。為了驗(yàn)證算法的穩(wěn)定性，本文在復(fù)雜環(huán)境中對(duì)每種算法分別進(jìn)行了30次實(shí)驗(yàn)，并記錄算法的運(yùn)行時(shí)間、生成路徑的長(zhǎng)度和迭代次數(shù)。飛行軌跡與迭代曲線如圖6所示，30次實(shí)驗(yàn)平均值如表2所示。

圖6 復(fù)雜環(huán)境下仿真Fig.6 Simulation in complex environment

表2 3種算法的30次實(shí)驗(yàn)平均值Table 2 Average value of 30 experiments of the three algorithms

結(jié)果表明，雖然IAACO算法運(yùn)行時(shí)間相較于IACO算法稍長(zhǎng)，但是IAACO算法規(guī)劃出的路徑更短且更加平滑，綜合性能表現(xiàn)更好。迭代穩(wěn)定次數(shù)相較于ACO算法和IACO算法更少，因此迭代至穩(wěn)定的時(shí)間更短。

5 結(jié)束語(yǔ)

針對(duì)蟻群(ACO)算法在無(wú)人機(jī)航跡規(guī)劃中存在的收斂速度慢、易陷入局部最優(yōu)等缺點(diǎn)，本文提出了改進(jìn)的自適應(yīng)蟻群(IAACO)算法。通過(guò)對(duì)二維空間進(jìn)行網(wǎng)格劃分，成功地將本文算法應(yīng)用于無(wú)人機(jī)航跡規(guī)劃問(wèn)題的求解。實(shí)驗(yàn)結(jié)果表明，所提算法收斂速度較快，不僅可以安全避開威脅，且規(guī)劃出的航跡相對(duì)平滑、長(zhǎng)度較短。但本文只考慮單機(jī)航跡尋優(yōu)，該方法還可以擴(kuò)展到多無(wú)人機(jī)的航跡規(guī)劃中，這有待進(jìn)一步研究。