潜艇在水深底质数据下的航线规划

李宏彪，张永亮

（华北计算技术研究所北京100083）

潜艇的航线规划是指在已有地形数据的基础之上，根据潜艇的潜水深度范围以及可作战需求，进行三维空间分析规划出一条合理且路程较近的航线。多数情况下，是基于Dem数据进行分析规划的，但往往某些海域并无详细可靠的Dem数据，而只有比较粗糙的水深底质或等深线数据，所以本文结合参考文献5的分治算法构造不规则三角网的方法，设计了一种通过水深底质或等深线数据快速计算Dem数据用来作为三维空间分析规划的基础。此方法效率较高，完全达到了实时航线规划的要求。

如此密集的网格利用地杰斯特拉算法进行航线规划复杂度太高，而A星虽然效率高，但在栅格数据下会走太多的弯路，所以目前解决这类航线规划的方法主要是智能优化算法，例如蚁群算法、遗传算法等方法在全局范围内搜索较优航线，但大多数方法效率还是达不到实时航线规划的效果。本文设计了一种A星加模拟退火算法的方式来进行分析规划航线，这样A星的作用是保证效率，模拟退火的作用是保跳出局部最优在全局范围内搜索，将二者优势相互结合，通过实验得到了比较理想的效果[1-11]。

1 基于不规则三角网的Dem插值

首先根据水深底质离散点构造三角网（图1），然后遍历三角网中的每一个三角形对三角形内Dem值未知的网格点根据公式（1）进行插值（图2），由于潜艇本身具有一定的宽度和长度，所以在通过Dem栅格块时要保证其直行或转弯时可以通过，为此我们选取的网格宽度为大于等于潜艇长度的两倍。在三角形ABC中O为待插值网格点其坐标为（x，y），三角形 ABC 的三点坐标分别为，高程值分别为

图1 构造三角网

图2 三角形内网格点的插值

设O到A的距离为LOA，O到B的距离为LOB，O到C的距离为LOC。根据距离对点O的Dem值DEMO成反比的假设，可得对O点的Dem插值公式为：

算法步骤[5]：

1）根据所需要的Dem密度构建网格。

2）根据高程离散点利用分治算法构造Delaunay三角网。

3）遍历三角网中的每一个三角形，对内Dem值未知的网格点，根据公式（1）进行插值计算。

2 构造Delaunay三角网的具体步骤

2.1 局部最优化处理

理论上为了构造Delaunay三角网，Lawson提出的局部优化过程LOP（Local Optimization Procedure），一般三角网经过LOP处理，即可确保成为Delaunay三角网，其基本做法如下所示[7]：

1）将两个具有共同边的三角形合成一个多边形。

2）以最大空圆准则作检查，看其第4个顶点是否在三角形的外接圆之内。

3）如果在，修正对角线即将对角线对调，即完成局部优化过程的处理。

LOP处理过程如图3所示。

2.2 Delaunay三角网的构造算法大体步骤

1）构造一个超级三角形，包含所有散点，放入三角形链表。

图3 LOP处理过程

2）将点集中的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。

3）根据优化准则对局部新形成的三角形进行优化。将形成的三角形放入Delaunay三角形链表。

4）循环执行上述第2）步，直到所有散点插入完毕[7]。

这一算法的关键的第2）步如图4所示。

图4 第2）步的操作过程示意图

为提高效率本文在构造三角网时采用的是参考文献[5]的分治算法，实验证明效率可大大提高[5]。

3 利用A星算法求出起点到终点的一条合理路径

在潜艇的潜水深度确定的情况下，一条合理路径就是找到一条可以由起点到末点的路径保证潜艇由此路径通过时不会触礁且此路径规避敌方打击区域。

在已通过插值计算出的Dem数据中，可以很快计算出哪些Dem栅格可以通过，哪些不可通过，即潜艇的可行区域。在此可行区域上可以利用A星算法求出一条合理路径。A星算法的基本思想与具体步骤如下。

每当主角走一步，就在身边的8个方向插上节点编辑，然后使用探路器，探路器会告诉主角，插的哪个节点标记距离目标的路径比较短，然后下一步就走向那里，走到之后，准备又插，发现，有的地方已经插过了，或者旁边有障碍物，不能插，就替换插过的节点的父节点，比较，是不是比当前的短，如果是，就让当前的父节点等于，被替换的父节点。

从A星算法的基本思想可以看到A星算法结果唯一，这样其实它就是一个带有方向指导的广度寻路算法，所以其不具备随机性，所以它只可能绕开障碍物，找到一个较优的代价路线，对于智能地放弃当前最优进而寻找另一条更加优越的代价路线做不到，通俗地说它只顾当下而不考虑全局。尤其在此种密集的网格数据中A星算法的弊端更是明显，当遇到障碍物时它在不断地试探靠近目标时走了太多的弯路，所以A星算法只可以找到一条合理绕开障碍物的较优的代价路线，但所以为实现在全局范围内搜索一条较优的代价路线必须引入带有随即性质可以跳出局部最优的优化算法。下一小节设将计一种A星+模拟退火算法寻找一条实用的规划路径。

4 A星+模拟退火算法寻找较优路径

