基于改進蟻群算法的無人機動態(tài)航路規(guī)劃

林 娜，劉二超

(沈陽航空航天大學 計算機學院，沈陽 110136)

?

基于改進蟻群算法的無人機動態(tài)航路規(guī)劃

林 娜，劉二超

(沈陽航空航天大學 計算機學院，沈陽 110136)

研究無人機航路規(guī)劃，針對基本蟻群算法易于陷入局部最優(yōu)、規(guī)劃航路耗時長的問題，對基本蟻群算法進行了改進；引入航路點的動態(tài)自適應選擇策略和信息素揮發(fā)因子動態(tài)自適應調整準則，有效克服了基本蟻群算法的不足，并對規(guī)劃出的航路進行了平滑處理，使其更加滿足無人機實際飛行需求；通過仿真分別規(guī)劃出無人機在靜態(tài)威脅和動態(tài)威脅中的航跡，仿真結果表明，與基本蟻群算法和遺傳算法相比，改進的蟻群算法在兩種飛行環(huán)境中均能規(guī)劃出較優(yōu)的航路。

無人機；蟻群算法；選擇策略；信息素；平滑處理

0 引言

無人機(unmanned aerial vehicle, UAV)在現(xiàn)代戰(zhàn)爭中的使用越來越廣泛，這與無人機自身獨有的零傷亡、體積小、成本低、機動性好以及對作戰(zhàn)環(huán)境要求低等特點密不可分。無人機航路規(guī)劃(UAV Route Planning)是無人機實現(xiàn)自主導航飛行的核心技術，它是在一個具有動態(tài)威脅的環(huán)境中，依據地形和敵方情報，在預定任務、威脅分布、燃油限制等約束條件下，于出發(fā)點和終點之間找到一條可飛航跡。

文獻[1]提出了一種基于A*算法的無人機航路實時規(guī)劃算法，然而A*算法計算量較大，因此對機載處理系統(tǒng)的性能要求較高。文獻[2]提出了一種改進概率地圖法的算法，作者只把最短航跡作為唯一的優(yōu)化目標，考慮因素較為單一。文獻[3]使用蟻群優(yōu)化算法對UAV進行航路規(guī)劃，但是作者只是針對室內環(huán)境進行試驗，而且規(guī)劃航跡呈折線狀，無法滿足無人機實際飛行需求。文獻[4]采用快速探索樹(rapidly exploring random tree, RRT)規(guī)劃算法提高無人機在線搜索速度，但并沒有考慮無人機自身的動力約束，無法滿足飛行條件。文獻[5]提出了基于Voronoi圖的航路規(guī)劃算法，該算法以已知的威脅為中心采用矢量法為無人機飛行空間建模時，當飛行空間復雜時存在較大的空間建模比較復雜。文獻[6-7]提出了基于遺傳算法的航路規(guī)劃方法，遺傳算法不受搜索空間的限制，不依賴梯度信息，在航路規(guī)劃中應用較廣，但是基本蟻群算法在求解復雜問題時會出現(xiàn)進化過程過早收斂的問題。

為了規(guī)劃出滿足無人機實際飛行的航路，本文設計了一種基于改進蟻群 (modified ant colony optimization, MACO)算法的無人機航路規(guī)劃算法。首先，改進基本蟻群算法的狀態(tài)轉移規(guī)則同時對信息素揮發(fā)因子進行自適應調整。其次，結合已知的威脅信息采用MACO算法對無人機進行航路預規(guī)劃，并對預規(guī)劃出的航路進行平滑優(yōu)化。最后，無人機按預規(guī)劃航路飛行，飛行過程中使用機載雷達等探測設備對周圍飛行環(huán)境進行探測，發(fā)現(xiàn)突發(fā)威脅時，對航路進行局部重規(guī)劃，從而避開動態(tài)攻擊。

1 航路規(guī)劃問題

當無人機以恒定高度飛行處于巡航狀態(tài)時，那么可以用二維平面等效其飛行區(qū)域。因此，研究無人機在二維平面下的航路規(guī)劃是必要且有意義的。本文就以二維平面為無人機飛行空間，假定無人機以恒定速度飛行，并綜合考慮各種威脅和約束，對無人機航路進行規(guī)劃。

