协同环境下复杂装配任务规划的研究

作者：王海军信息来源:无忧测量 2008-3-13

字体大小:小 中 大网友评论条 进入论坛

在多人参与的协同装配环境里，每个人要完成一定的装配任务，而且要求能协作地、无冲突地完成整个装配任务，这就要求合理地对装配任务进行分解，分工明确，并对每个装配任务生成可行的装配序列。对于复杂的产品，如何简化成简单的任务，这在装配序列的生成中起着重要作用。特别是子装配体中含有过多零件（指含多于6个零件...

在多

与的协同装配环境里，每个人要完成一定的装配任务，而且要求能协作地、无冲突地完成整个装配任务，

就要求合理地对装配任务进行分解，分工明确，并对每个装配任务生成可行的装配序列。

对于复杂的产品，如何简化成简单的任务，这在装配序列的生成中起着重要作用。特别

子装配体中含有过多零件（指含多于6个零件），这是因为割集法生成的装配序列随着零件数目的增多呈指数增

，因此在处理零件数目过多的装配体时有一定的局限性。本文通过断集法将这类子装配体的零件分成几部分，使每部分的零件数目不多于6个，从而可对每部分应用割集法，然后通过递归的方式处理整个装配体。针对大型压力机的装配，零件数目成千上万，通过本文的算法分解后，就可生成简化的多个与/或图，我们从中取用一个序列。

本文提及的装配冲突主要是由于各个子装配体间的耦合性造成的，装配顺序的不合理、提前安装了不该安装的零件致使后面的零件无法正常安装等情况，在协同装配中尤其容易发生，因此装配任务的分解要尽可能做到内聚性强。

一、相关工作

1.几个定义

（1）断集：设V1是图G＝（V，E）的点集V的一个非空子集，V1’为V中不属于V1的点的集合，G中端点分别属于V1和V1’的所有边的集合，称为G的断集；

（2）割集：在连通图G中，任一支路集若能符合下列条件，即：①移去该集的所有支路，能使图G分成两个独立部分；②在移去该集的支路时，只要留下其中的任一支路，图仍然是连通的。则此支路集称为图G的一个割集。

（3）与或图：某些困难的问题可以等价成另一个比较简单的问题，如果一个问题可能与若干个问题分别等价，而解决任何一个新问题又可以进一步转化为解决与此问题分别等价的某些问题，如此便构成一棵树，其中每个结点代表要解决的问题。这个棵树叫或树；某些困难的问题可以转化为与之等价的一组子问题。如果一个问题与一组子问题等价，每一个子问题与一组新的子问题等价，如此就构成一棵与树；把或树上的结点称为或结点，与树上的结点称为与结点，含有与、或两种结点的图叫与/或图。

（4）关联矩阵：设G＝（V，E，φ）是无向图，且V＝{x1, x2, …, xn}，E＝{e1, e2, … em}，称n×m阶矩阵M＝（mij）为无向图G的关联矩阵，其中：

2.团队的具体工作

我们在协同设计系统里实现了协同绘图、标记、碰撞、控制权分配、数据传输、立体显示等，接着要进行协同装配的实现，因此需要对复杂装配任务进行规划和分解，以期得到合理的装配任务分配和有效可行的装配序列。

有关装配任务的分解和序列的生成工作，许多人已作了探讨，L.S. Homem de Mello etc.中的割集算法，已成为今天装配序列生成的经典之作，但零件数目过多成为该算法的障碍。针对这种状况，许多文章都提出了改进的方法，因此本文在解决序列生成时引入关键零件，并在该过程中参考了实际的装配经验，使最后的序列更加符合实际使用。

二、装配任务的分解与序列的生成

1.装配任务的分解和实现的基础

我们以三个假设来保证本文方法的可行性：

（1）两个零件或子装配体之间确实存在连接关系，以保证装配序列生成的可行性；

（2）零件通过连接组成子装配体后，则子装配体内的零件间就建立了接触关系，以确保装配的连续性；

（3）在协同环境中支持两个或两个以上的装配动作。

2.装配任务的初步分解