算法设计主要思想：由于A星算法的弊端，必须引入一种优化算法从全局搜索的角度出发，来解决其走太多的弯路的问题。其主要思路就是以A星算法规划出的路径为基础，设定一种地理环境的随机改变与原始路径的随机取舍再利用A星算法求出一条合理的路径，将此路径与原路径进行代价比较，利用模拟退火的思想进行取舍，经过模拟退火的充分降温，最后得到一条合理并且行程较短的实用路径，这里目标函数就是全路径的路程长度。

5 试验结果与分析

试验平台是Microsoft Windows XP操作系统，机器配置为主频2.93 GHz，内存为2.93 GB，采用VC++6.0实现，实验数据为某海域水深底质数据，潜水深度为865米到700米。

构造三角网效果如图5所示。

利用A星算法求出起点到终点的一条合理路径效果如下：

A星+模拟退火算法寻找较优路径效果如图6所示。

实验各步骤性能（耗时）：

构造三角网，耗时578 ms。

图5 构造三角网

图6 A星+模拟退火算法寻找较优路径

Dem插值，耗时556 ms。

寻找较优路径效，843 ms。

共计1 977 ms，而原始的方法耗时6 788 ms，性能提高了70%。

实验结果表明：

1）基于水深底质可以快速地生成Dem数据，根据潜艇的潜水深度可以快速计算出其可行区域，在此基础上可以利用A星算法计算复杂度低的特性快速计算出一条合理的路线；

2）在栅格数据下A星算法计算出合理的路线弯路太多，在实际中无法作为一条潜艇的航行路线；

3）A星算法计算出合理的路线为基础结合模拟退火算法的全局搜索，可以去除A星算法走太多的弯路的弊端；

4）实验结果表明A星算法的高效率加上模拟退火算法的全局搜索，可以快速地规划处一条合理且较优的水下航行路线。

6 结论

在潜艇在水下的航线规划中，A星算法虽然具有效率高的优势，但存在着规划路径复杂的缺陷，地杰斯特拉算法虽然具有规划出最优的路线但存在着算法复杂度高的缺陷。文中将水深底质数据通过三角网Dem插值后，基于插值计算出的Dem数据，将A星算法与模拟退火算法综合应用，这样可以既利用了A星算法效率高的优势，而且可以通过模拟退火算法进行优化使得A星算法规划出的路径复杂的问题解决，达到快速规划出潜艇在水下的合理并且实用航线。实验表明，该方法在耗时时间与航线的合理程度上有比较实用的优势。但同时，在实际应用中可以通过设置规避区域（敌方打击区域、敌方可探测区域或山谷狭窄区域等）来得到不同的航线规划，指挥员可以选择符合作战要求的航线。由于本文算法具有效率较高的优势，所以可以根据战时突发情况实时规划航线来及时更新当下更符合要求的航线。另外，本文给出的是一条航线，在实际应用中如果将该航线周围一定范围的可通过的栅格块也纳入其中，从而形成一个通路区域，效果会更加理想，有助于判断该航线是否符合作战要求。

[1]胡鹏，黄杏元，华一新.地理信息系统教程[M].武汉：武汉大学出版社，2002.

[2]张宏，温永宁，刘爱利，等.地理信息系统算法基础[M].北京:科学出版社，2006.

[3]马少平，朱小燕.人工智能[M].北京:清华大学出版社，2004.

[4]张永亮，朱美正，李欣.模拟退火粒子群算法在矢量数据压缩中的应用[J].计算机工程与软件，2005，37（9）:1303-1306.

[5]张永亮，朱美正，李欣，等.基于稠密与稀疏高程点的Dem插值[J].计算机工程与应用，2014，50（1）:167-174.

[6]史娟.基于地形分析的路径搜索算法研究[D].武汉：华中科技大学，2005.

[7]武百超，吴捷，崔继宪.一种三角网的快速生成算法[J].矿山测量，2010（1）：41-43.

[8]顾春雷，杨漾，朱志春.几种建立DEM模型插值方法精度的交叉验证[J].测绘与空间地理信息，2011（5）：99-102.

[9]应申，李霖，王明常，等.计算几何在地图综合中的应用[J].测绘科学，2005（3）:64-66.

[10]Cormen T H，Leiserson C E，Ronald L，等.算法导论[M].潘金贵，顾铁成，李成法，等译.2版.北京：机械工业出版社，2011.

[11]齐英剑，池娟，张彬.基于Zernike矩亚像素边缘检测的改进算法[J].西安邮电学院学报，2010，15（5）：75-78.

[12]陈荣华，韩旭里，吴宗敏.某型拟插值的多项式再生性[J].计算机工程与应用，2010，46（1）：1-3.

[13]宋俊辉，冯岩.负载均衡的分布式系统任务调度优化算法[J].吉林大学学报（理学版），2017（2）:383-387.

[14]丁西明，段汉根，范益政.四叉树分解的图像插值[J].计算机工程与应用，2011，47（20）：191-193.

[15]马力，王大翊，汪永生.基于SOA的Web服务应用构建关键技术研究[J].物联网技术，2014（8）:76-79.

[16]鲍蕊娜，李向新，麻明，等.基于凸壳技术的Delaunay三角网生成算法研究[J].科学技术与工程，2011（4）:764-767.