優(yōu)化蟻群算法在無人機二維航跡中的應(yīng)用

徐宏宇,孫洪俊,韓 毅(沈陽航空航天大學(xué) 電子信息工程學(xué)院，沈陽 110136)

優(yōu)化蟻群算法在無人機二維航跡中的應(yīng)用

徐宏宇,孫洪俊,韓 毅
(沈陽航空航天大學(xué) 電子信息工程學(xué)院，沈陽 110136)

為了有效提高無人機在執(zhí)行偵察和攻擊任務(wù)的效率,提出了誘發(fā)向?qū)У南伻核惴ǖ臒o人機航跡規(guī)劃方法,將影響無人機飛行的敵方雷達偵測、飛行燃油代價、最大航程距離和高度代價四個因素進行了量化處理，建立了雷達威脅模型、燃油代價模型、最大航程距離限制模型和高度代價模型；并通過誘發(fā)向?qū)У脑O(shè)立提高螞蟻系統(tǒng)在局部搜索的效率，該仿真結(jié)果的分析證明該算法有效提高了無人機執(zhí)行任務(wù)的效率。

無人機，蟻群算法；航跡規(guī)劃；誘發(fā)向?qū)?；燃油代價；雷達偵測

隨著航空科學(xué)技術(shù)的快速發(fā)展，無人機(UAV)被廣泛應(yīng)用。無論是在民用領(lǐng)域，還是在戰(zhàn)場上，其具有體積小、造價低、使用方便、對作戰(zhàn)環(huán)境要求低、戰(zhàn)場生存能力較強等優(yōu)勢，幾次局部戰(zhàn)爭中的優(yōu)異表現(xiàn)，使得世界各國軍隊對無人機(UAV)高度重視。無人機(UAV)的航跡規(guī)劃的主要問題包括任務(wù)需求、雷達威脅分布、燃油限制、最大航程距離和飛行高度。蟻群算法(ant colony op-timization)[1-3]是由意大利科學(xué)家Marco Dorigo等人在20世紀(jì)90年代初提出來的，是一種在圖中尋找優(yōu)化路徑的機率型算法，其具有可靠性高、較強的魯棒性和全局搜索能力等優(yōu)勢。但蟻群算法也存在缺點，即收斂速度慢、易于陷入局部最優(yōu)、容易出現(xiàn)過早停滯。本文通過加入誘發(fā)向?qū)?yōu)化其局部搜索效率，從而提高其在自由空間上獲得更強的自適應(yīng)的能力，以便獲取最優(yōu)航跡。

1 規(guī)劃模型

無人機二維路徑搜索[4-5]的影響因素主要包括四個方面：雷達偵測、飛機的最大載油量、最大航程距離限制和飛行高度。首先假定所有雷達的工作方式完全一致，并且無人機具有相同的雷達反射截面，于是可以得出無人機的反射雷達回波強度與其和雷達的距離的關(guān)系，即強度與距離的四次方成反比(1/d4)，雷達的偵測范圍通?？梢哉J(rèn)為是圓球型，當(dāng)飛機距離越近，被偵測到的概率就越大，在二維平面上，可以將雷區(qū)的偵測范圍和威脅程度用同心圓來表示，雷達偵測的絕對威脅區(qū)域由同心圓的內(nèi)圓來表示，內(nèi)圓的面積表示雷達偵測的絕對威脅區(qū)域，由同心圓外圓的內(nèi)部與內(nèi)圓的外部之間的環(huán)形區(qū)域面積來表示非絕對禁止區(qū)域，被偵測到的概率定義為

(1)

其中p(m)為在m的時候被偵測到的概率，Rmin表征突防高度下絕對禁止區(qū)半徑,依據(jù)情報給定;Rmax表征突防高度下非絕對禁止區(qū)半徑,可作為威脅范圍估計補償加入，r表示無人機所處的位置到威脅點的距離的值，對于區(qū)域重疊部分,不同的雷達威脅點對于無人機的偵測概率計為pi(m),i=1,2,3,4,…,p(m)綜合評價偵測概率則由以公式(2)求取。

(2)

然后將地形圖劃分為若干等大的方塊，飛機沿著方塊的邊線和對角線飛行，可以到達與之相鄰的任何一個點。那么無人機沿每條邊或?qū)蔷€飛行的雷達威脅代價Ja是飛過該邊的積分：

(3)

其中，r(t)表示無人機到雷達的距離，p(m)表示雷達的偵測概率。為方便計算，將每條邊均勻地分為9等分，取每一段與威脅點的距離來代替整條邊的代價，Li是第i邊的長度，這樣第i條邊的雷達威脅代價Ja為

