一種面向潛艇管系自動布局的環境建模方法

曹洪茹，侯新國，馮 源，畢 敏

(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聚類算法的自適應柵格法得到柵格粒度不同的柵格圖，大大減少了柵格數量。同時引入了可通行性度量函數衡量柵格與障礙物的距離，為管系布局算法中目標函數的建立提供依據，可以有效提高潛艇管系布局的效率和準確性。