基于人工勢場法優(yōu)化的蟻群無人機航路規(guī)劃

王 芳，李昆鵬

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

1 引言

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

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

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

2 航路規(guī)劃問題描述

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

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

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

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

3 算法設(shè)計

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

3.1 基于AOC的航路規(guī)劃

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

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

期望啟發(fā)函數(shù)定義為節(jié)點i和j之間的距離dij的倒數(shù)，即，

(2)

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

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

(3)

(4)

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

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

3.2 基于人工勢場優(yōu)化的AOC航路規(guī)劃

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

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

引力場函數(shù)為：

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

(6)

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

斥力場函數(shù)為：

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

分別對引力場和斥力場函數(shù)按照相對位置的負梯度方向求導(dǎo)得到引力和斥力：

Fatt(q) =-(Uatt)

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

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

(8)

Frep(q) =-(∑Urep)

(9)

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

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

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

步驟2 初始化規(guī)劃任務(wù)，確定是否初次到達的柵格；

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

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

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

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

圖1 最佳柵格方向計算

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

4 仿真結(jié)果

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

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

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

(a)環(huán)境一(b)環(huán)境二(a)ACA (b)APFOA

圖2仿真測試環(huán)境圖3環(huán)境一信息素演化曲線

(a)ACA (b)APFOA (a)環(huán)境一最優(yōu)路徑(b)環(huán)境二最優(yōu)路徑

圖4環(huán)境二信息素演化曲線圖5最優(yōu)路線

5 結(jié)語

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

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

[2] 劉鋼，老松楊，譚東風(fēng)，等. 反潛導(dǎo)彈航路規(guī)劃問題的研究現(xiàn)狀與發(fā)展[J].自動化學(xué)報，2013，39(4)：347-359.

[3] 鄭銳,馮振明,陸明泉.基于遺傳算法的無人機航路規(guī)劃優(yōu)化研究[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] 劉振峰，謝洪森，危水根.基于蟻群遺傳算法的三維飛行器航路規(guī)劃[J].計算機仿真，2013, 30(9)：121-125.

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

[7] 袁明新，王孫安，李昆鵬，等.基于勢場法優(yōu)化的蟻群免疫網(wǎng)絡(luò)路徑規(guī)劃研究[J].系統(tǒng)仿真學(xué)報，2009，21(15)：4686-4690.