基于人工勢場法優化的蟻群無人機航路規劃

王 芳，李昆鵬

(1．西安航空學院 航空工程系，陜西 西安710077； 2．長安大學 機械學院，陜西 西安710064)

1 引言

航路規劃( Path Planning)是指在目標點與起始點之間，為運動物體尋找滿足某種性能指標和某些約束的線路、路徑[1]。隨著雷達探測跟蹤能力的不斷增強以及地面防空系統日益完善，無人機面臨的戰場環境也不斷變化，因此在有限時間內規劃全局最優路徑，使無人機能夠順利地往返可疑目標點( 有時是多個目標點) ，是保障無人機安全性和作戰效率的關鍵所在，也是目前航路規劃有待解決的問題。

目前，國內外常用的無人機航路規劃算法大致可分為兩類：確定型(或啟發式)搜索算法和隨機型(或智能優化)搜索算法。相對于確定型搜索算法，隨機型算法在求解復雜航路規劃問題上具有明顯優勢[2]。智能優化算法是隨機型搜索算法中的一個大類，由于其思想簡單，易于操作，且對優化函數沒有特殊要求，因此近年來被廣泛應用于航路規劃，常用的有遺傳算法[3]、粒子群算法[4]和蟻群算法(AOC)[5]等。上述仿生規劃算法雖然可以獲得較高精度的可行路徑，但是通常算法存在易于陷入局部最優和收斂速度慢等問題，難以滿足航路規劃實時性的要求。

為了解決上述問題，本文提出一種改進的AOC航路規劃算法，通過采用人工勢場法優化AOC，可以很好地改善AOC算法搜索中的盲目性以及收斂速度慢等問題。

2 航路規劃問題描述

無人機在巡航階段，一般僅考慮其橫側向運動，故可將三維航路規劃問題轉換成在某一高度下二維平面航路規劃。在航路規劃問題中，通常障礙、火力威脅區域、探測威脅區域是已知的，故可對飛行任務空間構建柵格環境模型。

無人機全局航路規劃不僅要依據預先獲得的威脅信息尋找安全的飛行軌跡，而且還要做到從起點到目標點所用燃油最小。本文采用如下方程來定義航路性能指標[6]：

對于每段航路的威脅代價，采用加權平均的辦法，威脅代價定義為：

上式中，N為無人機當前飛行位置探測到的威脅個數，Kj為第j個威脅的強度；Rij為該段航路上的點到第j個威脅中心的距離。

3 算法設計

螞蟻盡管個體行為比較簡單，但是由這些簡單個體所組成的群體卻表現出極其復雜的行為特征。考察無人機航路規劃問題，受自然界中螞蟻路徑搜索啟發而產生的蟻群算法，與航路規劃問題有著自然的聯系，因此結合無人機航路規劃特點，本文采用改進蟻群算法，搜索通往目標點的最優航路。

3.1 基于AOC的航路規劃

在路徑選擇階段，螞蟻會根據路徑上的信息素來選擇運動方向，t時刻螞蟻k從節點i轉移到節點j的概率按如下式計算[7]：

式中，τij(t)t時刻節點i和j之間殘留的信息素；α信息素啟發因子；ηij(t)t時刻節點i和j之間的期望啟發函數；β期望啟發因子；allowedk=(Tabuk)螞蟻下一步允許選擇的節點，Tabuk為禁忌表，記錄螞蟻k所走過的節點。

期望啟發函數定義為節點i和j之間的距離dij的倒數，即，

(2)

螞蟻走過的路徑上會留下信息素，同時為了避免路徑上因殘留信息素過多而造成啟發信息被淹沒，信息素會隨著時間的流逝而揮發，設ρ為信息素揮發系數且(0≤ρ<1)，t+Δt時刻節點i和j上的信息素更新規則為[7]：

τij(t+Δt)=(1-ρ)·τij(t) +Δτij(t)

(3)

(4)

式中，Q信息素強度；Lk螞蟻k在本次循環中所走過路徑的總長度；pk(begin,end)螞蟻k在本次循環中從起點到終點所走過的路徑。

