英译原材料.pdf

Journal of Manufacturing Systems Vol 15 No 4 1996 GAPP A Generative Assembly Process Planner Luc Laperri re Universit6 du Quebec a Trois Rivieres Trois Rivibres Quebec Canada Hoda A EIMaraghy University of Windsor Windsor Ontario Canada Abstract This paper presents results of exhaustive research in automated assembly planning A generative assembly process planner GAPP has been developed that takes as input a solid model of the product to be assembled and out puts its feasible assembly sequences Once the product has been modeled as a solid using a commercial solid modeler the resulting solid model s boundary representation B Rep file is interpreted by the GAPP to generate mating informa tion among parts in the form of a relational graph This graph becomes the input of a search graph process whose con strained expansion reveals all feasible assembly sequences from a geometric stability and accessibility point of view The relative goodness of different feasible assembly sequences can be determined using pertinent criteria such as the number of reorientations involved or the clustering of similar assembly operations into successive ones The expansion engine is very flexible and enables many different types of assembly problems to be handled uniformly for example finding disassembly repair sequences not requir ing complete product disassembly or generating assembly sequences that force the building of predefined subassem blies Examples with real industrial products are provided to illustrate the potential of using this tool Keywords Assembly Disassembly Assembly Sequence Assembly Planning Introduction Shorter product lifecycles smaller batches and just in time production have drastically reduced the time spent for assembly planning activities This has called for the development of efficient software tools to assist the planner Among the tasks the planner has to perform the choice of an appropriate assembly sequence is a cru cial one because of its economical impact Earlier research in assembly planning focused on methods for automatically generating the numerous assembly sequences of a given product as well as investigating potential compact assembly sequence representation schemes s Most of the reasoning was left to be done a posteriori by the human planner for example elim inating unfeasible assembly sequences with respect to some constraints and or evaluating and selecting a few good feasible ones based on some cost criteria Today there are many assembly planners that can automatically generate all possible assembly sequences of a product and discard all those that are unfeasible with respect to some constraints 6s Current research focuses on the formalization of such constraints used to reduce assembly sequence count and on the formalization of different relevant cost criteria that can be used to select better assem bly sequences among all feasible ones 9 12 This paper describes the developed integrated approach to assembly planning where generation elimination and evaluation of assembly sequences are all performed in a single process The resulting software tool called the generative assembly process planner GAPP is implemented in C and runs the OSF MOTIF window interface on a Silicon Graphics workstation Figure 1 shows a block diagram of the software A screen dump of the window interface is also presented in Figure 18 at the end of the paper The next section of the paper describes the prod uct s graph model which is generated automatically from the product s solid model and is used as input to the assembly sequence enumeration engine briefly described in the third section Next are outlined some constraints used to eliminate unfeasible assembly sequences and as a result reduce search space The fifth section briefly describes the role of cost criteria Practical applications are presented next and the last section discusses accomplishments Product Graph Model General Description Assembly operations can be viewed as establish ing contacts and attachments among parts or sub assemblies using collision free paths One central element in assembly planning is therefore the knowl edge of mating information among parts This kind of information lends itself to a binary relation on the set of parts that can be more appropriately represent ed in the form of a graph model where vertices are parts and edges are mating relations among them 13 282 Journal o ManuJacturing Systems Vol l 5 40 4 1996 User input Product s solid model I1 Feasibil ly constraints on or o I I Eva oat on cr teria ofre at ve mpo oce Search method I 1 1 Boundary representation file Product s graph model I I Assembly sequences enumeration engine I I S II Outputs Linear sequence of optimal assembly operations I moved subassembly I fixed subassembly directions of insertion L J Figure 1 Block Diagram of the GAPP Figure 2 shows a simple four blocks product along with its graph model As can be seen three types of mating relations are possible They are defined as follows 1 Two components have a contact relationship between them if they are in constant physical contact in the assembled product 2 Two components have a blocking relationship between them if they are not in constant physi cal contact in the product and if a linear transla tion of one of them in one of the orthogonal directions results in a collision with the other 3 Two components have a free relationship between them if they are not in constant physi cal contact in the product and if a linear transla tion of one of them in any of the orthogonal directions does not result in a collision with the other Figure 3 shows an example of two parts having a free relationship between them Note that although blocking and free mating rela tions do not involve contact they imply that colli sion free paths with respect to the chosen coordinate system may or may not exist These noncontact mat ing relations play an important role in determining feasible assembly sequences from a geometric inter ference point of view Clearly the above definitions are such that the graph model of any product is always a complete graph that is every part has at least one of the above three mating relations with every other part Generating the graph model is therefore a geometric reasoning process that mainly consists of identifying which parts have which types of mating relations with 283 Journal of Manufacturing Systems Vol 15 No 4 1996 Z x J Block a Block b i Block c Contact Blocking Block d Figure 2 Four Blocks Product Along with Its Graph Model Block a Z x L Plane surface P of block a Plane surface of block b Pz Figure 4 Identification of First Contact Between Surfaces of Two Blocks Z xft Block b Free Figure 3 Two Blocks Having a Free Relationship Between Them which other parts For a product with n components n n 1 2 mating relations must be identified Automatic Generation of Graph Model from Solid Model A method has been developed that builds the inter nal computer representation of the graph model auto matically from the information contained in the B Rep file resulting from the product s solid model using the ICEM DDN commercial hybrid solid modeler The method mainly consists of analyzing the part s surface information contained in the B Rep file In particular mathematical tests involving surface pairs each on a different part help determine whether the parts to which these surfaces belong are in contact blocked or free Figures 4 and 5 show an example for the identi fication of the contact mating relation between blocks a and b in Figure 2 from an analysis of their mat ing surfaces definition contained in the B Rep file In Figure 4 n and n2 are the unit normal vectors of the bold surfaces of blocks a and b respec tively The distance between the two blocks is denot ed by d Pl and P2 are points on the surfaces Assume the limits of the planes of blocks a and b with respect to the chosen Cartesian system are Xmi 1 Xmaxl Yminl Ymaxl Zminl Zmaxl and Xmi 2 Xmax2 Ymin2 Ym x2 Zmin2 Zm 2 respectively For identification of the contact between these two surfaces three condi tions must be satisfied nl n2 nix n2 nly n2y nl n2z I Figure 5 Identification of Another Contact Between Surfaces of Two Blocks a l p2xn l 0 Inl I where P P2 Pz P i Pzy Ply j P2z Pu k and 2 2 In 2 3 4 Xminl Pz Xm l andyminl P2y Ymaxl or Xmin2 Plx Xmax2 and Ymi 2 Ply Ymax2 5 All the information required for the above geo metric reasoning is directly extracted or computed from the B Rep file In Figure 5 nl and nz are the unit normal vectors of the bold surfaces of blocks a and b respec tively Assume the limits of the cylinders of blocks a and b with respect to the chosen Cartesian system are Xminl Xmaxl Ymlnl Ym l Zmi l Zm x0 and Xmin2 Xmax2 Ymin2 Y 2 Zraln2 Zmax2 respectively For the identification of the contact between these two surfaces three other conditions must be satisfied 284 Journal of Manufacturing Systems Vol 15 No 4 1996 result i loo ooo 1 ooo ooo 1 FM el b 1 l oo n ooo OlllJ lll 1 011 Figure 6 Freedom Matrices Associated with a Relation Between Two Parts nl nz 0 6 Xmin2 Xminl Xmax2 and Xmin2 Xmaxl Xmax2 Ymin2 Yminl Ymax2 and Ymin2 Ymaxl Ymax2 Zmi 1 Z ax2 7 diameter 1 diameter 2 8 The same conditions used to determine if surfaces are in contact are also used for blocking and free mating relations identification For example a blocking between two planar surfaces requires con ditions 1 and 5 to be satisfied but not condition 2 whereas a free relationship between the same type of surfaces only requires condition 1 to be sat isfied but not conditions 2 and 5 Building Freedom Matrices A part in 3 D space has a maximum of six degrees of freedom three translations and three rotations In assembly planning it is more appropriate to talk about half degrees of freedom by further considering the actual direction or of a translation or rota tion 4 This gives a total of 12 half degrees of free dom for the same part Tx Tx Ty Ty T T Rx Rx R Ry R R The letters T and R stand for translation and rotation respectively Once a contact blocking or free relationship has been identified conditions satisfied between any pair of surfaces between two parts the tmderlying half degrees of freedom this relation provides to the parts implied are represented in an appropriate 3 x 4 matrix called the freedom matrix where there exists a correspondence between each entry in the matrix and the half degree of freedom it represents Tx Rx R Tz L Rz Rz J Freedom matrices are built automatically for every contact surface pair A freedom matrix func tion FM argl arg2 has been developed where argl is a mating relation and arg2 is a part The function returns a freedom matrix representing this part s half degrees of freedom provided by that rela tion Every half degree of freedom that is available or not is represented by the entry 1 or 0 in the matrix respectively Such information is used for computing geometric interference in disassembly operations Figure 6 shows a simple example or freedom matrix computation using the two contact relations identified in Figures 4 and 5 The freedom matrices associated with both planar contact Figure 4 and cylindrical contact Figure 5 are shown To obtain the resulting freedom matrix at the part level all that is required is to perform a positionwise logical and between the entries of each of the surface level freedom matrices previously generated Limits of the Model For now every part of the product to be assem bled must be modeled using block cylinder cone sphere revolution and slab sweep primitives and their Boolean combination Although the solid mod eler used enables complex objects to be modeled for example using air tight B spline envelopes from which a solid can be computed the format of such solids in the B Rep file is complex and its interpre tation using some condition s to identify mating relations has not been formalized yet Another limitation lies in the automatic computa tion of the rotational part of freedom matrices For now only the translational part is generated auto matically from the B Rep file analysis using the concepts described so far The rotational part if nec essary must be supplied manually Complete automation of the graph model generation is there fore limited to this wide and representative category of products whose parts and subassemblies can be assembled from single translations this is also a fundamental design for assembly rule Finally the GAPP can process products whose parts and subassemblies can be assembled in direc tions complying with those of the chosen orthogonal coordinate system Because the B Rep file explicit ly represents surface normals using standard 4 x 4 homogeneous matrices it is possible to identify 285 Journal of Manufacturing Systems Vol 15 No 4 1996 assembly directions other than those aligned with the coordinate system Extending the approach for such cases has not been investigated Assembly Sequences Enumeration After having derived from the solid model a more suitable assembly representation scheme in the form of a graph model an algorithmic engine is next used to exploit this model and extract assembly sequences out of it Basic Enumeration Principle Homem de Mello and Sanderson have developed a mathematically robust and systematic assembly sequence enumeration engine The process starts by putting the product s graph model as the root node of a search graph Search graph expansion is accom plished through the computation of the cutsets in the root node a cutset is a set of edges in the graph the removal of which increases the number of graph components by onemS To every cutset there corre sponds a new node in the layer underneath Any new node has the graph representation of its parent node minus the edges in the cutsets from which it was generated Then the cutsets in the graph representa tions of the newly generated nodes are computed yielding another layer and so on This process stops when a node has been generated where all edges have been removed Note that this disassembly approach is close to that used by the human planner In the GAPP assembly sequences generated this way are represented compactly in a graph of assembly states Figure 7 2 Every path from top to bottom rep resents a disassembly sequence Going from the bot tom up gives the corresponding assembly sequence Figure 7 Unconstrained Graph of Assembly States of Four Blocks in Figure 2 of the root node are inherited by each new child node Some edges of the inherited cutsets which are not part of the new child node must first be deleted For example child5 was obtained from cutset e e3 es The edges in this cutset must not be part of any cutsets of child5 They are therefore deleted from the inherited set yielding the new cutsets 1 ea 2 e 3 e4 4 e4 5 and 6 e2 e4 Updating the Cutsets In reality one cannot afford to compute a new set of cutsets every time a new node is generated in the search graph because of the underlying combinator ial complexity that this computation involvesJ 6 A method has been developed that ensures that only the set of cutsets in the root node of the graph of assembly states is ever generated Any other cutset in any newly generated node is simply obtained by updating the set of cutsets of the root node Figure 8 is used to describe the approach After the six cutsets of the root node have been computed six new states of the graph are generated The six cutsets Out of this new list the first and second as well as the third and fourth are combined because they both represent the same cutset The fifth which was removed from the root node to generate child5 is eliminated as it became empty Therefore the list becomes 1 e 2 e4 3 ea e4 An algorithm is then used to check if the remain ing sets of edges are indeed cutsets that is yielding 286 Journal Of 44anujbcturing Systems Vol 15ANo 4 1996 Child 1 Child 2 Child 3 Child 4 Child 5 Child 6 Cutsets of root node J e e e e3 e e e es e e e e e es Inherited by child 5 e ez e2 e3 es e3 e e e eE e e3 eE e2 e es Remove edges not in child 5 ez eTJ e e e2 e I Combine similar remove empty e e2 04 Eliminate non cutset 1 e Figure 8 Determination of Cutsets of New Child Node by Analyzing Ones Inherited from Its Parent exactly one more subassembly in the child state than in the parent state Applying this algorithm for the above sets of edges eliminates the last one The cut sets of child5 are then 1 e 2 e4 This process is repeated for every new child node to determine their cutsets by means of a simple analysis of the ones inherited from their parent Note that only contact type edges are considered at this stage in the cutsets computations that is inclusion of other relation types like e6 in this example would not help identify more potential subassemblies and would simply decrease the computational efficiency Blocking and free relations are considered only when geometric interference issues are addressed L x 1 Block a Cutset Block c Block d FM e b FM e b FM e2 b Result ollo V l F l 000 0 0 oooo q oo n o ooo LOl 111 LlOllj LlOll OOllj Figure 9 Cutset in Graph Model of Four Blocks and Corresponding Freedom Matrices Using Feasibility Constraints The engine described earlier does not consider the physical feasibility of the disassembly operations associated with each cutset Three feasibility con straints are used to ensure that the generated assem bly sequences are indeed feasible They are 1 Geometric interference constraints 2 Stability constraints and 3 Accessibility constraints These can be turned on or off by the user for com parison purposes see Figure 18 Geometric Interference Figure 9 illustrates how freedom matrices are used to compute automatically the geometric feasi bility of separating two subassemblies in a disas sembly operation It is desired to determine if an operation that splits the four blocks into the two sub assemblies b and a c d is geometrically feasi ble The cutset e ez e6 is associated with this operation note that all types of relations m