基于A*算法的核電廠工藝管道自動布局方法

蘇錦成，王振中，賈小攀，薛靜，谷振杰

基于A*算法的核電廠工藝管道自動布局方法

蘇錦成，王振中，賈小攀，薛靜，谷振杰

（中國核電工程公司，北京 100840）

核電廠的工藝系統(tǒng)管道布局是核電廠設計的重要過程之一，工藝系統(tǒng)管道數(shù)量龐大，約束條件眾多，設計結果容易受到電廠結構和設備位置變更的影響。依靠人工對核電廠工藝系統(tǒng)管道進行布局已成為影響核電廠設計效率的因素之一。因此核電廠工藝系統(tǒng)管道的自動布局應用研究具有重要意義。本文針對核電廠工藝系統(tǒng)管道的自動布局問題，結合核電廠的廠房設備布局特點，考慮廠房大小、輻射屏蔽、管道成本等約束，依據(jù)核電廠工藝管道布局的要求，對核電廠廠房及設備采用柵格法進行空間離散，并采用A*（A-star）算法進行管路搜索。并基于此方法進行廠房主管道自動布局編程仿真，計算得出的主管道的自動布局方案能夠滿足模型設置的工藝管道的布局要求，驗證了該方法在核電廠廠房工藝管道自動布局中的適用性。

工藝系統(tǒng)管道；自動布局；A*算法

工藝系統(tǒng)管道布局是核電廠廠房布置設計中重要的環(huán)節(jié)。為了保障核電廠的運行和安全，在核電廠中設置了幾百個各種系統(tǒng)，這些系統(tǒng)的設備、部件采用管道進行連接。工藝系統(tǒng)管道的布局直接影響工藝系統(tǒng)功能的完整性，是核電廠安全運行的基礎。核電廠工藝系統(tǒng)管道布局工作量巨大，需要耗費大量的生產(chǎn)成本。主要體現(xiàn)在以下幾個方面：

（1）核電廠系統(tǒng)眾多，為了保證核電廠安全，大量系統(tǒng)設備和閥門都采用冗余設計，因此管道數(shù)量大；

（2）核電廠廠房布局初步設計之后，管道設計高度依賴廠房的布局和廠房的功能分區(qū)。而現(xiàn)代廠房設計采用螺旋迭代設計方法，前期設計的方案在后續(xù)與其他專業(yè)迭代的過程中，通常會進行改進，進而會影響管路的布局。因此核電廠工藝系統(tǒng)管路布局經(jīng)常會進行返工和迭代。

（3）核電廠由于其特殊性，為了保證設備的安全和可達性、操作人員的人生安全，管路布局需要遵守大量的規(guī)則和標準。

（4）目前核電廠工藝系統(tǒng)的管路布局主要依靠人工完成，管路布局設計的工程師需要熟悉廠房布局、系統(tǒng)流程、設備運行操作方式、約束標準等，需要經(jīng)過長期的經(jīng)驗積累。并且存在人因失誤造成管路布局不合理的風險。因此研究基于計算技術的核電廠工藝系統(tǒng)管路自動布局的方法，將工藝系統(tǒng)管路布置的標準約束和工程經(jīng)驗進行程序化，既能保證管路布局的合理性，同時能夠減少管路布局工程師的設計負擔，縮短設計周期，降低人因風險，對核電數(shù)字化具有重要的意義。

核電廠工藝系統(tǒng)管路布局屬于復雜方案設計問題，屬于布置問題的一種。自20世紀70年代開始，國內(nèi)外學者在管路自動布局的相關理論和方法上進行了多年的研究，從二維空間的簡單約束發(fā)展到三維空間內(nèi)的多目標、多約束。管路布局優(yōu)化的方法有很多，總體上可以分為：

（1）基于傳統(tǒng)優(yōu)化方法的管路布局方法；

（2）基于專家系統(tǒng)的啟發(fā)式管路布局方法[1]。