在蟻群航路規劃算法中，初始解的產生帶有隨機性，不利于路徑的快速搜索；同時，由于蟻群算法的正反饋機制，使得質量不高的初始解可能使算法收斂于次優解，即陷入局部極值點。因此，高效地獲得較高質量的初始解，同時改善蟻群路徑搜索中的盲目性對提高算法性能具有重要意義。

3.2 基于人工勢場優化的AOC航路規劃

人工勢場路徑規劃因其模型簡單、計算量小和實時性好等優點，在實時避障中得到了廣泛的應用，但由于其中沒有涉及到優化過程，所以得到的路徑雖然是安全的，但是并非最優。考慮到蟻群算法在航路規劃中存在的問題，有效地融合人工勢場法和蟻群算法的優點來實現最優路徑的搜索，必然會改善單一規劃算法的規劃效果。

人工勢場法中采用與位置有關的勢函數來進行路徑規劃控制，其基本思想是：首先在機器人運行空間構建虛擬力場，包括引力場和斥力場，引力場隨機器人與目標的距離減小而遞減，方向指向目標，斥力場隨機器人與障礙物的距離減小而增大，方向由障礙物指向機器人，且在障礙物處有一個極大值，整個勢場的合力是引力和斥力的疊加，則機器人在環境中的運動可視為在虛擬力場作用下的運動。引力場、斥力場和合力場的數學描述如下：

引力場函數為：

Uatt(q)=0.5ξρm(qr,qgoal)

(6)

式中，ξ為引力位置場正增益系數；qr為機器人在空間中的位置；qgoal為目標點在空間中的位置；ρ為機器人qr和目標qgoal之間的歐式距離；m為引力位置場階次，通常取吸引力場為拋物線形狀，即m=2。

斥力場函數為：

式中，η為斥力位置場正增益系數；ρ為機器人qr和障礙物qobst之間的歐式距離；ρ0為障礙物影響范圍。ρmin為機器人與障礙物之間所允許的最小距離，增加的ρn(qr,qgoal)項為機器人到目標點的最短距離，n為優化參數，這樣，當機器人向目標運動，到達目標點時，對應的斥力為零，從而可以保證機器人在目標點處達到全局最小。

分別對引力場和斥力場函數按照相對位置的負梯度方向求導得到引力和斥力：

Fatt(q) =-(Uatt)

=-0.5mξρ(qr,qgoal)m-1ρ(qr,qgoal)

=-0.5mξρ(qr,qgoal)m-1nrg

(8)

Frep(q) =-(∑Urep)

(9)

式中，nro為機器人指向障礙物的單位矢量；nrg為機器人指向目標點的單位矢量。

將人工勢場法得到的規劃結果作為蟻群算法較高質量的初始解，對初始到達的柵格進行鄰域柵格信息素的初始化，從而可以大大提高路徑搜索的效率，算法具體計算過程如下：

步驟1 初始化算法參數：包括螞蟻數m，最大循環次數Tmax，α、β、l及人工勢場法中的相關參數；

步驟2 初始化規劃任務，確定是否初次到達的柵格；

步驟3 利用勢場法，計算螞蟻在該柵格時受到的引力和斥力，并計算基于勢場法的轉移角度；

步驟4 計算勢場法轉移角度與螞蟻相鄰八個柵格轉移角度的差，如圖1所示；

步驟5 對上述角度差進行排序，角度差越小說明越接近勢場法轉移方向，此時對相應的轉移方向賦予較大的信息素，而其余七個方向，按照由小到大，分別賦予較小的初始信息素。

圖中，合力與方向7的角度差最小，則方向7即為螞蟻轉移的最佳柵格方向，因此將該柵格信息素賦予最大權值，勢必提高螞蟻的轉移概率，其余按照夾角由小到大分別賦予較小的權值，由于采用輪盤賭的選擇方法，因此大的權值，也就是信息素強度高的柵格被選中的機會較大，同時，信息素強度低的柵格也存在被選擇的可能性。

圖1 最佳柵格方向計算

