基于二叉树的装配序列规划新方法（部分供参考）.doc

窗体顶端基于二叉树的装配序列规划新方法（部分供参考）摘要:为了减少装配序列规划中约束条件的冗余计算,本文把装配序列规划转化成对应的二叉树规划,在二叉树变化中动态识别子装配体,从而把约束条件尽可能局部化处理.为此,本文首先引入并证明了基于二叉树变换的几个装配定理,然后给出了子装配体的动态识别方法,进而给出了基于二叉树变换的装配序列规划新算法.通过算法的时间复杂度分析和实例检验,证明了该算法是即可行又有效的.关键词:装配序列规划;二叉树;计算复杂度;机械工件A Novel algorithm Based on Binary Tree for Assembly Sequence PlanningCongwen Zeng1.2 Tianlong Gu2(1. School of Electronic Engineering, Xidian University, Xian, Taibai Road 710071, china;2. College of Computer and Control Engineering, Guilin University of Electronic Technology, Guilin, Jinji Road 541004)Abstract:Assembly sequence planning is converted into binary tree planning in the paper. Sub-assembly is recognized dynamically based on binary tree planning. Constraints are satisfied as possible as locality to decrease redundant computation. First several theorems are given out and proved. Then the process of sub-assembly recognized is given out. At last an algorithm is proposed to obtain a feasible assembly sequence. Its time complexity is analyzed and an example is shown,which prove it be feasible and effective.Key words:Assembly sequence planning;Binary tree;Computational complexity;Mechanical product引言一个由N个零件组成的装配体,可以看成由这N 个零件经过N一1次合并最后构成装配体. N个零件所有可能不同的合并序列不是N!个,而是有(2N一3)!个1,这是因为装配体中可能存在某些零件必须先装配成子装配体而后才可能合成装配体,这大大增加了问题的复杂性,因此,当装配体的零件数增多时,快速寻找到子装配体,避免组合状态空间爆炸,成为提高可行装配序列生成效率的关键.本文根据装配过程的特点,把装配序列规划转化成对应的二叉树规划,给出了装配过程中子装配体动态识别的新算法,从而提高了可行装配序列的生成效率.1.基于二叉树变换的装配定理为方便叙述,我们先引人几个概念, 同时均设所讨论的零件是刚体,即在装配过程中零件形状不改变.装配可分为单调装配规划,序列装配规划,线性装配规划.单调装配规划:每个零件装配一次到位,即a零件装配后. a与在a之前已装配零件的相对位置始终保持不变,这样的装配规划称单调规划.序列装配规划: 若一装配规划可以分解为若干步骤,每一步骤所有被移动的零件都沿同一轨迹运动,则称此规划为序列装配规划.(这等价于此规划是由一系列装配体(零件)经过逐步合并的操作,最后装配成装配体.)线性装配规划:每一步骤只移动一个零件的装配序列规划.(这等价于能将零件安排一个顺序,每个零件按顺序逐个安装上去.最后构成装配体.)若一装配体存在单调序列装配规划,则称该装配体可单调序列装配的.显然,图1中的装配体是可单调序列装配的.下文如无特别说明,装配体均是可单调序列装配的.我们约定把参与某一次装配动作的零件集合(部件)也称作装配体.假设A=(A1,A2),则认为装配体A是由装配体A1和A2装配而成,也可记作A(A1,A2).如果A1是最小装配单位零件,则称A1是0级装配体.设A (A1,A2,Am),如果A中的子装配体Ai(i=1,2m)全部都是0级装配体,则A是1级装配体,如果A中的子装配体Ai(i=1,2m)等级最高的是k(0=2时,仅说明A装配体是由零件组成,但如何装配还没有确定,即A是需要装配规划的装配体.这样,只有规范表达的装配体其装配序列才确定.如果我们规定装配总是假定左子树表达的装配体固定不动,移动右子树表达的装配体进行装配,则显然任一可行装配序列规划都可转化成相应的规范型,且这种表达是唯一的.定理2: 假设任一装配体, 其中是一棵已找到装配序列的二叉树, 设B=(A,p),p为欲装配的装配体(可以是零件).假设B存在一可行分解,即B也可由B1装配体和B2装配而成,设的左子树为B1中仅去除A2中零件形成的新二叉树.具体调整过程如下,如果非叶子结点只有一个子树,如果其有父结点,其父结点指向它的指针改为指向其子树(注:本文中二叉树结构用左,右指针表示),删除该结点.类似地,设的右子树为B1中仅去除A1中零件形成的新二叉树.设的左子树为B2中仅去除A2中零件形成的新二叉树.设的右子树为B2中仅去除A1中零件形成的新二叉树.则B=(C1, p),C2)二叉树是一可行装配序列规划.证明:如要C1中不含P零件,因为C1每个子树对应结点的装配体约束条件是A中的A1约束条件的子集,因此A1能进行的装配在C1的子树中必能进行,而C1两颗子树的约束条件又是A的子集,因此C1的两颗子树必能顺利装配.类似有C2子树有成立.又因为C1子树与C2子树间的约束条件等同B的B1子树与B2子树的约束条件,因此必有B=(C1, p),C2)成立.因此,定理2成立.当不装配其他新装配体,即P为空时,定理2提供了更新某个可行装配序列的方法.如图3给出了一个应用定理6调整装配序列的例子,即如果A(1,2),3), (4, (5,6)且A(1,4,5), (2,3,6),则应用定理2能得到A(1, (4,5), (2,3),6).假如A有m零件,p为零件, 则不难证明调整的时间复杂度是O(mlogm).定理3: 设B=(A,p),p为欲装配零件,A为已装配规划方案的装配体.如果B不存在一可行分解,则B装配体不存在可行装配序列规划,所求装配体无可行装配序列或不是单调序列装配体.参考文献1给出了任意含m个零件的装配体必可沿该装配体包含的某一装配方向分解生成两个装配体的结论,否则该装配体不存在可行装配序列.因此显然,欲求解的装配体的任意子装配体必然可分.分解计算的时间复杂度最坏是O(m(m-1).其中m是该装配体的零件数.2.子装配体识别可以用三元组模型表达装配体,其中P=P1,P2, ,Pn,是零件符号的集合,每个符号对应装配体中的一个零件.P中不存在两个相同的符号对应同一个零件.C:PP0,1为接触向量函数.Td:PP0,1为在D方向上的移动向量函数,则T=T1,T2,TD,D为装配体装配方向的集合,和零件相关.接触向量函数用来查找相邻零件.移动向量函数用来检测装配能否进行,C,T构建过程同文献6.子装配体识别是生成可行装配系列的关键技术,传统的子装配识别是从全局出发对装配体成分依次分解,得到各级子装配体,进而得到装配序列的,是基于可拆卸的子装配体识别方法.本文是在装配变得不可行时才进行子装配体识别,只考虑已装配零件间的相互约束,从而让识别子装配体尽可能局部化,是基于装配需要时才进行子装配体识别的方法,其子装配体的形成是动态的.具体做法如下:现假设有一装配体A,欲装配其相邻的零件P.令装配体=(A,P),假设根据移动向量装配不可行,现在我们来求的可行装配序列规划.思路是对装配体进行循环压缩分解(方法同文献3),直到P在父装配体中可拆为止,依据定理2得到的可行装配序列规划.具体算法如下:算法3.1设中的零件集合为Bset.从欲求解装配体数据模型中抽取取只含Bset中零件的模型数据,定义装配体B1,初始化B1只含P零件.是装配体装配方向的集合.如果为空,则装配体不存在可行装配序列规划,给出不存在单调可行装配序列规划提示,退出算法.否则在中选取某一方向d,把其从中删除.设定P为当前欲拆卸装配体.由局部模型找到在d对应的拆卸方向上阻碍当前欲拆卸装配体的零件Pi,如果找到转(5).如果没有找到,则(7) .如果Pi已在集合B1中,则把Pi到当前欲拆卸装配体的所有装配体合并为一个新装配体,设定该装配体为当前欲拆装配体,转(4).如果Pi不在B1中,则Pi加在B1中的最后面,即其父装配体为B1,Pi为当前欲拆卸装配体.转(4).把装配体中的A看成定理2中的A.如果Bset中已加到B1中全部零件看作一个装配体B1, Bset中其他零件合成一个装配体B2,由这两个装配体构造B,如果B2为空,设定B1只含P零件并转3(注:一次分解失败,试沿其它装配方向分解),否则按照定理2调整装配体的装配序列.在中查找P的父装配体,令其为新的.如果中的零件P可拆,则分解结束,由算法生成的二叉树即是包含P的可行装配序列规划,退出分解算法.否则转(1)(注:嵌套分解).例:在图1中,零件4和装配体(1,2),3)间的装配是不可行的.假设算法运行时选了向右,则中的零件被分解成如下两个装配体:.根据第(7)步进行调整.仍得到,4在装配体(2,4)中可拆,分解结束,从而得到可行装配序列(见图4). 另外,如果在所有局部装配方向分解失败,即在算法的第(3)步中会及时退出.图4 装配1个零件示例3 装配序列生成新算法3.1 算法步骤装配的思路是这样的,选定一个装配零件固定不动,根据接触向量选取和该零件有接触的零件进行装配,如果装配成功,把已装配成功的零件集合看成一个装配体,找到与该装配体直接相邻的零件继续进行装配,如果装配失败,则按算法3.1调整装配序列,得到包含该零件的可行装配序列规划.如此继续,直到完成所有零件装配.在实际工艺操作中,有些零件必须先装配,在算法中我们可以先选取这样的零件进行装配.具体算法如下.从任一零件出发(一般可从装配基准零件开始),设定该零件为初始装配体A.级别为零.随机选择和装配体A相邻的非A中的零件P(可根据实践中工艺要求确定),根据给定装配方向进行装配.如果装配成功,把P归并到包含全部和P相邻的零件的最低级装配体(设为B)中去,即产生一个新的结点(设为node)取代B的位置,而B作为node的左子树,P作为node的右子树.如果装配体A包含所有零件,算法转(6),否则,转(2).如果装配不成功,则把包括零件P相邻的所有已装配零件的最低级装配体和P看成是一个新的装配体,应用算法3.1求解的装配序列规划.如果装配体A包含所有零件,算法转(6),否则,转(2).把由定理生成的二叉树进行后序遍历,每个结点看成一个装配体,即得装配序列即为可行装配序列规划.3.2 算法复杂度在装配体分解过程中,假设装配体含有m个零件,由参考文献1知进行一次分解的时间复杂度是O(m(m-1).不难看出,抽取含m个零件的装配体局部模型的复杂度也是O(m(m-1), 分解后调整装配序列规划的时间复杂度是O(mlogm).假设在装配一个新零件P时,在装配体中装配不成功的可能性是p,则算法的计算量是:假设整个装配体有n个零件,则算法的全部计算量最坏为:mi表示当安装第i个零件时对应的局部装配体.Mmax表示分解过程中出现的最大子装配体.4.实例仿真图5为一手压阀,表1为相应零件的明细,装配的方向可以按工艺要求事先选定,也可随机选择后进行择优.假设我们规定装配按照从x,y,z方向顺序进行装配,为了节省篇幅,我们把对应的二叉树变迁用其规范型来表示,则应用上述算法装配过程如下:图5 手压阀装配图表2 手压阀零件明细表序号 名称 序号 名称 序号 名称1 球头5阀杆 9 弹簧2 手柄 6 锁紧螺母 10 调节螺母3 开口销 7 阀体 11 胶垫4 销钉 8 填料选中零件11胶垫到装配位置(11,10)(11,10),9)(11,10),9),7) (11,10),9),7),5)注:5装配不成功,分解该装配体得(11,10,9)(5,7),应用定理2调整装配序列得 (11,10),9),(5,7) (11,10),9),(5,7),8)注:8已装配相邻零件都在子装配体(5,7)中,故8和(5,7)合并为一个大装配体 ( (11,10),9),(5,7),8),6)(11,10),9),(5,(4,7),8),6)注:包含零件4全部相邻的零件子装配体是零件7,即单一零件也被看成是装配体,以下类似.(11,10),9),(5,(4,7),3),8),6)(11,10),9),(5,(4,2),7),3),8),6) (11,10),9),(5,(4,(2,1),7),3),8),6) .从上述装配过程可以看出,当装配某一零件不成功时,绝大多数情况下只需要对局部序列进行调整即可.目前,求解可行装配序列的方法大多是基于拆卸的4,表1给出了与基于拆卸方法的比较结果.其中拆卸方法采用了文献5给出的方法(找到可行序列为准).表1 实际装配体可行装配序列生成效率比较方法 初始零件 方向 最坏计算量 平均计算量 变更序列二叉树规划 可选 随意 15 13 可行拆卸方法 不可选 随意 60 36 不可行初始零件是可行装配推理的开始部分,基于拆卸的方法如果不存在初始推理零件,则需要寻找初始可拆部件,这将使得算法的计算量大大增加.而本文算法,初始推理零件理论上可任意选取(实践中可根据工艺要求择优选取),一旦推理失败,则通过调整已有序列的算法使得推理可继续进行.表1给出了它们的比较结果,结果表明本文算法具有明显优越性.计算量是按频度出现最高的语句进行比较的.图6 装配示例拼块图图5是实际产品例子,零件间约束较弱.为了更清楚说明本文算法的优点,我们构造了图6装配体.在图6中,我们假定装配体在平面装配,零件为刚性铁线,相邻零件的间隙是0(如2,3零件是直接相邻的,1,3不直接相邻,有间隙),相邻零件间有严格的定位要求(即缺口位置要求要按照图示装配).图6构造了一个模拟当零件间装配约束较强,装配体的装配方向较多,一次仅能拆出少量零件时装配拼块图,装配过程的二叉树变换与上例类似.并应用该方法和其他方法进行了比较,表2给出了比较结果.表2 强约束装配体可行装配序列生成效率比较算法名称 初始零件 方向 最坏计算量 平均计算量 变更序列二叉树规划 可选 折卸 8 7 可行拆卸规划 不可选 装配 30 18 不可行在表1中,算法1可从任意零件出发进行装配,而算法2是进行子装配体识别,识别后得到的第一个子装配体只能是零件5.算法2是基于求解拆卸序列来求装配序列的,而算法1是基于装配定理进行规划的,其直接影响是算法1得到的已得到的拆卸序列不可更改,而算法2却可根据定理2自适应地调整已有序列.在计算量上,如果算法2开始就选中了零件1,则每次装配均能顺利完成,其计算量是O(5),这是传统算法无法想象的.可见,能灵活选定初始装配零件对规划装配是非常有意义. 5. 结论针对目前大多数可行装配序列生成技术效率较低的问题,提出了可行装配序列生成的新算法.本算法有以下好处:通过约束的局部化处理,使得装配效率大大提高.目前大多数装配序列规划算法都是从全局角度考虑,而在实际问题中约束常是局部的,许多情况下还以明显的子装配体出现.约束的局部化处理明显能改善算法计算量.当零件数较多,装配体装配方向较多时,一次又仅能拆出少量零件时,如在图6中,假定从零件2出发,装配零件3,再装配零件1.装配1时,由于包含和1直接相邻且已装配的最低级装配体是2,而在2中1可直接装配,2和1可直接构成新的子装配体即可,并不需要从全局出发进行专门的子装配体分解,更不会放弃先前已经得到的装配序列成果,因而计算量大大减少.总之,由算法复杂度分析和仿真实例不难看出,本文方法的局部化处理优越性明显.推理过程非常灵活.推理在开始时对从那个零件开始没有约束,实际应用时即可随机又可根据需要人为调整.如在图6中,即可从零件1开始推理,也可从零件3开始推理.不论是在装配过程中还是装配结束,都可以利用定理2调整装配序列,从而得到许多不同的装配序列规划