基于蟻群優(yōu)化算法的水下航路規(guī)劃

張　毅, 高永琪, 牛興江

?

基于蟻群優(yōu)化算法的水下航路規(guī)劃

張毅, 高永琪, 牛興江

(海軍工程大學(xué) 兵器工程系, 湖北 武漢, 430033)

為了確保水下地形匹配輔助導(dǎo)航系統(tǒng)在規(guī)劃航路上獲得充足的地形信息, 從而獲得良好的匹配效果, 運(yùn)用蟻群優(yōu)化算法設(shè)計了航路優(yōu)化搜索方法, 研究了基于水下地形匹配輔助導(dǎo)航的潛航器航路規(guī)劃問題。定義了可行域的概念, 并詳細(xì)討論了算法中信息素的表示方法、啟發(fā)式函數(shù)的設(shè)計以及信息素的更新規(guī)則, 運(yùn)用算法得到了基于豐富地形信息的最優(yōu)航路。最后在真實(shí)地形數(shù)據(jù)的基礎(chǔ)上運(yùn)用質(zhì)點(diǎn)濾波(PMF)算法進(jìn)行了地形匹配仿真研究, 仿真結(jié)果表明, 運(yùn)用算法所規(guī)劃的航路能夠在水下地形匹配輔助導(dǎo)航中獲得優(yōu)良的地形匹配效果。

水下地形輔助導(dǎo)航; 蟻群算法; 航路規(guī)劃; 質(zhì)點(diǎn)濾波

0 引言

地形輔助導(dǎo)航(terrain aided navigation, TAN)是一種利用地形特征對飛行器或水下航行器進(jìn)行導(dǎo)航定位的技術(shù)。水下地形輔助導(dǎo)航的基本工作原理是, 讓水下航行器經(jīng)過具有某種特定地形特征的區(qū)域, 并將該區(qū)域及其周圍的地形數(shù)據(jù)(基準(zhǔn)圖)預(yù)先存入水下航行器的計算機(jī)中[1], 水下航行器航行時借助傳感器實(shí)時測量其航路下方的地形數(shù)據(jù)(實(shí)時圖), 然后根據(jù)匹配算法, 獲得水下航行器的當(dāng)前位置。因此合理規(guī)劃航路確保航行器途經(jīng)區(qū)域具有充足的地形信息量, 是提高地形匹配精度重要而有效的途經(jīng)。航路規(guī)劃需綜合考慮地形可導(dǎo)航信息、導(dǎo)航精度、數(shù)字地圖誤差和可能威脅等諸多因素。匹配區(qū)可導(dǎo)航性通常是利用其特征分布參數(shù)來分析判斷的, 其基本依據(jù)是幅值平坦區(qū)域的誤匹配概率比大起伏區(qū)域的誤匹配概率要大。文獻(xiàn)[2]選取了針對地形輔助導(dǎo)航的幾個地形分析度量指標(biāo), 有地形標(biāo)準(zhǔn)差、粗糙度等。文獻(xiàn)[3]以地形熵作為地形信息量引入到水下航行器的航路規(guī)劃中, 并運(yùn)用粒子群優(yōu)化算法, 得到水下地形輔助導(dǎo)航的最優(yōu)航路。本文使用地形標(biāo)準(zhǔn)差和經(jīng)、緯度方向上的絕對粗糙度的組合來定義某塊地形區(qū)域的導(dǎo)航系數(shù), 并運(yùn)用蟻群算法中的最大最小蟻群系統(tǒng)(max-min ant system, MMAS)算法[4-6]為基本優(yōu)化搜索算法, 研究了基于水下地形輔助導(dǎo)航的水下航行器航路規(guī)劃問題, 設(shè)計了水下地形環(huán)境模型和航路規(guī)劃搜索算法。仿真結(jié)果證明了該算法的正確性和有效性。

1 水下環(huán)境模型

