基于蚁群优化算法的水下航路规划

张　毅, 高永琪, 牛兴江



基于蚁群优化算法的水下航路规划

张毅, 高永琪, 牛兴江

(海军工程大学 兵器工程系, 湖北 武汉, 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-), 男, 在读硕士, 主要研究方向为兵器制导与控制技术.

(责任编辑: 杨力军)