基于改进A＊算法的三维智能布线技术研究＊

朱永辉 张胜文 支辰羽 罗瑞旭 李 坤

（江苏科技大学机械工程学院，江苏 镇江 212003）

线路设计是机电类产品设计制造过程中不可缺少的关键环节，线缆作为机电类产品的神经，担负着联系控制系统、配电箱、照明灯、空调和通风扇等电子设备的重任。随着机电类产品向大规模定制的方向不断发展，其布线结构与布线路径也越发复杂多样，线缆设计对产品性能和可靠性的影响也越来越大[1]，线缆的布设质量直接关系着机电类产品的安全性和功能性。

传统的布线设计过程主要通过二维CAD 图纸完成电路设计以及规划出线路的进出口，线缆路径由工艺人员在实际布线时根据产品的装配结构以及个人经验进行设计，并根据布线的实际情况对结构设计问题进行反馈，反推设计人员优化结构设计，属于边生产边修改的设计方法[2]。这种线路设计方法严重滞后被动，布线操作难度大，缺乏指导性，同时会增加产品研发周期，不适用于大规模定制趋势下的产品线路设计。因此，研究三维环境下的智能布线方法尤为重要。

随着计算机辅助设计技术与软件的不断发展，国内外专家对线路设计技术的研究也愈发深入。Conru A B 等[3]通过遗传算法对线缆的最优路径进行求解，同时采用并行工程的方法进行布线设计。Ilknur K 等[4]提出了使用随机路径图法计算布线路径的路径规划算法以应对针对复杂环境下的布线问题。蔡毅等[5]通过综合“迷宫法”“线搜索法”等搜索算法和路径干涉理论，提出了“按面自动布线”和“贴壁干涉自动调整”的方法，但对于布线环境复杂，布线路径多的产品适用性差。吴保胜等[6]提出了一种基于改进蚁群算法的线缆路径规划方法，通过分段式空间划分和栅格化处理获取三维布线路径的规划空间，但线缆路径基于自由空间生成，不适用于规定了走线通道的复杂产品的布线。李春泉等[7]提出了基于轮廓扩展法和改进RRT 算法实现了回转空间内电气线缆的自动布线。综上可知，三维布线技术的核心在于线缆路径的智能规划，而现有研究成果主要适用于自由空间的线路规划，不适用于具有特定走线空间的大规模复杂机电类产品的线路规划。

本文针对上述问题，在上述学者研究的基础上提出了一种基于SolidWorks 平台的三维智能布线方法，通过改进A*算法进行线缆的路径规划，并提出了一种基于通道网络的布线空间构建方法，约束布线路径的生成，保证布线路径的正确性。同时通过SolidWorks 二次开发，开发出了相对应的布线系统，实现了特定走线空间条件下的三维线缆智能布路，验证了该三维智能布线方法的可行性。

1 方法介绍

为实现三维设计环境下电气线缆的智能布线，本文基于SolidWorks 平台进行三维智能布线技术研究，提出了一种三维智能布线方法，其布线流程如图1 所示。

图1 SolidWorks 智能布线流程

本文提出的布线方法主要包括前期准备、线缆智能敷设和报表输出3 个环节。

（1）在前期准备环节中，要对产品三维模型和电气零部件库的进行创建与装配，并将线槽，PVC 管等走线通道以及锚定线路起点和终点的电器元件装配到需要布线的三维实体模型中，搭建出三维布线的基础环境。

（2）线缆智能敷设主要包括走线空间定义、走线路径智能规划、三维线缆敷设3 个部分。通过路径搜索算法智能规划出最优的走线路径，并通过定义走线空间约束路径搜索的范围，保证走线路径规划的正确性，同时在SolidWorks 平台基于走线路径生成线缆的三维实体模型，完成三维线缆敷设。

（3）报表输出环节主要是将线路的起点与终点、线缆型号、线缆长度以报表的形式输出，用于指导生产。

2 关键技术

2.1 布线空间定义

在三维布线设计过程中，产品三维实体模型与其内外部空间构成了基础的布线环境，同时产品三维实体模型也作为线缆布路的空间障碍物，为了防止生成的线缆路径与产品实体模型产生干涉，首先需要对线缆的可布线空间进行定义，即确定可进行路径搜索的范围。

现有研究对于布线空间的定义方法普遍采用包围盒技术（bounding box, BB），是三维物体干涉检测中常用的一种检测方法，其主要策略是用体积较大的简单形体近似地表达外形较为复杂的集合对象形体，然后对包围盒进行相交检测，求解出自由空间和障碍物空间，将自由空间作为布线空间[8]。但在大型复杂机电类产品中，在结构设计阶段已经布置了线槽、PVC 管和走线矩管等型材用于布线，即产品的布线通道是确定的，通过包围盒技术求解出的布线空间过于宽泛，因此该方法定义的布线空间与实际的布线空间很大程度上不相符，导致路径搜索算法规划出的走线路径不符合要求。

