基于网的装配研究

装配序列规划是CAD/CAM、数字化产品、并行工程、虚拟制造等领域的一个重要研究课题，主要研究装配产品信息的表示、可行装配序列的推理与表示、可行装配序列的评价与选择，对指导产品可装配性设计、提高产品装配质量和降低装配成本具有重要意义［1，2］。其中良好的装配信息模型是装配序列评价、优化和选择的前提，并且复杂产品可能存在大量的可行装配过程，如何简洁、有效且完备地表示所有可行装配过程就成为装配序列规划研究的重点。装配模型是以装配体信息和相关制造资源信息为基础得到由可行装配操作描述的产品详细装配过程。传统的表示装配过程的方法有状态转移图［3］、装配顺序图(表)［4，5］、AND/OR图［6］和Petri网［7～9］等。其中Petri网是一种适于对具有异步、并发特征的离散事件系统进行模拟、分析、设计和控制的图形数学工具，不仅能明晰、直观和紧凑地描述装配路径，而且可以通过分析Petri网的性能分析装配模型的性能，如果将装配类型和装配难度等影响装配操作的因素综合为装配代价以赋时的形式分配到表示装配操作的迁移上，就可以通过对赋时Petri网(又称时延Petri网或延时Petri网)的操作实现装配序列的优化和选择。文献［10］利用柔性装配单元的时延Petri网模型进行了机器人装配任务规划，文献［11］基于柔性装配系统的延时Petri网模型，利用遗传算法进行了装配任务的分配优化。但这些研究都有一个共同的前提:已经建立了可行装配赋时Petri网模型或基本Petri网模型，并且该模型是可靠而且完备的。但如何建立这样的模型则尚未给出。本文从装配产品的接触向量函数和移动向量函数出发，逐层分析所有可能的装配操作，包括零件与零件、零件与子装配体和子装配体与子装配体之间的操作，并逐一判断这些装配操作的几何可行性，最终建立完备、可靠的装配赋时Petri网模型。

1赋时Petri网

定义1赋时Petri网，又称时延Petri网或延时Petri网，形式化定义为一个五元组TPN=(P，T，F，M0，Γ)=(PN，Γ)，其中，PN=(P，T，F，M0)是普通Petri网，P={p1，p2，…，pn}为位置集合，T={t1，t2，…，tm}为迁移集合(P∩T=，P∪T≠)，F(P×T)∪(T×P)为流关系(关系弧)，M0:为初始标识向量，一个标识向量是一个函数M:PZ+∪{0}，表示位置中托肯的分布情况;Γ:TZ(PZ)是迁移(位置)赋时函数。具有迁移(位置)赋时函数的Petri网，称为赋时迁移(位置)Petri网;具有赋时因子的迁移(位置)称为赋时迁移(位置)。本文采用赋时迁移Petri网，以下简称赋时Petri网。

2装配体模型

Gottipolu通过定义装配体的接触向量函数和移动向量函数分别表示装配体中零件之间的接触(连接)关系和可相互移动关系，给出了装配体模型的三元组定义［4］。定义2装配体模型定义为三元组(P，C，T)，接触向量函数和移动向量函数可以直接从装配体的计算机辅助设计模型提取出来，如PADL-2软件的冲突检测功能就可以直接抽取这两个函数。

3装配赋时Petri网模型的构建

