一种面向潜艇管系自动布局的环境建模方法

曹洪茹，侯新国，冯 源，毕 敏

(1. 海军工程大学 电气工程学院，湖北 武汉 430033；2. 中国船舶集团公司第七一〇研究所，湖北 宜昌 443000)

0 引 言

潜艇管系布局是在有障碍物的潜艇空间里，按照相应管路布管的约束条件，找到一条连接起点与终点并避开障碍物的可行布管路径的过程。管系自动布局的实现主要包括环境建模和路径生成两部分，其中环境建模是将待布管空间映射到抽象模型空间，利用数学语言和方法进行表达以方便计算机规划算法进行处理。因此，环境建模是进行有效管系布局的基础，合理的环境建模对后续布局结果有重要的影响。

管系布局的环境建模方法主要有包括C空间法、自由空间法、Voronoi图法、拓扑图法等在内的图形学方法[1]和以栅格法为代表的单元分解法[2]。图形学方法利用点、线、面等生成具有空间邻接关系和拓扑意义的图，大多适用于障碍物较少、有效布局空间较大的二维空间。以栅格法为代表的单元分解法通用性较强，可以很好地与遗传算法等智能算法相结合，简单且易于实现，是管系布局领域应用最多的一种环境建模方法，但当布管空间较大时，栅格粒度和计算效率的矛盾是尚待解决的一个问题。栅格法作为机器人路径规划和管系布局领域的典型建模方法，受到了很多学者的关注。王伟峰等[3]在传统栅格法中融入单元遍历的思想，提高了栅格法的精确度，但计算量有所增加；韩忠华[4]针对无人机路径规划提出一种高度降维的三维环境建模方法，这种方法兼顾了环境模型的精度要求和规划算法的处理效率；刘晓磊等[5]将栅格法应用于非结构化环境中的机器人路径规划，验证了栅格法对复杂环境的适应性。

为了解决潜艇空间内主干管系的自动布局问题，本文研究一种基于栅格法的潜艇空间管系布局建模方法，该方法综合考虑布管约束以及布局算法的计算效率，有利于路径生成阶段产生好的布管结果。

1 基于栅格法的潜艇空间管系布局建模方法

基于栅格法的潜艇空间管系布局建模方法的主要步骤如下：

1）建立布管坐标系，将三维潜艇空间转化为二维潜艇内舱平面；

2）使用基于Sting聚类算法的自适应栅格法处理潜艇内舱平面，生成待布管空间；

3）引入可通行性度量函数表征栅格的可通行性属性，方便利用布管算法生成布管结果。主要思路如图1所示。

图1 基于栅格法的潜艇空间管系布局建模方法Fig. 1 A grid-based environment modeling method for piping layout of submarine

1.1 布管坐标系的建立

潜艇固壳为由圆柱和圆台拼接而成的不规则体，若在三维空间内做栅格分割（见图2），栅格数量较多，会对管系布局算法的计算效率和准确度产生影响，同时，艇体附近的栅格大多由于圆弧艇体的影响大多不是规则的立方体网格形状，而潜艇管系大多沿舱壁分布。为了减少三维空间内的栅格分割误差，将三维潜艇空间展开为二维潜艇内舱平面将舱内障碍物投影到二维平面上，在二维潜艇内舱平面进行管系布局[6-7]。

图2 潜艇三维空间栅格分割效果Fig. 2 Submarine raster segmentation effect in 3D space

图3 规则圆柱体包围后的潜艇固壳Fig. 3 Submarine solid shell surrounded by regular cylinder

图4 建立布管坐标系Fig. 4 Setting up the layout coordinate system

根据任意指定的管系起点和终点分布的区域，可以将布管策略分为2种情况：一种在Ⅰ区或Ⅱ区就可以完成路径规划，另外一种需在Ⅰ区和Ⅲ区搜索符合条件的路径，如下式：

1.2 基于Sting聚类算法的自适应栅格法

在传统的栅格法中，一般按照管系直径选取均等的栅格粒度对空间进行划分，并对栅格属性进行“0”和“1”的标记以方便计算机程序识别栅格的可布管性，管系布局算法搜索路径时需要遍历空间内每一个栅格以确定可行路径，包括各大小不一的障碍物处大量集聚在一起的不可布管栅格。这意味着均等的栅格粒度不仅缺乏对大小不一障碍物的灵活可适性，同时增加了路径搜索的工作量，影响算法的执行效率。Sting（Statistical Information Grid）算法[8]是一种基于网格的聚类算法，通过自顶向下多层次划分得到的多分辨率网格中的相关统计信息进行聚类。本文提出的基于Sting聚类算法的自适应栅格法[9]在众多栅格基础上对栅格面积进行聚类，可根据不同大小的障碍物生成相应的栅格区域作为栅格粒度，避免了同一栅格粒度过大或过小带来的布管精度损失或搜索效能下降[10]。