1.1 威脅表示和任務描述

為了明確表示出無人機的飛行航路，需要對無人機的飛行區(qū)域進行建模。假設無人機在大小為350 km×350 km的平面區(qū)域進行偵查作業(yè)。無人機在偵查過程中會遇到各種威脅，本文主要考慮敵方雷達，防空導彈陣地，地形威脅等約束條件。如圖1所示是無人機飛行環(huán)境模型，在笛卡爾坐標系下，采用平面圓域(X,Y,R)等效各種威脅，圓心所在位置(X,Y)用以模擬威脅源出現(xiàn)的位置，圓的半徑R用以模擬威脅源的有效威脅范圍，各種威脅圓構成了無人機的危險飛行區(qū)(danger zones)或者禁飛區(qū)(no-fly zones)。

(1)

(2)

圖1 無人機飛行環(huán)境

1.2 航路評價模型

無人機飛行航路的優(yōu)劣程度直接影響UAV的作戰(zhàn)能力，因此通過對無人機飛行區(qū)域進行建模得到航路節(jié)點后，仍需利用航路評價模型評估各段航路以及總體航路的性能。在考慮無人機飛行航距、受威脅影響程度和無人機拐角限制等因素的基礎上，本文采用如下的評價模型來對無人機航路進行評估[8]：

(3)

式中，F(xiàn)cost為無人機航路性能指標函數(shù)；ω1、ω2、ω3為權重系數(shù)，ω1、ω2、ω3∈[0,1]且有ω1+ω2+ω3=1，Clength懲罰飛行距離相對較長的航路，確保無人機飛行的飛行距離最短，從而降低其燃料消耗并減少飛行時間；Cturn懲罰存在較多拐角的航路，從無人機自身性能約束來講，一條拐角較多的航路意味著無人機在飛行時經歷的制動點多，頻繁的制動將會增加無人機的飛行風險，本文第4部分還采用了平滑的辦法對航路上的拐點進行平滑；Cthreat為第i段航路上的威脅代價，為了更加精確地表示某段航路上的威脅代價，將待評估的某段航路均分成N等分[1]，分別計算航路上的等分點到威脅的直線距離。如圖2所示，在待評估的航路上找出均勻分布的5個點，分別計算各個點到威脅源的威脅代價，最后累加求和即為該段航路上的威脅代價：

(4)

式中，Kj為第j個威脅的強度，Rij為航路上的點與第j個威脅的距離，N為無人機的機載雷達在當前飛行位置下所能探測到的威脅的總數(shù)。

圖2 威脅代價示意圖

2 改進蟻群算法的航路規(guī)劃

2.1 蟻群算法的基本原理

受到真實蟻群覓食行為的啟發(fā)，M.Dorigo、V.Maniez-zo、A.Colorini等人于1991年首先提出了蟻群算法(Ant Algorithm),并應用在TSP問題的求解上，取得了較好的成效[9]。

蟻群算法是一種生物仿真進化算法，旨在解決路徑規(guī)劃過程中的組合優(yōu)化問題。在蟻群算法中，一只螞蟻在其覓食過程中會路徑上釋放生物信息素，后到的螞蟻會感知到前者釋放的信息素，同時后到者也會釋放信息素從而強化已經存在的信息素，如此反復進行。因此，經過螞蟻越多的路徑信息素濃度越高，被后到螞蟻選中的概率就越大。因為在某段時間內，越短的路徑就會被越多的螞蟻選中，則積累的信息素濃度隨之提高，在后續(xù)時間內被其他螞蟻選中的概率也隨之越大。持續(xù)重復這個過程，直到幾乎所有的螞蟻都選擇最短的路徑為止，那么這條路徑也就是蟻群選擇的最優(yōu)或者次優(yōu)航路[10]。

2.2 航路點選擇規(guī)則

