林 娜，劉二超

(沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽 110136)

?

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

林 娜，劉二超

(沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院，沈陽 110136)

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

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

0 引言

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

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

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

1 航路規(guī)劃問題

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

1.1 威脅表示和任務(wù)描述

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

(1)

(2)

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

1.2 航路評(píng)價(jià)模型

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

(3)

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

(4)

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

圖2 威脅代價(jià)示意圖

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

2.1 蟻群算法的基本原理

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

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

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

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

(4)

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

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

(5)

(6)

2.3 蟻群算法的改進(jìn)

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

2.3.1 改進(jìn)航路點(diǎn)選擇策略

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

在t時(shí)刻，螞蟻從k按照下式確定下一時(shí)刻將要到達(dá)的航路點(diǎn)j：分別

(7)

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

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

2.3.2 改進(jìn)信息素?fù)]發(fā)因子調(diào)整準(zhǔn)則

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

(8)

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

(9)

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

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

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

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

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

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

Step 4：依據(jù)公式(3)對(duì)螞蟻得到的所有可飛航路進(jìn)行代價(jià)評(píng)估，保存所找到的最優(yōu)航路。

Step 5：對(duì)飛行區(qū)域中的各航路點(diǎn)按公式(5)、(6)進(jìn)行信息素調(diào)整。

Step 6：依據(jù)最優(yōu)解判斷是否需要進(jìn)行ρ值的調(diào)整，如需要?jiǎng)t按照公式(8)、(9)進(jìn)行信息素?fù)]發(fā)因子的自適應(yīng)調(diào)整。

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

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

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

(10)

圖3 存在拐角的航路

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

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

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

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

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

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

5 實(shí)驗(yàn)仿真與結(jié)果分析

5.1 實(shí)驗(yàn)仿真

為了驗(yàn)證以上提出的改進(jìn)蟻群算法在解決無人機(jī)航路規(guī)劃問題的有效性，這一部分在Windows 8操作系統(tǒng)中使用matlab 8.1平臺(tái)進(jìn)行仿真，硬件配置為：英特爾i5-2400 @ 3.10GHz 處理器，4GB內(nèi)存。仿真時(shí)使用的相關(guān)參數(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，無人機(jī)飛行區(qū)域內(nèi)，起始點(diǎn)S和目標(biāo)點(diǎn)G的坐標(biāo)分別為(10,10)和(10,10)，有3種威脅源分布在這兩點(diǎn)之間，不同種類的威脅源的威脅半徑不同，表1所示是6個(gè)威脅源的圓心位置坐標(biāo)和攻擊半徑。

表1 6個(gè)威脅源的分布

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果分析

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

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

表3 動(dòng)態(tài)威脅下各算法性能對(duì)比

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

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

6 結(jié)論

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

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

系統(tǒng)工程與電子技術(shù), 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] 潘廣貞, 秦 帆, 張文斌. 動(dòng)態(tài)自適應(yīng)快速擴(kuò)展樹航跡規(guī)劃算法研究[J]. 微電子學(xué)與計(jì)算機(jī), 2013,30(1):49-52.

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

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

[7] 劉振峰, 謝洪森, 危水根. 基于蟻群遺傳算法的三維飛行器航路規(guī)劃[J]. 計(jì)算機(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] 柳長(zhǎng)安, 梁廣平, 王和平，等. 蟻群算法在無人機(jī)航路規(guī)劃中的應(yīng)用[J]. 火力與指揮控制, 2005, 30(6):22-24.

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

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

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

[13] 鄔 琦, 潘廣貞, 楊江濤. 基于Voronoi圖和動(dòng)態(tài)自適應(yīng)蟻群算法的UAV航跡規(guī)劃[J]. 計(jì)算機(jī)測(cè)量與控制, 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。

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

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

1671-4598(2016)03-0149-05

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

TP311

A