可行装配序列是一个装配操作序列，该装配操作序列中的任一装配操作满足几何可行性、机械可行性和稳定性等约束。装配序列的几何可行性可以转换为连接关系约束和优先关系约束两类。连接关系约束规定了零件与零件、零件与子装配体及子装配体与子装配体之间只有相互连接才可以装配，是装配操作实施的必要条件。优先关系约束则规定一些零件必须在其它一些零件之前被装配，否则在后面的装配中它们会互相干涉，是装配操作实施的充分条件。装配序列的几何可行性就是所包含装配操作的几何可行性，可以转换为装配操作对于连接关系约束和优先关系约束的可满足性。用p(x1，x2，…，xl)表示一个由零件x1，x2，…，xl构成的子装配体，用p(y1，y2，…，ym)表示一个由零件y1，y2，…，ym构成的子装配体，装配两个子装配体的装配操作是否满足连接关系约束，可以通过下面的算法1进行判定。连接关系约束的满足是装配操作得以实施的必要条件，它不能保证装配操作的几何可行性，必须还要满足优先关系约束。为了判定装配两个子装配体的装配操作是否满足优先关系约束，给出下面的判定算法2。装配操作的表示应该包含装配操作实施前、后的两个状态以及装配操作本身，所以对于具有n个零件的装配体，用赋时Petri网中的位置表示零件或子装配体，用迁移表示装配操作，用迁移上的赋时表示装配操作的代价，用迁移引发前、后的两个状态标识表示操作实施前、后的状态。装配体的所有可行装配序列可以通过搜索赋时Petri网的状态可达图(树)获得，以迁移序列的形式描述。在构建装配赋时Petri网模型的过程中，按子装配体包含的零件数分层，在赋时Petri网的第l层，每个子装配体都包含l个零件，也就是在l层包含所有具有l个零件的子装配体。因此，第1层表示处于未装配状态的单个零件，第2层包含所有具有2个零件的子装配体，以此类推直到第n层，第n层与装配产品对应。从初始状态开始逐层分析所有的可能装配操作，通过逐一判定装配操作的几何可行性，最终获得完备的、可靠的装配赋时Petri网模型。为方便算法的自动实现，对赋时Petri网中的位置集P(子装配体)做如下规定:1)P中不同层次的位置按层次升序排列;2)P中相同层次的位置按序列号大小升序排列。下面给出具有n个零件的装配体的装配赋时Petri网模型的构建算法。算法3给定具有n个零件装配体的C函数和T函数，构建装配体装配赋时Petri网模型。步骤1创建赋时Petri网的初始位置集P，P={p1，p2，…，pn}，每个位置表示一个零件。当前层次l=1，迁移个数j=0。步骤2依次将当前层中的位置作为当前位置pcur，将P中排在当前位置之前的各位置作为参考位置pref，判定装配pcur与pref所代表的子装配体的装配操作是否满足连接关系约束和优先关系约束。1)取当前层中第一个位置为当前位置pcur，取其之前的位置中的第一个位置作为参考位置pref，开始判定。2)若pcur代表的子装配体不包含pref代表的子装配体或子装配体中的零件，开始几何可行性判定，即继续执行3);否则转到5)。3)利用算法1判定装配pref和pcur的装配操作是否满足连接关系约束，若满足，继续执行4)，否则转至5)。4)判定装配pref和pcur的装配操作是否满足优先关系约束。(1)若pref都属于第1层，转(3);否则继续。(2)利用算法2判定装配pref和pcur的装配操作是否满足优先关系约束，若满足优先关系约束，继续执行(3);否则转5)。(3)检查赋时Petri网中是否已经存在位置p(ref，cur)，若不存在，创建位置p(ref，cur)，P=P∪{p(ref，cur)};j=j+1，创建迁移tj，创建弧(pref不是位置集中在pcur之前的最后一个位置，取pref之后的一个位置为pref，继续执行2);若pref是位置集中在pcur之前的最后一个位置，且pcur不是当前层中的最后一个位置，则取pcur之后的一个位置为pcur，取pcur之前的位置中的第一个位置作为pref，继续执行2);否则继续执行步骤3。步骤3l=l+1。若l小于装配体元件总数n，转步骤2;否则继续执行步骤4。步骤4检查位置集合P中是否所有中间位置都具有后继。若存在中间位置p没有后继，确定该位置的所有输入迁移•p，从赋时Petri网中删除所有与•p相关的弧;删除这些输入迁移•p，j=j－|•p|;删除位置p，P=P－{p}。循环执行步骤4，直到位置集中所有中间位置都有后继。步骤5为赋时Petri网分配初始标识，即为代表已经准备就绪的零件或子装配体的位置分配托肯;将影响装配操作的因素统一为装配代价，以赋时的形式分配给赋时Petri网中代表装配操作的迁移，装配序列赋时Petri网模型构建结束。在上面的算法中，步骤5综合装配代价时要考虑多种影响装配操作的因素，包括装配时间、再定位和固定、稳定性和装配资源等。本文综合的装配代价参照了文献［6］给出的标准，主要由两方面因素相加得到。一方面是装配操作类型，不同类型的装配操作需要不同的装配时间、装配工具和装配条件，所以装配类型其实综合了装配时间、装配工具和装配条件这3个因素;另一方面因素是处理子装配体的难度，这与装配体的自由度成正比，一个子装配体的自由度越大，就越不稳定，越难处理。在算法3中，步骤2通过穷举的方法考虑了所有可能的装配操作，并依次判定这些操作的几何可行性，因此容易看出算法3具有如下性质:定理1相对于装配序列规划问题来说，算法3构建的装配模型是可靠并且完备的，即模型中包含的装配序列都是几何可行的，并且所有几何可行的装配操作都体现在模型中。

4实例

以图1所示的手电筒装配体为例，说明算法3构建装配赋时Petri网模型的过程。根据表1给出的手电筒装配体的C函数和T函数，行、列分别以零件对和方向索引，利用算法3构建装配赋时Petri网模型的详细过程如下:第一步创建赋时Petri网的初始位置集P，P={p}，每个位置表示一个零件，装配体零件数n=4，迁移个数j=0。第二步设置当前层次l=1，进行以下操作:1)pcur=p1，P中没有排在pcur之前的位置，所以继续;，满足连接关系约束并且当前位置和参考位置都属于第1层，创建位置p创建迁移t1，创建弧(p1)。3)继续进行当前位置pcur=p3，参考位置pref=p1和pref=p2的操作，以及当前位置pcur=p4，参考位置pref=p1、pref=p2和pref=p3的操作。第1层操作结束，构建的Petri网如图2a)所示，P={p，

5结束语

本文给出了装配赋时Petri网模型构建方法。该方法在构建过程中充分考虑了装配操作的几何可行性，并考虑了所有的可能装配操作，最终构建的赋时Petri网模型包含了完备并可靠的装配序列。下一步将利用装配约束条件、子装配体识别和经验知识来缩小解空间的搜索范围。同时装配赋时Petri网模型中还将装配类型和装配稳定性等影响装配操作的因素综合为装配代价体现在迁移的赋时上，为装配序列的评价和优选奠定了基础，这也是我们进一步的研究工作。