將無人機的起飛點視為蟻巢，目標點視為蟻群的食物源，這樣蟻群尋找最優(yōu)或者次優(yōu)路徑的過程就是對無人機進行航路規(guī)劃的過程。蟻群基于信息素濃度和可見度選擇下一段航路或者目標點，在t時刻第k只螞蟻從當前節(jié)點i轉移到下一節(jié)點j的轉移概率為：

(4)

其中：τij(t)為節(jié)點i與節(jié)點j連接路徑上的信息素濃度，ηij(t)為啟發(fā)函數(shù)，經典蟻群算法中該函數(shù)為節(jié)點i到節(jié)點j的距離倒數(shù)，表示螞蟻轉移到節(jié)點j的期望程度；allowk為螞蟻k即將訪問的航路點的集合；參數(shù)α和β分別表示為信息素重要程度因子和能見度重要程度因子。

螞蟻在釋放信息素的同時，各條航路上的信息素濃度逐步降低，令ρ表示信息素的揮發(fā)因子，因此當所有螞蟻完成一次搜索后，僅對成功搜索到目標點的螞蟻所經歷過的航路上的信息素進行更新，即：

(5)

(6)

2.3 蟻群算法的改進

采用基本蟻群算法為無人機規(guī)劃航路時，分析實驗結果可明顯發(fā)現(xiàn)基本蟻群算法具有收斂速度慢、易于陷入局部最優(yōu)的缺陷[11]。出現(xiàn)這種現(xiàn)象的原因是局部航路上的信息素堆積過量，這些濃度過高的信息素會對后到的螞蟻在選擇航路上造成影響，導致大量的螞蟻集中于此航路，最終導致算法出現(xiàn)早熟。因此直接將蟻群算法應用于無人機航路規(guī)劃問題欠妥。為了克服這些缺點，本文對基本蟻群算法進行了如下改進。

2.3.1 改進航路點選擇策略

傳統(tǒng)蟻群算法發(fā)生狀態(tài)轉移時，采用概率隨機選擇策略，這種策略缺乏引導因素，致使算法進化緩慢。因而本文從航路點選擇策略入手進行改進，引入隨機選擇和偽隨機性選擇相結合的選擇策略，如公式(7)，并且在搜索過程中動態(tài)調整作偽隨機性選擇的概率，這樣可以有效降低螞蟻在搜索過程中的盲目性。當搜索進行至一定代數(shù)時，搜索方向已經趨于穩(wěn)定，此時可以適當增加作隨機選擇的概率，以方便對解空間的更充分的搜索，從而達到克服基本蟻群算法不足的目的。

在t時刻，螞蟻從k按照下式確定下一時刻將要到達的航路點j：分別

(7)

式中，預先定義q0∈[0,1]，q為[0,1]上服從均勻分布的隨機數(shù)，α、β的含義同公式(4)，采用該改進的選擇策略，可以隨著搜索的進行動態(tài)調整q0的值，當q≤q0時，可以選擇改進的移動規(guī)則，由信息素濃度和啟發(fā)函數(shù)聯(lián)合決定螞蟻最佳的選擇方向；當q>q0時，可以執(zhí)行有誘導的探索，確保算法的收斂。使用該改進規(guī)則的主要目的不僅是節(jié)省搜索時間加快收斂速度，而且還能增強搜索的多樣化，避免停滯狀態(tài)的過早發(fā)生。

排砂冷采不進行防砂，所以單井出砂量很大。排砂冷采完全依靠天然能量進行開采，初期產量很高，但是持續(xù)時間比較短，采收率較低。由于地層形成了“蚯蚓洞”所以若后期轉注水和注汽措施容易發(fā)生氣竄水竄，另一方面“蚯蚓洞”一旦遭遇邊底水入侵開采效果將會劇降。

2.3.2 改進信息素揮發(fā)因子調整準則

