基于BIM信息和A＊算法改良实现工程线路线缆的自动规划与统计

■ 文/俞 洋

在电力设计中，目前已有方法可以进行基于距离的负荷自动分类，但如果仅使用欧几里得距离或者曼哈顿距离，并不能反映工程中的实际距离，因此，在负荷自动分类之前，应有方法可以测得所有负荷与电源之间的距离。

BIM 是一种可以对建筑附加信息的设计模式。在此种模式中，模型中的每样东西可以被赋予各种属性。各种工程问题可以利用其属性进行自动运算实现解决。

针对不同的专业，不同的问题。其需要赋予的属性是不同的，本文主要解决以下几个问题：在BIM 模型中需要录入的最少信息，A*算法应当如何改良适应工程应用，后续应用可行性探究，不足与展望。

1 工程背景

在电力工程中，有线供电是最常用的方式。路径规划应当综合考虑多种因素：路径距离应当尽可能短，隐蔽不影响美观，便于施工电缆抽动，便于检修等。路径规划完毕后，根据路径进行电缆的量取。电缆量大时，经常出现电缆错漏的情况，导致工程预算偏差大，现场无法施工等情况。这两项设计工作人工耗时非常久。本文提出一种路径规划的自动方法，使得工作耗时大大减少，提高了生产设计效率。

2 问题分析

在二维图中，求解两点之间的最优路径需要知道：两点所在的坐标和起始点的名称。因地图中有障碍物，对于图纸中的每一个块，需要一个“障碍”属性，或至少可以通过对实体的分类使用简单的逻辑推断其是否可通行。同时对于每一个块，应有办法碰撞检查。最短路径往往不是工程最优路径，会存在需要优先同行的地形和尽量避免的地形。因此，对于每一个可通行的物体（区域），算法和BIM 属性中应有能体现通行优先级的参数和方法。在路径规划中，应当尽可能减少弯折的次数，路径的规划应尽可能平直，避免电缆无法抽动。在电缆量取中，如当量非常大的时候，应当有方法降低计算复杂度，避免时间过长。

3 实现方法

电缆路径的规划变成计算机寻路问题，现有的寻路算法有很多，但每种都有局限性。经比较后，本文采用静态寻路中常用的A*算法，图1为A*算法说明。

图1 A*算法说明

图中底人字拼填充的为起点格，混凝土填充的为计算格，砖墙填充的为终点格，点划线占据的为周围格。斜线填充的为障碍物格。

针对当前计算格，垂直水平移动的代价距离为a，斜向移动的代价距离为

G 表示从起点到当前计算点的代价距离之和。

H 表示当前计算点到终点的估计距离（本文中为曼哈顿距离）。

F = G+H

Open 表示待计算的表格。

Close 表示已经计算过的表格。

A*算法具体伪代码本文不再赘述，读者可自行查阅资料。

4 问题

4.1 A*算法只寻找近路径

最短路径在实际工程中不可接受。当一个通路被障碍物横腰拦断时，为了走最短路径，A*算法规划的电缆路径会沿墙角密集施工3 个电缆井，导致施工过程中电缆难以穿行、运维困难。A*算法并没有要求网格是正四边形，亦可用正六边形或正三角形。但正三或正六边形会导致水平和竖直方向始终有一个无法走直线，不符合工程要求。虽然可以用算法平滑路径，但会影响线缆长度的计算。而使用正四边形，则可以通过调整代价G 值来影响电缆的走向，可以做到横平竖直的规划路径。正常情况，计算格周边的1、3、7、9 格的移动代价为计算格周边的2、4、6、8 格的移动代价为a。

为了使路径不走斜向，可以将1、3、7、9 格的移动代价设置≥2a，让计算机认为走斜向的代价超过走极轴。经过此番设置确实不走斜向，但是出现了新问题：无法一直沿极轴前进，原本走斜线的网格，因强制走极轴方向，路线变成了Z 字形，路线无端变长，无法用于工程。

因为如果前一格方向水平，后一格无论垂直还是水平其代价值均一样，所以应当加入判断：如果前两格与前一格处于同一列，则当前计算格周边的2、8 格的移动代价应小于4、6 格；如果前两格与前一格处于同一行，则当前计算格周边的4、6 格移动代价应小于2、8 格。

为了造成这种代价差异，一共有两种实现路径：方案1是单独增加水平或者垂直方向两格的移动代价；方案2 是先降低初始化时各方向的移动代价，然后再使水平方向和垂直方向的移动代价修改为正常移动代价。

经实验，方案2 会导致路径移动陷入局部最优解，故只能选用方案1。根据前两格和前一格的相对位置关系，最终生成的计算格移动代价如图2所示。

图2 计算框移动代价

其中，C 为常数，0＜C＜2a，当C＜0 时陷入局部最小值，当C ≥2a 时无解。本系数亦可通过乘法运算实现，但乘法容易导致权值混乱。

4.2 A*算法无法识别地形

A*算法只有障碍物和通路的区别，无法用于复杂的情况，缺少优先级，甚至会出现路径与马路重叠布置的问题。当车辆碾压通行时会影响供电安全。为实现A*识别地形，首先需要在BIM 工程中对地形进行标注。

