引入導引因子蟻群算法的無人機二維航跡規劃

胡中華 趙 敏 姚 敏

南京航空航天大學，南京，210016

0 引言

無人機航跡規劃是任務規劃中最為基礎，也是最重要的部分。合理的航跡規劃將有助于無人機有效地規避威脅、縮短飛行路徑長度，提高其生存概率和作戰效率。無人機航跡規劃問題是一個組合優化問題，是優化領域的重要分支，主要通過對數學方法的研究尋找離散事件的最優編排、分組或篩選等，這類問題通常隨著問題規模的擴大，求解問題的空間、時間復雜度呈指數級增長，無法用常規的方法求解。航跡規劃算法主要可以分為兩大類：一是傳統經典算法；二是現代智能算法[1]。其中，前者主要包括動態規劃法、最速下降法、最優控制法；后者主要有VORONOI圖搜索法、格柵搜索法、人工勢場法、神經網絡法和基于模糊邏輯的航跡規劃算法等[2]。目前最常用的方法是利用VORONOI圖構建初始可選路徑集或設置導航節點，然后通過智能優化算法，選擇合適的路徑，該方法存在的缺陷是導航節點位置及數量的確定往往需要進行反復推敲，而VORONOI圖的構建決定了航跡代價的優化精度，因為螞蟻只能在VORONOI圖上尋找航跡，而不能在之外的空間搜索。此外，每當威脅場模型發生改變時，都需重新構建導航節點和VORONOI圖，因此對于突發的新威脅問題，該方法適應性不強。本文研究引入導引因子的蟻群優化（ant colony optimization，ACO）算法，無需設置導航節點及構建VORONOI圖，便可在自由空間自動搜索最小代價航跡，具有較強的自適應能力[3－4]。

1 航路規劃問題描述

1.1 規劃空間的表示

本文假設無人機在巡航階段保持高度和速度不變，且敵方防御區處于平坦地域，因此無人機無需考慮利用地形因素進行威脅規避機動，航跡規劃問題就可簡化為一個二維航跡規劃問題，但仍然需要考慮無人機在執行作戰任務過程中的生存性和執行任務的有效性，并且考慮規劃算法的實時性，所以仍是較為特殊的優化問題[5]。通過對規劃空間進行直角網格劃分，由當前節點搜尋下一個相鄰節點，直至搜尋到目標節點，形成連接起始節點和目標節點的航跡，采用建立在網格圖上的代價模型及優化算法求解最優路線。網格圖中的每個節點到達相鄰節點需要通過連接相鄰節點且帶有權重的有向邊。因此，算法的數據結構是以當前節點為中心的九宮圖，共有8個相鄰節點，圖1為航跡節點i的數據結構，下一個節點必須從以其為中心構成8個節點中選擇，其中網格大小G需根據實際問題規模及威脅點分布狀況進行合理設置。

圖1 節點的網絡結構

1.2 航路優化指標

由于在實際情況中常采用低于某一探測性指標，而且具有可接受航程的航路作為任務航路，因此本文采用下式所示的代價函數來描述航路的性能指標，它是按最短航路和最小可探測性航路加權方法來計算的[6]：

式中，W 為優化目標函數，可稱為廣義代價；L為航跡路徑；wt（s）為航路的威脅代價；wf（s）為航路的油耗代價；δ為系數，表示根據任務安排，航路制定人員在制定航路過程中所做出的意向性選擇。

油耗代價是航程的函數，威脅代價與無人機的可探測性指標相關聯，而可探測性指標是根據無人機的雷達可探測概率計算的。

本文通過對雷達威脅模型進行簡化處理，認為敵方防御區域內的各個雷達均相同且無相互聯系。考慮到雷達信號正比于1／d4（d為無人機到敵方雷達、導彈威脅陣地的距離），故當無人機沿網絡圖的第p段航跡飛行時，兩節點間的威脅代價可近似地認為正比于1／d4。本文中把該條邊劃分為5段進行計算：

式中，Lp為第p段航跡的長度；B為雷達等威脅陣地的數目；dr為第p段航跡的r（r ＝ 1／10，3／10，5／10，7／10，9／10）處距第j個威脅點的距離。

另外，在速度一定的情況下可簡單地認為wf＝L，則有wfp＝Lp。

2 航跡規劃問題的ACO算法構造

