基于工程语义约束的线束预装配自动规划方法

刘晓平， 李忠泽， 徐本柱， 朱吉满， 何宏林

（合肥工业大学计算机与信息学院VCC研究室，安徽 合肥 230009）

汽车线束是指将不同工作用途的导线经捆扎成束而形成的用于连接汽车各个电子设备的重要组件。线束预装配是为了降低线束总成装配时的复杂度和减少工作量而把线束分解成若干个子线束的过程。线束预装配是线束进入总装流水线的前工序，是直接影响产品生产效率及质量提高的重要因素之一。目前现有的装配控制研究主要集中在机械零部件的装配序列规划方面，主要方法有遗传算法[1-2]、割集法[3-4]、优先约束规则法[5]等。然而，线束预装配主要完成把经过压接工序的导线预先装配到电器接插件的端口中，与传统的机械产品装配有很大不同。机械产品装配中零部件之间总是存在某种紧固或接触联接关系，相互关联的零件能自发分离或者借助外力能够发生分离[6-7]，然而线束中的导线经过压接工序后，导线之间复杂的实际物理连接关系便完全确定，在预装配过程中必须完全保持它们之间的联接约束，不能够随便发生分离。因此，传统的遗传算法、割集法、优先约束规则法等常见的装配序列规划策略并不能够直接应用于线束的预装配过程中。

文献[8]提出了一种基于约束集合模型的线束预装配过程控制方法，然而该方法需要用户手动选择基准件和删除不需预装的导线和接插件，因此其本质上只完成了导线连接关系的提取，并不是真正意义上的预装配序列自动规划。本文通过总结线束工艺设计中的工程语义约束信息，建立装配关联图模型，并在此基础上提出一种无需与用户进行交互的线束预装配自动规划方法，实现对线束预装配工艺的自动规划。

1 相关概念

1.1 导线、接插件分类

线束图纸是用来表示导线连接关系的 CAD图纸。线束图纸中存在大量的导线和接插件，为了在预装配过程中针对不同情况实施不同的处理方法，本文先对导线和接插件进行分类。线束图纸中的导线根据电路逻辑连接关系可以分为两大类：单根线和内联线。

在上述导线定义的基础上，本文根据端口连接的导线类型不同而把接插件分为以下3类：

定义3 简单接插件(Simple Connector，SC )设接插件全集为，若ci( ci∈C )端口中连接的任意导线wi均为单根线时，称ci为简单接插件。简单接插件端口中不同单根线的数目称为简单接插件的“单联度”，记为 s cdeg( S C )，显然 s cdeg( S C)≥ 1。

定义4 复杂接插件(Complicated Connector,CC ) 设接插件全集为，若 ci( ci∈C )端口连接的导线中至少存在一根内联线，称ci为复杂接插件。复杂接插件中不同内联回路的数目称为复杂接插件的“内联度”，记为 ic deg( C C )，显然 ic deg( C C)≥ 1。与简单接插件类似，复杂接插件也可能存在“单联度”，scdeg( C C )≥ 0 ，然而简单接插件的“内联度”一定为0。

定义5 孤立接插件(Isolated Connector，IC )设接插件全集为若ci( ci∈C )中所有端口均不连接任何导线时，称ci为孤立接插件。显然，s c deg( I C ) = i cdeg( I C )=0。由孤立接插件构成的集合记为ICS。

1.2 子装配体的定义

线束预装配规划主要完成从线束图纸中提取出各个符合工程设计要求的子装配体。子装配体是导线与接插件的集合，在线束预装配过程中，先要确定一个主接插件（简称主件），其它的接插件都是在主件的基础上进行装配。子装配体的形式化定义如下：

子装配体根据导线预装过程的不同，还可以分为两大类：后插型子装配体和非后插型子装配体。

如图1(a)所示的为后插型子装配体，图1(b)所示的为非后插型子装配体。

图1 子装配体

1.3 工程语义约束

对于导线和接插件数目很多的线束图纸来说，如果通过组合方式直接生成所有的预装配序列，必然会产生组合爆炸。然而，在实际的预装配过程中，很多的预装配序列并不符合工程设计上的要求。本文通过引入工程语义约束条件，可以直接在预装配过程中把不符合约束条件的装配序列排除掉，减少搜索空间，提高自动装配效率。

约束 1 回路约束 对于内联线 wi, wj，若wi, wj为同一内联回路中的导线，则 wi, wj必须在同一装配体SA内，即 wi, wj∈SA。

约束 2 主件约束 主件选择必须符合“CC先于SC”规则，即复杂、简单接插件同时存在同一子装配体时，应优先考虑把复杂接插件作为主件。若同时存在多个复杂接插件，则应选择“内联度”最大的接插件作为主件。

约束 3 端口约束 ICS=Ø，即预装配过程中，不能出现把简单、复杂接插件变成孤立接插件的情况。

2 预装配规划算法

2.1 装配关联图模型

