基于改進蟻群算法的無人機航跡規(guī)劃

韓 攀,陳 謀,陳哨東,劉 敏

(1.南京航空航天大學(xué) 自動化學(xué)院,南京 210016； 2.洛陽光電設(shè)備研究所 光電控制技術(shù)重點實驗室,河南 洛陽 471009)

0 引 言

隨著科技發(fā)展和社會進步,現(xiàn)代無人機運用的領(lǐng)域和范圍越來越廣,執(zhí)行的任務(wù)也更加復(fù)雜和多樣化。好的航跡可降低任務(wù)風險或成本,航跡優(yōu)化的價值也隨之變高。航跡規(guī)劃作為無人機自主飛行控制研究的重要內(nèi)容之一,一直都是人們研究的熱點,隨之興起的算法也是層出不窮。如果按實時性分類,可分為離線航跡規(guī)劃和在線航跡規(guī)劃[1]。離線航跡規(guī)劃一般是在無人機放飛前加載已規(guī)劃好的飛行航線,在飛行的過程中不再改變飛行航線,對航跡規(guī)劃的實時性要求不高； 在線航跡規(guī)劃是指無人機在飛行的過程中根據(jù)需要動態(tài)修改飛行航線,對實時性要求較高。文獻[1]對在線航跡規(guī)劃的相關(guān)問題進行了研究,研究了當前常用的在線航跡規(guī)劃方法,闡述了在線航跡規(guī)劃的通用結(jié)構(gòu)框架以及面臨的關(guān)鍵問題。但總體來說,在線航跡規(guī)劃是在離線航跡規(guī)劃基礎(chǔ)上進行的。因此,筆者主要研究離線航跡規(guī)劃技術(shù)并提高其全局優(yōu)化能力。

航跡規(guī)劃算法如果按照規(guī)劃決策的計算方法分類,可分為最優(yōu)式和啟發(fā)式算法。最優(yōu)式算法包括窮舉法、動態(tài)規(guī)劃和數(shù)學(xué)規(guī)劃等[2]。啟發(fā)式算法則包括啟發(fā)式搜索、神經(jīng)網(wǎng)絡(luò)、模擬退火和遺傳算法等[3]。兩者的根本區(qū)別在于,最優(yōu)式算法的計算時間隨系統(tǒng)規(guī)模的變大而呈現(xiàn)爆炸式增長。如果按照幾何學(xué)的觀點分類,可將其分為基于柵格的算法和基于圖形的算法。如文獻[4]運用Voronoi圖對航跡規(guī)劃問題進行建模,通過Voronoi圖對規(guī)劃空間進行分區(qū),然后根據(jù)約束條件求解航跡規(guī)劃問題。兩者各有所長,一般來說,后者的處理結(jié)果比較準確,但需要相對較長的收斂時間； 前者可在實時要求的條件下收斂,但對一些約束條件難以處理。

由于航跡規(guī)劃問題是個多約束條件的組合優(yōu)化問題,各約束條件之間存在耦合,目前常用的算法在航跡規(guī)劃的運用中各有所長,但也普遍存在著一些缺點。如傳統(tǒng)的數(shù)學(xué)計算方法結(jié)果精確,但對于模型要求嚴格,且隨著問題規(guī)模的增大,計算時間和所需的存儲空間也迅速變大； 新興的智能計算方法計算速度快,對模型要求不高,但算法易停滯和陷入局部最小值。所以,實際應(yīng)用中一般會根據(jù)具體的問題改進算法[4-7],如文獻[5]結(jié)合了蟻群算法和遺傳算法,利用遺傳算法的變異特性彌補蟻群算法運行后期收斂慢的缺陷； 文獻[6]結(jié)合了知識庫和蟻群算法,通過動態(tài)更新知識庫調(diào)整算法參數(shù),從而使算法的動態(tài)性增強。

蟻群算法最早由Dorigo等[8]作為一種多Agent的方法,很好地解決了一些復(fù)雜的組合優(yōu)化問題。目前已經(jīng)有很多種基于蟻群算法或其改進算法應(yīng)用于各種不同的離散優(yōu)化問題,這些研究已經(jīng)涵蓋了路徑規(guī)劃,順序訂貨問題以及網(wǎng)絡(luò)中的路由通信問題等[8-12]。蟻群算法以其良好的動態(tài)性、魯棒性以及全局的并行計算能力而被廣泛應(yīng)用于各領(lǐng)域。筆者以蟻群算法為基礎(chǔ),求解航跡規(guī)劃問題,對于蟻群算法在航跡規(guī)劃中的應(yīng)用做了分析和研究。針對基本蟻群算法在收斂后期易陷入局部最優(yōu)的缺點,通過引入去交叉禁忌搜索策略改進算法,提高了算法的全局優(yōu)化能力,進而提高無人機的航跡規(guī)劃效果。