基于Sting聚类算法的自适应栅格法的步骤如下：

1）以管系直径为基础栅格粒度对二维潜艇内舱平面图进行划分；

2）用“0”和“1”对每个基础栅格的可布管性进行标记（“0”为完全可布管栅格，“1”为不可布管栅格及未完全被障碍物填充的栅格）；

3）根据栅格可布管性的不同，采用自底向上的方式聚类生成不同层级的栅格单元以构建不同粒度的栅格区域。针对某一标记为“1”的栅格（i为聚类的层级，最底层时i=1，为栅格坐标），从其左侧栅格起沿顺时针方向依次搜索（假设基础栅格粒度为），倘若这3个栅格也均标记为“1”，则这4个栅格合并为，第1层次搜索聚类结束后，如图5所示。依照此法进行第2、第3层次等的聚类。关于聚类完成后栅格与原栅格坐标之间的关系满足下式：

1.3 可通行性度量函数的引入

在管系自动布局过程中，需考虑以下几方面因素：1）除完全避开被障碍物占据的区域以外，在不被障碍物占据的区域（即可通行区域）通行时，不允许紧贴障碍物设置；2）在沿高压、高温等危险性较高的设备布管时需要预留安全距离；3）管路长度尽量短，管路弯头数较少。为此，本文引入可通行性度量函数[11]，将栅格与周围障碍物的距离表征为栅格的可通行代价，为管系布局算法中目标函数的建立提供依据。

若定义第i层聚类，坐标为的栅格的可通行性度量函数为，假设栅格图中共存在N个独立的障碍物则有：

2 基于栅格法的潜艇空间管系布局建模方法的仿真与验证

为了验证本文中提出的环境建模方法的合理性和可靠性，利用该方法生成潜艇的二维栅格平面图（见图6（b）），采用A*算法[12]在设置起点和终点的条件下搜索寻求可行管路路径，并对所得到的路径进行分析评估。由于此处采用A*求管路路径只是为了验证本文中的环境建模方法是否有效合理，因此对生成的管路路径的优化性不作探索，此处假设路径搜索沿四邻域进行，管路均为正交分布，栅格的启发式函数为：

图5 基于sting聚类的自适应栅格法Fig. 5 Adaptive raster method based on Sting clustering algorithm

图6 潜艇内舱平面栅格图仿真结果Fig. 6 Simulation results of plane raster diagram of submarine interior cabin

仿真实验中，使用传统栅格法处理平面图（见图6（a）），考虑布管精度的需要，以管路直径为均一栅格粒度，此时栅格数目过多，势必会对算法执行效率产生影响。而观察运用基于Sting聚类算法的自适应栅格法处理潜艇内舱平面的结果（见图6（b）），在栅格数量、存储量、栅格粒度及产生布局结果所用时间方面均优于传统栅格法（见表1），基于Sting聚类算法的自适应栅格法不仅节省了信息存储量，而且在不影响障碍物边缘及形状精度的前提下，大大减少了栅格数量，提高了管路布局的效率和实时性。在栅格图基础上采用A*算法验证管路布局结果，人为设定障碍物和管路起点终点，分别使和1对基于Sting聚类算法的自适应栅格法和可通行性度量函数进行验证，如图7所示。在本文提出的自适应栅格法的基础上可以产生合理的管路路径，引入可通行性度量函数时，在保证路径相对较短的同时，管路路径与障碍物之间预留了一定的安全距离，且管路弯头数较少（见表2），更加符合实际布管需求。

表1 融合sting聚类算法的自适应栅格法仿真结果数据统计Tab. 1 Data statistics of sting clustering algorithm adaptive raster method simulation results

图7 管路路径布置仿真结果Fig. 7 Simulation results of pipeline path layout

表2 可通行性度量函数对管路弯头数的影响Tab. 2 The influence of the trafficability metric function on the number of pipe elbows

3 结 语

面向潜艇管系自动布局需求，针对潜艇形状不规则、潜艇空间管系布局计算量大的难题，提出一种面向潜艇管系自动布局的环境建模方法。通过建立布管坐标系将潜艇三维空间转化为二维内舱平面，利用融合Sting聚类算法的自适应栅格法得到栅格粒度不同的栅格图，大大减少了栅格数量。同时引入了可通行性度量函数衡量栅格与障碍物的距离，为管系布局算法中目标函数的建立提供依据，可以有效提高潜艇管系布局的效率和准确性。