對于傳統(tǒng)優(yōu)化方法的管路優(yōu)化方法，Lee[2]于1961年首次提出了迷宮算法，迷宮算法主要是基于波的連續(xù)擴散原理。迷宮法的布通率高、適應性強，但所需容量大，操作速度慢，尤其當障礙物增加時，其復雜性會成倍增長。模擬退火、遺傳算法[3]、蟻群算法[4]、粒子群算法[5]是典型的非確定性算法，尋優(yōu)過程包含隨機策略，結果沒有嚴格的可重復性，算法收斂時間也不確定，參數(shù)的設定也是算法研究的關鍵環(huán)節(jié)，存在一定的局限性。Dijkstra E.W.于1959年提出Dijkstra算法[6]，該算法應用貪心搜索的策略，以起點為中心，向周邊不斷搜索。但該算法因探索頂點數(shù)目多，效率較低。Hart、Nilsson和Raphael于1968年提出A*算法[7]，該算法基于最好優(yōu)先的策略搜索，A*在搜索過程中不斷更新已形成路徑代價和剩余路徑代價，使搜索更具有目的性[1]。

對于專家系統(tǒng)[8,9]的啟發(fā)式算法，將專家的知識及經(jīng)驗，采用數(shù)學函數(shù)表達進而用編程的手段實現(xiàn)。采用專家系統(tǒng)的模式聯(lián)合開發(fā)并構建專家數(shù)據(jù)庫，能夠解決只有領域專家才能解決的問題。但是建立專家系統(tǒng)需要大量的專家經(jīng)驗及實際驗證，相關研究目前還處于初步研究階段。

管路自動布局的相關理論和方法上的研究從最初的工廠管路自動化設計，擴展到多個領域的自動化管路布置，包括航空發(fā)動機管路布置，集成電路走線布置，機電產(chǎn)品管路布置，船舶管路布置等[1]。但鮮有應用于核電廠工藝系統(tǒng)管路自動布局中。隨著數(shù)字化核電的發(fā)展，更多的自動化，智能化的技術應用于核電廠的設計施工過程中，本文選取A*算法，A*算也成為A-star算法（下文簡稱A*），結合核電廠的廠房設計特點，考慮輻射屏蔽、管道成本等約束，依據(jù)核電廠工藝管道布局的要求，開展核電廠工藝管路的自動布局研究，促進核電廠設計數(shù)字化的發(fā)展。

1　管路自動布局方法

核電廠工藝系統(tǒng)的管路通常是連接設備或者閥門。為了保證自動布局的出一根無碰撞的合理的管路。將管道自動布局分為兩步：

（1）根據(jù)核電廠的廠房布置特點、考慮輻射屏蔽、設備位置等因素，建立管路布置環(huán)境圖。

（2）在環(huán)境圖中采用搜索算法進行管路搜索。

1.1　環(huán)境圖建模方法

核電廠工藝管道布置在廠房中，廠房的布置通常需要考慮廠房的功能和輻射屏蔽，既要保證系統(tǒng)功能，又要保證通行人員盡量少的受到輻射照射。因此廠房中通常包含大量的設備、人員通道和控制區(qū)。為了方便將廠房的實際物理環(huán)境轉換為計算機可以處理的數(shù)字環(huán)境，本文采用由Howden W E提出的柵格法[10,11]，該方法通過柵格來表示環(huán)境地圖，減少管路路徑規(guī)劃過程中障礙物邊界信息處理時的計算量和復雜性，提高管路路徑搜索的效率。

在本文中主要依據(jù)核電廠廠房控制區(qū)、內(nèi)部設備、建筑墻體邊緣來劃分柵格，將核電廠的廠房的土建、設備、控制區(qū)等內(nèi)容等效為柵格，其中設備、控制區(qū)等為不可穿行柵格，土建可以根據(jù)實際情況確定是否可穿行，在可穿行的柵格中進行管路搜索。

1.2　自動布局搜索算法A*

A*算法是經(jīng)典啟發(fā)式搜索算法，在搜索過程中加入評估函數(shù)，通過評估函數(shù)的引導減少搜索節(jié)點，進而提高搜索的效率。

1.2.1A*算法的原理[7,12]

目前A*算法中評估函數(shù)分為兩個部分：

（1）從起點到當前節(jié)點目標節(jié)點的實際代價。其代價可以是路徑長度、彎頭的數(shù)量等；對于核電廠的工藝管道系統(tǒng)，其代價可以包括穿過控制區(qū)的長度。

（2）從當前節(jié)點到目標節(jié)點的估計代價，常見的估計代價的計算方式包括曼哈頓距離、對角線距離或者歐幾里得距離等。A*算法的評估函數(shù)如式（1）所示。

1.2.2A*算法的基本流程

