基于A*算法的核电厂工艺管道自动布局方法

苏锦成，王振中，贾小攀，薛静，谷振杰

基于A*算法的核电厂工艺管道自动布局方法

苏锦成，王振中，贾小攀，薛静，谷振杰

（中国核电工程公司，北京 100840）

核电厂的工艺系统管道布局是核电厂设计的重要过程之一，工艺系统管道数量庞大，约束条件众多，设计结果容易受到电厂结构和设备位置变更的影响。依靠人工对核电厂工艺系统管道进行布局已成为影响核电厂设计效率的因素之一。因此核电厂工艺系统管道的自动布局应用研究具有重要意义。本文针对核电厂工艺系统管道的自动布局问题，结合核电厂的厂房设备布局特点，考虑厂房大小、辐射屏蔽、管道成本等约束，依据核电厂工艺管道布局的要求，对核电厂厂房及设备采用栅格法进行空间离散，并采用A*（A-star）算法进行管路搜索。并基于此方法进行厂房主管道自动布局编程仿真，计算得出的主管道的自动布局方案能够满足模型设置的工艺管道的布局要求，验证了该方法在核电厂厂房工艺管道自动布局中的适用性。

工艺系统管道；自动布局；A*算法

工艺系统管道布局是核电厂厂房布置设计中重要的环节。为了保障核电厂的运行和安全，在核电厂中设置了几百个各种系统，这些系统的设备、部件采用管道进行连接。工艺系统管道的布局直接影响工艺系统功能的完整性，是核电厂安全运行的基础。核电厂工艺系统管道布局工作量巨大，需要耗费大量的生产成本。主要体现在以下几个方面：

（1）核电厂系统众多，为了保证核电厂安全，大量系统设备和阀门都采用冗余设计，因此管道数量大；

（2）核电厂厂房布局初步设计之后，管道设计高度依赖厂房的布局和厂房的功能分区。而现代厂房设计采用螺旋迭代设计方法，前期设计的方案在后续与其他专业迭代的过程中，通常会进行改进，进而会影响管路的布局。因此核电厂工艺系统管路布局经常会进行返工和迭代。

（3）核电厂由于其特殊性，为了保证设备的安全和可达性、操作人员的人生安全，管路布局需要遵守大量的规则和标准。

（4）目前核电厂工艺系统的管路布局主要依靠人工完成，管路布局设计的工程师需要熟悉厂房布局、系统流程、设备运行操作方式、约束标准等，需要经过长期的经验积累。并且存在人因失误造成管路布局不合理的风险。因此研究基于计算技术的核电厂工艺系统管路自动布局的方法，将工艺系统管路布置的标准约束和工程经验进行程序化，既能保证管路布局的合理性，同时能够减少管路布局工程师的设计负担，缩短设计周期，降低人因风险，对核电数字化具有重要的意义。

核电厂工艺系统管路布局属于复杂方案设计问题，属于布置问题的一种。自20世纪70年代开始，国内外学者在管路自动布局的相关理论和方法上进行了多年的研究，从二维空间的简单约束发展到三维空间内的多目标、多约束。管路布局优化的方法有很多，总体上可以分为：

（1）基于传统优化方法的管路布局方法；

（2）基于专家系统的启发式管路布局方法[1]。

对于传统优化方法的管路优化方法，Lee[2]于1961年首次提出了迷宫算法，迷宫算法主要是基于波的连续扩散原理。迷宫法的布通率高、适应性强，但所需容量大，操作速度慢，尤其当障碍物增加时，其复杂性会成倍增长。模拟退火、遗传算法[3]、蚁群算法[4]、粒子群算法[5]是典型的非确定性算法，寻优过程包含随机策略，结果没有严格的可重复性，算法收敛时间也不确定，参数的设定也是算法研究的关键环节，存在一定的局限性。Dijkstra E.W.于1959年提出Dijkstra算法[6]，该算法应用贪心搜索的策略，以起点为中心，向周边不断搜索。但该算法因探索顶点数目多，效率较低。Hart、Nilsson和Raphael于1968年提出A*算法[7]，该算法基于最好优先的策略搜索，A*在搜索过程中不断更新已形成路径代价和剩余路径代价，使搜索更具有目的性[1]。

