基于改进A*算法的机电产品线缆布设

程倩

摘要：

为了实现多约束条件下机电产品线缆布设的智能化和自主化，提出了改进A*算法的机电产品线缆布设方法。分析了机电产品布设线缆时的约束条件，对机电产品建立了三维点云模型；介绍了传统A*算法原理，为了适用于三维机电产品模型，将此算法扩展到三维空间；划定工艺约束影响区域并赋予权值，节点权值大小代表此点作为路径的工艺优劣；将工艺约束权值引入到代价函数，使算法能够兼顾路径最优和工艺约束；仿真实验表明，改进A*算法能够在考虑多约束条件下，实现线缆布设的最优化，实现了机电产品线缆布设的智能化和自主化。

关键词：机电产品；线缆布设；改进A*算法；工艺约束权值

中图分类号：TP391、TN958.92 文献标志码：A

文章编号：2095-5383（2018）02-0025-05

Cable Laying of Mechanical and Electrical Products based

on Improved A* Algorithm

CHENG Qian

（Business and Electronic Information Department， Tongcheng Normal College， Tongcheng 231400， China）

Abstract：

In order to realize the intelligence and automation of mechanical and electrical products cable laying under multiple constraints， the cable laying method of mechanical and electrical products based on improved A* algorithm was proposed. The constraints of mechanical and electrical products cable laying were analyzed， and 3dimentional point cloud model of mechanical and electrical products was built. Traditional A* algorithm was introduced， and this algorithm was expanded to 3dimentional space. Influence area of technology constraints was delimited and the weight of point was given. The weight size of point respects technology quantity as path. The weight is introduced to cost function， so that the algorithm can balance the optimal path and technology constraints. By simulation trials， the improved A* algorithm can find the optimal path of cable laying with multiple constraints and realize intelligent and automation of mechanical and electrical products cable laying.

Keywords：

mechanical and electrical products； cable laying； improved A* algorithm； technology constraints weight

随着技术的发展和高新技术的使用，机电产品越来越复杂，线缆作为能量和信号的传输媒介，其布设也越来越复杂。但是线缆在机电设计中呈现“傻大笨粗”形象，说明线缆布设技术的发展没有受到应有的重视，从而使其发展远远落后于机械加工、软件和硬件的发展。

线缆布设问题的研究早期主要集中在理论上，学者包括Koch等[1]、Mascagni[2]、Abbasi等[3]。近年来的研究重点开始转向实际应用，黄训诚等[4-5]将粒子群算法和蚁群算法应用在布线设计上取得了较好效果；付宜利等[6]使用粒子群算法实现了单根管道的自动布设；陈世明等[7]使用粒子群算法实现了三维有障碍空间的点对点最优规划。但是这些单一路径规划或布设问题，无法解决线缆捆扎结构问题，因此本文在考虑线缆布设时避免悬空、避开热源和电磁干扰等多约束条件下，对机电产品线缆布设进行优化，将传统A*算法扩展到三维空间，提出引入工艺约束权值的代价函数，最终得到了多约束条件下的路径最优规划，实现线缆布设的智能化和自主化。

1 布线环境空间建模

1.1 布线工艺约束

在机电产品线缆的实际布设中，要考虑很多工艺约束问题，并将这些约束条件在环境建模或算法实现中，从而使线缆布设方法真正达到实用要求。典型的工艺约束[8]包括以下6个方面：1）线缆尽量贴近实体壁，尽量避免悬空，便于捆扎；2）线缆的路径尽量避开热源、电磁辐射源、避免烧坏和干扰；3）路径尽量避开钣金和尖锐角，避免割坏线缆；4）路径宽度必须大于线缆直径，才有足够空间容纳线缆；5）线缆束过孔时要加保护套保护线缆；6）考虑振动等防止线缆脱落。

不同约束条件针对不同的零件，比如热源是指电池、加热丝等发热部件，电磁辐射源指电磁计等。本文将这些可能影响线缆布设问题的部件称为工艺结构，在环境建模時，对不同的工艺结构赋予不同属性值进行区分。

1.2 布线环境建模

本文使用点云法对线缆布设的三维空间进行建模，将线缆布设空间离散化。对环境中的点云分为一般空间点、无工艺障碍点、热源点、电磁辐射点、锐边等，其中一般空间点是指空间位置，无工艺障碍点指机电产品的一般性结构件，热源点、电磁辐射点、锐边则是布线时尽量避开的工艺障碍点。为了使算法能够区分这些点云，依据点云位置特点赋不同的属性值，本文中将一般空间点赋值为0，无工艺障碍点为3，热源点为4，电磁辐射点为5，锐边为6。