1 問題描述

無人機執(zhí)行任務(wù)多種多樣,每個問題的約束條件也不完全相同。如何評價一條航跡的優(yōu)劣,是解決無人機航跡規(guī)劃問題的前提。不妨先設(shè)定按某一航跡執(zhí)行任務(wù)的航跡總代價為

C=∑Ci

(1)

其中Ci為每段航跡執(zhí)行任務(wù)的航跡代價,簡稱為任務(wù)段代價。任務(wù)段代價受任務(wù)段的約束條件控制,例如飛行距離、飛行時間和油耗等。設(shè)約束集合為Ri={Ri1,Ri2,Ri3,…},按任務(wù)段約束條件,Ci可看作是對Ri的加權(quán)求和

Ci=∑RijWij

(2)

其中Rij為當前任務(wù)段的約束,Wij為該約束對應(yīng)的權(quán)值。假設(shè)Ci可求出,并且Ci為無量綱數(shù)值,則每個任務(wù)段的代價可看做一個無量綱的確定值。每個任務(wù)段之間的代價Ci用任務(wù)段的代價Li表示

Li=liwi

(3)

其中l(wèi)i是航路點之間的歐式距離,wi為權(quán)值。在一般情況下無人機執(zhí)行偵察和巡邏任務(wù)都是在固定高度定速飛行,只有在起飛和著陸階段才有高度和速度的變化,因而在計算任務(wù)段代價時可以忽略高度的影響。筆者設(shè)定航路點集合為V={(Vx1,Vy1),(Vx2,Vy2),…,(Vxm,Vym)},m為航路點的個數(shù)。假設(shè)每個任務(wù)段的主要約束條件為飛行距離、飛行時間和油耗,當無人機速度一定時,飛行時間和油耗與飛行距離成正比,因此,在計算任務(wù)段的代價時可只用飛行距離表示,式(3)中wi為一個常數(shù)。為便于計算,假定wi=1。此時無人機的航跡規(guī)劃問題就是確定一條通過所有航路點的最短距離的閉合航路,這與旅行商問題的描述是一致的,因此無人機航跡規(guī)劃問題可以轉(zhuǎn)化為TSP(Travelling Salesman Problem)旅行商問題。

2 基于改進蟻群算法的無人機航跡規(guī)劃

2.1 蟻群優(yōu)化算法

(4)

其中ηij為啟發(fā)因子,表示從城市i到j(luò)的期望程度,一般是城市距離dij的倒數(shù),可寫為

ηij=1/dij

(5)

信息素更新公式為

(6)

其中

(7)

基本蟻群算法的參數(shù)主要有4個,其中α是表征信息素重要程度的參數(shù),β是表征啟發(fā)式因子重要程度的參數(shù),ρ是信息素蒸發(fā)系數(shù),Q是信息素增加強度系數(shù)。

2.2 基于蟻群算法的航跡規(guī)劃

大多數(shù)情況下,無人機執(zhí)行任務(wù)時飛行的航跡都是從起點出發(fā)到各個航路點完成任務(wù)再返回起點的過程。筆者的航跡規(guī)劃也是以此為前提,假設(shè)無人機飛行的航路點已確定,無人機到達各航路點無時間約束,不考慮垂直方向的運動。這樣航跡規(guī)劃問題就可轉(zhuǎn)化為TSP問題,在利用蟻群算法規(guī)劃航路時,只需要將求解TSP問題時的城市坐標改為航路點坐標即可。求解TSP問題時,基本蟻群算法完整的偽代碼如下[2,3]。

Step1 初始化,將螞蟻隨機分布到城市中,將螞蟻所在的城市添加到各自的禁忌列表中。

Step2 設(shè)定結(jié)束條件,不滿足結(jié)束條件,執(zhí)行Step3、Step4循環(huán)。

Step3 對螞蟻k,1≤k≤m,進行如下操作：

if (本次循環(huán)結(jié)束時能到達下一個城市i)

抵達下一個城市i；

else

記錄本次循環(huán)路徑。

Step4 更新路徑上的信息素。

Step5 輸出結(jié)果。

Step6 程序結(jié)束。

下面是運用基本蟻群算法對4個航路點的求解結(jié)果,設(shè)定4個航路點的坐標如表1所示,運用Matlab編程進行仿真,得到航跡規(guī)劃的結(jié)果如圖1所示。

表1 航路點坐標數(shù)據(jù)

