基于优化A*算法的选煤厂管路自动布置

肖林京， 姚培鑫， 刘瑞， 马山清， 马成瀚

（山东科技大学 机械电子工程学院，山东 青岛 266590）

0 引言

选煤厂各车间为了完成水、药剂等介质的转运，需要布置许多管路，这些管路的布置是否合理直接影响选煤厂的正常生产和工艺运行[1]。目前选煤厂管路还是依靠人工设计，难度大、耗时长且管路布置质量难以保证[2]，提高选煤厂管路设计的效率和质量是目前亟待解决的问题。

许多学者针对如何提高管路设计的效率和质量进行了研究。黄波等[3]研究了基于SolidWorks 的选煤厂管道设计，提出了选煤厂管路三维设计方法，有效降低了管路设计的难度。 韩小恒等[4]研究了选煤厂管道3 维软件的二次开发应用，提高了管路设计的自动化水平。通过上述研究发现管路设计仍无法摆脱对人工的依赖，管路设计的效率和质量无法得到保证。因此实现三维空间内的管路自动布置对选煤厂管路设计有着重要的意义。通过查阅大量文献，发现目前针对管路自动布置的研究主要集中在非煤行业[5-8]，对选煤厂管路自动布置的研究较少。针对以上问题，本文提出了一种适用于选煤厂管路自动布置的优化A*算法。首先分析总结选煤厂管路布置过程中的规则约束，并对布局空间模型进行简化处理；然后对A*算法的评价函数、数据结构进行优化改进，引入方向导向策略，提高A*算法的适用性和运行效率；最后以SolidWorks 为主要开发平台，采用C#语言进行二次开发，设计选煤厂管路自动布置软件系统 ，便于设计人员更加直观地对管路自动布置结果进行评价。

1 管路布置规则与空间处理

1.1 布置规则

选煤厂管路布置的规则：① 路径尽可能短，保证路径与路径之间、路径与障碍物之间不发生干涉；② 路径尽可能沿着空间内壁或障碍物表面，并预留一定空间，需考虑路径在不同障碍物表面的设计要求；③ 要减少路径折弯次数，折弯角要为直角；④ 走向相同、距离较近的路径尽可能并排布置。

1.2 布局空间处理

选煤厂管路布局空间内部设备多样，在应用管路自动布置算法前，要对布局空间环境进行简化处理，剔除不必要的细节，提高算法的运行效率，布局空间的处理流程如下：

（1） 采用轴平行包围盒方法简化三维设备模型。将设备放置在一个已知的坐标系中，设设备顶点坐标的最小值和最大值分别为A（xmin，ymin，zmin），B（xmax，ymax，zmax），则以这2 个坐标点作为对角线构建1 个长方体，这个长方体就是简化后的设备模型。

（2） 将选煤厂空间按其长、宽、高的最大值简化为立方体结构的三维模型空间，用栅格法将简化后的三维模型和空间划分为边长为1 的网格，每个网格作为1 个节点。

（3） 选择简化模型空间的任一顶点作为笛卡尔坐标系的原点，对划分的网格赋予坐标值，以便描述管路和设备在空间内的位置。在此布局空间内，将某个节点所在行、列、层的位置定义为它的坐标。

（4） 网格划分完成后，对网格节点进行赋值，用来判定每个节点是否为管路路径可通行的节点，被障碍物占据的网格（不可通行节点）赋值为1，未被占据的网格（可通行节点）赋值为0。

2 优化A*算法

A*算法是一种典型的启发式搜索算法，主要解决静态网格最短路径搜索的问题[9-11]，A*算法的评价函数f（i）由实际距离函数和估计距离函数2 个部分构成。

式中：g（i）为初始节点到当前节点i的实际距离函数；h（i）为从当前节点i通过最佳路径到达目标节点的估计距离函数。

A*算法广泛应用于二维平面的路径规划问题，将算法应用到三维选煤厂管路自动布置问题中时，搜索出的路径不符合管路设计要求，因此需要对算法的评价函数、数据结构等进行优化。

2.1 评价函数优化

A*算法的实际距离函数g（i）只考虑了路径的距离代价约束，没有考虑到路径过程中折弯代价约束，路径会出现过多折弯，因此对实际距离函数g（i）进行优化。

式中：L（i）为距离代价，即单条选煤管路的总长度（以网格数计），当布局空间划分的网格边长为1 时，管路路径每向前延伸1 个网格，距离代价就要加1；B（i）为折弯代价，即单条选煤管路的折弯次数，管路路径每向前延伸1 个网格，就要判断该网格与路径中的前一网格是否形成折弯，若形成折弯，则折弯代价加1；a，b分别为L（i）和B（i）的权重系数。

估计距离函数h（i）是一个启发函数，由于选煤厂中弯管大多为直角，故采用曼哈顿距离作为启发式函数。假设在三维布局空间内路径起点s的坐标为（xs,ys,zs），中间节点i的坐标为（xi,yi,zi），终点n的坐标为（xn,yn,zn），则优化估计距离函数为