蟻群算法中，信息素揮發(fā)因子ρ的取值與算法的全局搜索能力及其收斂速度密切相關，ρ的初始值直接影響各條航路上信息素的分布?；鞠伻核惴ㄖ?，ρ值保持不變。當無人機規(guī)劃空間較復雜時，由于信息素揮發(fā)因子ρ的存在，將導致未被搜索到的節(jié)點上的信息素濃度持續(xù)降低甚至逼近0的情況，影響了算法的全局搜索能力。ρ過大時，雖然會加快算法收斂，但易于陷入局部最優(yōu)；ρ過小時，以前搜索過的節(jié)點被再次選擇的概率較大，又會影響算法的的收斂速度。鑒于此，本文受最大-最小螞蟻系統(tǒng)思想的啟發(fā)[12]，給信息素揮發(fā)因子ρ設定上限和下限，在采用蟻群算法求解過程中，當?shù)欢ù螖?shù)求得的最優(yōu)值沒有顯著改善時，采用式(8)對ρ進行調整：

(8)

式中，ρmin、ρmax分別表示信息素揮發(fā)因子ρ的下限和上限，設定ρ的上下限，可以有效避免算法的易于陷入局部最優(yōu)和收斂速度慢的缺點。λ為引入的揮發(fā)約束系數(shù)，λ∈(0,1)，為了更加精確地模擬信息素的揮發(fā)情況，引入了一種隨機函數(shù)，即rand(t+1)，該函數(shù)的取值為(0.75, 0.95)的隨機數(shù)，并利用該隨機函數(shù)對揮發(fā)約束系數(shù)λ進行如下修正[13]：

(9)

采用引入隨機函數(shù)的機制，使得信息素能夠按照一種隨機的方式進行揮發(fā)，確保了信息素的更新更加符合自然界真實情況。將式(5)中的信息素揮發(fā)因子ρ用ρ(t)替代，使得信息素τ也隨之更新。每當循環(huán)結束時，保留最優(yōu)解，將其作為判斷ρ如何調整的條件。

2.4 改進蟻群算法實現(xiàn)過程

采用改進蟻群算法為無人機規(guī)劃航路的步驟如下。

Step 1：初始化無人機飛行區(qū)域所有航路點的信息素，即構造初始信息素矩陣；

Step 2：M只螞蟻置于起始點S處待出發(fā)；

Step 3：螞蟻依據公式(4)、(7)由當前航路點選擇下一航路點，如此迭代下去，直到抵達目標點，得到一條可飛航路。所有螞蟻均執(zhí)行此過程。

Step 4：依據公式(3)對螞蟻得到的所有可飛航路進行代價評估，保存所找到的最優(yōu)航路。

Step 5：對飛行區(qū)域中的各航路點按公式(5)、(6)進行信息素調整。

Step 6：依據最優(yōu)解判斷是否需要進行ρ值的調整，如需要則按照公式(8)、(9)進行信息素揮發(fā)因子的自適應調整。

Step 7：判斷是否已經滿足循環(huán)結束條件，即是否達到既定的迭代次數(shù)或找到最優(yōu)解，如果滿足則結束循環(huán)，否則轉至Step 2繼續(xù)執(zhí)行，直至滿足迭代條件。

3 航路的優(yōu)化處理

以上改進的蟻群算法規(guī)劃出的航路存在拐角，如圖3所示，無人機在這樣的航路上飛行需要頻繁的制動操作，這會增加無人機的飛行風險，對無人機的結構性能也是一種考驗，所以要對這些存在拐角的航路進行平滑處理。無人機的最小轉彎半徑按如下公式計算[14]：

(10)

圖3 存在拐角的航路

如圖4所示，如果3個航跡點Pi-1、Pi、Pi+1構成的航路段存在夾角，則以無人機最小轉彎半徑做拐角的內切圓，用內切圓的圓弧部分取代該拐角部分，使得航路平滑可飛。

圖5和圖6分別是改進蟻群算法平滑之前和平滑之后的航路，通過對比可以發(fā)現(xiàn)經過平滑處理的航路消除了原有航路上存在拐角的地方，這樣的航路更加滿足無人機實際飛行需求。

圖4 航路優(yōu)化示意圖

4 航路的預規(guī)劃與重規(guī)劃