对于专家系统[8,9]的启发式算法，将专家的知识及经验，采用数学函数表达进而用编程的手段实现。采用专家系统的模式联合开发并构建专家数据库，能够解决只有领域专家才能解决的问题。但是建立专家系统需要大量的专家经验及实际验证，相关研究目前还处于初步研究阶段。

管路自动布局的相关理论和方法上的研究从最初的工厂管路自动化设计，扩展到多个领域的自动化管路布置，包括航空发动机管路布置，集成电路走线布置，机电产品管路布置，船舶管路布置等[1]。但鲜有应用于核电厂工艺系统管路自动布局中。随着数字化核电的发展，更多的自动化，智能化的技术应用于核电厂的设计施工过程中，本文选取A*算法，A*算也成为A-star算法（下文简称A*），结合核电厂的厂房设计特点，考虑辐射屏蔽、管道成本等约束，依据核电厂工艺管道布局的要求，开展核电厂工艺管路的自动布局研究，促进核电厂设计数字化的发展。

1　管路自动布局方法

核电厂工艺系统的管路通常是连接设备或者阀门。为了保证自动布局的出一根无碰撞的合理的管路。将管道自动布局分为两步：

（1）根据核电厂的厂房布置特点、考虑辐射屏蔽、设备位置等因素，建立管路布置环境图。

（2）在环境图中采用搜索算法进行管路搜索。

1.1　环境图建模方法

核电厂工艺管道布置在厂房中，厂房的布置通常需要考虑厂房的功能和辐射屏蔽，既要保证系统功能，又要保证通行人员尽量少的受到辐射照射。因此厂房中通常包含大量的设备、人员通道和控制区。为了方便将厂房的实际物理环境转换为计算机可以处理的数字环境，本文采用由Howden W E提出的栅格法[10,11]，该方法通过栅格来表示环境地图，减少管路路径规划过程中障碍物边界信息处理时的计算量和复杂性，提高管路路径搜索的效率。

在本文中主要依据核电厂厂房控制区、内部设备、建筑墙体边缘来划分栅格，将核电厂的厂房的土建、设备、控制区等内容等效为栅格，其中设备、控制区等为不可穿行栅格，土建可以根据实际情况确定是否可穿行，在可穿行的栅格中进行管路搜索。

1.2　自动布局搜索算法A*

A*算法是经典启发式搜索算法，在搜索过程中加入评估函数，通过评估函数的引导减少搜索节点，进而提高搜索的效率。

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

目前A*算法中评估函数分为两个部分：

（1）从起点到当前节点目标节点的实际代价。其代价可以是路径长度、弯头的数量等；对于核电厂的工艺管道系统，其代价可以包括穿过控制区的长度。

（2）从当前节点到目标节点的估计代价，常见的估计代价的计算方式包括曼哈顿距离、对角线距离或者欧几里得距离等。A*算法的评估函数如式（1）所示。

1.2.2A*算法的基本流程

借鉴禁忌搜索方式，通常在A*算法中定义了两个节点集合，通常表示为CLOSED表和OPEN表。其中CLOSED表中存放搜索过的节点，OPEN表中存放搜索过节点的子节点。在搜索过程中，循环从OPEN表中选择估价函数最小的节点，直到找到目标节点，搜索停止。初始化之后，采用A*算法进行管路搜索，搜索流程为：

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

（2）判断OPEN表是否为空，若OPEN表为空，并且没有搜索到目标节点，搜索失败，程序退出；

（3）将OPEN表中节点估价函数值进行排序，并选取估价函数最小值的节点n作为最优节点，并从OPEN表中取出，放入到CLOSED表；