借鑒禁忌搜索方式，通常在A*算法中定義了兩個節(jié)點集合，通常表示為CLOSED表和OPEN表。其中CLOSED表中存放搜索過的節(jié)點，OPEN表中存放搜索過節(jié)點的子節(jié)點。在搜索過程中，循環(huán)從OPEN表中選擇估價函數(shù)最小的節(jié)點，直到找到目標節(jié)點，搜索停止。初始化之后，采用A*算法進行管路搜索，搜索流程為：

（1）將起始點放入到OPEN表中，并將CLOSED表清空；

（2）判斷OPEN表是否為空，若OPEN表為空，并且沒有搜索到目標節(jié)點，搜索失敗，程序退出；

（3）將OPEN表中節(jié)點估價函數(shù)值進行排序，并選取估價函數(shù)最小值的節(jié)點n作為最優(yōu)節(jié)點，并從OPEN表中取出，放入到CLOSED表；

（4）判斷當前節(jié)點是否是目標節(jié)點。若是，則表示求出一條最優(yōu)管路路徑，根據(jù)CLOSED表，輸出路徑節(jié)點編號并退出程序。若不是，則拓展到當前節(jié)點的后續(xù)節(jié)點+1；

（5）計算節(jié)點+1的估價值；

（6）如果節(jié)點+1已經(jīng)在OPEN表中，并且節(jié)點+1的估價函數(shù)值小于OPEN表中估價函數(shù)值最小的路徑，則將節(jié)點設置為+1節(jié)點的父節(jié)點，同時修正OPEN表中最小路徑序列，并轉到流程（2）；

（7）如果節(jié)點+1已經(jīng)在CLOSED表中，并且節(jié)點+1的估價函數(shù)值小于CLOSED表中估價函數(shù)值最小的路徑，則將節(jié)點設置為節(jié)點+1的父節(jié)點，同時修正CLOSED表中最小路徑序列和最小估價函數(shù)值。將節(jié)點+1從CLOSED表中取出，放入到OPEN表中，并轉到流程（2）；

（8）如果節(jié)點+1不在CLOSED和OPEN表中，則將其放入到OPEN表中，將節(jié)點設置為節(jié)點+1的父節(jié)點，并轉到流程（2）。

1.2.3基于核電廠的評估函數(shù)改進

評估函數(shù)的改進主要是根據(jù)核電廠管路布局的約束條件來開展。通常對于管路布局的評價主要從經(jīng)濟性及安全性上開展：包含管路的總長度，管路的受力，管路穿過危險區(qū)的長度等。本文選取管路經(jīng)濟性為主要指標，即管路長度較小，同時管路布置方案采用較少的彎頭個數(shù)。為了滿足管路布局中彎頭個數(shù)盡量最少，需要在實際代價函數(shù)中加入彎頭的代價，本文采用式（2）的方式計算實際代價。

為了滿足管路盡量在廠房上部布局，需要對A*算法的啟發(fā)函數(shù)部分，即估計代價函數(shù)進行改進。在傳統(tǒng)的A*算法中通常采用曼哈頓距離、對角線距離或者歐幾里得距離等。因此算法傾向于搜索到目標點所在的高度方向，然后停止在高度上進行變化。如果繼續(xù)在高度方向搜索就會產(chǎn)生相應的代價。本文的估計代價函數(shù)的計算采用曼哈頓距離，并進行了改進。如公式（3）所示。當搜索到目標節(jié)點所在的高度之后，繼續(xù)往更高的方向上搜索就會產(chǎn)生“負”的代價。因此能夠使管路盡量在廠房上部布置。

2　核電廠工藝系統(tǒng)管路自動布局仿真

本文首先建立一個簡略的環(huán)境圖模型，根據(jù)設定的障礙和起始點進行管路搜索，以驗證A*算法的可用性。同時為了驗證A*算法在核電廠工藝系統(tǒng)管路自動布置中的適用性，本文根據(jù)核電廠廠房的實際環(huán)境建立仿真環(huán)境圖并應用A*算法進行管路搜索。

2.1　簡略環(huán)境圖模型

2.1.1模型介紹