记机电产品三维模型的包络长宽高分别为lx×ly×lz，X轴上点云数量为nx，则点云间距为a=lx/nx。在机电产品三维模型中阵列以a为间距、以φ为直径的圆球。要求路径宽度必须大于电缆直径，因此点云间距a不小于线缆束直径。然后将整个三维模型按照1：a进行缩放，得到圆球之间距离1的三维模型。以圆球球心所在位置为标准进行属性赋值，在此需要强调的是一个圆球未必只有一个属性值，若圆球所在位置既是热源也是电磁辐射源，则需要赋两个属性值。

以图1所示的机电模型为例，图中灰色部分表示普通工艺结构，红色部分为热源，黄色部分为电磁源。

2 传统A*算法

A*算法[9-10]是融合了Dijkstra算法和最佳优化算法优势的智能算法，它既有Dijkstra算法的贪心性，也具有最佳优化算法的启发性，也就是说此算法兼顾了搜索时间和搜索空间。

A*算法的原理是在周围相邻的点云中，选择估价函数最小的节点作为下一步路径，若周围节点中估价函数最小值节点不止一个，则选择最近一次搜索到的节点。A*算法的关键在于估价函数的设计，传统A*算法的节点估价函数为

f（n）=g（n）+h（n） （1）

式中：g（n）为从起始点S到当前节点n的最小代价；h（n）为从当前节点n到目标点T的最佳路径代价估计； f（n）为对当前节点n的估价值。其中h（n）的设计对算法性能影响最大，记当前节点n到目标点T的真实最小代价为h（n），当h（n）≤h（n）时，就能保证算法找到最优解；但是为了保证算法求解效率，要求h（n）不能比h（n）小太多，所以h（n）的設计是A*算法的关键。

在A*算法中用到2个集合，记为Open集合和Close集合，其中Open集合存储待计算的节点信息，Close集合用于存储被选择的节点信息。在点云环境中使用A*算法，首先选择当前节点的相邻节点存入到Open集合中，计算每个节点的估价值并比较，选择估价值最小的节点作为下一步节点，将此节点存入到Close集合的同时释放Open集合，重复此过程就完成了线缆路线选择，最后从Close集合中导出线缆路径。

3 改进A*算法的线缆布设方法

3.1 二维A*算法扩展为三维

本文研究的是机电产品线缆布设问题，机电产品模型为三维模型，线缆布设环境为三维点云环境，而传统的A*算法只适用于二维平面路径规划问题，因此首先将A*算法扩展到三维空间。由于环境空间由二维变为三维，所以当前节点的相邻节点数由8个增加为26个，如图3所示。从图3可以看出，相邻节点距离不同，同轴节点距离为1.0，平面对角节点距离为1.4，空间对角节点距离为1.7。

3.2 代价函数设计

本文对机电产品线缆布设问题，在满足工艺约束条件下，以线缆距离最短为优化目标，因此代价函数选择一种距离计算方法。当前距离计算方法有曼哈顿距离、对角线距离、欧几里得距离等。

上文中提到h（n）对算法性能影响很大，h（n）数值大时会提高算法搜素效率，但是此时算法搜索范围小，很容易陷入如图4所示的U型陷阱。因此h（n）的选择在搜索效率和搜索范围上是矛盾的。

3种距离算法中，欧几里得距离最小，可以有效避免U型陷阱，但是算法效率最低；曼哈顿距离最大，但是可以通过改变系数k的数值进行调节。当环境复杂且时间要求不高时，将系数k设置大一些，以牺牲时间来求取最优路径，当环境简单时将系数k设置小一些就可以得到最优路径。因此本文代价函数采用曼哈顿距离乘以系数k，依据环境复杂度调节系数k大小，就能够兼顾算法的搜索空间和搜索效率。

记线缆路径当前节点为m，周围待搜索节点为n个，则代价函数f（n）设置为：

式中：g（m）为起点到当前节点m的代价值；（xm，ym，zm）为当前节点三维坐标；（xn，yn，zn）为待搜索节点三维坐标；（xgoal，ygoal，zgoal）为目标点三维坐标，为曼哈顿距离；k为权系数。

3.3 引入工艺约束权值代价函数

本文引入工艺约束权值的代价函数，工艺约束权值用于表征节点作为路径的工艺优劣，工艺约束加权规则如图5所示。

图5中绿色点云为空间点，灰色区域为普通障碍点，红色为热源，黄色为电磁辐射源。首先对所有空间点赋初始权值value=b，普通障碍点的权值影响范围为以物体边缘为圆心、以r1为半径的区域，此区域空间点权值在初始权值上叠加b1，热源、电磁源权值范围与此一致，分别叠加权值b2、b3，若空间某点在多个权值影响范围内则将这些权值相加，即value=b+∑li=1bi，式中l为节点受权值影响数量。若节点的工艺特征适于布线则权值取为负数，若不适于布线则取为正数，因此节点越适于布线则其综合权值越小。权值大小可以调整工艺约束的大小，比如在雷达等强电磁环境中，就可以增大电磁源权值b3，表示主要考虑避开电磁源这一约束。