启发函数h（i）的大小决定路径的搜索方向和效率，路径搜索越接近终点，h（i）越小，h（i）在评价函数中所占的比例减小，会导致搜索的方向性变差，搜索效率变低。

在启发函数中引入静态权重系数，可提高启发函数h（i） 在评价函数中所占比重，提升A*算法的运行效率，但在路径搜索后期，会因搜索速度过快、搜索范围变小，算法出现陷入局部最优解而不能找到最优路径的问题。为了在保证路径质量前提下提升算法运行效率，在评价函数中引入动态权重系数γ，γ值随当前节点与目标节点的距离动态调整，γ∈[0，2]。路径搜索前期以快速接近终点为主要搜索策略，采用较大的γ值，以提高算法搜索效率；随着当前节点逐渐靠近目标节点，γ值逐渐减小，此时以扩大搜索范围、提高搜索精度为主。优化A*算法的评价函数f′(i)为

式中：m为障碍物在布局空间内所占网格数；M为布局空间总网格数。

2.2 方向导向策略

选煤厂管路设计时需避开高温、高压设备，与墙壁、设备预留一定空间；在振动筛、浮选机等设备附近布置管路（便于布置分支管路），以满足对介质输送的需求。在管路布置的过程中发现，上述优化后的A*算法搜索出的管路路径虽符合选煤厂管路布置的基本规则，但部分管路会绕行有需求的设备，导致选煤厂管路系统整体布局不符合实际工程应用需求。因此本文引入方向导向策略。

将整个布局空间划分为禁行区、需求区、通行区3 个区域。设备及其周围扩展2 个管径区域设为路径禁行区，权重值为1；有些设备对管路有特定的需求，在这些设备的禁行区外再扩展3～5 个管径区域，设为路径需求区，权重值为0，此区域对管路搜索有方向导向作用；将布局空间区域、管路起始点周围2 个管径区域设为路径通行区，权重值为0.5，此区域内管路可通行，但无方向导向作用。方向导向策略如图1 所示。

图 1 方向导向策略Fig. 1 Direction-oriented strategy

2.3 Open 表优化

A*算法在搜索中引入Open 表和Close 表来储存节点，Open 表存储所有已经生成而未被考察的节点，Close 表记录已访问过的节点，A*算法的关键在于对引入的Open 表进行维护[12-13]。A*算法的运行过程：移入（将扩展的节点移入Open 表）-排序-移出（移出Open 表），其中最耗时的是排序，排序的目的是找到Open 表中评价函数值最小的节点。

Open 表的数组结构如图2 所示，在进行排序操作时，A*算法有时会遍历整个Open 表，运行时间会随着Open 表存储量的增大而变长。为了提高A*算法的运行效率，将Open 表的数组结构替换为最小二叉堆结构[14-15]，如图3 所示，此时A*算法查找f（i）最小值时，只需寻找堆顶的节点，使得算法运行的效率更高。

图 2 Open 表的数组结构Fig. 2 Array structure of the Open table

图 3 最小二叉堆结构Fig. 3 Minimum binary heap structure

3 仿真分析

在Windows 环境下运用Matlab 软件进行仿真对照实验。在Matlab 环境中构建100 dm×100 dm×80 dm 的选煤厂空间，并将其等分为边长为1 dm 的方格，同时在空间内设置10 个障碍物，障碍物位置信息见表1，布局空间如图4 所示。

图 4 选煤厂布局空间Fig. 4 Layout space of coal preparation plant

表 1 障碍物对角坐标Table 1 Obstacle diagonal coordinates dm

在空间内设置3 段不同起点的待布置路径：路 径Ⅰ为Ps1（5,2.5,2.5）-Pn1（95,90,65），路 径Ⅱ为Ps2（60,20,10）-Pn2（15,50,20），路径ⅢPs3（90,90,65）-Pn3（60,50,55）用于仿真对照实验，其中路径Ⅰ起点与终点距离最远且中间障碍物分布最多，路径Ⅱ起点与终点距离较远但障碍物不多，路径Ⅲ起点与终点距离最近且障碍物最少。

3.1 评价函数优化前后对比

在路径Ⅰ上检验A*算法优化评价函数后管路布置的质量，管路仿真结果如图5 所示。可看出评价函数优化前管路存在过多的拐点，明显不符合选煤厂管路布置的规则约束条件；优化后的管路路径折弯次数减少80%左右，且折弯都为直角，该路径更符合选煤厂管路布置的实际情况。

图 5 评价函数优化前后仿真结果Fig. 5 Evaluate the simulation results before and after function optimization

为验证评价函数中权重系数对算法的影响，设置A*算法无启发函数（权重系数为0）、有启发函数但不赋予静动态权重（权重系数为1）、有启发函数并引入静态权重（权重系数为2）、有启发函数并引入动态权重（权重系数为γ）4 组对比实验，执行路径Ⅰ，Ⅱ，Ⅲ的布置，统计数据见表2。