（4）判断当前节点是否是目标节点。若是，则表示求出一条最优管路路径，根据CLOSED表，输出路径节点编号并退出程序。若不是，则拓展到当前节点的后续节点+1；

（5）计算节点+1的估价值；

（6）如果节点+1已经在OPEN表中，并且节点+1的估价函数值小于OPEN表中估价函数值最小的路径，则将节点设置为+1节点的父节点，同时修正OPEN表中最小路径序列，并转到流程（2）；

（7）如果节点+1已经在CLOSED表中，并且节点+1的估价函数值小于CLOSED表中估价函数值最小的路径，则将节点设置为节点+1的父节点，同时修正CLOSED表中最小路径序列和最小估价函数值。将节点+1从CLOSED表中取出，放入到OPEN表中，并转到流程（2）；

（8）如果节点+1不在CLOSED和OPEN表中，则将其放入到OPEN表中，将节点设置为节点+1的父节点，并转到流程（2）。

1.2.3基于核电厂的评估函数改进

评估函数的改进主要是根据核电厂管路布局的约束条件来开展。通常对于管路布局的评价主要从经济性及安全性上开展：包含管路的总长度，管路的受力，管路穿过危险区的长度等。本文选取管路经济性为主要指标，即管路长度较小，同时管路布置方案采用较少的弯头个数。为了满足管路布局中弯头个数尽量最少，需要在实际代价函数中加入弯头的代价，本文采用式（2）的方式计算实际代价。

为了满足管路尽量在厂房上部布局，需要对A*算法的启发函数部分，即估计代价函数进行改进。在传统的A*算法中通常采用曼哈顿距离、对角线距离或者欧几里得距离等。因此算法倾向于搜索到目标点所在的高度方向，然后停止在高度上进行变化。如果继续在高度方向搜索就会产生相应的代价。本文的估计代价函数的计算采用曼哈顿距离，并进行了改进。如公式（3）所示。当搜索到目标节点所在的高度之后，继续往更高的方向上搜索就会产生“负”的代价。因此能够使管路尽量在厂房上部布置。

2　核电厂工艺系统管路自动布局仿真

本文首先建立一个简略的环境图模型，根据设定的障碍和起始点进行管路搜索，以验证A*算法的可用性。同时为了验证A*算法在核电厂工艺系统管路自动布置中的适用性，本文根据核电厂厂房的实际环境建立仿真环境图并应用A*算法进行管路搜索。

2.1　简略环境图模型

2.1.1模型介绍

为了验证A*算法的可用性，本文选取一个简单的环境图模型进行验证。简单的环境图模拟一个正方形厂房，在厂房的长、宽、高3个方向用栅格法进行离散。长和宽方向包含20个网格，高度方向包含10个网格。其平面图如图 1所示，图中填充部分为建筑结构，4个实线的矩形为4个障碍物。高度方向第1层、第10层网格为厂房楼板。其中1、4号障碍物的高度为6个网格，2号障碍物的高度为4个网格，3号障碍物的高度为8个网格。以图1的左上的网格为坐标（1,1,1）点。管路的起点坐标为（5,3,2），终点坐标为（18,14,5），估计代价的计算采用曼哈顿距离进行计算，在方案搜索中，直管前进一个网格的代价为1，1个弯头的代价为1.6。在简略环境图中进行管路搜索时考虑一下约束：

图1　简略环境图模型平面图

（1）管路不穿越障碍物和墙体；

（2）管路的弯头个数最少；

（3）管路中只采用90°弯头；

（4）管路路径最短；

（5）管路优先在上部布局。

2.1.2计算结果

根据以上栅格环境模型，采用A*算法进行管路搜索仿真。计算结果坐标如表1所示。在三维图中的管路如图2所示。管路共包含7个90°弯头，没有穿过障碍物和墙体。管路搜索过程中，首先到房间顶部，到达目标点上方然后往下连接。满足预先设置的管道布局要求。

