面向虚拟装配的装配顺序规划研究
系统仿真学报Vol. 15 No. 1
JOURNAL OF SYSTEM SIMULATION Jan. 2003 ? 44 ?
面向虚拟装配的装配顺序规划研究
卢小平
（北京航空航天大学计算机科学与工程系, 北京 100083）
摘要：针对虚拟装配中的产品装配顺序规划问题，提出层次化装配模型，在此基础上生成产品
装配层次树结构，并给出基于装配关联图的分层规划算法；进一步，分析简化装配关联图的有效
途径，并通过固定顺序判据法降低装配序列组合复杂性，提高装配顺序规划的效率。
关键词：虚拟装配；层次模型；装配关联图；装配顺序规划
文章编号：1004-731X (2003) 01-0044-04中图分类号：TP391.9 文献标识码：A
Study on Assembly Sequence Planning in Virtual Assembly
LU Xiao-ping
(Computer Department Beijing University of Aeronautics & Astronauts, Beijing 100083, China) Abstract: This paper proposes a layer-built model on virtual assembly. The layer-built model can present the layer-tree structure of assembly. Then the assembly sequence planning can be set up layer on layer based on mating graph.
Furthermore, by analyzing the available method to predigest mating graphs and by using the fixation sequence evaluation, the complexity in assembly sequence planning can be reduced and the efficiency of assembly sequence planning can be improved as well.
Keywords: virtual assembly; layer-built model; mating graph; assembly sequence planning
引言
虚拟装配（Virtual Assembly，V A）是在产品设计过程中，通过计算机对零部件装配过程的仿真模拟，检查产品零部件之间的正确装配关系，包括可达性、顺序性、方向性、干涉情况以及公差配合等方面的内容。虚拟装配的实现有助于对产品零部件进行虚拟分析和虚拟设计，有助于解决零部件从设计到生产所出现的技术问题，以达到缩短产品开发周期、降低生产成本以及优化产品性能等目的。
装配顺序规划（Assembly Sequence Planning, ASP）是虚拟装配过程中的重要环节，它是在虚拟装配建模的基础上，对零部件的装配序列进行推理，为下一步实现产品装配过程仿真提供基础。
装配顺序规划是基于装配建模的装配工艺顺序的自动生成。产品中零件之间的几何关系、物理结构以及功能特性等决定了零件装配的先后顺序，所有零件的装配序列形成产品的装配规划。20世纪80年代以来，ASP研究主要集中在几何可行装配序列的推理方法，法国学者 Bourjault提出了联系图模型，将零件之间的物理接触关系定义为联系即装配关系，并提出了装配优先关系的概念。随后，Homem de Mello 和Bourjault在此基础上引入了割集分析方法。各种算法都是在相对简单的装配模型信息基础上，在一定的推理算法和
收稿日期：2002-02-22 修回日期：2002-06-10
作者简介：卢小平(1963-), 男, 江西赣州人, 副教授, 研究方向为虚拟装配技术。简化规则支持下，推理出所有可行装配序列[1-2]。
本文提出了一种面向虚拟装配的产品装配顺序规划方法。该方法采用特征技术建立层次结构装配模型，在此基础上实现装配序列的分层规划，进一步，通过简化装配关联图及固定顺序判据法，降低了ASP问题的复杂性。
1 虚拟装配模型
虚拟装配建模是通过实体造型系统建立产品的装配关系进而形成装配模型。本文采用基于特征技术的装配建模方法，具体特征包括形状特征、精度特征、材料特征、工艺特征以及附加特征等。特征的联系可以用特征类和特征实例来表示，它们之间的联系主要有继承联系、邻接联系、从属联系和引用联系等。
装配模型所包含的基本信息主要有两类，一是装配体的分组与层次信息，如产品中的部件、组件的划分；二是零件之间的装配关系信息，如轴孔配合、螺纹联接等几何装配信息。这两类信息获取的方法，一是由人工根据图纸判断并输入到模型中，二是利用特征CAD系统在设计阶段进行装配特征定义，装配建模时便可以从特征
CAD的输出中获得这些信息。
产品通常由若干功能部件和零件装配而成，称为装配体（Assembly）。装配体的结构具有层次性，装配体可以分解为子装配体（Subassembly），子装配体又可以分解为下一层子装配体和零件的集合，如此层层拆分，直到最终不可拆分的零件。这个过程实际上也是装配设计时把产品自上而下逐
Vol. 15 No. 1
Jan. 2003 卢小平, 等：面向虚拟装配的装配顺序规划研究? 45 ?
渐细分的过程，这样使得虚拟装配系统具有支持自顶向下（Top-Down）的产品设计能力。
本文装配模型的特征表达如下：
struct AsmFeat //装配特征
{
char name ［MAXLEN］;
float MateLength, MateDim;
char type ［MAXLEN］;
char sMate ［MAXLEN］;
}
struct AsmObject //装配对象
{
enum AsmObjectType t;
struct Assembly *assm;
struct Part *part;
}
struct PartFeat //零件特征
{
char name ［MAXLEN］;
int num;
float maxx, maxy, maxz, mass, weight;
}
2 层次树与子装配体
产品结构具有层次性，层次模型的优点是能够表达产品中零部件之间的层次关系。不同层次零件的装配存在先后顺序约束，下层零件的装配应优先于上层零件的装配，不同子装配体中的零件可以并行装配。因而，模型隐含了部分装配顺序信息。基于层次模型的设计分析降低了问题求解的复杂度[3]。
层次模型以子装配体为研究对象，也就是将装配体分解为子装配体，子装配体再进一步分解下去，直至分解为不可再分的零件。所谓子装配体是一组零件的稳定组合，在其内部，零件之间有着稳固的配合关系，每个零件都能相对定位，而与其外部的零部件的配合则比较简单。模型的层次树结构如图1所示。
由装配模型生成层次树的过程中，首先可由层次模型获取装配体的分组与层次信息。子装配体与零件类型有一定的关系。从形成子装配体的角度来看，在盘、轴、箱、叉、套等五类机械零件中，轴类零件最容易形成子装配，其次是箱体零件，另外，螺纹联接件也可以形成结构稳定的零件组合。
在装配体中，轴类零件起着支撑和传递运动作用，一般处于子装配的中心位置，这在装配关联图中表现得很明显，通常情况下轴系组件都是典型的子装配；与箱体组成子装配的主要是轴承类零件，如果把这种结构从整个关联图中分离出来，局部呈树支状，当有多处轴承类零件时，则形成一个以箱体为核心的星形树；螺纹联接件是一组零件的紧密结合，通常螺栓处于中心位置，其周围与螺纹有配合关系的零件则是被螺纹联接件固定的零件。所有与螺栓有配合关系的零件都属于这个子装配[4]。
需要说明的是，在层次结构树中，除了叶节点为零件之外，中间节点有可能为零件。所以，当某一中间层级出现单一零件时，这些零件就被视为该层级中的装配单元，直接在相应的层级中进行装配序列推理。
最后，在生成层次树结构中，应当确定每一层的子装配体或零件中的基础件（Base-component），所谓基础件就是该层级中与最多子装配体或零件具有联接及配合关系的子装配体或零件[5]，基础件由该层级装配关联图中度数最大的节点来承担。
3 装配序列生成
对装配体进行装配顺序规划时，可以依据层次树结构，采用自下而上的顺序进行分层规划。首先，对最下层级的每一个子装配体中的零件进行装配顺序规划；然后，再对其上一层级的每一个子装配体中的装配单元进行装配顺序规划；…最后，对整个装配体中的子装配体进行装配顺序规划。
分层规划时采用装配关联图来表达装配信息。装配关联图是用节点和弧线表示的装配体的二维拓扑结构。
设G =（V，E）为一个有n个节点的关联图，由非空节点集V和边集E所组成。其中，V =｛V i | 0≤i≤n-1，n≥1，V i∈VertexType｝表示组成子装配体的零件或子装配体的集合（节点分为零件节点和子装配体节点），E表示零件或子装配体之间的配合属性的集合。如图2所示：
装配关联图具有以下重要特征：
(1) 装配关联图是一无向图；
(2) 如果装配设计正确，则有且只有惟一的装配关联图
图1 层次树结构图2 装配关联图
Vol. 15 No. 1
系统仿真学报 Jan. 2003 ? 46 ?
能够表达装配体中的零件之间的联接关系；
(3) 装配关联图中度数最大的节点通常即为装配基础件。
装配关联图存储结构采用邻接矩阵表达，它是表示装配关联图中各节点之间相邻关系的矩阵。
设G =（V，E）为一个有n个节点的装配关联图，节点序号依次为0、1、2、…、n-1，则G的邻接矩阵为n阶方阵：
1，(V i, V j) 或(V j, V i)∈E(G)
A[i,j] =
0，对应边不存在于E(G)中
在邻接矩阵中，如果两个节点之间存在边连接，则这两个节点所在的行和列对应的元素值为1；如果不存在边，则这两个节点所在的行和列对应的元素值为0。其中，某一节点对应的行向量的元素值的总和即为该节点的度，即表明与该节点相连接的节点数。
邻接矩阵需要用一个二维数组存储节点之间相邻关系。此外，还需要一个具有n个元素的一维数组存储节点信息。这两种数组的类型定义如下：
const int MaxVertexNum={图的最大节点数};
const int MaxEdgeNum={图的最大边数};
typedef VertexType vexlist[MaxVertexNum];
//定义vexlist为存储节点信息的数组类型
typedef int adjmatrix[MaxvertexNum][MaxvertexNum];
//定义adjmatrix为存储邻接矩阵的数组类型
下面给出装配关联图的算法描述：
void CreateMGraph(vexlist GV, adjmatrix GA, int n, int m)
// 建立关联图{ int i,j,k;
for (i=1; i cin>>GA[i]; for (i=1; i for (j=1; j GV[i][j]=0; for (k=1; k {c in>>i>>j>>1; GA[i][j]= GA[j][i]=1; } } 分层规划时各子装配体的装配过程即为图的搜索。每一个装配过程的起始点为其基础件，采用宽度优先搜索策略，从根节点出发，在扫描已发现节点的邻接矩阵的过程中，不断将新节点V及其边E添加到宽度优先树中。装配的过程就是搜索所有与父节点有直接装配关系的子节点，自始至终通过已找到的节点和未找到的节点之间的边界向外扩张。部分算法如下： void bfsMG(GV, GA, int k) { int r=0, f=0; int qu[MaxSize]; visited[k]=1; r++; qu[r]=k; while (r!=f) { f++; i=qu[f]; for(j=1; j<=n; j++) if (GV[i][j]=1 && !visited[j]) { visited[j]=1; r++; qu[r]=j; } } } 4 降低装配序列组合复杂性 按照上述推理方式，其装配序列可能具有很大的解空间。即使对于少零件数目的装配体，获得的可能装配序列的数量也是非常可观的，而实际上许多装配序列是不可行的。因此，如何对装配规划解空间求精具有重要意义。 分析表明，装配体中的某些特殊组件的装配顺序是固定的。例如，螺栓联接的装配顺序为垫圈、螺栓、螺母；螺钉联接的装配顺序是垫圈（或弹簧垫圈）、螺钉；螺钉联接和螺栓联接紧跟在被联接零件之后进行装配；定位件的装配则在被联接零件之前；键的装配次序位于轴孔装配之前；一般是先将轴承装配在轴上，然后，轴件再与孔件进行装配；皮带或齿形带的装配次序位于两个带轮之间等等。 由此，在求解层次树中的各装配体的装配顺序时，采用分步的方式进行。第一步是在层次树中各装配体装配信息简化模型的基础上，对其中所有的节点的装配顺序进行规划，主要任务是确定经简化后的所有节点间的装配顺序，它涉及到零件之间的几何干涉等复杂问题；第二步是规划出所有经过抽象化的节点的装配顺序。经过抽象化的节点是指螺栓、螺钉、轴承和键等零件，规划的主要任务是将这些零件按照相关的装配工艺知识插入到第一步规划所得到的粗装配顺序中相应的位置，从而得到完整的装配顺序。这种抽象化节点的方法可以减少装配关联图的节点和弧线的数量，即简化装配关联图。从而降低可能的装配序列的数量[6]。 进一步，为提高装配顺序规划的效率，本文采用基于固定装配顺序判据法的方法来进行可行装配顺序的选择，从所有可能装配序列中剔除大量不可行的装配序列。 固定装配顺序判据法的评价方法如下： 现有k条可能装配序列S=｛S i|1≤i≤k｝ 其中： S i= { V i1，V i2，…，V in }为有序序列，1≤i≤k； 若存在固定装配顺序判据A={A j|1≤j≤k} 其中： A j={A j1，A j2，…，A j l}为有序序列，1≤j≤k，1≤l≤n； 则，当S i满足条件A时，S i为可行装配序列。 基于固定装配顺序判据法算法如下： int Sequence (ElemType S[], ElemType A[], int n, int k, KeyType K) Vol. 15 No. 1 Jan. 2003 卢小平, 等：面向虚拟装配的装配顺序规划研究? 47 ? //从Si中的元素中顺序查找判据Aj的关键字K //若顺序一致则此装配序列为可行，否则为不可行 { for (int j=1; j≤k; j++) K= A[j] { for (int i=1; i≤n; i++) if (S[i].key = = K) return mid; if (i≤n) return i; else return –1; } if (j≤k) return j; else return –1; } 最后，通过装配过程仿真中的装配干涉检测实现装配顺序的优化。 5 结论 本文提出一种面向虚拟装配的ASP方法。该方法以特征技术为基础，建立层次化装配模型，在此基础上生成装配体的层次树结构，为下一步实现分层装配顺序规划提供基础。层次结构装配模型可以将一个由众多零件组成的复杂产品的装配顺序规划问题，简化为多个由为数较少的零件组成的子装配体的装配顺序规划问题，从而降低了求解复杂装配体的装配顺序规划的难度。 在分层规划过程中，给出了基于装配关联图的宽度优先搜索算法，实现层级装配序列的推理。该算法产生的装配序列数与装配关联图的节点和弧线数量成正比，因而装配序列的数量将是非常可观的，而实际上许多装配序列是不可行的。通过合理选择基础件和抽象化节点，减少装配关联图的节点和弧线的数量，简化装配关联图，从而有效地降低装配序列组合的复杂性。 进一步，采用基于固定装配顺序判据法，对已经生成的装配序列进行筛选，可以剔除大量不可行的装配序列，减少了可能装配序列的数量和装配序列评价的工作量。 最后，通过某减速器装配体进行验证实验。开发环境为Microsoft Visual Studio，工具平台使用OpenGVS、SolidWorks 等。实例验证了上述研究结果的可行性和有效性。 参考文献： [1] Bourjault A, Lbole A. Modeling an Assembly P rocess [J]. IEEE International Conference on Automation of Manufacturing Industry, 1986, 20(2): 183-198. [2] Homem de Mello L S. A Correct and Computer Algorithm for the generation of Mechanical Assembly Sequences [J]. IEEE Transaction on Robotics and Automation, 1991, 7(2): 228-240. [3] 苏强, 林志航. 产品装配顺序的层次化推理方法研究[J]. 中国机 械工程, 2000, 12: 1357-1360. [4] 潭光宇, 立广慧, 陈栋. 基于图的子装配识别与装配序列规划[J]. 机器人, 2001, 1: 68-72. [5] 李原, 曹哲, 张涛, 杨海成. 基于产品配合图的装配顺序自动规划 [J]. 工程设计, 2000, 2: 28-31. [6] 沈梅, 雷哲书, 张铁昌. 基于装配特征的装配顺序生成算法[J]. 工程图学学报, 2001, 3: 14-19. （上接第43页） 的开发思路可行，可以应用于虚拟战场环境中武器性能评测等领域。 本文下一步将在以下几个方面开展研究： ?研究多分辨率环境建模：同地形数据一样，各种仿真对象对自然环境数据的精度要求也是不一样的，因此需研究多分辨率的环境建模与数据表示； ?提高数据生成的实时性：目前自然环境的数字模拟模型还达不到实时生成数据的程度，因而数据只能离线生成，随着计算机技术的发展，同时在满足需要的基础上将数字模型合理简化，有可能解决这个问题； ?应用新的数据库技术：数据的组织与集成对于提高虚拟环境的运行效率十分重要，由于自然环境数据量巨大且多是动态变化的，同时仿真实体在运行时对数据也有时间要求，因此，需要在虚拟自然环境的仿真开展实时数据库和时态数据库等数据库新技术的研究。参考文献: [1] 汪成为, 高文, 王行仁. 灵境(虚拟现实)技术的理论、实现及应用 [M]. 北京: 清华大学出版社, 1996. [2] 赵沁平, 沈旭昆, 夏春和, 王兆其. DVENET: 一个分布式虚拟环 境[J]. 计算机研究与发展, 1998, 35(12): 1064-1068. [3] Barry R G, Chorley R J, 著. 施尚文, 张如一, 吴永莲, 巢俊民, 译. 大气、天气和气候[M]. 北京: .高等教育出版社, 1982 [4] Training and Instrumentation Command [R]. SEDRIS and the Synthetic Environment Domain. U.S. Army Simulation, 1998. [5] Department of Defense. Modeling and Simulation (M&S) Master Plan [R]. 1995. [6] Whitnty D A. Providing and Managing Real Natural Environments for Virtual Worlds [A]. Proceedings of the Fall Simulation Interoperability Workshop [C]. 1998. [7] Whitnty D A. Impacts of the Environment on Warfighter Training: STOW’97 Experiences with TAOS [A]. Proceedings of the Spring Simulation Interoperability Workshop [C]. 1998. [8] 庞国峰. 分布式虚拟战场环境中计算机机生成兵力系统的研究 [D]. 北京航空航天大学博士学位论文, 2000.