為了驗證A*算法的可用性，本文選取一個簡單的環(huán)境圖模型進行驗證。簡單的環(huán)境圖模擬一個正方形廠房，在廠房的長、寬、高3個方向用柵格法進行離散。長和寬方向包含20個網(wǎng)格，高度方向包含10個網(wǎng)格。其平面圖如圖 1所示，圖中填充部分為建筑結構，4個實線的矩形為4個障礙物。高度方向第1層、第10層網(wǎng)格為廠房樓板。其中1、4號障礙物的高度為6個網(wǎng)格，2號障礙物的高度為4個網(wǎng)格，3號障礙物的高度為8個網(wǎng)格。以圖1的左上的網(wǎng)格為坐標（1,1,1）點。管路的起點坐標為（5,3,2），終點坐標為（18,14,5），估計代價的計算采用曼哈頓距離進行計算，在方案搜索中，直管前進一個網(wǎng)格的代價為1，1個彎頭的代價為1.6。在簡略環(huán)境圖中進行管路搜索時考慮一下約束：

圖1　簡略環(huán)境圖模型平面圖

（1）管路不穿越障礙物和墻體；

（2）管路的彎頭個數(shù)最少；

（3）管路中只采用90°彎頭；

（4）管路路徑最短；

（5）管路優(yōu)先在上部布局。

2.1.2計算結果

根據(jù)以上柵格環(huán)境模型，采用A*算法進行管路搜索仿真。計算結果坐標如表1所示。在三維圖中的管路如圖2所示。管路共包含7個90°彎頭，沒有穿過障礙物和墻體。管路搜索過程中，首先到房間頂部，到達目標點上方然后往下連接。滿足預先設置的管道布局要求。

表1　管路坐標

圖2　簡略環(huán)境圖模型管路圖

2.2　核電廠環(huán)境圖模型

2.2.1模型介紹

核電廠廠房環(huán)境相比前文中所述的簡略環(huán)境，有著更復雜的布置，更大的廠房面積并且需要考慮控制區(qū)等核電廠特有的區(qū)域。本文所建立的核電廠環(huán)境圖模型如圖3、圖4所示。圖3為核電廠廠房俯視圖，圖中點填充部分為建筑結構，圓形及矩形為設備，可以視為障礙物?；疑兩畛洳糠譃榭刂茀^(qū)。圖4為核電廠廠房立體圖。在核電廠中，不帶放射性的工藝系統(tǒng)管道盡量不穿過控制區(qū)，帶放射性的工藝系統(tǒng)管道盡量不穿過人員通行區(qū)。針對本文中，設定所搜尋的管路為不帶放射性的工藝系統(tǒng)。因此圖中灰色填充區(qū)域不可穿越。廠房的長為34.7 m，寬為30.0 m，高度為5 m。廠房的底板和天花板的板厚為0.5 m，圖3中圓形設備的高度為4 m，其他設備的高度為1 m。為了將圖中的障礙物盡量都沿著邊界劃分，本文在采用柵格法建立環(huán)境圖時，采用非均勻網(wǎng)格進行劃分，如圖5所示。以圖中左上為坐標原點，向右為軸正向，向下為軸正向。沿軸方向共有36個網(wǎng)格，沿軸方向共有45個網(wǎng)格。由于采用了非均勻網(wǎng)格劃分的形式，因此需要對評估函數(shù)的計算進行修改。在本文中，根據(jù)管路在網(wǎng)格布局的方向，選取相應方向的邊長進行權重。

圖3　核電廠房俯視圖

對于只有部分障礙物在網(wǎng)格中的網(wǎng)格，在本文中假定障礙物的體積超過網(wǎng)格的60%，即認為管路搜尋時此網(wǎng)格不可穿過。

此次管路搜索的起點和終點如圖3中紅色圓點所示。在圖5中對應的坐標為（6，36，3），（25，7，7）。在核電廠環(huán)境模圖模型中進行管徑搜索時考慮一下約束：

（1）管路不穿越障礙物（設備）；

（2）管路可以垂直穿過墻體，即管路不能在墻體內(nèi)布局；

（3）管路不穿越控制區(qū)；

（4）管路優(yōu)先在廠房上部布局；

（5）管路的彎頭個數(shù)最少；

（6）管路中只采用90°彎頭；

（7）管路路徑最短。

圖4　核電廠廠房立體圖

圖5　核電廠非均勻網(wǎng)格劃分示意圖

2.2.2計算結果

根據(jù)核電廠環(huán)境圖模型，采用A*算法進行管路搜索仿真，最優(yōu)計算結果坐標如表2所示，在核電廠三維圖中的管路如圖6所示。管路中共包含4個90°彎頭，沒有穿過廠房中的障礙物，避開了控制區(qū)，同時在管路布局中，優(yōu)先在廠房上部布置。滿足預先設定的廠房管路布局要求。