针对上述问题本文提出了基于通道网络的布线空间定义方法，保证了布线空间定义的正确性，其流程如图2 所示，具体步骤如下。

图2 布线空间定义流程

步骤1：在布线环境中通过3D 草图沿线槽、PVC 管等走线通道的中心绘制出如图3 所示布线通道网络，定义出通道走向。

图3 布线空间定义示意图

步骤2：以走线通道网络为中心轴线，将其一定范围内的空间定义为布线空间，如图3 所示。

步骤3：将定义出的布线空间划分成一个三维空间点集合，便于后续路径搜索使用。

在空间划分的方法中，栅格法是目前最简单、常用、便捷的一种方法，其采用空间等分的方法将立方体空间栅格化，将三维空间离散化成路径搜索所需的一个三维空间点集合，如图4 所示。

图4 布线空间栅格化示意图

2.2 布线路径规划

路径规划是指在有障碍物的工作环境中寻一条从起点到终点、无碰撞地绕过所有障碍物的运动路径的过程[9]。布线路径的智能规划是研究三维智能布线技术的核心问题，研究布线路径路规划最重要的就是要保证布线路径的正确性与合理性，同时要考虑线缆与布线空间内其他障碍物以及与其他线缆之间的干涉问题。

本文提出的三维智能布线方法中布线路径的智能规划通过路径搜索算法自动完成。

在现有路径搜索算法中，A*算法是最有效的直接搜索算法之一，其具有可纳性和最优性[10]。但是在实际的线路设计过程中，对线缆的折弯长度以及折弯次数都有着一定的要求，使得A*算法难以被直接应用，因此本文针对这一问题对原始A*算法进行了改进和拓展，使其获得了更高的适用性。

2.2.1 A*算法估价函数改进

A*算法结合了Dijkstra 算法和BFS 算法的优点，将Dijkstra 算法靠近终点的节点和 BFS 算法靠近目标点的节点的信息结合起来，并引入了估价函数对搜索的位置节点进行评估[11]，该估价函数一般为

式中：f(n)为节点n的估价函数，表示从初始节点经过节点n到目标节点的最佳路径的代价；g(n)表示在状态空间中从初始节点到节点n的代价；h(n)为从节点n到目标节点的最短路径的估计代价[12]。

通常设定h(n)计算常用的启发式估价函数为欧几里得距离函数（ELDF），ELDF 是指在m维空间中两个位置节点之间的真实距离，二维平面中ELDF 的计算公式为可表示为

结合实际电气布线经验，在布线路径规划时要考虑到线缆折弯所带来的损耗问题，因此通过对A*算法的估价函数进行改进，引入第3 个评估因子q(n)，用来表示从起始节点到达当前节点n的折弯损耗[13]，改进后估价函数为

式中：k为每次折弯损耗转换成的距离；N为从初始节点到节点n的折弯次数。

A*算法作为1 种二维平面上的路径搜索算法而被广泛应用于AGV 小车线路规划、游戏地图等问题上。而本文研究的三维智能布线技术，布线路径规划都是基于三维实体空间进行可行路径的搜索工作，因此需要将A*算法的适用范围由二维向三维拓展，拓展后的h(n)计算方式为

2.2.2 A*算法求解流程改进

改进A*算法对最优路径进行求解需要通过3 个基本空间点集：Open 表、Close 表和Lattice 表。其中Open 表用于存放当前节点可用的相邻节点，Close表用于存放求解出的符合要求的路径节点，Lattice表储存本文章节2.1 中定义的走线空间经过栅格化后划分出的所有可用空间节点。改进A*算法在原A*算法求解流程上新增Lattice 表，约束路径点的搜索范围，保证了路径搜索的正确性与效率。改进A*算法流程如图5 所示，其具体求解步骤如下：

图5 改进A＊算法流程图

步骤1：将起始节点S设置为当前节点M。

步骤2：判定当前节点M是否为目标节点O，若当前节点M是目标节点O，则将前节点M放入Close 表中并输出Close 表中所有节点，组成布线路径。若当前节点M不是目标节点O，则转至步骤3。

步骤3：从Lattice 表循环搜索当前节点M的所有邻居点并计算各个邻居点的f(n)值，同时将搜索出的所有近邻节点加入Open 表中。

步骤4：将当前节点M从Open 表中删除，放入Close 表。

步骤5：将Open 表F值最小的邻居点设置为当前节点M，并删除其他邻居点，转至步骤2。

