基于电子海图的AUV多约束航路规划方法

赵玉新， 金 娜， 刘 厂

(1.哈尔滨工程大学 自动化学院， 哈尔滨 150000；2.空间物理重点实验室，北京 100076)

ZHAO Yuxin1, JIN Na2, LIU Chang1

基于电子海图的AUV多约束航路规划方法

赵玉新1， 金 娜2， 刘 厂1

(1.哈尔滨工程大学 自动化学院， 哈尔滨 150000；2.空间物理重点实验室，北京 100076)

电子海图涵盖丰富的地物信息，通过对S-57标准电子海图进行信息提取和融合，得到接近真实航行环境的三维规划空间。在此基础上，根据三维规划的需要扩展二维A*算法，并结合航路规划中常考虑的多种约束对A*规划算法进行改进。试验结果表明：基于电子海图的自主式水下航行器(Autonomous Underwater Vehicle,AUV)多约束航路规划方法能模拟出较为真实的规划空间，提出的规划算法能规划出符合多种规划约束的三维路径。

水路运输;S-57电子海图；自主式水下航行器；三维航路规划；A*算法

ZHAOYuxin1,JINNa2,LIUChang1

Abstract: The way to abstract geometric information from an S-57 electronic chart and fuse different element data is illustrated to define a 3D planning domain. The 2D A*algorithm is extended into 3D, and adapted to the constraints for path planning. The trial operation shows that the proposed method can simulate real 3D planning environment and the algorithm can produce 3D paths complying with given constraints.

Keywords: waterway transportation; S-57 electronic chart; AUV; 3D path planning; A*algorithm

随着现代航海技术不断发展，电子海图与导航应用技术的结合越来越紧密，航路规划就是其中一种很重要的结合方式。目前有很多基于电子海图的航路规划方法：栾禄雨等[1]通过提取原始海图数据，对规划环境进行栅格化处理，利用遗传算法规划航路，得到比较好的规划效果；吴博等[2]提出一种基于电子江图的路径遍历算法，该算法以分层的电子江图为基础，运用全局路径规划和局部路径规划的方法寻找到一条近似可航路径。

从算法设计的发展上看，越来越多的算法被应用到航路规划中，且都已得到很好的效果。但是，已有的规划算法大多是二维的，其规划的路径不适合航行在三维空间的水下运载器，而将其直接扩展到三维又不能保证规划效果。文献[3]提出在二维航路规划的基础上对深度进行解算，这种方法为三维航路规划提供了一种思路，但灵活性较差。

从航行空间生成方法上看，目前大部分研究都把关注点放在航路规划的算法设计上，忽略了规划空间的设计和环境信息的提取，而航行环境信息的准确度在航路规划中至关重要。[4]因此，有必要设计出一种基于海图数据的规划空间生成方法。

这里提出一种基于电子海图的全局规划方法。该方法通过对S-57标准的电子海图[5-6]进行信息提取和数据处理，形成可用于规划的三维航行空间。在此基础上，利用A*算法进行多约束的航路规划，给出一条符合航行约束的三维路径。

1 规划空间的生成

规划空间是根据规划任务确定的一个满足规划要求的最小空间，该空间不仅要在空间上包含所有可能的航路点，而且要在环境信息上尽量准确、全面地描述环境特征，从而保证规划空间的合理性和真实性。基于上述标准，给出基于电子海图的规划空间生成方法。这里提出的规划空间生成方法从电子海图中提取水深、陆地和岛屿等数据，通过插值、叠加和融合等处理，形成一个包含水深及陆地等信息的三维空间。水深插值利用自然邻点的插值方法；特征要素叠加及插值修补则通过缓冲区进行判断和赋值。特征要素叠加和插值修补的基本方法[7-8]如下。

1.1特征要素叠加

由于海洋中存在沉船、暗礁等很多障碍物，这些信息是以点、线、面要素的形式存储的，而依靠水深插值生成的网格数据只有基本的水深数据，不包含这些障碍物信息，因此需要把海图中的要素信息叠加到水深数据上。要素叠加的总体思想是制造要素点或水深点的缓冲区，判断缓冲区与水深或各要素之间的重叠关系，从而进行相应的赋值操作。下面通过线要素叠加和面要素叠加作进一步的说明。

1.1.1线要素的叠加

线要素的叠加分以下2步完成。

(1) 读取线要素中的位置点集p={p1,p2,…,pn}，对每个位置点pi构建一个水深单位网格大小的缓冲区pbuffer，通过计算缓冲区在水深网格的相对位置找到与pbuffer重合或相交的水深网格点qi；

(2) 利用pi的水深点对qi的水深值进行更新。

由于受海图信息分辨率的限制，线要素的位置点集在空间的分布不连续，因此要找到2个相邻点pi与pi+1的连线经过的所有网格，将相关网格的水深更改为该线要素的水深。

1.1.2面要素的叠加

读取面要素中的位置点集p={p1,p2,…,pn}，连接该点集的所有元素形成一个封闭图形U，对水深网格的每个网格点制造一个适当大小的缓冲区pbuffer，判断水深网格点pbuffer缓冲区与U的位置关系，表达式为

