基于改進自適應蟻群算法的無人機航跡規(guī)劃研究

陳 俠， 毛海亮， 劉奎武

(沈陽航空航天大學，沈陽 110000)

0 引言

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

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

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

1 改進的自適應蟻群(IAACO)算法

1.1 ACO算法基本原理

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

(1)

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

ACO算法迭代過程中信息素濃度值的更新表達式為

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

(2)

(3)

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

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

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

(4)

式中：djG為j點到目標點G的距離；自適應調整因子ε可以表示為

(5)

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

1.3 改進的狀態(tài)轉移規(guī)則

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

(6)

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

μi j(t)=acos θ·χ

(7)

(8)

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

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

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

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

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

(9)

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

(10)

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

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

為了使螞蟻的搜索范圍集中在最優(yōu)路徑的鄰域，在每次迭代后，本文算法只更新到達目標點的螞蟻走過路徑上的信息素，從而避免信息素的盲目更新。

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

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

(11)

(12)

其中，Jk為螞蟻k當前迭代路徑的性能指標。

在每次迭代后，為了增強最優(yōu)螞蟻走過路徑的信息素、削弱最差螞蟻走過路徑的信息素，對信息素更新規(guī)則進行改進，即

τ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為當前迭代最優(yōu)路徑性能指標值；Jworst為當前迭代最差路徑的性能指標值；pbest為當前迭代的最優(yōu)路徑；pworst為當前迭代的最差路徑。

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

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

1) 長度指標函數(shù)。

長度指標函數(shù)L(p)可以表示為

(15)

(16)

其中:n為無人機經過的路徑點總數(shù)；pi為路徑上的第i個點；(xi,yi)為pi的坐標值；d(pi,pi+1)為從pi到pi+1的歐幾里德距離。

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

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

(17)

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

圖2 轉彎角度示意圖Fig.2 Schematic diagram of turning angle

進而，根據長度指標函數(shù)和角度指標函數(shù)，可以將無人機航跡優(yōu)化的目標函數(shù)J(p)定義為

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

(18)

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

3 算法流程

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

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

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

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

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

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

5) 判斷螞蟻k是否到達終點或無節(jié)點可選，若是，則進行6)，否則，轉到4)。

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

7) 統(tǒng)計到達目標點的螞蟻走過路徑的長度和角度，根據式(18)建立目標函數(shù)，選擇最優(yōu)螞蟻和最差螞蟻，并根據式(11)，(13)，(14)更新信息素。

8) 若當前迭代次數(shù)小于上限Nmax，將當前迭代次數(shù)加1，并轉到3)，否則，進行9)。

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

4 仿真與結果分析

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

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

在目標函數(shù)中，不同權重的取值會導致規(guī)劃出的航跡不同，為了找到適合的權重，通過分析不同取值下規(guī)劃出的路徑長度和轉彎次數(shù)來確定權重的取值，如表1所示。

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

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

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

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

4.2 算法的比較分析

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

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

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

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

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

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

表2 3種算法的30次實驗平均值Table 2 Average value of 30 experiments of the three algorithms

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

5 結束語

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