水下地形輔助導(dǎo)航具有缺乏基準(zhǔn)數(shù)據(jù)(電子海圖精度較低), 水下航行器航行速度慢, 機(jī)動運(yùn)行實(shí)時測量誤差較大, 航行環(huán)境復(fù)雜等諸多特殊性[7]?；谝陨显? 當(dāng)水下航行器以等深航行時基于地形信息的匹配效果最好。本文主要討論怎樣規(guī)劃基于地形信息的最優(yōu)航路, 從而在地形輔助導(dǎo)航中獲得較好的匹配效果, 與航行深度無直接關(guān)系, 因此本文把水下航行器的水下3D航路規(guī)劃簡化為一個2D的航路規(guī)劃問題。

用于地形匹配輔助導(dǎo)航的海底地形數(shù)據(jù)一般采用以格網(wǎng)矩陣方式存儲的數(shù)字高程模型(digital elevation model, DEM), 以等分網(wǎng)格的方法對地形平面進(jìn)行劃分[8-9]。圖1(a)為本文仿真所用海區(qū)真實(shí)數(shù)字海圖某一視角的3D視圖, 圖1(b)為該地圖的等深線圖。

圖1 某海區(qū)海底數(shù)字地圖

使用雙線性多項式插值[10]的方法對地圖進(jìn)行處理, 得到精度為20 m數(shù)字海圖。以地圖的最左下角為坐標(biāo)原點(diǎn), 以緯度方向?yàn)檩S(東為正方向), 以經(jīng)度方向?yàn)檩S(北為正方向), 并分別用平行于、軸的直線等分地圖為20 m×20 m的離散點(diǎn)集。

2 航路規(guī)劃算法

2.1 可行域選取

通過對數(shù)字海圖進(jìn)行直角網(wǎng)格劃分, 由當(dāng)前點(diǎn)搜尋下一個相鄰點(diǎn), 直到搜尋到規(guī)劃航路終點(diǎn), 便形成連接起始點(diǎn)和終點(diǎn)的規(guī)劃航路。圖2為航跡點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。這個網(wǎng)格圖算法的數(shù)據(jù)結(jié)構(gòu)是以當(dāng)前點(diǎn)為中心的九宮圖, 共有8個相鄰點(diǎn), 下一個點(diǎn)必須從以為中心構(gòu)成的8個點(diǎn)中選擇, 其中網(wǎng)格大小1需根據(jù)實(shí)際問題規(guī)模及數(shù)字海圖的分辨率進(jìn)行合理設(shè)置。文設(shè)置網(wǎng)格大小1為數(shù)字海圖的分辨率, 水下航行器的旋回半徑為。

2.2 信息素表示方法

蟻群算法最開始用來解決旅行商問題(trave- ling salesman problem, TSP), 在離散域蟻群算法中, 信息素通常被殘留在2個節(jié)點(diǎn)連線上, 表示螞蟻經(jīng)過該條路徑的期望度[4-5]。由于本文中的2D空間航路規(guī)劃問題的環(huán)境模型是采用離散點(diǎn)集的方式來表示的, 這些離散點(diǎn)即對應(yīng)TSP中的城市節(jié)點(diǎn)。若將各個離散點(diǎn)間的連線作為信息素的存儲載體, 算法的空間復(fù)雜度將是無法承受的。因此, 本文中將信息素存儲在環(huán)境模型的離散點(diǎn)上, 每個點(diǎn)上信息素的大小代表該離散點(diǎn)對螞蟻的吸引程度。這種表示方法大大降低了算法的空間復(fù)雜度。

2.3 航路節(jié)點(diǎn)的選擇

2.4 啟發(fā)式函數(shù)設(shè)計

2.5 信息素更新

信息素的更新分為局部更新和全局更新。局部更新的目的是為了讓螞蟻能夠?qū)ふ腋鞣N不同的解, 從而有效避免螞蟻過早的收斂到同一路徑。局部更新在螞蟻移動過程中進(jìn)行, 當(dāng)螞蟻移動到節(jié)點(diǎn)的時候, 點(diǎn)的信息素便根據(jù)式(6)進(jìn)行更新

當(dāng)所有螞蟻完成一次航路的構(gòu)建以后, 再進(jìn)行信息素的全局更新。根據(jù)航路最短的原則, 每完成一次迭代后, 按式(7)對當(dāng)前最好航路進(jìn)行信息素的更新

2.6 算法實(shí)現(xiàn)步驟

本文蟻群優(yōu)化算法針對水下航行器水下地形輔助導(dǎo)航最優(yōu)航路規(guī)劃的運(yùn)算步驟如下。