表1　管路坐标

图2　简略环境图模型管路图

2.2　核电厂环境图模型

2.2.1模型介绍

核电厂厂房环境相比前文中所述的简略环境，有着更复杂的布置，更大的厂房面积并且需要考虑控制区等核电厂特有的区域。本文所建立的核电厂环境图模型如图3、图4所示。图3为核电厂厂房俯视图，图中点填充部分为建筑结构，圆形及矩形为设备，可以视为障碍物。灰色纯色填充部分为控制区。图4为核电厂厂房立体图。在核电厂中，不带放射性的工艺系统管道尽量不穿过控制区，带放射性的工艺系统管道尽量不穿过人员通行区。针对本文中，设定所搜寻的管路为不带放射性的工艺系统。因此图中灰色填充区域不可穿越。厂房的长为34.7 m，宽为30.0 m，高度为5 m。厂房的底板和天花板的板厚为0.5 m，图3中圆形设备的高度为4 m，其他设备的高度为1 m。为了将图中的障碍物尽量都沿着边界划分，本文在采用栅格法建立环境图时，采用非均匀网格进行划分，如图5所示。以图中左上为坐标原点，向右为轴正向，向下为轴正向。沿轴方向共有36个网格，沿轴方向共有45个网格。由于采用了非均匀网格划分的形式，因此需要对评估函数的计算进行修改。在本文中，根据管路在网格布局的方向，选取相应方向的边长进行权重。

图3　核电厂房俯视图

对于只有部分障碍物在网格中的网格，在本文中假定障碍物的体积超过网格的60%，即认为管路搜寻时此网格不可穿过。

此次管路搜索的起点和终点如图3中红色圆点所示。在图5中对应的坐标为（6，36，3），（25，7，7）。在核电厂环境模图模型中进行管径搜索时考虑一下约束：

（1）管路不穿越障碍物（设备）；

（2）管路可以垂直穿过墙体，即管路不能在墙体内布局；

（3）管路不穿越控制区；

（4）管路优先在厂房上部布局；

（5）管路的弯头个数最少；

（6）管路中只采用90°弯头；

（7）管路路径最短。

图4　核电厂厂房立体图

图5　核电厂非均匀网格划分示意图

2.2.2计算结果

根据核电厂环境图模型，采用A*算法进行管路搜索仿真，最优计算结果坐标如表2所示，在核电厂三维图中的管路如图6所示。管路中共包含4个90°弯头，没有穿过厂房中的障碍物，避开了控制区，同时在管路布局中，优先在厂房上部布置。满足预先设定的厂房管路布局要求。

图6　核电厂管路图

表2　核电厂管路坐标

3　结论

（1）本文提出一种基于A*算法的核电厂管路自动布局方法。该方法首先通过栅格法建立电厂环境模型图，在此基础上通过A*算法获取最佳管路，完成管路自动布局。最后通过仿真，获取较好的结果，为核电厂工艺管道自动布局提供一种可行方法，促进了为核电厂数字化施工设计研究。

（2）目前本文能够根据文中列出工艺系统管路布置要求，实现工艺系统单管道的自动布局。核电厂工艺管路布局可能有更多的约束，因此后续需要进一步研究更多约束条件下的自动布局。

（3）本文将符合约束条件的最优结果进行输出，可以在后续改进中输出评价较高的几个方案，根据布置工程师的经验进行筛选。

［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］ 张大船．专家系统在管道工程设计中的应用［J］．炼油设计，2001（01）：41-45.

［9］ 邬君．基于协同进化的船舶分支管路空间布局优化［D］．大连理工大学，2008.

［10］欧阳鑫玉，杨曙光．基于势场栅格法的移动机器人避障路径规划［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—），湖北黄冈人，工程师，硕士研究生，现主要从事核电厂布置设计相关研究