圖1是一個簡單的航跡規(guī)劃問題,有4個航路點,顯然圖1b是最優(yōu)解。當?shù)螖?shù)減少時,可能會出現(xiàn)圖1a所示的結(jié)果,其他和圖1a類似的幾條路徑這里就不列出了。

a 航跡規(guī)劃圖1 b 航跡規(guī)劃圖2

基本蟻群算法和其他組合優(yōu)化算法一樣,存在會陷入局部最優(yōu)解的現(xiàn)象。針對這一現(xiàn)象研究學(xué)者們也嘗試對基本的蟻群算法進行多方面改進。改進的思路主要有兩種：1)修改與算法相關(guān)的因子,使算法與問題的相關(guān)性增強,如天才蟻群算法(EAS:Elitist Ant System)[13,14]、排序螞蟻系統(tǒng)(Rank-Based Ant System)[15]； 2)與其他算法相結(jié)合,融合各算法的優(yōu)點,如與遺傳算法結(jié)合[5],利用遺傳算法的變異特性彌補蟻群算法運行后期收斂慢的缺陷。文獻[3]中對在基本蟻群算法中引入去交叉策略的改進做了分析,從這點出發(fā)對這種改進的具體實現(xiàn)做了研究。

2.3 改進蟻群算法

為比較圖1a和圖1b兩條路徑的優(yōu)劣,把圖1中兩條路徑放到一起并標識路徑端點(見圖2)。

通過比較,可發(fā)現(xiàn)實線所示的路徑(圖1a上的路徑)中AB段與CD段相互交叉,由三角形的定義知

(8)

圖2 路徑示意圖

顯然|AB|與|CD|的距離大于|AC|與|BD|的距離,由此可推出圖2中實線所示的路徑比虛線路徑長。同時可推出只要路徑有交叉點,就一定有一條更優(yōu)的路徑存在。由此得出如下兩點結(jié)論：

結(jié)論1 如果優(yōu)化的路徑中存在相互交叉的路徑,則這條路徑一定不是最優(yōu)的；

結(jié)論2 如果存在一條路徑使除該路徑兩端點以外的其他任務(wù)點,在路徑規(guī)劃中不得不與之交叉,則該路徑一定不是最優(yōu)路徑里的路徑。

簡單的螞蟻之所以可解決復(fù)雜的問題,是因為大量簡單規(guī)則的涌現(xiàn),也是團體智能的體現(xiàn)。任何一種改進方式,必須遵循這些簡單的規(guī)則或是這些簡單規(guī)則的結(jié)合與派生。人工蟻群算法中的螞蟻和自然界真實的螞蟻主要區(qū)別有:1)人工螞蟻記憶能力更強,在一次循環(huán)中不會重復(fù)走過的路； 2)人工螞蟻比較“聰明”,可以思考問題,有學(xué)習能力。如果螞蟻能懂上面的結(jié)論,則在路徑選擇的過程中就能更快地找到想要的路徑[4]。

針對上面的改進規(guī)則,改進思路主要如下。

1)在Step1中初始化一個啟發(fā)因子,啟發(fā)因子代表從城市i到j(luò)的期望程度,如果從城市i到城市j滿足結(jié)論2的條件,則將這個啟發(fā)因子設(shè)為零,假設(shè)螞蟻先到達城市i,則它選擇下一個城市是j的概率就是零。

2)結(jié)合結(jié)論1和結(jié)論2,在Step3中的if判斷語句下增加如下代碼：

if(當前到達城市i的路徑不和最近走過的p條路徑相交)

抵達下一個城市i； (p≤禁忌列表中的路徑條數(shù))

else

找出相交的路徑,重置禁忌列表,使路徑不相交。

對于1)來說,對給定的一組城市數(shù)據(jù),要找到所有的滿足結(jié)論2的路徑,是個比較復(fù)雜的問題,但對一些特定的點來說,比較容易找到。改進思路是分區(qū)域地找這一類直線,顯然外圍點更容易產(chǎn)生這些直線。第1種方法,利用程序自己尋找,將外圍點分類,然后用結(jié)論2進行判斷； 第2種方法,可以通過程序人為地引導(dǎo)或設(shè)定。

對于2)實現(xiàn)相對容易,判斷線段相交的方式有多種,重置禁忌列表的過程類似于遺傳算法里的變異,而且這里的變異是向好的方向變異。假設(shè)p值代表螞蟻的思考能力,p值越大,則同一次得到的路徑趨于更優(yōu),但螞蟻思考的時間會相應(yīng)變長,這里可以根據(jù)具體的問題去調(diào)整。并且根據(jù)p值的不同,能進一步改進算法,因為變異后可能會發(fā)現(xiàn)新的滿足結(jié)論1的路徑,即變異后的路徑可能與之前的路徑相交,這時可以進行再次的變異,得到更優(yōu)的路徑。