本文采用无向连接图G( V, E)来对线束图纸进行描述，其中顶点集合 V ( v1, v2,… ,vn)表示线束图纸中的接插件集合C，边集合E( e1, e2,…,em)表示导线的连接关系，它体现了线束图纸中的回路约束，G( V, E)称为装配关联图。由于接插件端口内可能包含多根导线从而与多个接插件存在连接约束关系，即 vi={w1, w2,…,wj, …,wk} ,wj∈W ，因此G( V, E)存在平行边，是一个多重图。

如图2(a)所示，顶点圆圈内的数字表示该顶点所代表的接插件端口中包含的导线代号，该图中包含 2 个内联回路（1，4，6）、（2，3，5）。顶点V1和V4之间存在两条边，其中一条边表示V1中的导线2和V4中的导线5连通，另一条边表示V1中的导线1和V4中的导线6连通。为了方便起见，规定把装配关联图中两个顶点之间的平行边均合并为一条，于是，装配关联图由多重图变为简单的无向连通图，如图2(b)所示。根据装配关联图的定义，可建立G( V, E)对应的关联矩阵 M ( G ) = (aij)n*n，其中i行 j列元素aij定义如下：

图2 装配关联图

显然，关联矩阵M( G)具有以下规律：

1）M( G)是一个n阶方阵，n为线束图纸中接插件的数目。

2）由初始的G( V, E)建立M( G)时，M( G )是一个对称矩阵。

3）M( G)中任意顶点对应的行向量元素值不能同时存在1和-1。

4）M( G)中选为主件的顶点对应的行向量元素值不能存在-1。

5）若内联回路的导线不满足导线约束时，该内联回路导线所在顶点对应的行向量元素值均为0或-1。

2.2 预装配规划算法

1）主件选取

为了满足前面所述的主件约束条件，首先必须分析每个接插件的“内联度”和“单联度”，因此从G( V, E)中确定当前子装配体主件的步骤如下：

Step 1 求出M( G)中行向量元素值不存在-1或2的顶点集合Vm；

Step 4 若满足 ic deg( vi) = δ(vi)的顶点有多个，假设分别为只有一个，则把该顶点对应的接插件作为主件；否则，随机选取其中一个作为主件，主件选取结束。

2）最大子装配体提取

主件确定后，需要提取出该主件对应的最大子装配体，在提取最大子装配体时必须将与主件存在回路约束的顶点都归入该子装配体中。根据装配关联图的关联矩阵定义，若两个顶点之间有边连接，其所在的行和列对应元素值为1或-1，说明这两个顶点存在回路约束，因此由主件行向量的元素值便可得到其对应的最大子装配体。

图3所示的是某装配关联图的关联矩阵。若当前主件对应的顶点为vi，vi对应的行向量说明vi和vj、vs存在回路约束关系，vi、vj、vs构成了以vi为主件的最大子装配体，如图3(b)所示。

直接由装配关联图关联矩阵的行向量得到的最大子装配体并不一定是最终的子装配体，因为其可能违背第1节所述的工程语义约束规则。如图4所示，顶点圆圈内的数字表示该顶点所代表的接插件端口中包含的导线代号，图4(a)中包含了 3 个内联回路（1，2，3）、（4，5，6）、（7，8，9）。如果选择顶点v2作为主件（虚线方框表示），直接由v2对应的行向量提取得到的最大子装配体如图 4(b)所示，v3中包含了（7，8，9）内联回路中的导线7，从而造成图4(b)、图4(c)所示的子装配体不满足回路约束。因此需要将图4(b)中v3顶点的导线7删除，从而得到图4(d)、图4(e)所示的子装配体。图4(e)中虚线圆圈表示顶点v3对应的接插件已经在其它子装配体中预装，其实际为一个后插型子装配体。

图3 装配关联图的关联矩阵

图4 子装配体提取示例

由前面分析可见，最大子装配体提取完成后，还需要对其进行工程语义约束检测，对不符合约束规则的最大子装配体通过适当删除某些接插件或导线，使得该最大子装配体本身及随后生成的各个子装配体都能满足所有工程语义约束规则。因此，最终得到的子装配体是最大子装配体的一个子集。

3）工程语义约束检测

为了叙述的方便，下面首先引入集合封闭性的定义。

定义9 集合封闭性 在G( V, E)中，设存在非空顶点集合任意顶点 vi( 1 ≤ i≤n )，若与vi存在回路约束的顶点都是顶点集合V中的元素，则称V具备集合封闭性。

在关联矩阵M( G)中，行向量值为 1或-1的元素表明了与该行向量对应顶点存在回路约束的其它顶点。如图 5所示，若关联矩阵中时，顶点集合 V { vi, vj, vk}具备集合封闭性；若 ajs=1， asj= 1 或-1时，顶点集合 V { vi, vj, vk}不具备集合封闭性，因为这时vj与vs存在回路约束，

图5 装配关联图的关联矩阵