在装配体的关联图中首先指定起始装配件，去掉该零件顶点的所有边，可能将装配任务分为两部分或几部分，如果是几部分，将离散的顶点划归为一部分，其余有联系的顶点分别作为一部分，这样保持每部分的最大内聚，然后对多于6个零件或部件的部分再进行分解。根据每部分装配任务的关联图，找出关联集最大的顶点，然后求出该图的断集，则该断集将装配体分为两部分。分解过程中的约定：

（1）若出现关联集最大的顶点有多个，则这些顶点作为一部分；

（2）对离散的点，其间不存在连接关系，因此其装配顺序任意，可把它们归为一部分；

（3）关联集最大的顶点在所属于的部分中指定为首装零件；

（4）有同一零件用到多次（关键零件除外），若在装配树中处于同一层次，只取其中一个即可；

以此为原则进行分解，直至每部分零件数不多于6个（不包括由离散点组成的部分）。而最终每个人的装配任务要在整个装配任务分解完毕并生成序列后，按照装配量进行分配。

3.装配体中零件分类

根据零件间的接触关系，我们给出存在连接关系的子装配体中几种零件的定义：

（1）某一子装配体中与其他子装配体无任何关联的零件，称为普通零件；

（2）某一子装配体中与其他子装配体有关联的零件，又分两种：

①与其他子装配体存在装配约束关系的零件，称之为关键零件；

②与其他子装配体只有接触关系的零件，称之为次要零件；

这两类零件主要为解决冲突服务的，以保证装配任务的顺利完成。在安装时的处理方法将在后面详细介绍。

4.装配体的装配序列生成算法

参与协同装配的人数首先决定了整个装配任务的最后安排。整个装配任务经过初步分解后，算法针对每个部分进行，使协同装配中每个人有自己的装配序列；同时算法保证在每个人完成自己的装配后，也就是整个装配任务完成的时候。

（1）首先对每个部分生成装配树，这可从SolidEdge的pathfinder中提取；

（2）从装配树最低层的叶子结点（表示零件）往上依次处理各个子装配体。对每个子装配体首先根据连接关系图，得到关联矩阵：

①对所有含多于6个零件的子装配体转③处理，否则转②；

②对于有6个或6个以下叶子结点的子装配体，可利用割集法生成以与/或图表示的装配序列；

③生成了装配序列的子装配体用一个结点表示，如果有上一层，作为叶子结点加入上一层后，如果使兄弟数多于六个，转（3），否则转②；如果没有上一层即为最顶层装配体（top-level assembly），则最终的装配序列生成，转（4）；

（3）对多于6个零件的子装配体，按下列方法分解：

①根据该部分的关联矩阵，找出关联集最大的顶点，然后求出该图的断集，该断集将装配体分为两部分；如果关联集最大的顶点有多个，将其生成序列，作为一个节点，分到零件数少的部分；

②然后逐部分判断零件数，如果存在零件数多于六个的部分，将该部分转①处理；若所有部分中没有零件数多于六个则转③；

③对每个零件数少于等于六个的部分，调用割集法和与或图生成算法生成装配序列，存放于链表中，返回一个链表指针；

④根据返回的链表指针数，如果只有一个，表明最终序列生成则转⑤，否则将每个链表看作一个结点，连同起始装配件组成一个连通图，如果图中顶点数大于六个，转①，少于等于六个则转③；

⑤将最后的装配序列的链表结点逐步用该结点表示的装配序列代替，直至结点表示的是零件为止，此时就是该子装配体最后的一条可行装配序列，转（4）；没考虑优化问题；

（4）为了简化整个与/或图，各个子装配体的与/或图不进行合并，因此最终将生成由多个与/或图表示的整个装配体的装配序列，我们选取其中之一的序列使用即可。

5.算法流程

装配序列的主流程和子流程，见图1和图2。

图1 配序列算法主流程

图2 装配序列算法子流程

6.最后装配序列的调整原则

机械产品中经常一件多用，对于这种情况，在装配任务分解过程中只取其中一个作为代表（但关键零件除外），最后再在适当的位置插入。关键零件由于要在多个子装配体中参与序列的生成，因此最后要去掉添加的一些节点，规则如下：