以前面4個航路點的路徑規(guī)劃為例,假設(shè)在某次迭代過程中第m只螞蟻從A點出發(fā)到達C點后禁忌列表如圖3a所示,路徑如圖4a所示,螞蟻要選擇的下一個城市是D點,路徑用虛線表示,運用改進算法判斷,這時路徑CD與AB相交,滿足結(jié)論1的條件。下一步重置禁忌列表,重置后禁忌列表如圖3b所示,路徑如圖4b所示。重置的規(guī)則是：假設(shè)當前路徑和前面禁忌列表中的某條路徑相交,則在禁忌列表中將當前路徑的起始點和相交路徑的結(jié)束點位置互換。如上例中當前路徑為CD,相交路徑為AB,在禁忌列表中將當前路徑起始點C和相交路徑的結(jié)束點B交換位置如圖3b所示。

a 初始禁忌列表 b 修改后的禁忌列表

a 初始路徑 b 修改后的路徑

圖4是一個簡單的示意圖,描述了重置禁忌列表變化的過程,可以看到這種改進可以增加一次迭代的優(yōu)化能力,并且這種路徑的改變是一種突變,類似于遺傳算法里的基因變異,在一定程度上增強了算法跳出局部最優(yōu)解的能力。蟻群算法是基于正反饋的算法,在算法后期解空間里路徑上的信息素遠遠大于非解空間里路徑上的信息素,一旦算法陷入局部最優(yōu)解,難以再跳出來。在仿真的過程中發(fā)現(xiàn)這種改進可以在算法后期加入,這樣在減少運行時間的同時,改進算法依舊具有一定的跳出局部最優(yōu)解的能力,可以根據(jù)具體的問題去設(shè)置參數(shù)。

3 仿真測試

以chn31城市為例,設(shè)其中每個城市的坐標是無人機必經(jīng)的航路點。用Matlab7.0編程對設(shè)計的算法進行了仿真測試并和基本蟻群算法做了比較。仿真硬件環(huán)境：CPU為Inter Core2 Duo 1.83 GHz,內(nèi)存為2 GByte。仿真參數(shù)選取如表2所示,仿真結(jié)果如圖5所示。

表2 蟻群算法參數(shù)

a 改進蟻群算法計算結(jié)果 b 基本蟻群算法計算結(jié)果

圖5a是改進后的算法航跡規(guī)劃結(jié)果圖,圖5b是基本蟻群算法的航跡規(guī)劃結(jié)果圖。圖5中的左邊黑色圈圈代表航路點,黑色實線是規(guī)劃的航路； 右邊黑色實線表示每次循環(huán)的平均值,黑色虛線表示每次循環(huán)的最優(yōu)值。結(jié)果表明,蟻群算法可以運用于航跡規(guī)劃和航跡尋優(yōu)。仿真分析中已知的chn31最優(yōu)解是15 377,迭代到200次時基本蟻群算法最優(yōu)解是15 602,改進的算法是15 599,這已經(jīng)接近最優(yōu)解。實際上在迭代超過200次后結(jié)果已經(jīng)很接近最優(yōu)解了,后面曲線也比較平滑。所以,取前100次迭代的圖像進行了對比。由圖5可看出,改進后的算法在前期收斂速度比基本算法快,并且整體平均值較好,與前面分析的結(jié)果一致。

為進一步證實去交叉策略的有效性,筆者用幾組不同城市坐標作為航路點進行仿真分析,測試結(jié)果如表3所示。

表3 不同城市坐標測試結(jié)果

通過表3可發(fā)現(xiàn)在有限的迭代次數(shù)中,改進后的算法可較早地搜尋到更優(yōu)的解。

4 結(jié) 語

筆者對蟻群算法在無人機航跡規(guī)劃中的應(yīng)用進行了研究,針對蟻群算法在收斂后期易陷入局部最優(yōu)的缺點,通過引入去交叉禁忌搜索策略來改進算法以提高無人機的航跡規(guī)劃效果。對引入去交叉策略的蟻群算法做了仿真分析,通過仿真測試,證明了該改進增強了算法的全局優(yōu)化能力,并能在航跡規(guī)劃中運用和實現(xiàn)。通過建模和仿真測試,證明了蟻群算法應(yīng)用于航跡規(guī)劃是可行的。

參考文獻：