(4)

其中N為雷達的個數(shù)。d1/10,i,j是第i條邊上的1/10處到第j個雷達的距離。

另一方面，在假定無人機以恒定的速度在同一高度水平面飛行的情況下，無人機的燃料消耗和航跡的幾何長度成正比，比例常數(shù)為c,可表示為

Jb,i=cLi

(5)

綜合考慮上面兩方面的因素，無人機第i條邊的總代價為

Ji=kJa,i+(1-k)Jb,i

(6)

其中，k為安全性能與燃油性能的系數(shù)，可根據(jù)任務(wù)需求調(diào)整k的大小，k越接近1表示越重視燃油的使用情況，越接近0表示越重視危險性代價。其中M為邊的條數(shù)。

(7)

設(shè)置最大航程距離值，即無人機航跡的最大有效值，路徑規(guī)劃的每一段距離La都應(yīng)該實現(xiàn),由式(8)所示，因此當(dāng)航跡規(guī)劃出一個路徑時，如果超過最大值有效值時，認(rèn)為航跡為無效，應(yīng)重新規(guī)劃。

L≤Lmax

(8)

常規(guī)的航跡規(guī)劃問題需要考慮飛機的飛行高度，飛行高度可能直接導(dǎo)致穿越云層時遇見惡劣天氣不能飛行，而本文主要針對的是小型無人機，飛行高度在百米以內(nèi)，很大程度可以認(rèn)為是在距離地面較低的高度上緊貼地表進行飛行，這樣可以忽略天氣的影響，只需對高山進行特定區(qū)域標(biāo)定，無人機需要繞過此區(qū)域，無人機可以通過將高山模擬成雷達偵測的禁止區(qū)域進行躲避。

通過模型的建立，有效地將飛機最大載油量限制，雷達偵測，最大航程距離主要影響因素考慮到航跡規(guī)劃中，為之后的優(yōu)化蟻群算法提供求解條件，否則將無法進行有效求解。因此，合理、有效地建立模型是規(guī)劃的關(guān)鍵。

2 蟻群算法的構(gòu)造

2.1 誘發(fā)向?qū)?/h3>

蟻群算法[4-6]最初用于商旅問題[7](TSP)，M.Dorigo等人充分利用了蟻群覓食的過程與商旅問題之間的相似性，通過人工模擬螞蟻覓食的過程，即通過個體之間的信息交流與相互協(xié)作最終找到從蟻穴到食物源的路徑來求解商旅問題。原有的蟻群算法的路徑搜索依據(jù)信息濃度和啟發(fā)因子的概率選擇，本文在原有的蟻群算法基礎(chǔ)之上，通過加入誘發(fā)向?qū)?，以達到對蟻群算法的優(yōu)化。將航跡規(guī)劃簡化在二維平面上，考慮到二維平面上是一個連續(xù)的集合，將無人機搜索的平面劃分成有限個正方形的網(wǎng)絡(luò)格，通過對這樣的網(wǎng)絡(luò)格不停搜尋節(jié)點，直到目標(biāo)點，將所有搜索的節(jié)點連在一起，這便是所求的最優(yōu)路線。以i節(jié)點為例，從節(jié)點i開始搜索，搜索的下一個節(jié)點必須是從其為中心組成的8個相鄰節(jié)點中選擇，但考慮實際搜索中需要前進性，剔除不滿足條件的節(jié)點，由剩下的5個節(jié)點構(gòu)成的扇形面才是需要考慮的節(jié)點，即如圖1所示組成的黑色區(qū)域的節(jié)點。設(shè)節(jié)點i到目標(biāo)節(jié)點j的距離為dij,則誘發(fā)向?qū)?/p>

λi=1/dij

(9)

圖1 扇形面

這5個節(jié)點的啟發(fā)因子的數(shù)值相差不大，在算法的初期容易導(dǎo)致盲目選擇，不能夠有效地到達目標(biāo)節(jié)點。由公式9可知，某節(jié)點的誘發(fā)向?qū)У拇笮∨c距離目標(biāo)節(jié)點的距離成反比，加入誘發(fā)向?qū)?，可以有效提高搜索的效率?/p>

2.2 信息素矩陣

將網(wǎng)絡(luò)格依據(jù)其大小和起始點、目標(biāo)點和威脅點的位置來規(guī)劃二維地圖，設(shè)其中空間的4個點坐標(biāo)分別為(xmin,ymin)、(xmax,ymin)、(xmin,ymax)、(xmax,ymax),設(shè)網(wǎng)絡(luò)格大小為G，則網(wǎng)絡(luò)格共有行數(shù)h和共有列數(shù)v分別為

