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

(1. 海軍工程大學(xué) 電氣工程學(xué)院，湖北 武漢 430033；2. 中國船舶集團(tuán)公司第七一〇研究所，湖北 宜昌 443000)

0 引 言

潛艇管系布局是在有障礙物的潛艇空間里，按照相應(yīng)管路布管的約束條件，找到一條連接起點(diǎn)與終點(diǎn)并避開障礙物的可行布管路徑的過程。管系自動(dòng)布局的實(shí)現(xiàn)主要包括環(huán)境建模和路徑生成兩部分，其中環(huán)境建模是將待布管空間映射到抽象模型空間，利用數(shù)學(xué)語言和方法進(jìn)行表達(dá)以方便計(jì)算機(jī)規(guī)劃算法進(jìn)行處理。因此，環(huán)境建模是進(jìn)行有效管系布局的基礎(chǔ)，合理的環(huán)境建模對(duì)后續(xù)布局結(jié)果有重要的影響。

管系布局的環(huán)境建模方法主要有包括C空間法、自由空間法、Voronoi圖法、拓?fù)鋱D法等在內(nèi)的圖形學(xué)方法[1]和以柵格法為代表的單元分解法[2]。圖形學(xué)方法利用點(diǎn)、線、面等生成具有空間鄰接關(guān)系和拓?fù)湟饬x的圖，大多適用于障礙物較少、有效布局空間較大的二維空間。以柵格法為代表的單元分解法通用性較強(qiáng)，可以很好地與遺傳算法等智能算法相結(jié)合，簡(jiǎn)單且易于實(shí)現(xiàn)，是管系布局領(lǐng)域應(yīng)用最多的一種環(huán)境建模方法，但當(dāng)布管空間較大時(shí)，柵格粒度和計(jì)算效率的矛盾是尚待解決的一個(gè)問題。柵格法作為機(jī)器人路徑規(guī)劃和管系布局領(lǐng)域的典型建模方法，受到了很多學(xué)者的關(guān)注。王偉峰等[3]在傳統(tǒng)柵格法中融入單元遍歷的思想，提高了柵格法的精確度，但計(jì)算量有所增加；韓忠華[4]針對(duì)無人機(jī)路徑規(guī)劃提出一種高度降維的三維環(huán)境建模方法，這種方法兼顧了環(huán)境模型的精度要求和規(guī)劃算法的處理效率；劉曉磊等[5]將柵格法應(yīng)用于非結(jié)構(gòu)化環(huán)境中的機(jī)器人路徑規(guī)劃，驗(yàn)證了柵格法對(duì)復(fù)雜環(huán)境的適應(yīng)性。

為了解決潛艇空間內(nèi)主干管系的自動(dòng)布局問題，本文研究一種基于柵格法的潛艇空間管系布局建模方法，該方法綜合考慮布管約束以及布局算法的計(jì)算效率，有利于路徑生成階段產(chǎn)生好的布管結(jié)果。

1 基于柵格法的潛艇空間管系布局建模方法

基于柵格法的潛艇空間管系布局建模方法的主要步驟如下：

1）建立布管坐標(biāo)系，將三維潛艇空間轉(zhuǎn)化為二維潛艇內(nèi)艙平面；

2）使用基于Sting聚類算法的自適應(yīng)柵格法處理潛艇內(nèi)艙平面，生成待布管空間；

3）引入可通行性度量函數(shù)表征柵格的可通行性屬性，方便利用布管算法生成布管結(jié)果。主要思路如圖1所示。

圖1 基于柵格法的潛艇空間管系布局建模方法Fig. 1 A grid-based environment modeling method for piping layout of submarine

1.1 布管坐標(biāo)系的建立

潛艇固殼為由圓柱和圓臺(tái)拼接而成的不規(guī)則體，若在三維空間內(nèi)做柵格分割（見圖2），柵格數(shù)量較多，會(huì)對(duì)管系布局算法的計(jì)算效率和準(zhǔn)確度產(chǎn)生影響，同時(shí)，艇體附近的柵格大多由于圓弧艇體的影響大多不是規(guī)則的立方體網(wǎng)格形狀，而潛艇管系大多沿艙壁分布。為了減少三維空間內(nèi)的柵格分割誤差，將三維潛艇空間展開為二維潛艇內(nèi)艙平面將艙內(nèi)障礙物投影到二維平面上，在二維潛艇內(nèi)艙平面進(jìn)行管系布局[6-7]。