（1）某关键零件在子序列的前边出现的，最后在总序列中保留最靠前的位置，以后出现的删掉；

（2）某关键零件在子序列的后边出现的，最后在总序列中保留最靠后的位置，在它前面出现的删掉。

7.装配中的冲突防范机制

为了避免装配冲突，装配序列的每个结点设有标志位flag，flag=0时表明该零件被安装，flag=1时表示还未被安装，flag=2时表示零件安装前该结点被访问过。在协同环境中设置时间因子，定时对选定的装配序列扫描，若发现序列结点的值有变化，则根据flag的值给出相应的信息。在此条件下给出两类零件的处理方法：

（1）对第一类，根据装配序列安装即可；

（2）对第二类第一种关键零件：因与其他子装配体的零件存在装配关系，即具有耦合性，因此要考虑它在其他子装配体中的装配次序，这在协同装配中会引起冲突，因此应遵循如下机制：

①按选定的序列进行装配，当轮到该类零件装配时，首先检测该零件在另一子装配体序列中结点的标志位，如果该标志位被置0，表明另一子装配体的装配进度已满足该零件的装配，否则将该位置置2，然后返回一相应信息提示暂时不能装配，装配者可再参考其他可行装配序列，看是否在该零件装配前还有别的零件可被安装，若无则需等待；

②当装配过程中，检测到序列中flag的值为2时，表示其余的装配者中有人需要该零件的装配信息，则搜索所有可行的装配序列，找出最早装配该零件的序列进行装配，安装上该零件后flag被置0，由定时检测程序可向其余装配者发送装配完毕信息；

③对第二类第二种零件：因为只有接触，注意安装位置（一般设计者会给出标记）即可，如齿轮传动中齿的啮合位置。

通过这种机制可保证整个装配任务的顺利完成，既可节约时间提高装配效率，又可有效避免一些不必要的冲突。

三、压力机的装配实例

图3是压力机的装配图，图4是J39-600压力机的装配爆炸图，都是在SolidEdge中完成的。图5是手工绘制的装配树,叶子节点都由部件（即子装配体）组成，这些部件基本构成了整个压力机。每个叶子节点又包括部件（子装配体）和零件，而且数目很多。

图3 J39-600压力机装配图

图4 J39-600压力机的装配爆炸图

在图5中黄色框代表的零件表示关键零件，绿色框表示次要零件；零件号×n，n表示该零件的数量。一个零件用到多次，只取一个进行排序，最后再根据在序列中的位置添加进去，关键零件除外：虚线表示简化中它们之间仍然存在连接关系。在关联图6中，首先指定起始装配部件，根据断集概念，可将整个装配任务分解成几部分，见图7所示；然后进行第二次分解，蓝色圆圈内的部件依次这样分解下去，直至分解后的各部分零件数目少于6个，最后对各部分使用割集法可自动生成装配序列。当每一部分生成序列之后，再按分解时的逆序再次参与序列规划，直到得到整个装配体的序列。

图5 J39-600的装配树

图6 指定10101为起始装配件，它的关联集将整个关联图分为两部分

图7 一部分10102可生成序列，另一部分20101的关联集最大，它又把该部分分为两部分

按照生成的序列，在开发的虚拟装配系统中进行了装配试验，图8显示了在不同地点两个装配人员参与装配的情景，他们同时在装配齿轮。

图8 在虚拟装配系统中的协同装配情景

五、结论

本文首次提出采用断集的方法分解复杂的装配任务，由此生成的序列个数比所有可能的装配序列数要少得多。由于分解时考虑到尽量减少关键零件，因此零件并不会增加很多，对算法的复杂性影响不大。根据生成的装配序列，在虚拟装配系统中进行了装配试验，既加快了装配速度，又提高了装配正确度。虽然算法是针对虚拟环境下的协同装配（见图8），但对实际的装配序列生成也有很好的参考价值。当然还有许多后续工作要做，要对生成的装配序列进行评价和优化，以得到更优化的装配序列。

分页：