ACO算法最早用于求解旅行商問題（travel salesman problem，TSP），將算法用于航跡規劃問題存在一定的困難，主要表現在以下兩個方面：①航跡節點位置及數量不固定。一般的組合優化問題，如TSP等問題，路徑的節點是固定的，因此只是幾個節點之間的組合實現優化，所有的節點必須經過且只能經過一次，因此可以通過構造禁忌節點集（已經過的節點），剩下節點就是待選節點集，而航跡規劃問題是自由搜索空間，既沒有固定節點位置，也沒有固定節點數目，空間內不存在已知的路徑節點。因此，這些因素給規劃帶來了很大的難度。②如何保證到達目標節點。TSP問題將所有節點經過一次后，返回到起始節點，因此，目標節點就是起始節點，而航跡規劃問題的目標節點與起始節點不同，由于ACO按信息素及啟發因子構造狀態轉移策略，根據概率進行局部搜索，能見度限于局部范圍內，因此，如何保證找到目標節點，是完成航跡規劃的關鍵問題。

本文通過合理構造ACO算法，解決了以上兩個問題。

（1）設定航跡節點數最大允許限度。無人機存在最大航程參數，即無人機在整個飛行過程中的飛行路程，受到飛機燃油和飛行時間配給的限制。記最大航跡長度為Lmax，則每一個航段距離Lp應滿足：

根據式（3）可知，航跡節點數不能超過某范圍，這是無人機自身條件限制的。此外，由式（1）可知，航跡代價包含了油耗代價，油耗代價大的航跡可能會導致航跡代價增大。油耗代價也必須滿足一定的范圍，超過這個范圍認為是不可接受的。因此，盡管航跡節點不固定，但可設定最大節點數，當超過最大節點數時，即認為該航跡不可行，則放棄。

（2）引入導引因子。常規蟻群算法的狀態轉移策略根據信息素及啟發因子按概率選擇，沒有導引因子，本文根據航跡規劃問題的需要，引入了目標節點信息素導引因子，以節點i為例，設節點i到目標節點D 的距離為diD，則導引因子λi＝1／diD。常規狀態轉移策略中，九宮圖中8個相鄰節點的啟發因子數值相差不大，因此目標節點的局部預見性不強，尤其在算法迭代初期，節點間的信息素相差無幾，狀態轉移容易陷入盲目選擇，難以快速到達目標節點。由λi＝1／diD可知，離目標節點越遠的節點，導引因子越大；反之，導引因子越小。因此狀態轉移策略中，導引因子的引入，可以有效減小螞蟻搜索的盲目性，使螞蟻朝著目標節點的方向搜尋航跡。

2.1 信息素矩陣設計

根據劃分的網格大小及起始點、目標點及威脅點的位置來確定規劃空間，設該空間4個點坐標 分 別 為 （xmin，ymin）、（xmax，ymin）、（xmin，ymax）、（xmax，ymax），設網格大小為G，則網格共有行數hn＝ （ymax－ymin）／G，共 有 列 數 vn＝ （ymax－ymin）／G，其中，n為節點數，n＝hnvn，坐標為（xi，yi）的網格節點編號pi的計算公式為

由式（4）建立信息素矩陣τ，τ為n×n矩陣。

2.2 啟發因子設計

啟發因子主要是用來提高節點選擇的能見度，加快算法的收斂速度，使算法快速收斂于最小代價的航跡。本研究的代價主要來源于威脅代價，因此啟發因子設計為威脅代價點的倒數。

設共有B個威脅點，第j個威脅點坐標為（xj，yj），則節點i到威脅點j的威脅代價表示為

根據式（5）求出節點i到所有威脅點的代價為

節點的啟發因子等于總威脅代價的倒數，即ηi＝1／εi，因此當節點威脅代價小時，啟發因子大，能見度高；反之，則能見度低。啟發因子起到加速算法收斂的作用，但相對于信息素，所占比重不宜過大，否則信息素無法發揮指引作用。

2.3 狀態轉移策略

設蟻群規模為m，τij（N）表示迭代N次時在節點i到j段航跡的信息素濃度。初始迭代時，各條路徑上信息素的濃度相同，設τij（0）＝h（h為常數）。螞蟻k（k＝1，2，…，m）在運動過程中，根據各條路徑上的信息素濃度決定轉移方向，（N）表示第N代螞蟻k從節點i轉移到節點j的概率，其計算公式如下：