pbuffer∩U≠Θ,pi=0

(1)

式(1)中：pbuffer=(x:d(x1,pi)≤R)；R为缓冲区半径；d为两点之间的距离。

1.1.3点要素的叠加

点要素主要包括沉船、暗礁及危险区等信息，点要素的叠加主要通过读取点要素的位置信息找到水深网格的对应位置，再对水深网格的深度进行赋值。

1.2插值修补

在插值过程中，不可避免地会存在因可参考海图水深数据较少而使插值失败的现象。插值失败的区域没有其他陆地等要素的叠加，这就造成了规划信息的残缺。该问题的存在不利于路径规划，因此要对插值失败的区域进行修补。插值修补的主要思想是获取插值失败区域的点集，探测点集附近成功插值点的数据，再通过加权平均的方法获取水深值，流程见图1。

图1 插值修补流程

图2为插值修补示意，其中：实心点为插值成功点；空心点为插值失败点；圆圈区域是以插值失败点为中心的缓冲区，半径为R。这里采用一个以插值失败点为中心的缓冲区来探测附近的插值成功点，若依靠当前半径的缓冲区仍找不到一定数量的插值成功点，则扩大缓冲区的半径。需指出，缓冲区的半径应合理地设置，既能包括足够多的插值成功点，保证节点水深修补的有效性，又能保证半径尽量小，防止缓冲区过大导致修补水深严重失真。

图2 插值修补示意

2 多约束航路规划方法设计

A*算法[9]是一种启发式搜索算法，由于其对空间的探索机制非常适合于寻路，因此该算法(二维)已被广泛应用于路径规划问题的求解中。SZCZERBA[10]提出一种改进的A*算法，称为稀疏A*算法。该算法根据约束条件有效削减搜索空间，实现算法的快速有效规划。由于水下运载器的航行空间复杂，且实际航行时受多种约束限制，二维规划远远达不到要求，因此这里把二维稀疏A*算法扩展到三维，并考虑实际航行常见的几种约束，提出一种多约束三维A*算法。该算法在三维空间中根据航路规划约束削减算法每步扩展出的大量子节点，达到快速规划的目的。

三维A*算法是在二维A*算法的基础之上建立的，主要步骤包括A*地图的建立、启发函数的构建及closed表和open表的维护。对于三维A*算法，栅格地图占用的内存及扩展的子节点数明显增多，这使得算法计算的效率明显降低。因此，三维A*算法要尽量平衡计算精度和计算效率，设法快速且精准地计算出栅格空间数据及扩展子节点是算法的关键。

2.1三维A*地图的建立

三维A*地图是由多个立方体构成的，因此需要计算立方体的可航行性。由于三维数据的信息量巨大，对每个立方体都尽量精准地计算会消耗大量的时间和内存，因此考虑到陆地等面要素和线要素数据的连续性及点要素的离散性，采用大面积粗算、边缘精算和离散点数据叠加的方式进行地图构建。具体方法如下。

1) 大面积粗算：判断立方体的中心点是否在障碍物中，若是则赋值为1，否则赋值为0。

2) 边缘精算：找到值为1且周围存在0值的立方体，精确计算该立方体周围值为0的立方体的可航行性。

3) 离散点数据叠加：由于沉船、暗礁等点数据障碍物的面积很小且分布分散，不具有连续性，因此获取这些点数据的位置数据并将其叠加到相应的立方体中。

2.2子节点的扩展

普通二维A*算法扩展的子节点方向有4个或8个，由于三维航行增加了纵向方向，因此三维A*算法扩展的子节点方向应增加到6个、18个或26个，扩展子节点数越多，规划出的路径就越接近实际航线，相应的计算时间就越长。这里为使航路具有较高的实用性，扩展26个子节点，即在三维空间中紧邻被扩展节点的栅格，通过考虑多种航行约束，达到削减子节点并保证满足约束的目的。

2.3多约束的处理

由于水下运载器的运动受下潜深度、自身尺寸及灵活性的限制，因此只有充分考虑这些约束条件才能使规划出的航路具有较强的实用性。此外，通过约束处理，也可达到消减规划过程中的子节点的目的，以提高计算的效率。针对上述问题，给出深度和安全距离及最大转向角、俯仰角的约束处理方法。

2.3.1深度约束的处理

水下运载器的工作深度由自身特性决定，包括最小深度和最大深度，超过该深度范围，运载器将无法正常工作。因此，在构建A*栅格地图时根据最小深度和最大深度对网格节点进行判断，表达式为

(2)

这样不仅能保证规划出的航路始终在一个安全的深度范围内，而且可减少算法需要遍历的空间节点。

2.3.2安全距离约束的处理

对于安全距离，为简化问题,对障碍物进行“膨胀”处理，即将障碍物向外扩展一定的距离，以满足安全距离的要求。从空间分析的角度来说，障碍物的膨胀处理相当于以一定的半径对障碍物建立缓冲区。对于三维缓冲区的建立，通用的方法是计算A*地图节点与规划空间中障碍物的欧氏距离，若该距离小于安全距离，则认为该节点是不可航的。具体方法如下。