经以上分析，本文引入工艺约束权值的代价函数为：

式中；wA为A*算法的公益性约束。通过调整wA与k值，就可以调整距离优化与工艺约束对算法的影响程度。

4 仿真实验

4.1 环境建模

给出如图6a所示机电产品三维模型，三维结构包络体积为30×30×15，线缆最大直径为1。建模所用参数为a=1.5、φ=0.1，得到其点云模型如图6b所示。建模后起点坐标为（10，2，3），终点坐标为（10，19，5），缩放后得到20×20×10的三维点云模型。

4.2 算法验证

本文对算法的改进包括两个方面：一是将算法扩展为三维，二是引入了工艺约束权值value。因此，对算法的验证就是通过改变value值来验证不同工艺约束对算法的影响。算法中用到的参数为k=wA=0.5，初始权值b=0，贴壁工艺权值b1=-5、r1=1，热源工艺权值b2=3、r2=2，电磁源工艺权值b3=3、r3=2。

本文共进行了4组实验，分别为：

实验1：不考虑工艺约束，以线缆路径最短为优化目标；

实验2：只考虑贴壁约束，以线缆路径最短为优化目标；

实验3：考虑贴壁和避开热源，以线缆路径最短为目标；

实验4：考虑贴壁、避开热源和电磁源，以线缆路径最短为优化目标。

图7中，绿色节點表示贴近实体壁的节点，是布线工艺性较优的点，红色是考虑热源和电磁源而权值较高点。实验1不考虑任何工艺约束，因此得到的路径最短，但是从图7a中可以看出线路悬空部分较多，不利于捆扎，若机电产品震动大时线缆容易散落；实验2考虑了贴壁约束，使线缆优先选择实体壁附近的路径，得到此约束下的最优路径，较实现1牺牲了0.7个单位长度，从图7b可以看出线缆贴壁较好，利于捆扎和固定；实验3考虑贴壁和避开热源约束，得到了一条绕行结构B上表面和结构A内壁的路径，很好的避开了热源，较实验2牺牲了0.1个单位距离；实验4同时考虑贴壁、远离热源和电磁源的约束，能够完全避开图7中的红色点云空间，得到了一条绕行结构A外表面的路径，具有最优工艺性，实现了多约束条件下的路径最优。

5 结论

通过以上分析可得以下结论：1）本文将A*算法扩展到三维空间，可以实现三维空间的路径规划；2）将工艺约束权值引入到代价函数中，得到了多工艺约束下的路径最优规划，实现了机电产品线缆布设的智能化和自主化。

参考文献：

[1]KOCH C， POGGIO T. A simple algorithm for solving the cable equation in dendritic trees of arbitrary geometry.[J]. Journal of Neuroscience Methods， 1985， 12（4）：303315.[

2]

MASCAGNI M. A parallelizing algorithm for computing solutions to arbitrarily branched cable neuron models[J]. Journal of Neuroscience Methods， 1991， 36（1）：105114.[

3]

ABBASI V， HEYDARI H， FAGHIHI F. Heuristic mathematical formulations and comprehensive algorithm for optimal decision making for power system cabling[J]. Scientia Iranica， 2012， 19（3）：707720.[

4]

黄训诚， 庄奕琪， 耿阿囡. 基于粒子群优化算法的集成电路无网格布线[J]. 西安电子科技大学学报（自然科学版）， 2007， 34（1）：3437.[

5]

黄训诚. 基于蚁群算法的超大规模集成电路布线研究[D]. 西安：西安电子科技大学， 2007.[

6]

付宜利， 封海波， 孙建勋，等. 机电产品管路自动敷设的粒子群算法[J]. 机械工程学报， 2007， 43（11）：194199.[

7]

陈世明， 谢竟， 陈文栋，等. 基于HPSO算法的三维空间路径规划[J]. 华中科技大学学报（自然科学版）， 2013， 41（2）：109113.[

8]

刘潇. 复杂产品中的线缆自动布局设计技术研究[D]. 北京：北京理工大学， 2015.[

9]

张前哨. 基于A*算法的地图寻径的研究[D]. 武汉：武汉科技大学， 2005.[10]

秦玉鑫， 王红旗， 杜翠杰. 基于双层A*算法的移动机器人路径规划[J]. 制造业自动化， 2014（24）：2125.