圖2 潛艇三維空間柵格分割效果Fig. 2 Submarine raster segmentation effect in 3D space

圖3 規(guī)則圓柱體包圍后的潛艇固殼Fig. 3 Submarine solid shell surrounded by regular cylinder

圖4 建立布管坐標(biāo)系Fig. 4 Setting up the layout coordinate system

根據(jù)任意指定的管系起點(diǎn)和終點(diǎn)分布的區(qū)域，可以將布管策略分為2種情況：一種在Ⅰ區(qū)或Ⅱ區(qū)就可以完成路徑規(guī)劃，另外一種需在Ⅰ區(qū)和Ⅲ區(qū)搜索符合條件的路徑，如下式：

1.2 基于Sting聚類算法的自適應(yīng)柵格法

在傳統(tǒng)的柵格法中，一般按照管系直徑選取均等的柵格粒度對(duì)空間進(jìn)行劃分，并對(duì)柵格屬性進(jìn)行“0”和“1”的標(biāo)記以方便計(jì)算機(jī)程序識(shí)別柵格的可布管性，管系布局算法搜索路徑時(shí)需要遍歷空間內(nèi)每一個(gè)柵格以確定可行路徑，包括各大小不一的障礙物處大量集聚在一起的不可布管柵格。這意味著均等的柵格粒度不僅缺乏對(duì)大小不一障礙物的靈活可適性，同時(shí)增加了路徑搜索的工作量，影響算法的執(zhí)行效率。Sting（Statistical Information Grid）算法[8]是一種基于網(wǎng)格的聚類算法，通過自頂向下多層次劃分得到的多分辨率網(wǎng)格中的相關(guān)統(tǒng)計(jì)信息進(jìn)行聚類。本文提出的基于Sting聚類算法的自適應(yīng)柵格法[9]在眾多柵格基礎(chǔ)上對(duì)柵格面積進(jìn)行聚類，可根據(jù)不同大小的障礙物生成相應(yīng)的柵格區(qū)域作為柵格粒度，避免了同一柵格粒度過大或過小帶來的布管精度損失或搜索效能下降[10]。

基于Sting聚類算法的自適應(yīng)柵格法的步驟如下：

1）以管系直徑為基礎(chǔ)柵格粒度對(duì)二維潛艇內(nèi)艙平面圖進(jìn)行劃分；

2）用“0”和“1”對(duì)每個(gè)基礎(chǔ)柵格的可布管性進(jìn)行標(biāo)記（“0”為完全可布管柵格，“1”為不可布管柵格及未完全被障礙物填充的柵格）；

3）根據(jù)柵格可布管性的不同，采用自底向上的方式聚類生成不同層級(jí)的柵格單元以構(gòu)建不同粒度的柵格區(qū)域。針對(duì)某一標(biāo)記為“1”的柵格（i為聚類的層級(jí)，最底層時(shí)i=1，為柵格坐標(biāo)），從其左側(cè)柵格起沿順時(shí)針方向依次搜索（假設(shè)基礎(chǔ)柵格粒度為），倘若這3個(gè)柵格也均標(biāo)記為“1”，則這4個(gè)柵格合并為，第1層次搜索聚類結(jié)束后，如圖5所示。依照此法進(jìn)行第2、第3層次等的聚類。關(guān)于聚類完成后柵格與原柵格坐標(biāo)之間的關(guān)系滿足下式：

1.3 可通行性度量函數(shù)的引入

在管系自動(dòng)布局過程中，需考慮以下幾方面因素：1）除完全避開被障礙物占據(jù)的區(qū)域以外，在不被障礙物占據(jù)的區(qū)域（即可通行區(qū)域）通行時(shí)，不允許緊貼障礙物設(shè)置；2）在沿高壓、高溫等危險(xiǎn)性較高的設(shè)備布管時(shí)需要預(yù)留安全距離；3）管路長(zhǎng)度盡量短，管路彎頭數(shù)較少。為此，本文引入可通行性度量函數(shù)[11]，將柵格與周圍障礙物的距離表征為柵格的可通行代價(jià)，為管系布局算法中目標(biāo)函數(shù)的建立提供依據(jù)。