[1] 胡中華,趙敏.無人飛行器在線航跡規(guī)劃技術(shù)研究[J].航天電子對抗,2010,26(4):11-15.

HU Zhong-hua,ZHAO Min.Research of Real Time Route Planning for UAV[J].Aerospace Electronic Warfare,2010,26(4):11-15.

[2]左洪浩.蟻群優(yōu)化算法及其應(yīng)用研究[D].合肥：中國科學(xué)技術(shù)大學(xué)合肥智能機械研究所,2006.

ZUO Hong-hao.Research on the Ant Colony Optimization Algorithm and Its Applications[D].Hefei：Institute of Intelligent Machines,University of Science and Technology of China,2006.

[3]段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,2005.

DUAN Hai-bin.Ant Colony Algorithm Theory and Applications[M].Beijing:Science Press,2005.

[4]何艷萍,張安,劉海燕.基于Voronoi圖與蟻群算法的UCAV航路規(guī)劃[J].電光與控制,2009,16(11):22-24.

HE Yan-ping,ZHANG An,LIU Hai-yan.Path Planning for UCAV Based on Voronoi Diagram and Ant Colony Optimization[J].Electronics Optics &Control,2009,16(11):22-24.

[5]吳慶洪,張紀會,徐心和.具有變異特性的蟻群算法[J].計算機研究與發(fā)展,1999,36(10):1240-1245.

WU Qing-hong,ZHANG Ji-hui,XU Xin-he.An Ant Colony Algorithm with Mutation Features[J].Journal of Computer Research and Development,1999,36(10):1240-1245.

[6]孫勇,李妮,龔光紅,等.基于知識庫的動態(tài)蟻群算法[J].北京工業(yè)大學(xué)學(xué)報,2012,38(3):374-379.

SUN Yong,LI Ni,GONG Guang-hong,et al.Dynamic Ant Colony Algorithm Based on Knowledge Base[J].Journal of Beijing University of Technology,2012,38(3):374-379.

[7]胡中華,趙敏,劉世豪,等.基于自適應(yīng)蟻群算法的無人飛行器航跡規(guī)劃[J].計算機集成制造系統(tǒng),2012,18(3):560-565.

HU Zhong-hua,ZHAO Min,LIU Shi-hao,et al.Unmanned Aerial Vehicle Flight Path Planning Based on Adaptive Ant Colony Optimization Algorithm[J].Computer Integrated Manufacturing Systems,2012,18(3):560-565.

[8]DORIGO M,MANIEZZO V,COLORNI A.Positive Feedback as a Search Strategy[R].Milan,Italy:[s.n.],1991.

[9]王佳文,李麗,易偉,等.3D NoC映射問題的動態(tài)蟻群算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2011,23(9):1614-1621.

WANG Jia-wen,LI Li,YI Wei,et al.A Dynamic Ant Colony Optimization Algorithm for 3D NoC Mapping[J].Journal of Computer-Aided Design &Computer Graphics,2011,23(9):1614-1621.

[10]何麗莉,王克淼,白洪濤,等.基于CMP的多種并行蟻群算法及比較[J].吉林大學(xué)學(xué)報:理學(xué)版,2010,48(5):787-792.

HE Li-li,WANG Ke-miao,BAI Hong-tao,et al.Multi Parallel Ant Colony Optimization Algorithms Based on CMP and their Comparison[J].Journal of Jilin University:Science Edition,2010,48(5):787-792.

[11]倪世宏,秦軍立,蘇晨.一種求解連續(xù)空間優(yōu)化問題的動態(tài)蟻群算法[J].電光與控制,2009,16(12):12-15.

NI Shi-hong,QIN Jun-li,SU Chen.Dynamic Ant Colony Algorithm Used in Continuous Space Optimization[J].Electronics Optics &Control,2009,16(12):12-15.

[12]葉文,廉華耕,漆云海,等.無人機航路規(guī)劃算法研究[J].電光與控制,2011,18(2):8-17.

YE Wen,LIAN Hua-geng,QI Yun-hai,et al.Path Planning Algorithm for UAV[J].Electronics Optics &Control,2011,18(2):8-17.

[13]DORIGO M.Optimization,Learning,and Natural Algorithms[D].Milan,Italy:Dipartimento di Elettronica,Politecnico di Milano,1992.

[14]DORIGO M,DI CARO G,GAMBARDELLA L M.Ant Algorithms for Distributed Discrete Optimization[J].Artificial Life,1999(5):137-172.

[15]BULLNHEIMER B,HARTL R F,STRAUSS C.A New Rank Based Version of the Ant System-Acomputational Study[J].Central Europen J Oper Rea Econom,1999(7):25-38.