步驟6 經過路徑信息素強度初始化之后，采用蟻群算法進行路徑搜索，螞蟻在相鄰的位置間轉移，按照公式(1)定義的轉移概率進行，而當螞蟻到達目標，完成一次搜索后，按照式(3)進行信息素的更新，完成一次群體優化，不斷重復此過程，最終完成最佳路徑的搜索。

4 仿真結果

為了驗證文中算法的有效性，針對不同環境給出了算法的仿真實驗測試。本文提供了如圖2所示兩種環境，環境一相對比較簡單，障礙物較少。環境二比較復雜，且存在明顯的局部極小。針對兩種環境，分別對基本蟻群算法，基于勢場法優化的蟻群算法進行規劃對比測試，結果如圖3所示。考慮到算法的隨機性，仿真中，每種環境進行了50次獨立隨機測試。算法中的具體參數設置分別為：最大循環次數為Tmax=50，每次出動的螞蟻數為m=15，α=1，β=2，ρ=0.2。

圖3(a)(b)分別為環境一中兩種規劃算法的螞蟻信息素演化曲線。圖5(a)為兩種算法最優規劃結果。從結果可見，在環境簡單時，兩種方法基本上都能得到最優路徑。從信息素演化圖可見ACA算法(圖3(a))在路徑搜索過程中帶有一定隨機性，而APFOA方法則減少了盲目搜索，因而最優路徑的規劃效率也較高。

圖4(a)(b)為環境二中兩種規劃算法的螞蟻信息素演化曲線。圖5(b)為兩種算法最優規劃結果。和環境一相比，環境二更為復雜，且存在明顯局部極小，雖然兩種方法最終都能收斂到各自的最優路徑，但從蟻群信息素演化圖可見，在人工勢場作用下，螞蟻的路徑搜索更趨理性，減少了對明顯非最優路徑的嘗試，體現了較強的規劃能力。

(a)環境一(b)環境二(a)ACA (b)APFOA

圖2仿真測試環境圖3環境一信息素演化曲線

(a)ACA (b)APFOA (a)環境一最優路徑(b)環境二最優路徑

圖4環境二信息素演化曲線圖5最優路線

5 結語

蟻群算法是一種仿生學隨機搜索全局尋優算法，具有正反饋、并行性等特點，但在搜索初期具有盲目性和隨機性。人工勢場法搜索效率高，導向性強，具有良好的局部搜索性能。本文針對復雜環境中無人機航路規劃問題，融合蟻群全局航路規劃算法和人工勢場局部規劃各自優點，提出一種勢場法優化的蟻群算法，不但可以避免局部優化算法容易陷入局部極值的問題，而且可以改善螞蟻路徑搜索的盲目性，從而顯著提高收斂速度。仿真實驗測試表明，在收斂速度及最優規劃方面，經過勢場法優化的蟻群算法整體上要明顯好于蟻群算法和人工勢場法。

[1] 莊夏，戴敏，賀元驊.基于改進AOC算法的無人作戰飛機航路規劃設計[J].計算機測量與控制，2014，22(1)：270-272.

[2] 劉鋼，老松楊，譚東風，等. 反潛導彈航路規劃問題的研究現狀與發展[J].自動化學報，2013，39(4)：347-359.

[3] 鄭銳,馮振明,陸明泉.基于遺傳算法的無人機航路規劃優化研究[J].計算機仿真，2011， 28(6)：88-91.

[4] Jung L F,Jared S K,James H O,et al.Three-dimensional multi-objective path planning of unmanned aerial vehicles using particle swarm optimization[C] // In: Proceedings of the 48th AIAA/ASME/ASCE/AHS Structures, Structural Dynamics, and Materials Conference. Hawaii: AIAA, 2007:1881-1890.

[5] 劉振峰，謝洪森，危水根.基于蟻群遺傳算法的三維飛行器航路規劃[J].計算機仿真，2013, 30(9)：121-125.

[6] 稅薇，葛艷，韓玉，等.基于混合蟻群算法的無人機航路規劃[J].系統仿真學報，2011，23(3)：574-576.

[7] 袁明新，王孫安，李昆鵬，等.基于勢場法優化的蟻群免疫網絡路徑規劃研究[J].系統仿真學報，2009，21(15)：4686-4690.