0 引　言

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

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

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

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

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

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

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

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

1.1 布管坐标系的建立

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

以潜艇最大半径 $a$ 为半径，以潜艇中轴线为轴作一圆柱体包围不规则的艇体（见图3），建立布管坐标系进行坐标变换。以最大半径 $r = a$ 处展开的圆周为 $u$ 轴，潜艇内舱任意一点 $M(x,y,z)$ （见图4（a）），可按照式（1）变换为二维平面内任意一点 ${M'}(u,h)$ （见图4（b））。

$\left\{ \begin{array}{l} h = z\text{，}\\ u = \theta r,\theta \in [0,2{\text{π}} ]\text{，}\\ \theta = \arctan \dfrac{x}{y},\theta \in [0,2{\text{π}} ]\text{。} \end{array} \right.$

(1)

将圆柱体按照某一条母线展开，图4（b）中 $h$ 和 ${l^{''}}$ 在三维空间中实际上重合，当管系起点和终点分别在 $h$ 和 ${l^{''}}$ 附近时，在二维空间中避障寻得的路径在三维空间中并非最短路径。将Ⅱ区平移至 $h$ 轴左侧作为Ⅲ区，对Ⅲ区内的点满足下式：

$\left\{ \begin{array}{l} {u_{{\rm{III}}}}{\rm{ = }}{u_{{\rm{II}}}}{\rm{ - 2}}{\text{π}} a\text{，}\\ {h_{{\rm{III}}}}{\rm{ = }}{h_{{\rm{II}}}}\text{。} \end{array} \right.$

(2)

式中， $({u_{{\rm{II}}}},{h_{{\rm{II}}}})$ 和 $({u_{{\rm{III}}}},{h_{{\rm{III}}}})$ 分别表示Ⅱ区和Ⅲ区内任意一点的坐标。

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

$\left\{ \begin{array}{l} {\rm{|}}{u_S}{\rm{ - }}{u_D}{\rm{| > }}{\text π} a,{\text{在Ⅰ区和Ⅲ区搜索路径}}\text{，}\\ {\rm{|}}{u_S}{\rm{ - }}{u_D}{\rm{|}} \leqslant {\text π} a,{\text{在Ⅰ区和Ⅱ区搜索路径}}\text{。} \end{array} \right.$

(3)

式中， $S({u_S},{h_S})$ 和 $D({u_D},{h_D})$ 分别为管系的起点和终点。

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

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

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

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

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

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

$\left\{ \begin{array}{l} i = 1{\text{时}}\left\{ \begin{array}{l} x' = x\text{，}\\ y' = y\text{，} \end{array} \right.\\ i \ne 1{\text{时}}\left\{ \begin{array}{l} x' = x - {2^{i - \frac{5}{2}}}c\text{，}\\ y' = y + {2^{i - \frac{5}{2}}}c\text{。} \end{array} \right. \end{array} \right.$

(4)

式中， $(x',y')$ 和 $(x,y)$ 分别为聚类完成后栅格与原栅格的坐标。

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

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

若定义第 $i$ 层聚类，坐标为 $(x,y)$ 的栅格的可通行性度量函数为 $f_{{P_i}(x,y)}^{metric}$ ，假设栅格图中共存在N个独立的障碍物 $OB{S_j}$ （ $j = 1,2, \cdots ,N$ ），则有：

$f_{{P_i}(x,y)}^{metric} = \sum\limits_{j = 1}^N {{e^{ - d({P_i}(x,y),OB{S_j})}}}\text{，} $

(5)

$ \begin{aligned} & d({P_i}(x,y),OB{S_j}){\text{ = }}\mathop {{\text{min}}}\limits_{{G_j} \in OB{S_j}} d({P_i}(x,y),{G_j}) = \hfill \\ & \quad \quad \mathop {{\text{min}}}\limits_{{G_j} \in OB{S_j}} (\left| {x - {x_{Gn}}} \right| + \left| {y - {y_{Gn}}} \right|),n = 1,2,3 \cdots \text{。}\\ \end{aligned} $

(6)

式中： $({x_{Gn}},{y_{Gn}})$ 为某一障碍物的第 $n$ 个边界栅格的坐标； $d({P_i}(x,y),OB{S_j})$ 为某一栅格 ${P_i}(x,y)$ 与障碍物的距离，定义为该栅格与此障碍物各边界栅格曼哈顿距离的最小值。

通过引入可通行性度量函数，每一个栅格的属性可通过一个4元组来描述 $(i,x,y,f_{{P_{i(x,y)}}}^{metric})$ ，其中 $i$ 为聚类层次， $(x,y)$ 为栅格坐标， $f_{{P_{i(x,y)}}}^{metric}$ 则表征 ${P_i}(x,y)$ 栅格的可通行性高低，将其加入目标函数中可在管路与设备之间预留安全距离，提高布管安全性。

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

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

$h(n) = h'(n) + \alpha \cdot {f^{metric}}(n)\text{，}$

(7)

$h'(n) = c \cdot (\left| {{x_n} - {x_D}} \right| + \left| {{y_n} - {y_D}} \right|)\text{。}$

(8)

式中： $h'(n)$ 为栅格 $n$ 到终点栅格D的距离代价； $\alpha $ 为权值； ${f^{metric}}(n)$ 为栅格 $n$ 的可通行性度量函数值； $c$ 为聚类前的基础栅格粒度； $({x_n},{y_n})$ 和 $({x_D},{y_D})$ 分别为栅格 $n$ 到和栅格D的坐标。

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

3 结　语

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