基于蟻群優化算法的水下航路規劃

張　毅, 高永琪, 牛興江

?

基于蟻群優化算法的水下航路規劃

張毅, 高永琪, 牛興江

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

為了確保水下地形匹配輔助導航系統在規劃航路上獲得充足的地形信息, 從而獲得良好的匹配效果, 運用蟻群優化算法設計了航路優化搜索方法, 研究了基于水下地形匹配輔助導航的潛航器航路規劃問題。定義了可行域的概念, 并詳細討論了算法中信息素的表示方法、啟發式函數的設計以及信息素的更新規則, 運用算法得到了基于豐富地形信息的最優航路。最后在真實地形數據的基礎上運用質點濾波(PMF)算法進行了地形匹配仿真研究, 仿真結果表明, 運用算法所規劃的航路能夠在水下地形匹配輔助導航中獲得優良的地形匹配效果。

水下地形輔助導航; 蟻群算法; 航路規劃; 質點濾波

0 引言

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

1 水下環境模型

水下地形輔助導航具有缺乏基準數據(電子海圖精度較低), 水下航行器航行速度慢, 機動運行實時測量誤差較大, 航行環境復雜等諸多特殊性[7]。基于以上原因, 當水下航行器以等深航行時基于地形信息的匹配效果最好。本文主要討論怎樣規劃基于地形信息的最優航路, 從而在地形輔助導航中獲得較好的匹配效果, 與航行深度無直接關系, 因此本文把水下航行器的水下3D航路規劃簡化為一個2D的航路規劃問題。

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

圖1 某海區海底數字地圖

使用雙線性多項式插值[10]的方法對地圖進行處理, 得到精度為20 m數字海圖。以地圖的最左下角為坐標原點, 以緯度方向為軸(東為正方向), 以經度方向為軸(北為正方向), 并分別用平行于、軸的直線等分地圖為20 m×20 m的離散點集。

2 航路規劃算法

2.1 可行域選取

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

2.2 信息素表示方法

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

2.3 航路節點的選擇

2.4 啟發式函數設計

2.5 信息素更新

信息素的更新分為局部更新和全局更新。局部更新的目的是為了讓螞蟻能夠尋找各種不同的解, 從而有效避免螞蟻過早的收斂到同一路徑。局部更新在螞蟻移動過程中進行, 當螞蟻移動到節點的時候, 點的信息素便根據式(6)進行更新

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

2.6 算法實現步驟

本文蟻群優化算法針對水下航行器水下地形輔助導航最優航路規劃的運算步驟如下。

1) 對數字海圖進行處理, 按式(5)計算所用海圖區域的導航系數值; 初始化算法參數和環境信息, 信息素矩陣賦初值; 確定航路規劃的起點和終點; 將所有螞蟻置于起點位置。

2) 確定各螞蟻的下一航路節點的可行域, 按式(3)計算可行域內各點的啟發式函數值, 并根據啟發式函數值和信息素值, 按式(2)和式(3)確定螞蟻下一航路節點。

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

5) 按式(7)進行全局信息素更新, 并判斷算法是否滿足停止條件(算法已經收斂或達到迭代次數), 若滿足則輸出最優結果, 否則, 轉到步驟2)再次迭代, 直到滿足算法結束條件。

3 仿真驗證

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

圖3 不考慮威脅等條件的規劃航路

圖4 考慮威脅等條件的規劃航路

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

圖5 規劃航路的匹配誤差

圖6 直線航路的匹配誤差

4 結束語

針對水下地形輔助導航問題, 本文運用蟻群優化算法對水下航行器航路規劃問題進行了研究, 詳細闡述了航路優化搜索算法, 給出了算法的具體流程, 并在真實數字海圖的基礎上, 運用PMF算法對規劃的最優航路進行了仿真驗證。仿真結果表明, 利用所設計算法規劃出的最優航路能夠在水下地形匹配導航中獲得優良的地形匹配效果。

[1] 張紅梅, 趙建虎, 楊鯤, 等. 水下導航定位技術[M]. 武漢: 武漢大學出版社, 2010: 73-74.

[2] 鄭彤, 蔡龍飛, 王志剛, 等. 地形匹配輔助導航中匹配區域的選擇[J]. 中國慣性技術學報, 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] 諶劍, 李恒, 張靜遠. 水下地形輔助導航最優航路規劃[J].魚雷技術, 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] 馬良, 朱剛, 寧愛兵. 蟻群優化算法[M]. 北京: 科學出版社, 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] 林沂, 晏磊, 童慶禧. 針對水下輔助導航相關匹配算法的特征區最優航跡規劃[J]. 吉林大學學報(工學版), 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] 周啟鳴, 劉學軍. 數字地形分析[M]. 北京: 科學出版社, 2006: 2-4.

[9] 高曼, 劉以安, 張強. 優化蟻群算法在反艦導彈航路規劃中的應用[J]. 計算機應用, 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] 李志林, 朱慶. 數字高程模型[M]. 武漢: 武漢大學出版社, 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算法的水下地形匹配技術研究[D]. 武漢: 海軍工程大學, 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-), 男, 在讀碩士, 主要研究方向為兵器制導與控制技術.

(責任編輯: 楊力軍)