具备集合封闭性的顶点集合中任意顶点与集合外其它顶点不存在回路约束关系，因此如果最大子装配体中所有顶点构成的集合具有集合封闭性，那么此最大子装配体与其它顶点也不会存在任何回路约束关系，其它子装配体也不会因为此最大子装配体而产生违背工程语义约束规则的情况。所以，具备集合封闭性的最大子装配体可以直接作为最终的子装配体而无需经过工程语义约束检测。

如果提取得到的最大子装配体SA不具备集合封闭性，我们必须利用工程语义约束规则对它进行检测，具体检测方法如下：

Step 2 判断wi是单根线还是内联线，并由判断结果分别执行1）或2）。

（1）若iw是单根线，则进行端口约束检测，即判断wi另一端是否存在于其它未被预装的接插件内，若是则把wi从SA中删除，否则保留wi。

（2）若wi是内联线，判断wi所在内联回路是否属于SA的主件c1中的内联回路，若不是则把wi从SA中删除，同时判断wi所在内联回路的导线是否满足导线约束，若不满足，把iw所在的接插件也从SA中删除。

Step 3 取出SA中下一根未处理的导线wj，重复，Step 2直至把SA中所有的导线处理完毕，这时SA便是最终的子装配体。

4）预装配规划算法

根据前文所述，得到下面完整的线束预装配规划算法：

Step 1 由线束图纸G( V, E)构造初始关联矩阵M( G)；

Step 2 在M( G)中选取一个主件顶点vi，同时提取出vi对应的最大子装配体SiA；

Step 3 对SiA进行工程语义约束检测，得到最终的子装配体SA，并更新M( G)；

Step 4 重复Step2至Step3，直到M( G)中所有元素的值均为2。

3 应用实例

本文所述的思想已经在由作者所在研究团队基于Object ARX进行开发的线束工艺设计软件系统中得到验证。系统把线束图纸读入后，用户只需要从菜单执行“预装设计”命令，便能够自动生成各个子装配体，并保存到指定目录中。

图6为某汽车车型简化的线束图纸，其中包含了9个接插件，内联回路为（11，21，32）、（43，50，16）、（71，82，91）、（104，89，13）、（143，152，160），其中101号导线为单根线，其两端分别接于接插件HL02FB-M和HNMWP02FGYM-LOCK端口内。

经过预装配自动规划后依次得到的子装配体如图7(a)、图7 (b)、图7 (c)所示，其中图7 (b)、图7 (c)为后插型子装配体，图7 (a)为非后插型子装配体。

图6 线束图纸

图7 子装配体

4 总结与展望

本文针对线束预装配设计的特点，总结了线束预装配过程中的工程语义约束信息，并建立装配关联图模型，通过主件选取、最大子装配体提取以及工程语义约束检测来自动完成对整个线束图纸的预装配序列规划。最后的实例表明该方法是有效可行的，能较好的解决大线束图纸中预装配序列规划问题。本方法的最大优点是整个预装配序列规划能够自动完成，不需要与用户进行交互。然而由本文方法得到的装配序列仅是所有可行装配序列中的一个，并不能确保其是最优的，原因在于当多个接插件的“内联度”和“单联度”都相等时，主件选择具有一定的随机性。此外，若遇到线束图纸中存在某些极端情况，如大接插件与其它所有接插件均有回路约束关系时，该算法会把整个线束作为一个子装配体。如果能够进一步总结线束预装配过程中的其他约束，如设定主件的内联回路数目阈值，考虑压接位置约束、子装配体数目约束等，将使自动预装配规划的结果更符合工程设计上的要求，进一步提高装配的效率。

[1]王敬品, 胡志勇, 蔺吉顺, 等. 基于遗传算法的装配序列规划[J]. 机械工程与自动化, 2008, (2): 9-11.

[2]Shan Hongbo, Li Shuxia, Gong Degang, et al. Genetic simulated annealing algorithm-based assembly sequence planning [C]//Technology and Innovation Conference, 2006: 1573-1579.

[3]张艳萍, 李从东. 集成环境下基于割集的装配顺序生成算法研究[J]. 机械设计, 2004, 21(9): 10-13.

[4]Mello L S, Sanderson A C. A correct and complete algorithm for the generation of mechanical assembly sequences [J]. IEEE Transactions on Robotics and Automation, 1991, 7(2): 228-240.

[5]朱海平, 邵新宇, 张国军. 基于自动拆卸过程的装配序列生成方法研究[J]. 工程图学学报, 2008, 29(4):27-32.

[6]杨培林, 朱 均, 陈晓南. 装配规划中装配体的表达及子装配的识别[J]. 西安交通大学学报, 1999,33(12): 40-43, 60.

[7]张 勐, 古天龙. 基于带权无向连接图的子装配体识别方法研究[J]. 桂林电子科技大学学报, 2008,28(1): 18-22.

[8]何士双, 程光春, 吴 黄, 等. 汽车线束预装配过程控制研究[C]//计算机技术与应用进展(下), 2007:957-960.