Representations of Assembly Sequences

1. Introduction

Choosing the representation of assembly sequences is an impor­ tant decision both in creating an assembly sequence planner and in designing an intelligent control for the assembly process.

Several methodologies for representing assembly sequences have been utilized. These include representations based on directed graphs, on AND/OR graphs, on establishment conditions, and on precedence relationships. Those based on directed graphs and on AND/OR graphs are explicit representations since there is a mapping from the assembly tasks into the elements of the represen­ tations. Those based on establishment conditions and on precedence relationships are implicit representations because they consist of conditions that must be satisfied by the assembly se­ quences. Despite the diversity of representations, there is a lack of understanding of how each representation maps into the others and of how one representation can be derived from the others. Further­ more, the correctness and completeness of the implicit represen­ tations have not received adequate attention. By correctness of the representation we mean that only feasible sequences satisfy the conditions. By completeness we mean that all the feasible se­ quences satisfy the conditions. A prerequisite for a proof of correctness and completeness of algorithms that generate assembly sequences [Bourjault 84, De Fazio and Whitney 87, Homem de Mello and Sanderson 89] is a proof that the representation of assembly sequences used is correct and complete.

This paper analyses these four representations and shows how they are interrelated. The correctness and completeness of these representations are also addressed.

2. Background

A mechanical· assembly is a composition of parts interconnected forming a stable unit. Each part is a solid object. Parts are interconnected whenever they have one or more surfaces in con- A. C. Sanderson Electrical, Computer, and Systems Engineering Department Rensselaer Polytechnic Institute Troy, New Yolk 12180-3590

tact. Surface contacts between parts reduce the degrees of freedom for relative motion. A cylindrical contact, for example, prevents any relative motion that is not a translation along the axis or a rotation around the axis. Attachments may act on surface contacts and eliminate all degrees of freedom for relative motion. For example, if a cylindrical contact has a pressure-fit attachment, then no relative motion between the parts is possible.

A subassembly is a nonempty subset of parts that either has only one element or is such that every part has at least one surface contact with another part in the subset. Although there are cases in which it is possible to join the same pair of parts in more than one way, a unique assembly geometry will be assumed for each pair of parts. This geometry corresponds to their relative location in the whole assembly. A subassembly is said to be stable if its parts maintain their relative position and do not break contact spon­ taneously. All one-part subassemblies are stable.

The assembly process consists of a succession of tasks, each of which consists of joining subassemblies to form a larger sub­ assembly. The process starts with all parts separated and ends with all parts properly joined to form the whole assembly. For the current analysis, it is assumed that exactly two subassemblies are joined at each assembly task, and that after parts have been put together, they remain together.

It is also assumed that whenever two parts are joined all con­ tacts between them are established. Due to this assumption, an assembly can be represented by a simple undirected graph ( P , C) in which P= { p 1 ,p 2 , · · · ,pN} is the set of nodes, and C= { c 1 , c2 , · · · , c L } is the set of edges. Each node in P corresponds to a part in the assembly, and there is one edge in C connecting every pair of nodes whose corresponding parts have at least one surface contact. The elements of C are referred to as connections, and the graph ( P, C) is referred to as graph of connections. Figure 1 shows an assembly in exploded view, and figure 2 shows its corresponding graph of connections. The state of the assembly process can be characterized by the connections that have already been established, and it can be represented by an L-dimensional binary vector:!= [x 1 ,x 2 , · · · ,xL] in which the ;th component xi is Tor F respectively if the ith connection is established in that state or not.

Furthermore, it is assumed that whenever a subassembly is formed all connections between its parts are established. There­ fore, any subassembly can be characterized by its set of parts, and any state of the assembly process can be characterized by a par­ tition of the set of parts of the whole assembly. For example, the initial state of the assembly process of the assembly shown in figure 1 is characterized by { {CAP}. { RECEPTACLE}. {STICK}, {HANDLE} } whereas the final state is characterized by { {CAP, RECEPTACLE, STICK, HANDLE} }. In the rest of this paper, references to subsets of parts should be understood as references to the subassemblies made up of those parts. It will always be clear from context what the whole assembly is.