無人機實際執(zhí)行任務時應該首先根據已知的情報信息規(guī)劃出一條最優(yōu)或者次優(yōu)的飛行航路，無人機先按照該航路飛行，飛行過程中由無人機機載雷達等設備不斷地對周圍環(huán)境進行檢測；當檢測到突發(fā)威脅后，無人機將判斷預規(guī)劃的航路是否處于改為的有效殺傷范圍，若不在有效殺傷范圍內，則無人機按原有航路飛行，若在有效殺傷范圍內，則無人機以當前點位新的出發(fā)點重新規(guī)劃航路，以確保能夠躲避檢測到的突發(fā)威脅。重規(guī)劃流程圖如圖5所示。

圖5 重規(guī)劃流程圖

5 實驗仿真與結果分析

5.1 實驗仿真

為了驗證以上提出的改進蟻群算法在解決無人機航路規(guī)劃問題的有效性，這一部分在Windows 8操作系統(tǒng)中使用matlab 8.1平臺進行仿真，硬件配置為：英特爾i5-2400 @ 3.10GHz 處理器，4GB內存。仿真時使用的相關參數(shù)，ω1=0.4，ω2=0.4，ω3=0.2，M=90，Q=100，α=1,β=4,q0=0.8，ρmin=0.1，ρmax=0.95，無人機飛行區(qū)域內，起始點S和目標點G的坐標分別為(10,10)和(10,10)，有3種威脅源分布在這兩點之間，不同種類的威脅源的威脅半徑不同，表1所示是6個威脅源的圓心位置坐標和攻擊半徑。

表1 6個威脅源的分布

針對上述只存在靜態(tài)威脅的飛行環(huán)境，分別采用基本蟻群算法、遺傳算法和改進蟻群算法進行仿真，設定各算法迭代次數(shù)均為300次。圖6為3種仿真效果圖，其中的航路均已進行平滑優(yōu)化。

圖6 靜態(tài)環(huán)境下3種算法航路規(guī)劃示意圖

另外，為了驗證改進蟻群算法躲避具有規(guī)避動態(tài)威脅能力，在上述飛行環(huán)境的基礎上加入動態(tài)威脅，用虛線圓模擬該動態(tài)威脅，圖7為3種算法仿真效果圖，其中的航路均已進行平滑優(yōu)化。

圖7 動態(tài)威脅下3種個算法航路規(guī)劃示意圖

5.2 實驗結果分析

針對只存在靜態(tài)威脅和存在動態(tài)威脅兩種飛行環(huán)境，基本蟻群算法、改進蟻群算法和遺傳算法的性能分析分別如表2、3和圖8、9所示。從表2和圖8可以看出，在只存在靜態(tài)威脅的飛行環(huán)境下，與基本蟻群算法和遺傳算法相比，改進蟻群算法能在相對較短的時間內搜索出最優(yōu)航路；從表3和圖9可以看出，在存在動態(tài)威脅的飛行環(huán)境下，與基本蟻群算法和遺傳算法相比，改進蟻群算法也能用較短的時間搜索出最優(yōu)航路。

表2 靜態(tài)威脅下各算法性能對比

表3 動態(tài)威脅下各算法性能對比

圖8 靜態(tài)威脅中3種算法收斂圖

圖9 靜態(tài)威脅中3種算法收斂圖

6 結論

傳統(tǒng)的蟻群算法在解決無人機航路規(guī)劃時存在易于陷入局部最優(yōu)，收斂速度慢的問題，鑒于此，對傳統(tǒng)的蟻群算法做了改進，提出航路點的自適應選擇策略和信息素揮發(fā)因子自適應調整準則，并進行了仿真，實驗結果表明改進蟻群算法有效克服了基本蟻群算法的不足，并與遺傳算法做了對比，對比顯示改進的蟻群算法在搜索時間和搜索的航路長度上優(yōu)于遺傳算法，還引入了在線重規(guī)劃機制，該機制提高了無人機在真實戰(zhàn)場環(huán)境下的作戰(zhàn)能力。

[1] 李士波, 孫秀霞, 王 棟，等. 無人機動態(tài)環(huán)境實時航跡規(guī)劃[J].

系統(tǒng)工程與電子技術, 2007,29(3):399-401.