若定義第i層聚類，坐標(biāo)為的柵格的可通行性度量函數(shù)為，假設(shè)柵格圖中共存在N個(gè)獨(dú)立的障礙物則有：

2 基于柵格法的潛艇空間管系布局建模方法的仿真與驗(yàn)證

為了驗(yàn)證本文中提出的環(huán)境建模方法的合理性和可靠性，利用該方法生成潛艇的二維柵格平面圖（見圖6（b）），采用A*算法[12]在設(shè)置起點(diǎn)和終點(diǎn)的條件下搜索尋求可行管路路徑，并對(duì)所得到的路徑進(jìn)行分析評(píng)估。由于此處采用A*求管路路徑只是為了驗(yàn)證本文中的環(huán)境建模方法是否有效合理，因此對(duì)生成的管路路徑的優(yōu)化性不作探索，此處假設(shè)路徑搜索沿四鄰域進(jìn)行，管路均為正交分布，柵格的啟發(fā)式函數(shù)為：

圖5 基于sting聚類的自適應(yīng)柵格法Fig. 5 Adaptive raster method based on Sting clustering algorithm

圖6 潛艇內(nèi)艙平面柵格圖仿真結(jié)果Fig. 6 Simulation results of plane raster diagram of submarine interior cabin

仿真實(shí)驗(yàn)中，使用傳統(tǒng)柵格法處理平面圖（見圖6（a）），考慮布管精度的需要，以管路直徑為均一柵格粒度，此時(shí)柵格數(shù)目過多，勢(shì)必會(huì)對(duì)算法執(zhí)行效率產(chǎn)生影響。而觀察運(yùn)用基于Sting聚類算法的自適應(yīng)柵格法處理潛艇內(nèi)艙平面的結(jié)果（見圖6（b）），在柵格數(shù)量、存儲(chǔ)量、柵格粒度及產(chǎn)生布局結(jié)果所用時(shí)間方面均優(yōu)于傳統(tǒng)柵格法（見表1），基于Sting聚類算法的自適應(yīng)柵格法不僅節(jié)省了信息存儲(chǔ)量，而且在不影響障礙物邊緣及形狀精度的前提下，大大減少了柵格數(shù)量，提高了管路布局的效率和實(shí)時(shí)性。在柵格圖基礎(chǔ)上采用A*算法驗(yàn)證管路布局結(jié)果，人為設(shè)定障礙物和管路起點(diǎn)終點(diǎn)，分別使和1對(duì)基于Sting聚類算法的自適應(yīng)柵格法和可通行性度量函數(shù)進(jìn)行驗(yàn)證，如圖7所示。在本文提出的自適應(yīng)柵格法的基礎(chǔ)上可以產(chǎn)生合理的管路路徑，引入可通行性度量函數(shù)時(shí)，在保證路徑相對(duì)較短的同時(shí)，管路路徑與障礙物之間預(yù)留了一定的安全距離，且管路彎頭數(shù)較少（見表2），更加符合實(shí)際布管需求。

表1 融合sting聚類算法的自適應(yīng)柵格法仿真結(jié)果數(shù)據(jù)統(tǒng)計(jì)Tab. 1 Data statistics of sting clustering algorithm adaptive raster method simulation results

圖7 管路路徑布置仿真結(jié)果Fig. 7 Simulation results of pipeline path layout

表2 可通行性度量函數(shù)對(duì)管路彎頭數(shù)的影響Tab. 2 The influence of the trafficability metric function on the number of pipe elbows

3 結(jié) 語

面向潛艇管系自動(dòng)布局需求，針對(duì)潛艇形狀不規(guī)則、潛艇空間管系布局計(jì)算量大的難題，提出一種面向潛艇管系自動(dòng)布局的環(huán)境建模方法。通過建立布管坐標(biāo)系將潛艇三維空間轉(zhuǎn)化為二維內(nèi)艙平面，利用融合Sting聚類算法的自適應(yīng)柵格法得到柵格粒度不同的柵格圖，大大減少了柵格數(shù)量。同時(shí)引入了可通行性度量函數(shù)衡量柵格與障礙物的距離，為管系布局算法中目標(biāo)函數(shù)的建立提供依據(jù)，可以有效提高潛艇管系布局的效率和準(zhǔn)確性。