4.2.1 A*算法实现二维地形识别及通行策略

对常见的具有通行策略的地形（下文简称“策略地形”）进行属性标注。

BIM 的标注要求：

（1）在总图中：围墙、建筑物、消防场地等应当标注，且可在后期通过简单布尔运算进行不可通行的设定。

（2）在室内：如果是已经布置好的平面，则仅需标注电缆沟与桥架为通路。如果是未布置好的平面，则需要标注剪力墙、防火门、结构柱、重要设备等，并通过布尔运算设置为不可通行。

为了加权，对A*网格再增加一个属性coefficient（权值）。即在地图初始化时其每个网格的权值默认为0，当地图需要优先通行时，其权值＞0；需要绕开通行时，其权值＜0。

实验发现，由于在前期为了极轴寻路已设置过权值，其系数的加权方法应与前期一致，否则会因为G 值的运算混乱出现各种奇怪结果。为保证G 值稳定，宜采用加法运算。在对于周围格进行迭代时。其F 值应当为F=G+H+权值，同样的-2a＜权值＜2a，否则会出现局部最优解。

4.2.2 寻路提前转向

经改良，当周围格出现具有通行策略的地形时，算法会优先通行。但实际中绿化带，马路等不一定在通行路径周围，甚至需要绕路实现路径美观，基于此本文提出如下方法。

（1）优化周围格搜索范围。A*周围格迭代的是8 个格子的FGH 值，为扩大搜寻范围，可以将周围格的计算步长改为3 格，同时为了降低计算量，只考虑水平垂直两个方向。如图3所示。

图3 优化搜索

这样，当在3 格范围内出现具有权值的地形时，会优先通行/避让。此方法在不显著增加算法复杂度的前提下可以实现提前转向。

（2）增加阶梯地势。在具有通行系数的网格周围，生成具有递减效果的权值，这个权值可以视作标高，等效成地形图。此方法尚未找到合适的电脑标记法，在极端情况下会出现多个局部最优解而无法找到路径。为了防止陷入局部最优解，需要对迭代次数进行限定，当迭代次数超过限定时，加入随机扰动或修改步长。

（3）优化地图抽象逻辑。在将地图抽象成网格的过程中，对于障碍物和有权值的网格，应该具有一像素原则。如果此网格内任一像素落在障碍物中，则此网格为障碍物格。如果此网格内任一像素落在策略地形中，则此网格为策略地形格。如果此网格内既有障碍物，又有策略地形，则此网格为障碍物格。如果此网格内既没有障碍物也没有策略地形，则此网格为普通网格，其权值为0。

经过优化后，扩大了障碍物的边缘，避免出现电缆井半径太大与障碍物冲突的问题。同时扩大了策略地形的面积，更容易被算法发现。

5 A＊转化为工程结果

5.1 分层级统计电缆长度

电缆网络图较为复杂，如果每一根电缆都用A*算法计算会导致计算量过大。工程中发现，不需要统计从电源到用户的电缆，因负载电压不同，每段电缆的规格不一样，需要分类分段统计。要求在BIM 当中标注每一个负载的电压等级。只量取相同电压等级之间的电缆长度。

5.2 转化为管网图的方法

将所有路径的网格求并集为管网图。

5.3 线缆长度量取：生成管网图

在同一个电压等级下，对于每一个实体起止点，需要知道其父实体。对父实体的起止点进行去重后，对其进行寻路。针对父实体有多个出入口的情况，对多个出入口之间进行H值排序，找到H 值最小的出入口作为寻路起始点。对于每一个父实体内部的电缆通路，套用模板典设或人工规划。将多个起止点的A*网格求并集结果为通路，将父实体内部的电缆通路设置为通路，其他网格均设置为障碍物，生成管网图。对于每一个起止点，在管网图中运行原版A*算法，可使得周围格的计算量降至原先的，运行速度大大加快。且因为G值为网格的真实代价，终点格的G 值长度即为电缆的真实长度。

6 不足与展望

6.1 无法解决最开始的需求

本文的初衷是要解决基于K 最近邻对负荷进行基于距离分类的距离选取问题，但如果对所有的负荷遍历寻找所有电源的可能路径，对算力的要求过高，A*算法虽然对于静态路径求解速度较快，但是遇到多起点多终点的情况时有些捉襟见肘。即为了分配负荷需要知道距离，为了减少距离的计算量又要求先分配负荷，可以考虑使用其他算法以降低计算量。对于该使用何种算法，还有待探究。

6.2 权值约束过多

在A*寻路的过程中，可以通过权值修改G 值使计算格按照设想的方向前进，但权值的选择约束过多。权值设置的太小，计算格的转向动力不足。权值设置的过大或地形过于复杂，会导致计算格陷入局部最优解。两者修改的权值应当与网格边长a 正相关，而不是一个固定常量。应结合工程实际，根据不同的工程设置不同的权值。建议采用增加十字搜索格结合修改策略地形的权值来实现提前转向。

6.3 G 值的其他可能

本文中仅采用加法系数来对G 值进行变动，也可以引入其他的决策算法来计算权重，或将G 值设定成为一种与地形相关的启发函数。

6.4 展望

本文可以广泛地应用在电力工程，以及设计管网道路规划均可使用本文方法。