（机械电子工程专业论文）基于装配优先图的装配顺序规划.pdf

华中科技大学博士学位论文 作为并行工程与计算 魂快速产品开发，提升 。模，零件间优先关系的 摘要 装配顺序规划对 对装配体分析及 行了系统深入研 究，并初步建立了一个面向机械产品的装配顺序规划原型系统。 提出了由直接配合关系罹疆丽e 合关系的算法；为减少后续的几何推理，根据 零件间的配合关系以及点接触约束分析，定义了一种具有较好丌放性和柔性的装配体 配合关系模型：为表达产品中零件的功能信息和层次结构，降低规划的复杂度，定义 了一种装配体层次关系模型，并提出了分级识别部件、组件的算法。 在已建立的装配体模型基础上，提出了几何约束推理的运动空间方法。陋过引入 局部自由锥概念，减少了无向阻塞图上的单元数目；根据运动旋量空间与力旋量空间 的对偶性，提出了在力旋量空1 1 日j 进行力约束推理的方法，并分析了力约束对装配拆 卸顺序可逆性的影响；通过把装配体中的零件划分为部分受约束零件、完全受约束零 件两类，基于得到的几何约束，提出了影响零件拆卸优先关系的提取算法，从而实现 了由装配体模型直接获取优先关系的过程，避免了从显性表示到隐性表示的转化过 程，为集成装配工艺师的经验知识提供了极大便利。 针对生成一组装配顺序的要求，引入装配优先图概念，提出了由优先关系系统生 成所有装配优先图的算法；在子图替换基础上，通过计算装配优先图包含顺序的多少， 实现了装配优先图的评价；为表达所有可行的装配顺序，提出了由装配优先图生成或 图的算法：为便于在不同的装配顺序规划系统上统一利用装配优先图进行顺序规划， 探讨了如何构造与一组装配顺序等价的装配优先图的途径。 在获取优先关系或装配优先图以后，利用遗传算法具有顺序级全局搜索的能力， 提出了基于遗传进化的顺序生成方法；利用主动稳定与减少装配方向改变次数两个启 发式规则，提出了基于拆一装策略的顺序生成方法，从而实现了一种满意装配顺序的 生成。入一，亚 ，其中p 为零件集，c 为零件间的面接触集，a 为 零件间的联接集，胄为p uc u a 中各元素的关系集，a - f u n c t i o n s 为p uc u au r 中 的属性函数集。该模型区分了零件间的接触关系和联接关系，所含信息量较多，建模 的难度比较大，但更易于装配顺序规划的自动化。 ( 5 ) 层次树模型。h e e d o n g k o 7j 等人认为装配体自然地可表达为图1 5 所示的层次 树结构，但他们应用配合条件，集中研究了零件层次结构( 即结构中的每个接点表示 一个原零件) ，并且假想该结构为一棵树，结果使得当零件结构为片森林，或者该 结构存在两零件相互阻塞情形时，经常导致他们提出的装配顺序生成算法失效。同时， 根据他们提出的f i t 配合条件无法具体推理出零件的局部可行性，并且仅考虑了直接 配合条件，忽略了隐含配合条件，而隐含的配合条件可加快推理过程。 图1 5 层次树模型 对于部件的识别，许多作者1 1 8 1 9 2 0 2 1 1 针对特定的产品，从不同侧面提出了相应方 法。遗憾的是，这些方法或者集中在一个层次上进行，或者假想已经由人工完成。根 据一定知识对零件进行分组( g r o u p i n g ) ，把一些零件合并为组件( g r o u p s ) ，也不失为减 少装配体中零件数的途径。l e e - 2 2 l 为缩减联络图提出超( s u p c r ) 节点和组( g r o u p ) 节点概 。念。超节点由那些出予工具或联接件不能到达指定位鼍，或者所需配合力不能传递过 6 华中科技大学博士学位论文 去的原因，而不能作用的一些零件构成；组节点由拥有特殊装配工艺的一些零件构成， 但是该方法不能自动对零件进行分组。h e e m s k e r k l 2 3 1 基于用户提供的零件清单有关特 征，提出了一种分组方法。他粗略地把组件定义为一组装配过程中不穿插组件外其它 零件的零件，并把组件分为种类( s o n ) 、堆栈( s t a c k ) 、层次( l a y e r ) 三种类型。其中种 类组件由具有相同形状和在装配体中具有类似相对位置的零件构成，堆栈组件由在相 同装配方向接触的零件构成( 形状可以不同) ，层次组件由被外面两个零件夹在中间的 些零件构成。h a d i l 2 4 】利用拆卸方法，基于装配体中零件间的阻塞关系，在每一拆卸 步骤识别目前子装配体中可能存在的组件。 另外，还有w o l t e r t 2 5 】提出的装配约束图，h u a n ga n dl e e l 2 6 提出的特征配合操作 圈等模型。 不难看出，对大多数的图结构装配模型来说，它们的区别只不过在于图接点及不 同接点间连接的包含信息量多少而已。点接触模型虽然适合表示大部分的多面体之间 或非多面体之间的接触形式，但需要大量的几何推理；配合图模型只适合典型的配合 条件，但减少了几何推理。两者相结合来构造一种图结构装配模型，不失为一条好途 径，不过目前还没有人提出该方法。为降低规划的复杂度，层次树模型也显得很有必 要。遗憾的是，如何分级识别部件、组件，最终建立合理的层次树模型，也未见报道。 当前大部分用于顺序规划的装配模型，仅仅考虑到几何约束信息，除此之外的设 计、技术等信息没有在装配模型中表达出来，因此普遍存在包含装配约束信息不完备 的缺点。这种不可避免的客观事实，要求我们在后续的装配顺序推理和表示中提供弥 补该缺点的手段。 1 3 3 装配顺序的生成( 推理) 相对于非几何信息而言，几何信息更易于建模，因此，几何装配顺序规划一直是 当前研究装配顺序规划的主要潮流。从根本上讲，每种装配顺序必须确保新装配的零 件不与己装配上的零件发生干涉，这就是所谓的几何优先约束。然而实际上为了得 到最终的装配顺序，经常还需考虑其它附加的非几何约束。只要获得零件或零件连接 间的优先约束关系，装配顺序就很容易获得。按照获取优先约束的方式，可把装配顺 序的生成方法分为两大类：直接法和间接法。 ( 1 ) 直接法。在早期的装配顺序规划系统中，经常从装配的观点，利用人机交互 “问答式”方法获取装配优先约束。如b o 嘶a u l t 2 提出的构造所有不同装配连接间优 先关系的交互式方法。该方法采用连接图模型描述零件之间的装配关系。 令甩表示产品连接图的装配连接数，= l ”，厶) 表示包括所有装配连接的集 合。为得到连接厶与其它连接的所有可能优先约束关系，显然必须以厶和三圮中的 任意组合为问题主体向用户提出下列两类问题： g j ：在装配连接i 厶 ，厶巾 c 厶，上，建立之后，装配连接厶能够建立吗? ( y e s n o ) q 2 ：在装配连接 厶，m ) c 建立之前，装配连接厶能够建立吗? ( y e s n o ) 7 华中科技大学博士学位论文 其中o p 一2 。如果问题q l 的回答是“n o ”，则建立p 元优先关系彤( 厶，厶，l j + p ) ， 表示连接厶必须在 厶，易叩) 建立之前建立；如果问题q 2 的回答是“n o ”，则建立 p 元优先关系品( l “，与枷厶) ，表示连接厶必须在 与，与印) 建立之后建立；在对每 个装配连接完成上述提问后，我们可以得到装配连接之间所有可能的优先约束关系。 采用上述方法产生优先约束需要用户回答大量的问题。为减少提问的次数，在提 问过程中可以利用已有优先关系推导出其它优先关系，如在已知r ( 工n 句) 以及连接厶 和厶不能同时建立的前提下，能够推理出双上，厶) 。在最坏情况下，所需提问的次数 为月2 ”一2 ”，因此该方法只能应用于由较少零件组成的装配体。 针对上述方法所需提问次数多的缺点，d ef a z i o p l 改变了提问的方式，对于每个 装配连接厶向用户提出下面两个问题： q ：哪些装配连接必须在建立装配连接厶之前建立? q 2 ：哪些装配连接必须在建立装配连接厶之后建立? 根据用户的回答，分别建立以下优先约束关系： r l ：( 与o r a n d l m ) o r ) 一厶 r 2 ：l ，一，o r ，a n d 上。) o r ) 其中“啼”表示“必须优先于”。这样使得提问的次数减少至2 n 个，但是回答问题 的难度却大大增加。利用该方法，在获取优先关系过程中能够考虑到包括几何及与工 艺相关的等诸多约束。用户在问答问题的过程中会不可避免地出现失误，可能导致生 成不可行的装配顺序，或者遗漏一些可行装配顺序，从而难以保证装配优先关系的完 备性和正确性。 在上述提问过程中，如果采用下列两条规则来回答部分问题，用户需要回答的问 题数将进一步减少： 超集规则。如果两个部件由于几何干涉无法装配，那么在其任一部件中增加一个 或多个零件后，这两个部件仍然不能装配； 子集规则。如果两个部件可以装配，那么在去掉其任一部件中不与另部件发生 装配关系的任何零件后，这两个部件依然可以装配。 ( 2 ) 间接法。 使用直接方法获取优先关系，往往会碰到这样难题：不是向用户提问的问题过多， 令用户厌烦，就是回答问题太复杂，令用户疲于烦琐的推理。一些学者从拆卸的观点 来着手，采用不明显生成优先关系的方法，直接生成由a n d o r 图等表示的拆卸顺 序。表面上看来，该方法没有生成优先关系，实际上a n d o r 图等本身隐含了优先 关系。对大多数产品来讲，装配顺序与拆卸顺序往往是可逆的。通过对产品进行拆卸 顺序规划，然后将拆卸顺序颠倒过来将得到产品的装配顺序。拆卸的方法起始于产品 中各零件处于最终装配状态，在该状态各零件所受到的约束最多，并且零件或子装配 体的可拆卸性直接包含了零( 部) 件问优先关系的满足与否问题。相反，装配的方法起 始于产品中各零件处于开始装配状态，在该状态各零件往往假设为不受任何约束，只 有穷举出各种组合，爿能知道零( 部) 件删的优先关系。因此采用间接法获取优先约 束比直接法更有效。 8 华中科技大学博士学位论文 在间接法中，又可分为两大类：“生成一检验”( g e n e r a t e - a n d - t e s t ) 方法和“检验 一生成”( t e s t a n d g e n e r a t e ) 方法。使用前者的主要代表是h o m e md e m e l l o p l ，其中 以图论作为理论基础。使用后者的主要代表是w i l s o n 【8 刀】，其中以计算机几何作为理 论基础。 h o m e md em e l l o 采用了问题分解的方法，即首先利用图论中的割集算法对连接 图进行划分，生成所有可能的子装配体，然后对每个予装配体的拆卸操作进行几何和 物理检验，排除不可行装配操作，从而生成所有可行的拆卸顺序。这里实现的关键在 于稳定性、几何可行性和机械可行性的三个谓词的可计算性。作者在其算法中只是假 设这三个谓词是可判定的，没有提及实现这三个谓词的途径和难度。另外，其算法计 算复杂性为0 ( 3 “) ( 为零件个数) ，存在指数爆炸问题。g u 【2 8 】利用双向连接 ( b i c o n n e c t i v i t y ) 把装配体的连接图分解为双向连接的子图，即不存在任何割点的连接 图( 这些连接子图对应不能再分解的零件组或子装配体) ，然后对每个子装配体的装配 顺序进行搜索，所有子装配体的装配顺序合并在一起就形成了产品的装配顺序。 稳定性 2 9 , 3 0 , 3 1 , 3 2 , 3 3 1 主要解决三类问题：稳定性与否。给定一装配体，判断它在 某一方向是否稳定。稳定方向。识别一方向( 如果存在) ，使得该装配体稳定。最 小不稳定方向。装配体在所有方向都不是稳定的，寻找一方向，使得该装配体尽可能 稳定。由于稳定性问题本身是个n p 问题，对于装配顺序规划来讲，往往只研究第一 类问题，即识别在重力方向装配体上的所有零件是否稳定。采用拆卸方法来获得产品 的装配顺序，必须对每一拆卸步骤剩下的零件进行稳定性检验。这意味着从被动的角 度来考虑稳定性。由于需要稳定性检验的次数往往过多，导致在实际应用中难于自动 实现。 计算机几何方法起初应用在路径规划领域，主要集中在基于元特征，开发有关把 两维的多边形或三维的多面体零件分离为平移顺序的几何算法上。目前，该种方法得 到了扩展并应用到装配顺序规划领域。w o o l 3 4 j 利用穿透射线( r a y t r a c i n g ) 算法识别零 件的拆卸方向。该算法的原则是，如果从待考虑的零件出发的射线不穿透装配体中的 任何其它零件，则该零件可以从装配体中移去。这一可移方向是根据零件间配合面的 法向量计算得到的。该方法仅仅考虑了由面面接触的零件构成的装配体，并且仅允许 平移运动，平移时一次只能移动一个零件的情形。 形位空间【瑁”6 3 9 l ( c o n f i g u r a t i o ns p a c e ，c 空问) 作为描述机器人、刀具和测量 头等刚体位姿( 位置和姿态) 的一种抽象数学结构，近几年来在机器人运动规划、n c 机床刀具轨迹规划和三坐标测量机( c m m ) 测头路径规划等相继被采用。w i l s o n i s j 首先利用c 空间对几何装配顺序规划进行了数学描述，基于零件的一组等价点接触 约束集合，识别所有可行拆卸方向，然后在这些拆卸方向上把装配体分解为子装配体。 利用无向阻塞图( n d b g ) ，即运动球，以及与之相关的有向阻塞图( d b g ) ，来表示装 配体中所有零件问的阻塞关系。一旦从n d b g 识别出候选拆卸方向，就可生成对应 的d b g 。d b g 是一个有向图，表示了给定方向上零件间的局部阻塞关系。可以利用 d b g 识别局部可移的子装配体，然后再对这些局部可移的子装配体进行全局几何干 涉检查。该方法既考虑了平移装配操作，又考虑了旋转装配操作。r o m e n y l 4 0 l 等利用 9 华中科技大学博士学位论文 面面接触约束识别零件间的阻塞关系。他们把每个零件的所有可移方向合成一个局部 平移自由锥( l t f ) ，然后合并装配体中所有零件的l t f 而生成n d b g 。该方法大大减 少了n d b g 的搜索空问，但只考虑了装配操作中的单步平移，且装配体中的零件仅 限于是多面体的。 由于一个装配体连接图包含的割集经常随着零件数呈指数增长，当产品中的零件 数目较多时，“生成一检验”方法因需要进行的可行性检验太多而常常无法进行。采 用“检验一生成”方法，先识别拆卸零件时不发生干涉的可行方向范围，然后在这些 方向上拆卸零部件，避免了几何不可行装配顺序的产生。 装配顺序的生成除了受几何因素、技术因素的影响外，还存在模糊经验知识的使 用问题。一些装配顺序可能满足几何条件，但不一定符合实际生产情况，这就识别涉 及到人的经验知识。