外文翻譯--GAPP一個裝配工藝生成規(guī)劃器 英文版

Journal of Manufacturing Systems Vol. 15/No. 4 1996 GAPP: A Generative Assembly Process Planner Luc Laperrire, 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 models 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. 912 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- ucts graph model, which is generated automatically from the products 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 Products solid model I1 Feasibil,ly constraints (on or o I I Eva,oat,on cr,teria,% ofre,at,ve,mpooce, Search method . I . 1 . 1 . Boundary representation file Products 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 products solid model, using the ICEM/DDN commercial hybrid solid modeler. The method mainly consists of analyzing the parts 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, Zm2), 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 pairof 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 parts 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 products 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 Blocka Cutset Block c Blockd FM(e, b) FM(e, b) FM(e2, b) Result ollo V l Fl 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 must be considered here in the cutsets). The freedom matri- ces of block b relative to the relations in this cut- set, also shown in Figure 9, are used to compute the geometric feasibility of this operation. In particular, by performing a positionwise logical and between the binary entries of the freedom matrices, the resulting matrix contains all zeros in the first two columns associated with translations. The interpretation is that this operation is not geometrical- ly feasible because there does not exist a disassembly direction along which part b can be removed. 287 Journal of Manufacturing Systems gol. 15/No. 4 1996 Stability Another important constraint during assembly execution is stability. Among all possible assembly sequences, many must be discarded due to stability problems. Because the four blocks in Figure 2 are not very interesting from a stability point of view, consider instead the flashlight in Figure 10. Note that although the represented disassembly operation is geometrically feasible, it clearly results in a high- ly unstable configuration. Following is a brief description of the stability model used by the GAPP. Stability is computed by first finding a subgraph of the graph model called the stability-directed subgraph. It is build by a progressive graph-grow- ing procedure using an algorithm. The basic con- struction principle is to find, for every component in the original graph model, which other component stabilizes (or secures) it, using which relations. The first step is to identify a part considered fixed (or grounded) in the complete product (usually the one with the lower z-coordinate assuming the z-axis is pointing upward). This part is put in the set P of processed components. Then the algorithm starts and picks another part not yet in P. It checks if this component is secured by any relation with the parts in P. If so, the relation(s) is (are) added to the set A of arcs. The arc(s) point(s) from the secured component to the securing component. As an example, in Figure 11 the component head was chosen as the initially fixed (or ground- ed) component and put in set P. Assume the part reflector was then chosen by the algorithm. Because this part is implicitly attached to the head by a snap fit, this part is in turn added to P and the relation between the reflector and head becomes an arc in the stability subgraph. This arc points from the Cap =- Spring Body Flashlights graph model I _ battery2 battery1 Reflector J- H Bulb r., . _- Lens Head Figure 10 Geometrically Feasible Disassembly Operation that Can Be Applied to Completely Assembled Flashlight reflector to the head and is added to the set A. Assume the cap is chosen next. This part is not secured by any of the parts in P at this stage. Another part is then chosen, say, the bulb. This part is secured by an implicit screwing to the reflector, already in P. The bulb is then added in turn to P and the arc pointing from the bulb to the reflector is added to A. The process continues until all parts have been successfully processed. A much more detailed description of the stability subgraph and the algorithm used to build it can be found in Lavoie and Laperri6re. v Once the stability subgraph D = P, A has been constructed, stability can be computed by the fol- lowing simple rule: if a cutset breaks at least one outgoing edge of the fixed subassembly or more than one outgoing edge of the moved subassembly, Cutset associated with Figure 10 X Cutset Moved subassembly fixed Flashlights stability subgraph Fixed subassembly Figure 11 Using Stability Subgraph to Estimate Disassembly Operations Stability 288 Journal qf Manufacturing Systems Vol. 15/No. 4 1996 then the corresponding disassembly operation is considered unfeasibleJ 7 Going back to Figure 11, it can be seen that the cutset under investigation breaks the flashlight into the following two subassemblies: cap spring body and head lens reflector bulb batteryl battery2. The former is the moved subassembly (grasped), and the latter is the fixed subassembly (because it contains the head initially chosen as grounded). This cutset breaks one outgoing edge of the moved sub- assembly: body head. Thus the rule above is not violated so far. But it is also seen from the figure that two outgoing edges of the fixed subassembly are broken by the cutset: batteryl body and bat- tery2 body. Thus by taking away the body, the bat- teries become unsecured and fall instantaneously (unless special fixtures are supplied, which is not considered for now). Experiments with this stability model have shown surprising results on how stringent the stability con- straint can sometimes be. For the flashlight product in Figure 1 O, by turning on only the geometric inter- ference constraint, there were 331 nodes expanded in the graph of assembly states, giving 12 896 paths (assembly sequences). By adding the stability con- straint in the expansion process, 17 nodes with 14 paths were generated (Figure 12). This drastic reduction is explained by the fact that for this prod- uct the stability constraint leads to the elimination of many nodes in the higher levels of the search graph, close to the root node. Accessibility Consider the removal of part a in Figure 13. The restricted access of a tool to hold and remove it makes the corresponding disassembly operation very difficult or impossible to execute. Such a constraint is used during graph of assembly states expansion to eliminate those state transitions that imply unfeasible operations with respect to accessibility. The notion of accessibility is implemented using models and con- cepts whose preliminary description can be found in Sere, Laperrire, and MascleJ 8 Search for Optimal Solutions In spite of considering all the above constraints, the graph of assembly states usually contains more than one feasible solution. To make a choice, one must then reason on pertinent criteria to determine the relative goodness of the feasible alternatives. Up to now, four such criteria have been used in the GAPP. They are: 1. Reorientations 2. Parallelism 3. Stability 4. Clustering Note that stability appears at two levels: as a con- straint to eliminate unstable states during graph expansion, and as a criterion to evaluate the relative stability of those states that have successfully passed the stability constraint test (using the stability sub- graph described earlier). ltiiiiiiiii iiiiiii l - ,.:. . b L% %. % % %.%,%,%.% Figure 12 Graph of Assembly States of Flashlight Considering Both Geometric Interference and Stability Figure 13 Typical Example of Inaccessible Component (in this case, a) in a Geometrically Feasible and Stable Disassembly Operation 289 Journal of Manufacturing Systems Vol. 15/No. 4 1996 By triggering one criterion on and leaving all three others off prior to search graph expansion, one can generate the optimal assembly sequence with respect to this criterion. By further providing relative importance (in terms of a percentage) to each criteri- on, optimal solutions with respect to all four criteria and their relative importance can also be obtained (see the window interface in Figure 18, where each criterions weight is represented as a slider from 0 to 100). Typically, this is useful for comparing different solutions in concurrent engineering. 13 Practical Examples Generation of Repair Disassembly Sequences of an Electrical Switch Some components within a product may be expected to fail during service and be replaced peri- odically. The disassembly sequences allowing access to these components generally do not require total product disassembly. Consider, for example, the insulators of the elec- trical switch in Figure 14, shown along with its graph model in Figure 15. The goal is to partly dis- assemble this product to get to the insulators and replace them. To generate a repair plan, all that is required is the identification of the contact relations of the graph model that should not be broken in the repair disassembly plan. In this particular example, these relations could be: ( central_body, switchcase ) ( terminal_blocks, switch_case ) ( spark_covers, switch_case ) ( sparkcovers, terminal_blocks ) ( actuator, central_body ) These relations are not part of any cutset used in the search process. This ensures that the generated disas- sembly plan will preserve the above relations and avoid total disassembly. A first disassembly sequence generated for this example is presented below: 1. remove (screws)from (switch_case central_body spark covers insulators terminal_blocks actua- tor switch cover) along z+ 2. remove (switchcover) from (switch_case cen- tral_body spark_covers insulators terminal_blocks actuator) along z+ switch_cover screws (4) insulators (3) terminalblocks I actuator spark_covers (3) centralbody switch_case Figure 14 Exploded View of Simplified Electrical Switch Assembly 1 - switch_case 2 - central_body 3 - spark_covers 4 - insulators 5 - terminal blocks 6 - actuator 7 - switch cover 8 - screws- Figure 15 Graph Model of Electrical Switch in Figure 14 3. remove (insulators)from (switch_case cen- tral_body sparkcovers terminal_blocks actua- to O along z+ It has been generated using only the geometric interference constraint turned on. Breadth-first was the chosen search mode. All cost criteria were turned off (sliders to zero). Note that the spark_covers were left in place, as required by the specification of the above relations to be preserved. Another test was performed with the same para- meters, except that the accessibility constraint was 290 Journal qf Manufacturing Systems Vol. 15/No. 4 1996 also turned on. No solution was returned by the GAPP. The reason is that the spark_covers were rec- ognized to interfere with the final removal of the insulators. Because the spark_covers were at the same time specified not to be disassembled in the preserved relation list above, no solution could be found. A more appropriate solution is shown below: 1. remove (screws)from (switch_case central_body spark_covers insulators terminalblocks actua- tor switch_cover) along z+ 2. remove (switch_cover)from (switch_case cen- tral_body spark_covers insulators terminal_blocks actuator) along z+ 3. remove (spark_covers)from (switch_case cen- tral_body insulators terminalblocks actuator) along z+ 4. remove (insulators)from (switch_case cen- tral_body terminal_blocks actuator) along z+ Note that the sparkcovers have been removed to provide better access to the tool before removing the insulators. This new solution required the relation (spark_covers, switch_case) to be removed from the list of relations not to be broken during the expansion process. Depth-first search was used in this case. Another approach where only the part or sub- assembly to be replaced is specified instead of the relations not to be broken is being implemented. Generation of Assembly Sequences that Build Predefined Subassemblies Consider the air cylinder in Figure 16. A first assem- bly sequence generated by the GAPP is shown below: 1. fit (bearing_oring) (bearing) along z- 2. fit (bearing_oring bearing) (body) along z- 3.fit (piston_rod) (bearing_oring bearing body) along z- 4. fit (piston_oring) (piston) along z- 5. fit (piston_oring piston) (bearing_oring bearing body piston_rod) along z- 6. screw (pistonscrew) (bearing_oring bearing body piston_rod piston_oring piston) along z- 7. against (cover_oring cover) along z- 8. reorient (cover_oring cover) 180 degrees 9. against (cover._oring cover) (bearing_oring bearing body piston_rod piston_oring p i s - ton pistonscrew) along z- / beadng_oring bearing body IF piston_ring piston pistonscrew piston oring cover oring cover ,- cover screws (2) Figure 16 Exploded View of Air Cylinder 10. screw (cover_screws) (bearing_oring bearing body piston_rod piston_oring piston piston_screw cover_oring cover) along z- This solution was obtained using clustering as the only criterion turned on. This has led to the genera- tion of an assembly sequence where, as much as pos- sible, consecutive operations are of the same type (as determined by the operation name, such as fit, against, and so on, and neglecting reorientation operations, which are not considered during cluster- ing). However, in trying to do so, it can be seen that this solution does not build one inherent subassem- bly of that product, that is, the piston, piston_rod, piston_oring, piston_screw. Another solution is shown below where the input graph model was that of Figure 17: 1. against (piston) (piston_rod) along z- 2. against (cover_oring body) along z- 291 Journal of Manufacturing Systems Vol. 15/No. 4 1996 3. screw (piston_screw) (piston piston_rod) along z- 4. fit (piston_oring) (piston piston_rod piston_screw) along z- 5. fit (bearing_oring) (bearing) along z- 6. fit (bearing_oring bearing) (cover_oring body) along z- 7. fit (piston piston_rod piston_screw piston_oring) (cover_oring body bearing_oring bearing) along z- 8. against (cover) (cover_oring body bearing_ oring bearing piston piston_rod piston_screw piston_oring) along z- 9. screw (cover_screws) (cover_oring body bear- ing_oring bearing piston piston_rod piston_ screw piston_oring cover) along z- Note that this unconnected graph model encom- passes the inherent subassembly (one component of the graph) along with the subassembly bearing_oring bearing body cover_oring, for demonstration purposes. As a result, the solution returned builds the required subassemblies. On the other hand, assuming that each operation name requires a different tool, then this new solution requires one more tool change than the previous one. Conclusions This paper presented an approach for integrating assembly sequence generation, elimination, and evaluation. Compared to other works reported in the literature, the developed GAPP presents: an efficient method for computing the cutsets, a rather straight- forward method for computing geometric interfer- ence based on freedom matrices, and a new stability model for computing stability constraints, all embedded in a functional computer software that can be easily used to tackle different kinds of assem- bly problems. 2 - bearing 3 - body 4 - piston_ring 5 - piston 6 - piston_screw 7 - piston_oring 8 - cover_oring 9 - cover /r 1 n 10 - cover_screws kS) Figure 17 Unconnected Graph Model of Air Cylinder The product to be assembled is first described in a relational graph model. The data structures underly- ing this model are built from the products B-Rep file resulting from solid modeling. An important piece of information resulting from the B-Rep file analysis is the freedom matrix. The freedom matrix approach is explicit because it directly specifies which assembly directions are available. On the other hand, this approach is limited to assembly directions aligned with the chosen coordinate system. Although the approach works for a vast variety of mechanical products compatible with this limitation, it would be desirable to investigate how the generalization of the model to arbitrary directions could be implemented using the same basic approach. Once the graph model has been generated, Homem De Mello and Sandersons engine is used to find a sequence of mutually exclusive cutsets in the prod- ucts graph model and its subgraphs. From a purely mathematical point of view, the combinatorial com- plexity behind this computation when used with the expansion of graph of assembly states is nontrivial. 1 However, the computation of feasibility constraints, including geometric interference, stability, and acces- Figure 18 Screen Dump of GAPPs Window Interface 292 Journal of Manufacturing Systems Vol. 15/No. 4 1996 sibility, as the search graph is expanded greatly reduces this combinatorial complexity. Experience with the system has shown that search space reduc- tion is not always the same using the same constraint for different products. For example, the electrical switch in Figure 14 is highly geometrically con- strained by nature. Thus the geometric interference constraint leads to the most significant reduction for that product. For the flashlight in Figure 10, it is the stability constraint that leads to the most important reduction in the number of possible solutions. Many standard AI search modes are available for the GAPP: breadth-first, depth-first, best-first, and hill climbing. Hill climbing is not guaranteed to return optimal solutions. However, as this search method picks only the best node at each newly gen- erated level of the search graph and flushes any other node generated so far, it is an appropriate search method for products with larger number of parts. For a product whose graph model consists of n connected parts, this search method returns a good (but not necessarily optimal) solution in only n-1 steps, making the search almost instantaneous. References 1. A. Bourjault, Contribution une approche mthodologique de lassemblage automatisr: llaboration automatique des srquences oprra- toires, Th+se dltat, Universit6 de Besangon, Franche-Comtr, France (1984). 2. T.L. DeFazio and D.E. Whitney, Simplified Generation of All Mechanical Assembly Sequences, 1EEE Transactions on Robotics and Automation (vRA-3, n6, 1987), pp640-658. 3. L.S. Homem de Mello andA.C. Sanderson, A Correct and Complete Algorithm for the Generation of Mechanical Assembly Sequences, IEEE Transactions on Robotics and Automation (v7, n2, 1991 ), pp228-240. 4. M. Shpitalni, G. Elber, and E. Lenz, Automatic Assembly of Three Dimensional Structures via Connectivity Graphs, Annals of C