h=(ymax-ymin)/G

(10)

v=(xmax-xmin)/G

(11)

其中n為節(jié)點數(shù)，n=hv,坐標(biāo)為(xi，yi)的網(wǎng)絡(luò)格節(jié)點編號pi的計算公式為

(12)

2.3 啟發(fā)函數(shù)

啟發(fā)函數(shù)主要是用來提高節(jié)點選擇效率，提高算法的收斂速度，加速算法的最小航跡。本文中以雷達的偵測為主，因此啟發(fā)函數(shù)[8-10]的設(shè)計為威脅點的倒數(shù)，設(shè)置B個威脅點，第J個威脅點坐標(biāo)為(xi,yi),則節(jié)點i到威脅點j的威脅代價表示為

εij=1/[(xi-xj)2+(yi-yj)2]2

(13)

根據(jù)式(13)求出節(jié)點i到所有威脅點的代價為

(14)

節(jié)點的啟發(fā)函數(shù)等于總威脅代價的倒數(shù)，即ηi=1/εi，因此當(dāng)節(jié)點威脅代價越小時，啟發(fā)函數(shù)越大，選擇效率越高，反之選擇效率越低，啟發(fā)函數(shù)的作用是加速算法收斂，但相對于信息濃度而言，所占比重如果過大，信息濃度將失去指引作用。

2.4 轉(zhuǎn)移概率函數(shù)

(15)

(16)

2.5 信息素軌跡更新與限制

迭代次數(shù)N每增加一次，路徑上的信息素[11-15]就要揮發(fā)一次，用參數(shù)(1-e)表示信息素的揮發(fā)程度，所有螞蟻完成一次迭代循環(huán)，各航跡段上信息的濃度根據(jù)式(17)和(18)作調(diào)整。

(17)

其中，Δτij(N)b表示第N次迭代中最小代價的螞蟻所對應(yīng)的航跡，和一般算法對螞蟻進行對信息濃度增強不同，本文考慮最小代價航跡的信息濃度增強，這樣更有效地提高算法收斂速度，但是可能出現(xiàn)某條邊上信息素增長過快，因此設(shè)置區(qū)間把信息濃度限制在范圍[τmin,τmax]內(nèi)，以避免算法陷入停滯。

(18)

Q為常數(shù)，表示信息濃度增加強度系數(shù)，Lk表示第K只螞蟻在本次循環(huán)里所走過的路程。Q、ρ根據(jù)求解規(guī)模確定其取值。固定迭代次數(shù)或者當(dāng)解的變化不明顯的時候停止計算。

3 航跡規(guī)劃仿真驗證示例

圖2為二維等高線地形圖，地形的大小為20 km×20 km,地形圖中，出發(fā)點的坐標(biāo)為(1,2)和目標(biāo)點的坐標(biāo)為(19.18)，圖中每兩個同心圓的圓心表示威脅點，即雷達所在的位置，圖中一共選擇了8個點來進行標(biāo)記雷達的位置分別為(4,8)、(9,6)、(11,14)、(13,4)、(15,18)、(14,17)(15,10)和(19,14)。將雷達的偵測的絕對威脅區(qū)域用同心圓的內(nèi)部圓覆蓋的面積來表示，內(nèi)部圓的半徑為Rmin=2 km，由同心圓外圓的內(nèi)部與內(nèi)圓的外部之間的環(huán)形區(qū)域來表示非絕對禁止區(qū)域，外部圓的半徑為Rmax=2.5 km。用矩形來表示不可穿越的高山區(qū)域，中心坐標(biāo)分別為(15.7,6.5)，(16,5.5)寬度為1，中心坐標(biāo)(5,8)寬度為4，長為6。

圖2 等高線地圖

無人機根據(jù)所處的地形、雷達偵測位置和燃油代價對目標(biāo)節(jié)點進行路徑搜索，用線段表示無人機的搜索路線，其中Nmax=100，m=29，α=1，β=0.25，γ=0.5,e=0.1,Q=15,R=4，G=1，Lmax=35，K=0.5,C=1，圖3為普通蟻群算搜索的路線圖，圖4為加入了誘發(fā)向?qū)У南伻核惴?，根?jù)扇形區(qū)域提高了搜索效率，達到優(yōu)化路徑的目的。

圖3 改進前

圖4 改進后

4 結(jié)論