1) 對數(shù)字海圖進(jìn)行處理, 按式(5)計算所用海圖區(qū)域的導(dǎo)航系數(shù)值; 初始化算法參數(shù)和環(huán)境信息, 信息素矩陣賦初值; 確定航路規(guī)劃的起點(diǎn)和終點(diǎn); 將所有螞蟻置于起點(diǎn)位置。

2) 確定各螞蟻的下一航路節(jié)點(diǎn)的可行域, 按式(3)計算可行域內(nèi)各點(diǎn)的啟發(fā)式函數(shù)值, 并根據(jù)啟發(fā)式函數(shù)值和信息素值, 按式(2)和式(3)確定螞蟻下一航路節(jié)點(diǎn)。

3) 螞蟻移動至下一航路節(jié)點(diǎn), 并按式(6)進(jìn)行局部信息素的更新。

5) 按式(7)進(jìn)行全局信息素更新, 并判斷算法是否滿足停止條件(算法已經(jīng)收斂或達(dá)到迭代次數(shù)), 若滿足則輸出最優(yōu)結(jié)果, 否則, 轉(zhuǎn)到步驟2)再次迭代, 直到滿足算法結(jié)束條件。

3 仿真驗(yàn)證

為驗(yàn)證所提出的蟻群優(yōu)化算法的有效性, 利用Matlab 7.0對該算法進(jìn)行仿真試驗(yàn)。仿真試驗(yàn)在圖1所示真實(shí)數(shù)字海圖基礎(chǔ)上進(jìn)行。根據(jù)雙線性插值方法使地圖分辨率為20 m, 即使用20 m× 20 m的格網(wǎng)模型。設(shè)置航路規(guī)劃的起點(diǎn)坐標(biāo)為 (1 000, 4 600), 終點(diǎn)坐標(biāo)為(7 800, 3 800)。經(jīng)過多次仿真計算, 算法中的基本參數(shù)取如下初始值時, 能夠獲得良好的仿真結(jié)果:=1.0,1=3=1.0,2=2.0,=0.05, 螞蟻數(shù)量=20, 迭代次數(shù)=100。

圖3 不考慮威脅等條件的規(guī)劃航路

圖4 考慮威脅等條件的規(guī)劃航路

3) 為了驗(yàn)證本文方法所規(guī)劃航路的可行性, 以1) 所規(guī)劃的航路作為水下航行器真實(shí)航跡, 編寫基于質(zhì)點(diǎn)濾波(point-mass filter, PMF)算法[11-12]的水下地形匹配程序, 得到如圖3中雙畫線所示的地形匹配航跡, 匹配誤差如圖5所示。當(dāng)水下航行器不進(jìn)行航路規(guī)劃時, 即以由起點(diǎn)到終點(diǎn)的直線為真實(shí)航跡進(jìn)行基于PMF算法的匹配仿真, 匹配誤差如圖6所示。從匹配結(jié)果可以看出, 該算法所獲得的最優(yōu)航路在進(jìn)行地形匹配輔助導(dǎo)航時具有很好的快速收斂性, 誤差很快就收斂到地圖的分辨率以內(nèi)(小于20 m)。因此本文算法所規(guī)劃的最優(yōu)航路能夠在地形匹配輔助導(dǎo)航中得到非常良好的地形匹配效果。

圖5 規(guī)劃航路的匹配誤差

圖6 直線航路的匹配誤差

4 結(jié)束語

針對水下地形輔助導(dǎo)航問題, 本文運(yùn)用蟻群優(yōu)化算法對水下航行器航路規(guī)劃問題進(jìn)行了研究, 詳細(xì)闡述了航路優(yōu)化搜索算法, 給出了算法的具體流程, 并在真實(shí)數(shù)字海圖的基礎(chǔ)上, 運(yùn)用PMF算法對規(guī)劃的最優(yōu)航路進(jìn)行了仿真驗(yàn)證。仿真結(jié)果表明, 利用所設(shè)計算法規(guī)劃出的最優(yōu)航路能夠在水下地形匹配導(dǎo)航中獲得優(yōu)良的地形匹配效果。