There are partitions of the set of parts of the whole assembly that cannot characterize a state of the assembly process. For example, the partition { {CAP, HANDLE}. {RECEPTACLE}, {HANDLE} } cannot characterize a state of the assembly process for the assembly shown in figure 1 because the subset {CAP, HANDLE} does not characterize a subassembly. Partitions that characterize a state of the assembly process will be referred to as state partitions, and partitions that don't characterize a state will be referred to as nonstate partitions.

Similarly, not all £-dimensional binary vectors can characterize a state. For example, for the product shown in figure 1, the 5-dimensional binary vector [T, T, F, F, F] does not correspond to a state because if connections c 1 and c 2 are established then connec­ tion c 3 should also be established. £-dimensional binary vectors that characterize a state will be referred to as state vectors whereas £-dimensional binary vectors that don't characterize a state will be referred to as nonstate vectors.

We will use the subassembly predicate sa to determine whether a subset of parts makes up a subassembly. The argument to this predicate is a subset of parts, and its value is either T or F depend­ ing on whether that subset of parts corresponds to a subassembly. For example, for the assembly shown in figure 1, sa( {RECEPTACLE, HANDLE} )=T, whereas sa( {CAP, HANDLE})= F. From the assembly's graph of connections it is straight forward to compute sa for any given subset of parts. Similarly, we will use the subassembly-stability predicate .st to determine whether a sub­ assembly described by its set of parts is stable. The computation of .st has been addressed elsewhere [Blum et al. 70, Boneschanscher et al. 88).

Given two subassemblies characterized by their sets of parts 9; and ej. we say that joining 9; and ej is an assembly task if the set 9k=9.u9 . characterizes a subassembly. For example, for the assembly Jshown in figure 1, if 9;= { RECEPTACLE} and 9j= { HANDLE } then joining 9; and 9 ·is an assembly task, whereas if 9. = { CAP } and 9 . = { HANDLE } fuen joining 9 . and 9 . is not an I _) I J assembly task. The subassemblies 9; and ej are the input subassemblies of the assembly task, and 9k is the output subassembly of the assembly task. Due to the assumption of unique geometry, an assembly task can be characterized by its input subassemblies only.

An assembly task is said to be geometrically feasible if there is a collision-free path to bring the two subassemblies into contact from a situation in which they are far apart. And an assembly task is said to be mechanically feasible if it is feasible to establish the attachments that act on the contacts between the two sub­ assemblies. We will use the geometric-feasibility predicate gf and the mechanical-feasibility predicate mf to determine whether two subsets of parts characterize, respectively, a geometrically feasible and a mechanically feasible assembly task. These predicates take as argument a set of two subassemblies, each characterized by its set of parts. The computation of these predicates is discussed elsewhere [Homem de Mello and Sanderson 89).

Given an assembly that has N parts, an ordered set of N -1 assembly tasks is an assembly sequence if there are. no two tasks that have a common input subassembly, the output subassembly of the last task is the whole assembly, and the input subassemblies to any task T; is either a one-part subassembly or the output sub­ assembly of a task that precedes T;. To any assembly sequence T 1 , T 2 , · · · , T N-l there corresponds an ordered sequence .s 1 , s 2 , · · · ,sN of states of the assembly process. The state s 1 is the state in which all parts are separated. The state .sN is the state in which all parts are joined forming the whole assembly. And any two consecutive states s i and s i+ 1 are such that only the two input subassemblies of task T; are in .s i and not in .s i+ 1 , and only the output subassembly of task T; is'in si+l and not ins;. Therefore, an assembly sequence can also be characterized by an ordered se­ quence of states.

An assembly sequence is said to be feasible if all its assembly tasks are geometrically and mechanically feasible, and the input subassemblies of all tasks are stable.

Since one assembly sequence can be represented by an ordered list of tasks, it is possible to represent the set of all assembly sequences by a set of lists, each corresponding to a different assembly sequence. Since many assembly sequences share com­ mon subsequences, attempts have been made to create more com­ pact representations that can encompass all assembly sequences. The next sections discuss different approaches towards represent­ ing all assembly sequences of a mechanical assembly.

3. Directed Graph Representation of Assembly Sequences