由表2 可看出，A*算法没有启发函数时，在3 段路径上的搜索时间都远远超过其他3 组实验的运行时间，这说明启发函数对A*算法的运行效率有重要影响。对比A*算法不赋予静动态权重与引入静态权重时的管路布置结果可知，A*算法引入静态权重后，在3 段路径上算法的运行时间都明显缩短，但管路长度、评价函数值增大，折弯次数增多，这说明A*算法引入静态权重后，效率提升，但管路布置的质量在降低。对比A*算法不赋予静动态权重与引入动态权重时的管路布置结果可知，A*算法引入动态权重后，在3 段路径上的运行时间都短于不赋予静动态权重情况，且管路长度、评价函数值、折弯次数与不赋予静动态权重情况基本相同，这说明A*算法引入动态权重后，运行效率提升且能保证管路布置质量。

表 2 权重系数对A*算法的影响Table 2 Effect of the weight coefficient on the A* algorithm

3.2 引入方向导向策略前后对比

在其他条件不变的情况下，验证算法引入方向导向策略对管路布置的影响。假定图4 中障碍物2-6 为对管路有特定需求的设备，执行3 段管路路径布置进行仿真对照实验，引入方向导向策略前后管路路径布置结果如图6 所示。可看出引入方向导向策略前后3 段管路路径长度并无变化，都满足选煤厂管路布置的基本约束规则；引入方向导向策略后的管路更倾向于在对管路有特定需求的设备附近规划，管路有并排布置的趋势，这说明方向导向策略引入后管路的布置满足整体布局最优的要求，更符合选煤工程应用需求。

图 6 引入方向导向策略前后管路路径对比Fig. 6 Comparison of pipe paths before and after introducing the direction oriented policy

3.3 Open 表优化前后对比

为了便于对比，将优化A*算法的参数统一设置为a=1，b=10，γ=1，仅考虑搜索最短路径，Open 表优化前后3 段管路路径布置时间如图7 所示。可看出Open 表优化后算法的效率明显提高；管路路径越长、中间障碍物越多，算法效率提高越明显。

图 7 Open 表优化前后算法运行时间对比Fig. 7 Comparison of algorithm operating time before and after Open-List optimization

4 应用实例

设计并开发选煤厂管路自动布置软件系统，对优化A*算法进行验证。将通过Matlab 开发的算法封装为dll 文件，在Visual Studio 平台使用C#语言调用封装的dll 文件对SolidWorks 软件进行二次开发，创建可进行人机交互的WinForm 窗体应用，实现选煤厂管路布置系统智能化设计，系统由土建环境、设备布局和管路布局3 个部分构成。

在土建环境界面（图 8）对选煤厂内部环境进行参数设置，搭建进行管路自动布置的布局空间，界面右侧使用C#.net 程序调用Matlab 窗口显示实时仿真结果。

图 8 土建环境界面Fig. 8 Civil environment interface

在设备布局界面（图 9）对选煤设备进行参数化建模后，置入搭建的三维空间，实现选煤厂内部设备的智能布局。运用SolidWorks 软件建立选煤设备的三维模型库，然后采用编程法和尺寸驱动法相结合的方式对选煤设备及其零部件进行参数化设计，通过WinForm 窗体界面实现驱动参数的更新，从而生成新的模型。在选煤设备三维模型库基础上，进行设备的智能布局。首先选择待布置设备及其型号，将其保存到指定的文件夹，完成设备的参数化设计过程；然后输入该设备在选煤厂布局空间内的位置坐标，点击“更新设备布局”按钮完成设备的布局。

图 9 设备布局界面Fig. 9 Device layout interface

最后进入管路布局界面（图10），在该界面内选择管路的起点和终点。选择“管路起点”或“管路终点”框体时，程序会遍历三维布局环境中所有设备的出水口或入水口（利用SolidWorks Routing 插件提前建立），然后自动抓取三维空间中连接点并将其显示在“起点”和“终点”后的2 个下拉列表中，用户选择结束后，点击“管路布局”按钮即可实现管路布局的自动设计，三维设计效果如图11 所示。

图 10 管路布局界面Fig. 10 Pipe layout interface

图 11 三维设计效果Fig. 11 3D renderings

5 结论

（1） 对A*算法的评价函数进行优化，优化前的管路存在过多拐点，优化后的管路路径折弯次数减少80%，且折弯都为直角，更符合选煤厂管路布置的实际情况；评价函数引入静态权重后，A*算法的效率提升，但管路布置的质量降低，A*算法引入动态权重后，运行效率提升且能保证路径质量。

（2） 引入方向导向策略后的管路更倾向于在对管路有特定需求的设备附近规划，管路有并排布置的趋势，这说明引入方向导向策略后管路的布置满足整体布局最优的要求，更符合选煤工程应用需求。

（3） Open 表优化后算法的效率明显提高；管路路径越长、中间障碍物越多，算法效率提高越明显。

（4） 设计并开发选煤厂管路自动布置软件系统，对优化A*算法进行验证。验证结果表明，优化后的A*算法提高了选煤厂管路设计的效率和质量，且具有更好的可视性。