[1] 張紅梅, 趙建虎, 楊鯤, 等. 水下導(dǎo)航定位技術(shù)[M]. 武漢: 武漢大學(xué)出版社, 2010: 73-74.

[2] 鄭彤, 蔡龍飛, 王志剛, 等. 地形匹配輔助導(dǎo)航中匹配區(qū)域的選擇[J]. 中國慣性技術(shù)學(xué)報, 2009, 17(2): 191-196.Zheng Tong, Cai Long-fei, Wang Zhi-gang, et al. Selection of Matching Area in Terrain Match Aided Navigation[J]. Journal of China Inertial Technology, 2009, 17(2): 191-196.

[3] 諶劍, 李恒, 張靜遠(yuǎn). 水下地形輔助導(dǎo)航最優(yōu)航路規(guī)劃[J].魚雷技術(shù), 2012, 20(4): 276-380.Shen Jian, Li Heng, Zhang Jing-yuan. Optimal Path Planning Method for Underwater Terrain-aided Navigation[J]. Torpedo Technology, 2012, 20(4): 276-380.

[4] Dorigo M, Thomas S. Ant Colony Optimization[M]. Brussels: MIT, 2004: 33-45.

[5] 馬良, 朱剛, 寧愛兵. 蟻群優(yōu)化算法[M]. 北京: 科學(xué)出版社, 2008: 15-47, 188-201.

[6] Dorigo M, Gambardella L M. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Transactions on Evolutionary Computation (S1089- 778X), 1997, 1(1): 53-66.

[7] 林沂, 晏磊, 童慶禧. 針對水下輔助導(dǎo)航相關(guān)匹配算法的特征區(qū)最優(yōu)航跡規(guī)劃[J]. 吉林大學(xué)學(xué)報(工學(xué)版), 2008, 38(2): 439-443. Lin Yi, Yan Lei, Tong Qing-xi. Optimum Trajectory Plan- ning in Characteristic Areas for Underwater Aided Navigation Correlation Matching Algorithms[J]. Journal of Jilin University(Engineering and Technology Edition), 2008, 38(2): 439-443.

[8] 周啟鳴, 劉學(xué)軍. 數(shù)字地形分析[M]. 北京: 科學(xué)出版社, 2006: 2-4.

[9] 高曼, 劉以安, 張強(qiáng). 優(yōu)化蟻群算法在反艦導(dǎo)彈航路規(guī)劃中的應(yīng)用[J]. 計算機(jī)應(yīng)用, 2012, 32(9): 2530-2533.Gao Man, Liu Yi-an, Zhang Qiang. Application of Improved Ant Colony Algorithm to Route Planning of Anti-ship Miss- ile[J]. Journal of Computer Applications, 2012, 32(9): 2530- 2533.

[10] 李志林, 朱慶. 數(shù)字高程模型[M]. 武漢: 武漢大學(xué)出版社, 2001: 33-36.

[11] Anonsen K, Hallingstad O. Terrain Aided Underwater Navigation Using Point Mass and Particle Filters[J]. Position, Location, And Navigation Symposium, 2006 IEEE/ION.

[12] 劉洪. 基于PMF算法的水下地形匹配技術(shù)研究[D]. 武漢: 海軍工程大學(xué), 2012.

Underwater Route Planning Based on Ant Colony Optimization Algorithm

ZHANG Yi , GAO Yong-qi, NIU Xing-jiang

(Department of Weaponry Engineering, Navy University of Engineering, Wuhan 430033, China)

To ensure the underwater terrain-aided navigation system can obtain sufficient terrain information on planned route, a route planning method is designed with the ant colony algorithm, and the underwater route planning for terrain-aided navigation is studied. The concept of feasible region is defined, and the pheromone representation, heuristic functions and pheromone updating rules are discussed in detail. Simulation with point-mass filter(PMF) is conducted, and the results show that the proposed route planning method can achieve good match in underwater terrain-aided navigation.

underwater terrain-aided navigation; ant colony algorithm; route planning; point-mass filter

TJ630.33

A

1673-1948(2013)04-0272-05

2013-03-29;

2013-06-14.

張 毅(1989-), 男, 在讀碩士, 主要研究方向?yàn)楸髦茖?dǎo)與控制技術(shù).

(責(zé)任編輯: 楊力軍)