Given an assembly whose graph of connections is (P ,C), a directed graph can be used to represent the set of all assembly sequences. The nodes in this directed graph correspond to stable state partitions of the set p. These are the partitions e of p such that if e e e then e is a stable subassembly of p . The edges in this directed graph are ordered pairs of nodes. For any edge, there are only two subsets 9; and e. in the state partition corresponding to the first node that are not dt the state partition corresponding to the second node. Also, there is only one subset 9k in the state partition corresponding to the second node that is not in the state partition corresponding to the first node, and 9k=9;u9/ Further­ more, the assembly task that joins e j and e. is feasible. Therefore, each edge corresponds to an assembly tasl!. This graph is referred to as directed graph of feasible assembly sequences, and it can be formally defmed as follows:

Definition 1: The directed graph of feasible assembly sequences of an assembly whose set of parts is P is the directed graph (Xp.Tp) in which Xp = {81 [E> e A.(P)] A [V'9(9 e E>) ::::> sa(9) A st(9)]}

is the assembly's set of stable states, and

is the assembly's set of feasible state tiansitions.

The notation A ( P ) has been used to represent the set of all partitions of P, and U( {A ,B, · · · ,Z}) =AvBv · · · vz. As an example, figure 3 shows the directed graph of feasible assembly sequences for the product shown in figure 1.

A path in the directed graph of feasible assembly sequences (X p , T p) whose initial node is 8 1 = { { p 1 } , { Pz } , · · · , { PN } } and whose terminal node is 8 F = { { p 1 , Pz, · · · , PN } } cor­ responds to a feasible assembly sequence for the assembly P, and conversely. In such a path, the ordered sequence of edges cor­ responds to the ordered sequence of tasks, while the ordered se­ quence of nodes corresponds to the ordered sequence of states of the assembly process.

4. AND/OR Graph Representation of Assembly Sequences

In our previous worlc [Homem de Mello and Sanderson 86], we introduced art AND/OR graph representation of assembly sequences. The nodes in this AND/OR graph are the subsets of P that charac­ terize stable subassemblies. The hyperarcs correspond to the geometrically and mechanically feasible assembly tasks. Each hyperarc is an ordered pair in which the first element is a node that corresponds to a stable subassembly 9k' the second element is a set of two nodes { 9; ,9j} such that 9;v 9j=9k' and the assembly task characterized by 9; and 9j is feasible. This AND/OR graph can be formally defined as follows:

Def'mition 2: The AND/OR graph of feasible assembly sequences of an assembly whose set of parts is P = {PI, Pz, · · · , PN } , is the AND/OR graph ( S p, D p) in which

is the set of stable subassemblies, and

is the set of feasible assembly tasks.

The notation n ( p ) has been used to represent the set of all subsets of P. As an example, figure 4 shows part of the AND!OR graph for the assembly shown in figure 1. Each node in that graph is associated with a subset of parts that corresponds to a sub­ assembly. There are only two stable subassemblies of the product shown in figure 1 whose corresponding nodes were not included in figure 4; they are the subassembly made up of the cap, the recep­ tacle, and the handle, and the subassembly made up of the cap, the stick, and the handle. They were not included to avoid cluttering the figure.

From the AND!OR graph of feasible assembly sequences one can defme feasible assembly trees as follows:

Def'mition 3: Given the AND!OR graph of feasible assembly sequences of an assembly whose set of parts is P = { pI , Pz , · · · , PN } , any AND/OR path havi!lg {pI , Pz, · .. , PN } as its initial node, and having {PI } , { p 2 }, · · · , { PN} as its terminal nodes is a feasible assembly tree of that assembly.

Figure 4: AND!OR graph of feasible assembly sequences for the assembly shown in figure 1.

An assembly tree induces a partial order among its hyperarcs: hyperarc h; is said to precede hyperarc hj if there is a node nk in the assembly tree such that h; is incident from nk and hj is incident to nk' At least one sequence of the hyperarcs of an assembly tree is consistent with this partial order. Furthermore, every sequence of the hypearcs that is consistent with the partial order corresponds to a feasible assembly sequence.

· The Correspondence between the Directed Graph and the AND/OR Graph

Every feasible assembly sequence in the directed graph of feasible assembly sequences corresponds to a feasible assembly tree in the AND/OR graph of feasible assembly sequences. And every feasible assembly tree in the AND/OR graph of feasible as­ sembly sequences corresponds to one or more feasible assembly sequences in the directed graph of feasible assembly sequences. The two theorems below establish the correspondence between assembly trees and assembly sequences. Proofs of these theorems are presented elsewhere [Homem de Mello 89].

Theorem 4: Given an assembly tree of an assembly, if h 1 .~. · · · ,h;=(0;,8;). · · · ,hN-I is a sequence of all the hyperarcs of that assembly tree that is consistent with the partial order in­ duced by the tree, then the sequence 0 1 , n 2 , · · · , ON, in which 01 ={{pi },{pz}, · · · , {pN}}, and Oi+l =(0;-8;) u { 0;} is a feasible assembly sequence of the assembly.

Theorem 5: If 0 1 , 0 2 , · · · , ON is an assembly sequence of

then (s;, H;) is an assembly tree of that assembly.

The useful feature of the AND/OR graph representation for as­ sembly sequences is that for assemblies of more than 5 parts it encompasses all possible assembly sequences with a reduced num­ ber of nodes than the directed graph of assembly states [Homem de Mello and Sanderson 88]. Furthermore, it explicitly shows the possibility of simultaneous execution of assembly tasks.

5. Establishment Condition Representation of Assembly Sequences

If we represent the states of the assembly process by L-dimensional binary vectors, then a set of logical expressions can be used to encode the directed graph of feasible assembly se­ quences. Let E;= { ~ 1 .~ 2 , · · · ·~K.} be the set of states from I

which the ith connection can be established without precluding the completion of the assembly. The establishment condition for the i th connection is the logical function

where the sum and the product are the logical operations OR and AND respectively, and 'Ykl is either the symbol x 1 if the zth component of ~kisT, or the symbol Xr if the zth component of ~k is F. Clearly, every element ~k of E; is such that F;(~k) =T. It is often possible to simplify the expression ofF; using the rules of boolean algebra.

The establishment conditions can be obtained from the directed graph of feasible assembly sequences by systematically looking at the edges leaving each of the nodes that correspond to states from which the assembly can be completed. The establishment con­ ditions can also be Obtained from the AND/OR graph of feasible assembly sequences by systematically looking at the hyperarcs of each assembly tree.

As an example, the establishment conditions for the assembly shown in figure 1 are:

The first establishment condition (F 1 (x 1 ·Xz ,x 3 ,x 4 ,x 5 )) cor­ responds to the fact that the only states in which connection c 1 (i.e. the connection between the cap and the stick) can be established without precluding the completion of the assembly are either the state in which no connection has been established (node 1 in figure 3), or the state in which only connection c 2 is established (node 2), or the state in which only connection c 3 is established. (node 4 ), or the state in which only connection c 5 is established (node 5), or the state in which only connections c 2 and c 4 are established (node 9), or the state in which only connection c 1 and c 2 are not established (node 12). It should be noticed that there is no term corresponding to the state in which only connection c 4 is established (node 6); although it is feasible to establish connection c 1 , the resulting state (node 10) is a dead-end from which the assembly cannot be com­ pleted. Using the rules of boolean algebra the first establishment condition can be rewritten as

Although further simplification is still possible, in this paper it is assumed that a boolean function even when simplified is a sum of products. Depending on the application it may be useful to drop this restriction and to further simplify the boolean functions.

Any assembly sequence (~ 1 .~ 2 , · ·· .~)that is feasible is such that if the ith connection is established in task Tk then F;(~k)=T. And any assembly sequence is feasible if for any of all its tasks Tk are such that if the i th connection is established in T k then F;(~k)=T. Therefore, the set of establishment conditions is a correct and complete representation of assembly sequences.

The establishment conditions as defined in this paper can only discriminate between feasible and nonfeasible assembly sequences. There are sequences of states that "satisfy" the establishment con­ ditions but are not assembly sequences and therefore cannot be feasible assembly sequences.

Knowing F I , F 2 , · · · , F L' and the assembly's graph of connec­ tions, it is straight forward to construct the assembly's directed graph of assembly states.

6. Precedence Relationship Representation of Assembly Sequences

Two types of precedence relationships can be used to represent assembly sequences: precedence relationships between the es­ tablishment of one connection and the establishment of another connection, and precedence relationships between the establish­ ment of one connection and states of the assembly process.

· Precedence relationships between the establishment of one connection and the establishment of another connection

We will use the notation C· < C · to indicate the fact that the establishment of connection c i 1 mu~ precede the establishment of connection cj' And we will use the notation ci S cj to indicate the fact that the establishment of connection ci must precede or be simultaneous with the establishment of connection c ·· Further­ more, we will use a compact notation for logical combinations of precedence relationships; for example, we will write ci < cr ck when we mean (ci < cj)A(ci < ck), and we will write ci+cj < ck when we mean ( ci < ck) v ( cj < ck).

Each feasible assembly sequence of a given assembly can be uniquely characterized by a logical expression consisting of the conjunction of precedence relationships between the establishment of one connection and the establishment of another connection. For example, for the assembly shown in figure 1, the assembly sequence ~I= [ F, F, F, F, F ], ~ 2 = [ T, F, F, F, F ], ~ 3 = [ T, T, T, F, F ], and ~ 4 = [ T, T, T, T, T] can be uniquely characterized by the following conjunction of precedence relationships

The set of all M feasible assembly sequences can be uniquely characterized by a disjunction of M conjunctions of precedence relationships in which each conjunction characterizes one as­ sembly sequence. Clearly, this logical combination of precedence relationships constitutes a correct and complete representation for the set of all assembly sequences.

h is often possible to simplify this logical combination of precedence relationships using the rules of boolean algebra. Fur­ ther simplification is possible if one notices that there are logical combinations · of precedence relationships that cannot be satisfied by any assembly sequence. For the assembly shown in figure 1, for example, the combination ( ci < c 2 ) A ( c 2 < c 3 ) A ( c 3 < c 4 ) A ( c 4 < c 5 ) cannot be satisfied by any assembly sequence. These combinations can be set as don't care conditions in the simplifica­ tion process.

For the assembly shown in figure 1, the precedence relationship

is sufficient to discriminate the feasible assembly sequences from the unfeasible assembly sequences.

Unlike the logical combination of precedence relationship ob­ tained directly from the feasible assembly sequences, this logical combination of precedence relationships is satisfied by some se­ quences that are not assembly sequences. h can only discriminate the feasible assembly sequences from the unfeasible assembly se­ quences. This is due to the introduction of don't care conditions.

· Precedence relationships between the establishment of one connection and states of the assembly process

We will use the notation ci ~ Sk(~) to indicate that the es­ tablishment of the jth connection must precede any state of the assembly process for which the value of the logical function S k ( ~) is T. The argument of Sk(~) is an L-dimensional binary vector. We will also use a compact notation for logical combinations of precedence relationships. For example, we will write ci+cj ~ Sk(~) when we mean [ci ~ Sk(~)] v [cj ~ Sk(~) ].

Let 'I' = { ~ I , ~ 2 , · · · , ~~ } be a set that includes all unstable assembly states plus the stable states from which the final state cannot be reache-d plus the states that cannot be reached from the initial state. Every element x . of 'I' is such that the value of the logical function G ( ~ j ) is T, ;&ere .

The sum and the product in equation 1 are the logical operations OR and AND respectively, and 'Yjr is either the symbol x 1 if the [th component of ~ . is T, or the symbol Xi if the l th component of ~ j is F. In many cas~s the expression of G ( ~) can be simplified usmg the rules of boolean algebra. Allowing for simplifications, but maintaining the assumption that a boolean function is a sum of products, equation 1 can be rewritten as

where 8/~) is the product of a subset of {xi ·Xz, · · · ,XL ,xi ,Xz, · · · , XL } that does not include both xi and xi for any i. Each term 8/~) can be rewritten grouping all the nonnegated variables frrst and all the negated variables last, i.e., 8/ ~) =