通過使用MATLAB仿真生成的路徑圖進行對比，從圖3上可以看出，普通的蟻群算法為了躲避威脅點，選擇以犧牲時間和路程為代價，采取遠距離繞行雷達威脅點的方式進行路徑搜索，雖然也可以實現(xiàn)路徑搜索，但是其無法滿足實際戰(zhàn)場對無人機的高效、快捷的需要。圖4為本算法的結(jié)果，可以看出在無人機路徑規(guī)劃上，加入誘發(fā)向?qū)е?，算法的收斂速度得到了保證，并且通過設(shè)置最優(yōu)路徑的信息濃度更新策略和范圍，不僅提高算法速度并且避免了算法陷入局部最優(yōu)及出現(xiàn)停滯的問題，有效提高局部搜索的效率，尤其是在路徑的選擇上，提供了一條捷徑優(yōu)化路徑來實現(xiàn)無人機對目標(biāo)的路徑搜索，達到了路徑優(yōu)化的要求。

[1] DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of coorperating agents[J].IEEE Transaction on Systems,Man and Cybernetics-Part B,1996:26(1):29-41.

[2] 段海濱,馬冠軍，王道波,等.一種求解連續(xù)空間優(yōu)化問題的改進蟻群算法[J].系統(tǒng)仿真學(xué)報，2007,19(5)：974-977.

[3] 溫文波,杜維.蟻群算法概述[J].石油化工自動化，2002(1)：19-22.

[4] RANDALL M,LEWIS A.A parallel implementation of ant colony optimization[J].Journal of Parallel and Distributed Computing,2002,69(9):1421-1432.

[5] 馮琦,周德云.軍用無人機發(fā)展趨勢[J].電光與控制,2003,10(1):9-13.

[6] KROZEI J,DOMINICK A.Navigation path planning for au-tonomous aircraft:voronoi diagram approach[J].Journal ofGuidance,Control,and Dynamics,1990,13(3):1152-1154.

[7] ZHANG WENDONG,BAI YANPING.The incorporation of an effieient initialization method and Parameter adaptation using self-oranizing maps to solve the TSP[J].Applied Mathematics and Computation,2006,172(1)：603-623.

[8] 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.

[9] 王萬良.人工智能及其應(yīng)用(第3版)[M].北京：高等教育出版社，2016：248-257.

[10]劉玉軍,張行知,蔡猛,等.基于監(jiān)測任務(wù)的多旋翼無人機路徑規(guī)劃[J].中國電子科學(xué)研究院學(xué)報,2017,12(1):20-24.

[11]陳海,何開鋒,錢煒祺.多無人機協(xié)同覆蓋路徑規(guī)劃[J].航空學(xué)報,2016,37(3):928-935.

[12]符小衛(wèi),程思敏,高曉光.無人機協(xié)同中繼過程中的路徑規(guī)劃與通信優(yōu)化[J].系統(tǒng)工程與電子技 術(shù),2014,36(5):890-894.

[13]李士勇,李研.智能優(yōu)化算法原理與應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2012:47-54.

[14]朱黔,周銳.具有持續(xù)偵察時間約束的協(xié)同航路規(guī)劃[J].北京航空航天大學(xué)學(xué)報，2016，42(10):2130-2138.

[15]齊乃明,孫小雷,董程,等.航跡預(yù)測的多無人機任務(wù)規(guī)劃方法[J].哈爾濱工業(yè)大學(xué)學(xué)報，2016,48(4):32-36.

UAV2Dpathplanningbasedonantcolonyoptimizationalgorithm

XU Hong-yu，SUN Hong-jun，HAN Yi
(College of Electronics and Information Engineering,Shenyang Aerospace University,Shenyang 110136,China)

To effectively improve the efficiency of unmanned aerial vehicle (UAV) in reconnaissance and attacking missions,a UAV path planning method based on guided ant colony algorithm is proposed.First,the four factors (i.e.enemy radar detection,flight fuel cost,maximum range and height cost) that affect the UAV flight are quantified.Then,the models of radar threat,the fuel cost,the maximum range limit,and the altitude cost are built respectively.And the efficiency of the ant system in local search is improved by setting the guidance factor.The analysis of the simulation results shows that the algorithm can effectively improve the efficiency of the UAV missions.

UAV;ant colony optimization algorithm;path planning;evoked guidance;fuel cost;radar detection

2017-07-20

徐宏宇(1965-)，男，遼寧沈陽人，副教授，主要研究方向：信息獲取與處理，E-mail：413945957@qq.com；孫洪俊(1987-)，男，遼寧鞍山人，碩士研究生，主要研究方向：信息獲取與處理，E-mail:369092349@qq.com。

2095-1248(2017)06-0078-05

V21

A

10.3969/j.issn.2095-1248.2017.06.013

劉劃 英文審校：齊義文)