步骤6：循环步骤2 至步骤5，直至求解出的当前节点M为目标节点O，则将Close 表中所有节点按搜索的顺序排列即可得到最优路径。

2.3 三维实体线缆敷设

三维实体线缆敷设是指在虚拟环境下通过建立线缆实体模型的方法来实现对三维空间中线缆姿态和属性的表达和可视化的一种方法。三维环境空间下的线缆实体模型包含几何特征和信息属性[14]。

2.3.1 几何特征

线缆几何特征包括线缆的几何形态、颜色、粗细等信息，线缆几何模型的建立主要是通过数字化手段完成对线缆几何特征的可视化描述和表达。

在SolidWorks 二次开发中，三维模型驱动方法有编程法和尺寸驱动法。本文线缆几何模型的构建采用编程法，通过VB.net 编程语言对SolidWorks进行二次开发来实现。

编程法是将三维模型的所有建模操作和特征的参数关系都按照固定的顺序的编写成相应的程序，平台按照程序规定的建模过程逐步执行相应的操作，完成三维模型的生成。这种方法每生成或更新一次模型都需要从头至尾执行一次应用程序代码[15]。

2.3.2 信息属性

在实际的产品设计过程中，线缆都有着不同的线缆信息用于线缆间的彼此区分，线缆信息属性包括线缆的名称、编号、型号和材质等，为方便对线缆信息进行统一的储存、组织和管理，本文通过数据库构建相应的线缆信息库，用于线缆信息的管理，便于将数据库表中的线缆信息赋予对应的线缆的几何模型。

2.3.3 线缆模型构建

通过对线缆几何特征的创建和信息属性的填写，能够构建出符合需求的线缆三维实体模型用于指导生产。通过对SolidWorks 模型驱动与属性赋值等API 函数的应用，结合本文2.2 节中所述的改进A*算法的求解结果提出了如图6 所示的三维实体线缆敷设流程，具体步骤如下：

图6 三维实体线缆敷设流程

步骤1：根据求解出的Close 表中的路径点，通过SolidWorks 二次开发，在布线空间中生成中心轴线。

步骤2：根据线缆信息库中线缆相对应的直径和颜色，沿线缆三维中心轴线生成线缆几何特征模型。

步骤3：按照线缆信息库中线路编号和线缆型号给线缆几何模型添加相对应的线缆属性。

3 实例验证

本文基于上述三维布线关键技术的研究，通过Visual Studio2019、SolidWorks2020、SQL Server2008协同开发，基于SolidWorks 平台开发了相对应的三维智能布线系统，用于验证本文提出的三维智能布线方法可行性与实用性。

本文以机柜布线为例对该布线系统及方法进行了验证，首先根据机柜内部线槽的摆放，通过3D草图绘制出如图7 所示的机柜的布线通道网络。

图7 布线通道草图网络绘制

布线通道网络草图绘制完成后，打开三维智能布线系统，进入如图7 所示的布线空间定义界面，在该界面选择布线通道网络并根据输入的通道直径，定义相对应的布线空间，通过栅格法根据人工定义的划分密度对该布线空间进行空间划分，获取如图8 所示的布线空间路径点集，并放入Lattice 表中供后续路径搜索使用。

图8 布线空间定义与划分

布线空间定义完成后，选择如图9 所示的线路设计界面，根据需求定义线路的编号、起始点、终点和线缆型号。布线系统后台程序根据定义的线路起始点，驱动改进A*算法在图8 所示的Lattice 表中进行路径点的搜索，求解出每条线路的最优路径，并将路径点放入相对应Close 表中。通过选择图9中线路列表中定义的线路，可在最优路径点集区域显示求解出的相对应最优路径点集。

图9 线路设计

线缆路径规划完成后，点击轴线创建按钮，系统根据求解出的每条线路对应Close 表中的路径点生成如图10 所示的线路中心轴线，点击线缆创建按钮，根据线路所用线缆的直径和颜色沿线路中心轴线生成如图11 所示的线缆三维实体模型。

图10 线路中心轴线生成

图11 线缆三维实体生成

线缆敷设完成后，在如图12 所示的报表输出界面，可查看线路相对应的线缆信息报表，包含线路的连接关系、线缆长度的信息。线缆信息报表见表1。

表1 线缆信息报表

图12 改进A＊算法流程图

4 结语

本文针对三维环境下的智能布线技术展开了研究，提出了一种基于SolidWorks 的三维智能布线方法，并通过对A*算法的改进和布线空间定义新方法的应用，结合SolidWorks 二次开发技术开发了相应的三维智能布线系统，并通过实例验证了该方法的可行性。结果表明，基于此三维智能布线方法开发的布线系统能实现布线路径的快速智能规划以及三维实体线缆的快速敷设，极大地提高设计效率、降低成本，具有很高的现实使用价值。