圖6　核電廠管路圖

表2　核電廠管路坐標

3　結論

（1）本文提出一種基于A*算法的核電廠管路自動布局方法。該方法首先通過柵格法建立電廠環(huán)境模型圖，在此基礎上通過A*算法獲取最佳管路，完成管路自動布局。最后通過仿真，獲取較好的結果，為核電廠工藝管道自動布局提供一種可行方法，促進了為核電廠數(shù)字化施工設計研究。

（2）目前本文能夠根據(jù)文中列出工藝系統(tǒng)管路布置要求，實現(xiàn)工藝系統(tǒng)單管道的自動布局。核電廠工藝管路布局可能有更多的約束，因此后續(xù)需要進一步研究更多約束條件下的自動布局。

（3）本文將符合約束條件的最優(yōu)結果進行輸出，可以在后續(xù)改進中輸出評價較高的幾個方案，根據(jù)布置工程師的經(jīng)驗進行篩選。

［1］ 董宗然．船舶管路自動布置方法及應用研究［D］．大連理工大學，2017.

［2］ Lee C Y.An Algorithm for Path Connections and Its Applications［J］．IEEE Transactions on Electronic Computers，1961，3（EC-10）：346-365.

［3］ Ito T.Implementation and evaluation for GA-based pipe route planning method［C］//Proceedings of European Simulation Symposium.2001：462-466.

［4］ Medjdoub B，Richens P，Barnard N.Generation of variational standard plant room solutions［J］．Automation in Construction，2003，12（2）：155-166.

［5］ Liu Q，Wang C.Pipe-assembly approach for aero-engines by modified particle swarm optimization［J］．Assembly Automation，2010，30（4）：365-377.

［6］ Dijkstra E W.A note on two problems in connexion with graphs［J］．Numerische mathematik，1959，1（1）：269-271.

［7］ Hart P E，Nilsson N J，Raphael B.A formal basis for the heuristic determination of minimum cost paths［J］．IEEE transactions on Systems Science and Cybernetics，1968，4（2）：100-107.

［8］ 張大船．專家系統(tǒng)在管道工程設計中的應用［J］．煉油設計，2001（01）：41-45.

［9］ 鄔君．基于協(xié)同進化的船舶分支管路空間布局優(yōu)化［D］．大連理工大學，2008.

［10］歐陽鑫玉，楊曙光．基于勢場柵格法的移動機器人避障路徑規(guī)劃［J］．控制工程，2014，21（01）：134-137.

［11］ Mansor M A，Morris A S.Path planning in unknown environment with obstacles using virtual window［J］．journal of intelligent and robotic systems，1999，24（3）：235-251.

［12］ Dechter R，Pearl J.Generalized best-first search strategies and the optimality of A［J］．Journal of the ACM（JACM），1985，32（3）：505-536.

Automatic Layout of Pipelines for Process Systems of Nuclear Power Plant Based on A*Algorithm

SU Jincheng，WANG Zhenzhong，JIA Xiaopan，XUE Jing，GU Zhenjie

（China Nuclear Power Engineering Co.，LTD，Beijing 100840，China）

Pipes layout of nuclear power plantprocess system is significant phase of nuclear power plant design.Number of pipes in process system is huge and there are many constraints for the layout of these pipes.The design layout of the process pipes is easily affected by the plant structure and the change of equipment location.The traditional manual piping routing of process system in nuclear power plant has become one of the factors that affect the design efficiency of nuclear power plant.Therefore，it is of great significance to work on automatic piping layout in nuclear power plant.Considering the plant size，radiation shielding and pipeline cost，according to the requirements of plant process piping layout，this paper adopted grid method to perform spatial dispersion and A*（A-star）method to perform process system pipeline search according to the characteristics of plant design and equipment location. Automatic pipe routing of the pipeline in plant process system has been simulated based on this method.The design schemes which are the results of the automatic piping simulation code are accord with the requirement of process piping layout.It is verified that this method can be used in process piping layout of nuclear power plant.

Process piping；Automatic piping；A*method

TL48

A

0258-0918（2022）01-0129-07

2020-12-12

蘇錦成（1990—），湖北黃岡人，工程師，碩士研究生，現(xiàn)主要從事核電廠布置設計相關研究