其中，Tk用以記錄螞蟻k本代所走過的節點，Tk隨螞蟻不斷選擇下一個節點而做動態調整表示所有未經過的節點，Bi表示節點i的相鄰節點集，Ak表示螞蟻k下一步待選的節點集，與一般TSP問題不同，待選節點不是剩余未經過的全部節點k，而是由九宮圖中相鄰的節點組成的節點集（圖1），并排除已經經過的節點，螞蟻不斷在局部范圍內搜索節點，最終到達目標節點，完成一次航跡。而為了保證螞蟻能最終達到目標節點，與一般ACO算法不同，本研究的狀態轉移概率引入了導引因子λi（N），使螞蟻搜索具有一定的方向性，即使螞蟻朝著目標節點的方向搜尋航跡，式中α、β、γ分別表示信息素、啟發因子及導引因子重要性程度參數，仿真實踐表明β及γ取值不宜過大，否則算法容易陷入停滯。此外，對于Ak中存在的離威脅點太近的節點，通過設置啟發因子臨界值R來實現不選擇該節點的目的，當某節點j啟發因子ηj小于R時，令ηj為無窮小。那么選擇無窮小節點的概率幾乎為0，從而達到排除選擇該節點的目的，由此保證算法不會出現經過威脅節點。

2.4 信息素更新策略

進化代數N每增加一次，各條路徑上的信息素就要揮發一次，用參數（1－ρ）表示信息素的揮發程度，所有螞蟻完成一次迭代循環，各航跡段上信息素的濃度根據式（8）和式（9）作調整。

其中，Δτij（N）b表示第N次迭代中最小代價的螞蟻所對應的航跡，區別一般算法對所有螞蟻行走的航跡進行信息素增強，本文僅考慮最小代價航跡的信息素增強，以便加快算法的收斂，但為防止某些邊上的信息素增長過快，把信息素大小的取值范圍限制在一個區間[τmin，τmax]內，以避免算法陷入停滯。

其中，Q為常數，表示信息素增加強度系數；WbN表示第N次迭代中最小航跡代價。Q、ρ根據求解規模確定其取值。固定迭代次數或者當解的變化不明顯時便停止計算。

3 航跡規劃實例仿真

為驗證算法的性能，本文采用MATLAB進行編程仿真。將航跡分成兩部分，設置一個中間過渡節點T（10，20），起始節點S到節點T時刻航跡為固定航跡，這是因為此段航跡離威脅點有較長距離，威脅代價小，幾乎可以忽略，而節點T到目標節點D時威脅代價大，因此對此部分作航跡優化，參數見表1。

表1 威脅點、起始點及目標點坐標

算法仿真參數設置為Nmax＝100、m＝31、α＝1、β＝0.25、γ＝0.5、ρ＝0.1、Q＝50、R＝4、G＝2、Lmax＝30。參數Nmax表示最大迭代次數，Lmax可以保證無人機航程油耗基本在允許范圍內。圖2分別為δ＝1.0、δ＝0.9、δ＝0.5時的最優航跡，從圖2可以看出，最小代價航跡隨著迭代的進行不斷地進行著調整，并最終獲得全局最小代價航跡。本文ACO算法結果如表2所示，在權值系數δ取不同值的情況下，本文算法均取得較好的結果。

圖2 不同權重系數下的最佳航跡

表2 算法結果對比

4 結語

本文將ACO算法應用于無人機航跡規劃問題，通過解決兩大構造難題，并將導引因子引入到狀態轉移策略當中，保證了算法的收斂速度，同時確保螞蟻最終完成航跡搜索，通過設置當前最優路徑信息素更新策略，同時設置信息素上下限，在提高算法速度的同時，防止算法陷入局部最優及出現停滯。仿真結果表明，該算法的構造非常合理，在沒有設置導航節點及構建VORONOI圖的情況下，螞蟻在自由空間自動尋找到目標節點，且收斂速度快，克服了傳統ACO算法航跡規劃需要預先設置導航節點及構建VORONOI圖的缺點，在航跡規劃問題領域具有令人鼓舞的應用前景。

[1]Eun Y，Bang H.Cooperative Task Assignment／Track Planning of Multiple Unmanned Aerial Vehicles Using Genetic Algorithms[J].Journal of Aircraft，2009，46（1）：338-343.

[2]周成平，陳前洋，秦筱.基于稀疏A＊算法的三維航跡并行規劃算法[J].華中科技大學學報（自然科學版），2005，33（5）：42－45.

[3]高暉，陳欣，夏云程.無人機航路規劃研究[J].南京航空航天大學學報，2001，33（2）：135－138.

[4]劉森琪，段海濱，余亞翔.基于Voronoi圖和蟻群優化算法的無人作戰飛機航路規劃[J].系統仿真學報，2008，20（21）：5936－5939.

[5]陳美軍，張志勝，史金飛.多約束下多車場車輛路徑問題的蟻群算法研究[J].中國機械工程，2008，19（16）：1939－1944.

[6]陳謀，肖健，姜長生.基于改進蟻群算法的無人機三維航路規劃[J].吉林大學學報（工學版），2008，38（4）：991－995.