电子制造装备电气布线路径优化搜索

电子制造装备电气布线路径优化搜索

0电子制造装备自动表面织构电子制造是国家经济、金融和国防信息系统安全的重要组成部分。它也是许多高科技行业的中心规模，如计算机和存储设备、能源电池、光刻设备和通信设备。实现我国在21世纪成为电子制造强国的关键是开发具有自主知识的电子制造装备。近年来，随着各种新材料、新技术和新工艺的大量应用，使得电子制造装备的开发面临着前所未有的挑战。提高装备的可靠性和竞争力，缩短设备的研发周期的瓶颈之一是电子制造装备的布线技术。传统的布线方式以基于实物的模装试验手工布线方法为主。布线时间长，可靠性差，需要反复修改，从而严重影响了产品的开发周期，难以适应激烈的市场竞争。随着计算机辅助设计的日趋成熟，国内外专家对线缆的研究逐步深入。1992年，斯坦福大学的CDR实验室开发出了First-Link并行布线系统，但其处理对象仅是平面的。SunandSandukar等开发了GAPRUS系统，用STL文件来描述障碍物，能够在存在障碍物的环境中得到无碰和高效的布线路径，但是搜索的复杂度较高。桂林电子工业学院的吴银峰等对三维布线技术做了初步研究，在电磁兼容性有所探讨，并用迷宫算法和最小斯坦纳树生成法进行自动布线，但偏重于单一线缆的连通。电子制造装备自动布线的核心问题是路径搜索，A*算法作为一种经典的最优启发式算法，在移动机器人的路径规划、最佳航迹选择和电脑游戏的寻径计算等领域有着广泛的应用，被公认为是最实用的二维路径规划算法，但无法直接应用于三维路径搜索中。针对上述问题，本文提出了一种改进A*算法，通过在估价函数中引入了折弯耗费和工艺耗费，以实现三维空间路径搜索。同时，引入刚性因子，从而较大程度地提高了算法的效率。通过算法驱动搜索最优路径，使搜索结果更加符合实际情况。1在a#算法中创建最短路径A*算法通过在搜索中加入了与问题有关的启发性的信息，以指导搜索朝着最有希望的方向前进，加速问题的求解过程，并找到最优解。如果一个估价函数可以找出最短的路径，被称为可采纳性。一般估价函数为式中：f*(n)为节点n的估价函数，表示从初始节点经过节点n到目标节点的最佳路径的代价；g*(n)表示在状态空间中从初始节点到节点n的代价；h*(n)为从节点n到目标节点的最短路径的估计代价，通常设定h*(n)为2个节点的欧式距离，可表示为在A*算法中分别创建2个表：Open表和Closed表，其中Open表用于保存所有已生成而未考察的节点，Closed表中记录已访问过的节点，求解步骤如下：1)把起始节点S放入Open表，Closed表置空。达到起始节点的代价为0，故初始化f=h。2)LOOP：重复下面的过程。若Open表为空，则失败退出。3)取出Open表中f值最小的节点，记为节点M，并放入Closed表。若B为目标节点，则成功找到最短路径，退出。4)令N为M的一个可到达的相邻节点：(1)若N已经在Closed表中，继续步骤5)。(2)计算节点N的f,g和h值。(3)若N已经在Open表中，则将上一步计算得到的f值与Open表中该节点的f值比较；若新值较小，则以新值代替旧值。若新值较大，则转向步骤5)。(4)若N不在Open表中，将N加入Open表。(5)为N设置指针指向节点M，则M为N的父节点。5)对M的所有相邻节点执行步骤4)。6)转至第2)步LOOP。算法找到目标点之后，只需从目标点回溯，直到树根就可以得出最短路径，并对其保存即可。如果起始点和目标点之间存在有效路径，A*就一定能够找到。只要h*(n)是可接受的，它就能找到一条最短路径，并且A*算法在启发式搜索算法中搜索状态最少，使启发式函数得到了最有效的应用。然而，由于在电子制造装备的电气布线中，存在如线缆的折弯长度不能过短，仅允许小范围的悬空等特殊性情况，使得该算法难以直接应用，需要对其进行改进。2改进的a-*算法2.1实验结果和分析结合实际电气布线经验，在估价函数中引入第三评估因子p*(n)和第四评估因子q*(n)，其中，p*(n)表示从起始节点到达当前节点n的折弯耗费，q*(n)表示从起始节点到达当前节点n的工艺耗费，则估计函数变为其中，在新的估价函数中，h*(n)从二维空间扩展到了三维空间，仍然取其欧式距离，p*(n)的取值是将折弯的耗费转化成欧式距离，q*(n)的取值是将工艺耗费转化为欧式距离，从而使得上述4种评估因子可同时进行运算。图1为某模块的布线平面投影图，从起始点A到目标点B存在2条可行路径1和路径2，长度分别为310和265，拐角数量均为4。如果估价函数中只加入第三评估因子p*(n)，则得到最优解为路径2，但是路径1更有利于线缆敷设的实施，工艺耗费较低。假设该模块布线平面边角的工艺耗费为0.6，布线平面的工艺耗费为1，每次折弯耗费为20，那么这2条路径的总耗费分别为：310+20×4+0.4×270+1×40=538,270+20×4+0.4×120+1×150=548，因此路径1才是从点A到点B的最优路径。由此可见，在相同折弯次数的条件下，未加入工艺耗费，算法会得到一条可行路径并认为其是最优路径，而加入了工艺耗费之后，估价函数会贴近工程实践，得到更优的路径解。2.2路径搜索过程不同材料、不同型号的线缆对最小弯角半径的要求各不相同。因此加入线缆的刚性因子，以防止路径在某一方向出现过短的情况。对于最小弯角半径比较大的线缆，在布线过程中加入了刚性因子，在路径搜索过程中就可以保证某个方向的最小长度，不允许随意折弯。实际布线中的线缆是具有相对柔性的，因此刚性因子大多以线缆的最小弯角半径作为参考。另外也要考虑不同的线材及敷设环境的要求对刚性因子值的影响。确定刚性因子之后，路径在扩展的时候就不是逐步向多个方向进行扩散，而是扩散时在该方向必须要满足刚性因子的要求。如图2所示，线缆中心线的MN段长度非常小，在路径弯角处理过程中无法同时完成2个弯角的处理，而图3中MN段长度适中，可以满足2个最小弯角半径，因此带有刚性因子的路径是满足最小拐弯半径条件下的最短路径。2.3节点c的获取改进后的A*算法仍然维护着2个表（Open表和Closed表），分别存放所有已生成而未考察的节点和已访问过的节点。把起始节点S放入Open表，Closed表置空。初始化时g*(S)=0,q*(S)=0，此时的估价函数表示为f*(S)=h*(S)+q*(S)。在扩展节点M生成后继节点N时，对每个后继节点N都进行回溯，若其不满足刚性因子要求，则舍弃该节点，直至该方向上满足刚性因子要求后，则计算节点的f值。改进后的A*算法流程图如图4所示。3市场中的纱线布置在UGNX3.0环境下，通过UG/OPENMenuScript,UG/OPENUIStyler和UG/OPENAPI联合开发，设计编制了布线模块，对电子制造装备某电气箱体进行虚拟建模和装配，适当简化后如图5所示。对电气布线三维空间作如下假设：1)机械组件和电气组件的结构与位置已经确定，并且所有组件都不发生实体干涉和电气干涉。2)在误差允许的范围内，线缆实体用其中心线表示，并且中心线的路径通过网格点。3)装配体已进行带有权值的网格划分，用于区别布线可行空间和障碍物空间。4)不同线缆的折弯耗费相同，而且同一区域所有线缆的工艺耗费相同。基于以上假设，对空间闲置点赋予较高的工艺耗费，布线平面赋予较低的工艺耗费，四周边角最低，使路径悬空的可能性最小，然后调用A*算法，选择起始端和目的端方向，输入刚性因子，得到路径搜索如图6所示。设定好每根线缆的种类、线径等参数，在得到线缆敷设的路径后，通过自动敷设线材，系统会对所有路径敷设对应的线材，如图7和图8所示。此时线缆的空间走线已经清晰的呈现出来，可以得到每根线缆的编号，包括