Any assembly sequence that includes a state ~ i for which G ( ~ i ) = T (i.e. ~ i E 'I' ) is not a feasible sequence. Therefore, a necessary condition for an assembly sequence (~ 1 .~ 2 · · · · ·~N) tobefeasibleisthat�(~I)=�(~ 2 )= ··· =�(~N)=F. This condition is equivalent to 8. ( ~ i) = F for i = 1 , 2 , · · · , N and for j = 1 , 2 , · · · ,J'. For a spelial class of assemblies, this necessary condition is also sufficient. This class is composed of the as­ semblies that satisfy the following condition:

• If it is feasible to establish the i th connection from a state in which the set of all connections that are established is r. then it is also feasible to establish the jth connection from any state in which the set of all connections that are established is a subset of r.

If C={ci,c 2 ,··· ,cL} is the assembly's set of connections between parts and(~ I .~ 2 , · · · · ~N) is an assembly sequence, the condition 8·(x I)= 8 ·(x 2 ) = · · · = 8 ·(xN) = F corresponds to }- }- }- a precedence relationship. The following theorem establishes the correspondence. A proof of this theorem is presented elsewhere [Homem de Mello 89].

Theorem 6· Ifg(x) = x ·x · · · · ·xh · x ·x · · · · ·x {a b · - ab pq z· ·· · · · , h } r1 { p, q, · · · , z } = 0, { a, b, · · · , h } u { p, q, · · · , z } !:: { 1 , 2 , · · · , L } , and the sequence of L-dimensional binary vectors (~ 1 .;! 2 · · · · ·:!N) is such that :!I =[F,F, ···,F), :!N= [T, T, · · · , T], and xil=T :::;. xj 1 =T for all j > i, then the con­ dition g(~ 1 ) = g(;! 2 ) = · · · = g(:!N) = F is equivalent to the condition