(1) 找到A*地图节点的经纬度位置对应的障碍物局部区域；

(2) 计算地图节点到障碍物单位平面的欧氏距离θ；

(3) 判断θ与安全距离dsafe的大小关系，若不满足安全距离要求，则设置该节点为不可航点。

2.3.3转角约束的处理

如“2.2”节所述，在三维A*算法中可扩展出26个子节点，因此转角也对应26种情况。在处理最大转向角和最大俯仰角时，首先判断子节点的扩展方向，若是向上方或下方扩展的,则对应最大俯仰角;若是在同一水平面内扩展的,则对应最大转向角。接着计算夹角θ，并判断θ与角度约束的大小关系，若不满足角度约束,则该子节点被删除。这样的处理方法不仅能满足角度约束，同时可减轻open表的存储负担，有利于快速规划出符合要求的路径。

3 仿真验证及试验结果

3.1规划空间生成方法的测试

从电子海图中选择一个特定的区域，该区域含有4块陆地和若干个岛屿，水深从左至右逐渐加深。图3为规划空间对应的电子海图，其中：A位置为暗礁；B位置和C位置为危险区。

为验证规划空间生成方法的有效性和正确性，把生成的空间数据导入到Surfer中绘制成二维和三维地形(见图4和图5)。

图3 规划空间对应的电子海图

图4 规划空间的渐变地形图

图5 规划空间的三维效果图

从图4和图5中可看出，利用所提出的规划空间生成方法得到的地形图与图3的特征基本吻合。由此可知，提出的面要素和线要素的叠加方法是正确的。

此外，通过对比图3～图5中的点要素A，B，C的位置可看出，要素A，B，C均被处理成障碍物，符合路径规划的要求。

3.2多约束三维A*算法的测试

为验证航路规划算法的有效性，基于规划空间生成的三维空间设计多约束三维A*算法性能验证试验，试验参数见表1。

程序仍用C++编写，计算结果显示在二维海图上。为验证算法规划的路径满足航路约束，统计所有路径段中深度、转角和俯仰角的最大值，判断与障碍物的距离是否小于安全距离。给出的规划结果见图6，结果统计见表2。

表1 航行约束设置

图6 电子海图路径结果图

表2 规划路径约束统计结果

图6中：S为起点；D为终点。由图6和表2可知，该算法成功规划出了一条三维无碰路径，且该路径符合航路规划约束的要求。

4 结束语

给出基于S-57标准电子海图的规划空间生成方法，保证规划空间的真实性；基于规划空间并结合实际规划需求，设计多种规划约束的处理方法，提出多约束的三维A*规划算法，提高规划算法的实用性。仿真结果表明：所提出的方法能生成接近真实航行环境的规划空间，并能规划出一条符合多个约束要求的三维无碰路径。

[1] 栾禄雨，朱海.基于改进遗传算法的潜艇隐蔽航路规划[J].武器装备自动化，2005,25(9):3-4.

[2] 吴博，文元桥，肖长诗.一种内河海事无人艇路径规划算法设计与仿真[J].计算机工程与应用,2013,49(14):241-246.

[3] 栾禄雨，朱海，蔡鹏.舰艇航路规划系统研究[J].中国航海，2008,31(4)：392-404.

[4] 张欣景，胡训强，谢国新，等.航路规划中数字地图综合处理技术[J].火力与指挥控制，2012,37(1):95-98.

[5] 孟婵媛，翟京生，陆毅.S-57数据的组织与实现[J].测绘学院学报,2003,20(4):275-278.

[6] 扈震,杨之江,马振强.基于S-57标准的电子海图三维可视化[J].地球科学——中国地质大学学报，2010,35(3)：471-474.

[7] 王辉.海底地形三维可视化技术研究[D].哈尔滨：哈尔滨工程大学,2013:31-32.

[8] 王胜正，黄玉贵，施朝健.基于区域层次细节绘制的 3D ECDIS实现方法[J].中国造船，2014,55(3)：175-184.

[9] MITCHELL J S B, KEIRNEY D M. Planning Strategic Path Through Variable Terrain Data[C]//Proceedings of the Applications of Artificial Intelligence. USA: SPIE Press, 1984:172-179.

[10] SZCZERBA R J. Robust Algorithm for Real Time Route Planning[J]. IEEE Transaction on Aerospace and Electronic System, 2000, 36(3): 869-878.

Multi-ConstraintPathPlanningforAUVwithElectronicChart

(1.College of Automation，Harbin Engineering University, Harbin 150000, China； 2. Science and Technology on Space Physics Laboratory, Beijing 100076, China)

U612.1

A

2016-01-11

赵玉新(1980—)，男，黑龙江哈尔滨人，教授，研究方向为现代舰船综合导航系统及无人海洋运载器导航技术。 E-mail: zhaoyuxin@hrbeu.edu.cn 金 娜(1989—),女，辽宁铁岭人，硕士生，研究方向为智能算法和航路规划。E-mail：jinna8899@163.com

1000-4653(2016)02-0011-04