[2] Qian X, Peng C, Nong C. Offline Path Planning and Online Replanning of UAVs in Complex Terrain[A]. Proceedings of 2014 IEEE Chinese Guidance, Navigation and Control Conference[C]. Yantai, China, 2014:2287-2292.

[3] He Y F, Zeng Q H, Liu J Y, et al.Path Planning for Indoor UAV Based on Ant Colony Optimization[A]. 2013 25th Chinese Control and Decision Conference[C]. Guiyang, China, 2013: 2913-2923.

[4] 潘廣貞, 秦 帆, 張文斌. 動態(tài)自適應快速擴展樹航跡規(guī)劃算法研究[J]. 微電子學與計算機, 2013,30(1):49-52.

[5] 張?zhí)陨? 魯 藝, 張 亮，等. 改進型Voronoi圖和動態(tài)權值A*算法的無人機航跡規(guī)劃[J]. 火力與指揮控制, 2015,40(2):156-160.

[6] 唐 強, 王建元, 朱志強. 基于粒子群優(yōu)化的三維突防航跡規(guī)劃仿真研究[J]. 系統(tǒng)仿真學報, 2004,16(9): 2033-2036.

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

[8] Vincent Roberge, Mohammed Tarbouchi, Gilles Labonté. Comparison of Parallel Genetic Algorithm and Particle Swarm Optimization for Real-Time UAV Path Planning[J]. IEEE Transaction on Industrial Informatics, 2013, 9(1):132-141

[9] 柳長安, 梁廣平, 王和平，等. 蟻群算法在無人機航路規(guī)劃中的應用[J]. 火力與指揮控制, 2005, 30(6):22-24.

[10] 邱小湖,邱永成. 優(yōu)化蟻群算法在無人機航路規(guī)劃中的應用[J]. 計算機仿真, 2010, 27(9):102-105.

[11] 柴毅哲, 楊任農, 馬明杰，等. 基于改進蟻群算法的可規(guī)避威脅源最優(yōu)航線規(guī)劃[J]. 空軍工程大學學報(自然科學版), 2015,16(2):23-27.

[12] 黃永青, 楊 凡, 張峻嶺，等. 一種交互式最大最小螞蟻算法[J]. 計算機工程, 2012,38(20):128-131.

[13] 鄔 琦, 潘廣貞, 楊江濤. 基于Voronoi圖和動態(tài)自適應蟻群算法的UAV航跡規(guī)劃[J]. 計算機測量與控制, 2014,22(9):3037-3037.

[14] Wen N F, Zhao L L, Su X H, et al. UAV Online Path Planning Algorithm in a Low Altitude Dangerous Environment[J]. IEEE/CAA Journal of Automatica SINICA,2015,2(2).

UAV Route Planning in Dynamic Environment Based on Modified Ant Colony Opimization

Lin Na， Liu Erchao

(College of Computer Science, Shenyang Aerospace University, Shenyang 110136, China)

On the research of route planning for UAVs, the basic Ant Colony Optimization algorithm is easily trapped into local optimal and takes very long time to plan the route, so the Ant Colony Optimization is modified in this paper; by introducing dynamic adaptive route selection and pheromone evaporation factor dynamic adaptive criteria, we overcome the shortage of basic Ant Colony Optimization algorithm effectively, at the same time measures are taken to smooth the planned route to make it meet the demand of UAVs’ flight. By simulation, we get the routes in static threat environment and dynamic threat environment respectively, the results show that modified Ant Colony Algorithm can map out optimal routes in both environment.

UAVs; ant colony optimization; selection strategies; pheromone; smoothing

2015-08-25；

2015-10-26。

遼寧省自然科學基金聯(lián)合基金(2015020008)；遼寧省自然科學基金(20102175； 201102171)；遼寧省高等學校優(yōu)秀人才支持計劃(LJQ2012011)；遼寧"百千人才工程"人選項目(2010921080；2009921089)。

林 娜，遼寧沈陽人，博士，副教授，主要從事智能交通，下一代網絡，無人機航跡規(guī)劃方向的研究。

1671-4598(2016)03-0149-05

10.16526/j.cnki.11-4762/tp.2016.03.041

TP311

A