with the product being the logical operation AND.

Each of the J' terms on the right side of equation 2 leads to one precedence relationship between the establishment of one connec­ tion and states of the assembly p~ss. As a consequence of theorem 6, for assemblies that satisfy the condition stated above, if an assembly sequence is such that all J' precedence relationships are satisfied, then that sequence is feasible, and conversely. There­ fore, the set of J' precedence relationships is a correct and com­ plete representation of the set of all feasible assembly sequences.

For the assembly shown in figure 1, which satisfies the con­ dition stated above, and whose directed graph of assembly states is shown in figure 3, 'I' includes :!s = [ F, T, F, F, T] and :! lO = [ T , F , F , T , F ). Therefore,

In this case the expression of G (:!) cannot be further simplified; the precedence relationships are:

A simpler set of precedence relationships can be obtained if in the simplification of G(x) we set the nonstate vectors as don't care conditions. For the-assembly shown in figure 1, the set of precedence relationships

was obtained in the same fashion as Set 1, except for setting the nonstate vectors as don't care conditions. Set 2 is simpler and yet equivalent to Set 1.

Both set 1 and set 2 of precedence relationships can only dis­ criminate feasible from non-feasible assembly sequences.

7. Conclusion

Four types of representations for assembly sequences were reviewed: the directed graph of feasible assembly sequences, the ANDIOA graph of feasible assembly sequences, the set of establish­ ment conditions, and the set of precedence relationships. The mappings of one representation into the others have been es­ tablished. The correctness and completeness of these represen­ tations have also been established. To the author's knowledge no previous precedence relationship representation of assembly se­ quences has been shown to be correct and complete.

In previous worlc [Homem de Mello and Sanderson 89], we have presented an algorithm for the generation of the ANDIOR graph of feasible assembly sequences and a proof of its correctness and completeness. Depending on the application, other represen­ tations of assembly sequences might be preferred. The results presented in this paper allows us to construct the other three types of representation and to guarantee their correctness and complete­ ness.

Furthermore, there has been other worlc on the generation of assembly sequences [Bourjault 84, De Fazio and Whitney 87]. To the author's knowledge the correctness and completeness of these other algorithms have not been established. The results presented in this paper allow the proof of the correctness and completeness of algorithms for the generation of assembly sequences that yield precedence relationships or establishment conditions.

Acknowledgements

We thank Thomas L. De Fazio and Daniel E. Whitney for helpful discussions, and James Daniell for making the software for simplification of boolean functions available to us.· The respon­ sibility for the paper, of course, remains with the authors.

This research was supported by the Conselho Nacional de Desenvolvimento Cientffico e Tecnol6gico (Brazil), the Jet Propul­ sion Laboratory of the California Institute of Technology, and The Robotics Institute of Carnegie Mellon University.