Simplification and Abstraction of Kinematic Behaviors

1 Introduction

Recent methods for the analysis of mechanical devices derive descriptions of a mechanism's kinematic behavior from the shape and the initial position of its parts [Falt­ ings, 87a; 87b), [Nielsen, 88a; 88b), [Joskowicz, 87, 88; 89a). Although qualitative, these descriptions provide a single level of abstraction which is often too detailed and complex to be of practical use in automated design. The complexity of the behavioral descriptions arises from two factors: (1) from the (local) kinematic pair descriptions, as a result of the objects' shape complexity, and (2) from the overall (global) mechanism descriptions, as a result of the combinatorial complexity of possible object posi­ tions.

Local descriptions are derived from two-dimensional configuration spaces 1 defined by the objects' degrees of freedom. The configuration space of a pair of objects is computed by analyzing all pairwise contacts between object features (the vertices and edges of the objects'

1 The configuration space of a mechanism defines the set of free placements (position and orientations) of objects so that no two objects overlap [Lozano-Perez, 83].

contours). Each pairwise contact defines a half-space bounded by a one-dimensional curve (called a configu­ ration space boundary or CS-boundary for short) that separates free and forbidden placements. The intersec­ tion of these half spaces defines the components of the configuration space, which are then partitioned into re­ gions. The regions, defined by monotone CS-boundary segments, reflect the qualitatively different behaviors of the pair. There can be as many regions as there are possible contacts; as a result, behavioral description are frequently too detailed.

Consider the half-gear pair in Fig. 1, consisting of a 20-teeth gear and a 9-teeth half gear of equal diameter pinned at their centers to a fixed frame. Their configura­ tion space is shown in Fig. 2(a): dark areas correspond to forbidden object positions; solid lines correspond to CS-boundaries. Fig. 2(b) shows a detailed view of the CS-boundaries and the partition into regions 2 .

Region R0 corresponds to positions in which the two gears are disengaged, and thus their rotations are in­ dependent; regions r; correspond to positions in which the two gears are meshed. Each r; region is delimited by two CS-boundaries, corresponding to the upper and lower contact between two teeth. When a contact occurs, the rotating one gear causes the rotation of the other in the opposite direction; the ratio between both rotations is given by the function defining the CS-boundary. The fragmented nature of the CS-boundary reflects the teeth contact changes, and indicates slight variations in the motion transmission ratio. The small intervals between CS-boundaries in each region corresponds to gear inter­ play (backlash), Since there are two regions for each pair­ wise tooth contact, there are 20 x 9 x 2 = 360 r; regions; the regions are qualitatively different due to angular off­ set and interval differences. This kinematic description is clearly too detailed for a CAD system designing a gear­ box with many gear pairs.

2 Both figures adapted from [Faltings, 87a]; for clarity, only half of the "strips" are shown in (a).

Global behaviors are obtained by composing all local descriptions. In general, composing local descriptions requires algebraic techniques. However, for fixed axes mechanisms, in which objects can only move along axes that are fixed in space, the composition requires a small set of symbolic rules [Joskowicz, 87]. In the worst case, the composition results in the cross-product of all local regions for every pair, producing an overall mechanism description with exponentially many regions.

Consider the cylinder lock in Fig. 3, consisting of a cylinder C rotationally mounted on a fixed frame F. Five pairs of pins of different lengths, (P;, Q;), are mounted inside five aligned cylindrical holes in the cylinder and the frame. The pins are kept in contact by springs and can only translate along the axes of the holes; their role is to prevent the rotation of the cylinder. When the right key is inserted, the pins are raised so that the top of the lower pins and the bottom of the upper pins coincide exactly with the outer surface of the cylinder (Fig. 3(b )). When the pins are aligned, the cylinder rotates together with the key, as there are no obstacles to prevent this rotation. The cylinder then pushes a tumbler (not shown in the figure) that locks the door by preventing it from rotating around its axis.

The analysis identifies three qualitatively different po­ sitions of the pins: (1) the upper and lower pins are in contact with the cylinder, preventing it from rotating; (2) the upper and lower pins are in contact with the fixed frame, also preventing the cylinder from rotating; (3) the top of the lower pin, the bottom of the upper pin, and the top of the cylinder are aligned; the cylin­ der is then free to rotate, in which case the pins cannot translate. The key/ cylinder pair has two characteristic positions: (1) the key and the cylinder are not in con­ tact; the rotation of the cylinder is independent from the rotation and/or translation of the key; (2) the key is inside the cylinder; the key is free to translate inside the cylinder, but the rotations of the key and cylinder are dependent. The global description contains many unreachable regions and irrelevant detail. For example, 3 5 = 243 regions correspond to all the possible com­ binations of pin positions when the key is outside the cylinder . But these positions can only be reached when the pins are directly pushed from the outside! Assuming that input motions are only applied to the key, all t hese regions are unreachable. Another source of detail comes from the regions created by the pin positions as the key is inserted: the pins follow the upper contour of the key, thereby changing characteristic positions . All these dis­ tinctions are irrelevant if we are only interested in the behaviors of the key and the cylinder.

Two ideas play a key role in coping with the complex­ ity and focus of behavioral descriptions: simplification and abstraction. Simplification incorporates additional information in the form of assumptions and constraints. Abstraction ignores irrelevant detail by defining different levels of resolution. This paper defines a set of simplifi­ cation and abstraction operators for kinematic descrip­ tions.

2 Describing Kinematic Behavior

This section presents the symbolic language used to de­ scribe kinematic behaviors. Objects in a fixed axes mechanism can only rotate or translate (or both) along axes that are fixed in space. We can thus classify all their possible motions along a fixed axis into five cat­ egori~s: no motion, rotation, translation, independent rotat10n and translation, and coordinated rotation and translation. To each category, we associate a predicate indicati~g the type of motion and the axis along which the mot10n takes place. To describe the extent of the motion, we associate motion parameters bound by inter­ vals defining the motion's range. The type of motion together with the motion parameters and their interval~ form a possible motion label which completely describes an object's kinematic behavior. The five possible mo­ tion lab.els for object A along axis 0 are: fixed(A, O,p), p_rot~twn(A , 0, B), p..;translation(A, 0, X), p_cylmder(A, 0, X, B), and p_h.elical(A, 0, X, B).

~elationships between object motions, indicating how obJects constrain each other's motion through contact are specified by motion parameter relations. Mechanis~ behaviors are described by a set of possible motion labels (one for each object) and the dependencies between their motion parameters. Such a description is called a possi­ ble motions region of a mechanism's behavior 3 . A region diagram describes all the possible kinematic behaviors of a mechanism and the transitions between them. The region diagram is an undirected graph whose nodes rep­ resent possible motion regions and whose edges represent possible transitions between regions ."

To distinguish between qualitatively different behav­ i~rs, all regions in the diagram must be qualitatively dtffe~en~. Two ?ossible. motions regions, Ri and R;, are quahtattvely dtfferent tff at least one of the following holds: (1) the motion type of at least one object is dif­ ferent in ~ and R;; (2) the motion parameter intervals defining ~ and R; cannot be merged into continuous intervals formin~ a n~w region Rk = ~ U R;; (3) motion par~meter relattons m f!i a~d R; are not identical; ( 4) mot10n parameter relat10ns m ~ and R; are identical but ~t le~t one of. these relations is monotonically in­ creasmg m one reg10n and monotonically decreasing in the. other. ~g.ion diagrams constitute a symbolic, quali­ tative descnpt10n of all the possible kinematic behaviors of a mechanism.

3 Simplification and Abstraction Operators

We define simplifications and abstractions as operations on .kinematic descriptions and their underlying configu­ rati~n spaces. To be meaningful, these operations should no~ mtroduce spurious behaviors or alter the original re­ latiOns between behaviors; in other words they should be sound and complete. Soundness guarantees that no new behaviors are introduced, whereas completeness guar­ antees that no possible behaviors were lost. A third prop~rty, compositionality, guarantees that the simpli­ ficatt?n( abstraction can be applied to the local pairwise descnp~10ns b~fore comi;>osing them. The following two subsect10n~ bnefi~ descnb~ the operators to simplify and abstract km~mattc behavtors . For detailed algorithms and complextty analyses, see [Joskowicz, 89b].

3 These de.scriptions are called regions because they corre­ spond to regaons of the mechanism's configuration space.

3.1 Local Operators

Local operators simplify and abstract kinematic pair de­ scriptions; they are applied to their two-dimensional con­ figuration spaces defined by n monotone CS-boundary segments. Local operators are applied immediately after the configuration space is computed. There are ten local operators, all sound and complete:

Kinematic Constraints Simplifications: specify the object that causes the motion, the type of motion, and the extent of the motion (Input-Part, Input-Type, and Input-Range, respectively). These additional con­ straints, derived from the context in which the pair is operating, rule out possible behaviors that become un­ r~achable as a consequence of this constraining informa­ tion. Input-Part transforms every region R into a new set of regions, ri . In the new regions, the motion pa­ rameter of the passive object changes only when the ac­ tive object's motion parameter changes; there is one ri for every region adjacent to R. Input-Type reduces the number of pairwise configuration spaces to be analyzed (one f?r every pair of fixed axes) . Input-Range rules out behav10rs that are outside the specified motion range by deleti?g regions outside the range, and restricting those who he on the boundary. All three simplifications can be implemented in O(n).

Dynamic Constraints Simplifications: account for the ?-ction of gravity, springs, and friction, thereby restrict­ mg the possible motions of objects. Three kinematic constraints are used to model these dynamic constraints: (1) a constant contact relation between two objects; (2) a preferred (or default) position of an object when it is ~ot subject to ot~er cont~ct constraints, and; (3) condi­ t~ons on the. ~otton relatton parameters restricting mo­ tion transmtsston. The first two constraints model the effects of springs and gravity. A force applied to an ob­ jec~ cau~es it to. re~ain in contact with its neighboring ?bJec~s m the duect10n of the force. Thus, all positions m whtch the two objects are not in contact can be ruled out. When no contact occurs, the object will move in t~e direction of the force until it reaches a stable posi­ tion. To avoid introducing time information we assume that motions due to forces are infinitely faster than in­ put ~~tions. !he third constraint models friction by restnctmg mot10n transmission through contacts whose CS-boundary tangent at the point of contact is smaller than a predefined coefficient J.l, regardless of the force's magnitude and objects' masses. These constraints rule out possible transitions between regions and reduces re­ gion intervals. All three simplifications can be imple­ mented in O(n).

Linearization Abstraction: approximates the exact motion parameter relations with piecewise linear rela­ tions. Every CS-boundary is divided into monotonically c.ontinuous seg~ents, which are then replaced by a set of hnes. The new lmear CS-boundary might intersect other ~S-boundaries, thereby producing a topologically incon­ ~tstent abstraction. This is avoided by further subdivid­ mg the CS-boundary into smaller segments. Assuming that each segment is broken only a constant number of t~mes, . lin~arizatio? can be implemented using an effi­ ctent hne mtersectton algorithm in O(nlogn).

Qualitative Abstraction: groups contiguous behav­ iors with similar monotone motion parameter relations into one behavior. This abstraction hides the con­ tact details that produce fragmented behavioral descrip­ tions. The operator merges contiguous monotone CS­ boundaries and creates qualitative CS-boundaries. These boundaries indicate the qualitative motion parameter re­ lation (monotonically increasing or decreasing) in the new regions. Merging CS-boundaries also requires test­ ing for intersections, and thus can be implemented in O(n log n). Linearization and Qualitative abstraction have been used for the design of new object shapes in kinematic pairs [Joskowicz and Addanki, 88].

Gap-Closing Abstraction: transforms behaviors with small backlash into behaviors without backlash, where object motions are tightly coupled. This operator merges CS-boundaries defining narrow "channels" of free place­ ments reflecting backlash and tolerancing errors (Fig. 2(b )). The small positional variations inside the chan­ nels reflect negligible variations that can usually be ig­ nored. The operator examines every region for a possible boundary merge, and can be implemented in O(n).

Behavior Parametrizations: these operators are not simplification or abstraction operators per se: they are designed to compare two kinematic behaviors and find a common description by parameterizing their possible motion labels. This operation is useful for detecting be­ havioral similarities and periodicity. Possible motions labels have three potential candidates for parameteri­ zation: region intervals, axes of motions, and motion parameter relations. Two regions can be parameterized in their intervals when: (1) their motion type is iden­ tical, and is defined along the same axis; (2) the rela­ tions between their motion parameters are identical, and (3) their interval regions are different but proportionally scaled. Similarly, two regions can be parameterized in their axes when the axes of motion are not required to be identical. Finally, two regions can be parameterized in their motion relations when these relations are lin­ early similar (y ~ f(x) and y ~ f(x) +c), scalarly sim­ ilar (y ~ f(x) andy~ c.f(x)), have a phase difference (y ~ f(x) and y ~ f(x +c)), or any combination of them. This operation takes constant time when applied after Linearization.

Periodicity Abstraction: detects patterns of repeti­ tive behavior to create a common behavioral descrip­ tion. This description is produced by identifying para­ metrically isomorphic subgraphs in the region diagram. Two subgraphs are parametrically isomorphic iff they are topologically equivalent and there is a one-to-one parametr~c matching between regions. Although graph 1somorph1sm can be tested efficiently - region diagrams are graphs with a planar embedding - subgraph isomor­ phism, even for planar graphs, is in NP-Complete, and 1s thus computationally expensive.

The order in which the operators are applied obeys two motivations: (1) discard as soon as possible the be­ haviors that, due to constraints, are unreachable, and (2) reduce the number ofregions in the diagram as quickly as possible. Therefore, simplification operators are applied first, because they incorporate additional constraints.

Then, abstraction operators are applied in increasing or­ der of coarseness: first Linearization, then Qualitative abstraction. Gap-Closing depends on the results of the previous two abstractions and is applied repeatedly un­ til no further change occurs. Periodicity abstraction is applied at the very end, when the local region diagram is smallest.

As an example, consider the effects of local operators on the half-gear pair's configuration space of Fig. 2. We assume that input motions are only applied to gear B and that the initial placement is ()A = ()B = 0. First, Input-Part simplification reduces Ro to a set of disjoint two-dimensional strips bounded by the linear relations ()A ~ Ot and ()A ~ Ot +fin the interval ()B E (1r,2·n-]. Only two strips, Ot = 0 and 1r, are reachable from the initial placement. As a consequence, only the regions connected to these two strips are reachable in the inter­ val ()B E (0, 1r]; all other regions are unreachable and are thus discarded. Linearization and Qualitative abstrac­ tion merge the remaining CS-boundaries in the interval ()B E (0, 1r] into two regions, each defined by two parallel lines. Gap-Closing merges the parallel lines in these re­ gions as well as the two strips in the interval() B E ( 1r, 21r]. The .successive effects of these operators on the config­ uration space are shown in Fig. 4. Periodicity abstrac­ tion identifies two parametrically isomorphic subgraphs, (ro, r.) and (r2, r3), commonly described with a param­ eter i, where i = 0 describes (r0 , r.) and i = 1 describes (r2, r3) :

MESH: p_rotation(A, OA, OA), p_rotation(B, OB, ()B) ()BE (0, 7r]mod2.-, ()A E (i .7r, (i + 1).7r]mod2.- (JA = -OB

FREE: fixed( A, OA, OA), p_rotation(B, OB, OB) ()BE (1r, 27r]mod2.-, ()A= i .1rmod2.-

Transition(MESH,FREE): ()B = 11j ()A= (i + 1).7r

3.2 Global Operators

Global operators simplify and abstract behavioral de­ scriptions of complete mechanisms; they are applied to the global region diagram, after the local operators. There are six global operators, most of them generaliza­ tions of local operators; their complexity is proportional to the number of regions in the global diagram. Only the first one is compositional.

Kinematic Constraints Simplification: specify which objects can receive input motions, the types of these mo­ tions, and their extent (Input-Parts, Input-Types, and Input-Ranges, respectively). Like local kinematic con­ straints, they are derived from the context in which the mechanism operates. These operators further discard unreachable regions and restrict possible motions in the remaining regions. They can be applied while compos­ ing local region diagrams, thereby ruling out potential regions without computing them.

Relevance-Set Simplification: filters out behavioral distinctions created by uninteresting objects that intro­ duce too much detail. The user indicates the set of rel­ evant objects whose behaviors s/he is interested in; the most common relevance set is the input/output parts set. This operator projects each region into a new re­ gion from which the possible motion labels and relations of uninteresting objects are removed. As a consequence, contiguous regions whose difference lay solely in the be­ havior of uninteresting objects become qualitatively sim­ ilar and can thus be merged. This operator is both sound and complete, but not compositional.

Region-Difference Abstraction: defines how qualitative behavioral distinctions are made. By relaxing the crite­ ria that establish the difference between two kinematic behaviors, coarser behavioral descriptions are obtained. We consider two relaxations of the qualitative region dif­ ference criteria (section 2): (1) motion parameter rela­ tions can be monotonically identical, instead of identical. Two relations are monotonically identical iff they both specify the same relation (~, =, or ~) and their func­ tions are both simultaneously increasing or decreasing in the given interval, and (2) Motion predicates need not be all identical. For example, to distinguish between ob­ jects that move and objects that don't regardless of their motion type, we define two categories: "no-motion", con­ sisting of the motion type fixed, and "motion", consist­ ing of all the other motion types.

Behavior Parametrization and Periodicity Abstrac­ tion: These two operators are direct extensions of the local diagram operators. Regions are parameterized by taking into account all motion labels, motion parame­ ter relations, and intervals. Periodicity abstraction finds isomorphisms between subgraphs by using the extended definition of region similarity.

The order in which the global operators are applied follows the same rationale of local operators: the global kinematic constraints simplifications are applied first during the computation of the global region diagram be­ cause they discard potential regions without computing them explicitly; Then, Relevance-Set is applied to fo­ cus on the behaviors of relevant objects. Next, Region­ Difference is applied to create a coarser behavioral description; if the number of regions does not decrease, these abstractions are unnecessary. Periodicity abstrac­ tion is applied at the end.

As an example, consider the effects of global operators on the description the cylinder lock of Fig. 3. We assume that the key can only receive input motions along axis 0, and that the only behaviors of interest are those of the key and the cylinder. Applying the kinematic con­ straints simplifications to the local descriptions of the pairs key flower pins, ( K, P;), discards all the regions in which K and P; are not in contact, except for the re­ gion containing the initial placement. This eliminates the 3 5 - 1 potential global regions resulting from the pin position combinations when the key is outside the cylin­ der . This operator also eliminates all the regions where pins not in contact with the key are in different positions as the key is inserted; there are 3 x (3 4 +3 3 +3 2 +3 1 ) = 360 such potential global regions. The Relevance-Set simpli­ fication merges all the regions specifying different pin positions but no difference in the angular position of the cylinder or the key. The resulting projected region dia­ gram consists of three regions:

OUT The key and the cylinder are not in contact. The key can both rotate and translate along 0, and the cylinder cannot rotate.

IN The key is inside the cylinder. The key translate along 0, but cannot rotate. The cylinder cannot rotate either.

UNLOCK The key is at the end of the cylinder. The key can rotate together with the cylinder, but it cannot translate.

No further application of Region-Difference or Periodic­ ity abstraction is necessary.

4 Comparing Two Mechanisms

Mechanism comparison is an example of a task that can­ not be automated without simplifications and abstrac­ tions. It consists of determining when two mechanisms can be considered kinematically equivalent. The ability to compare two mechanisms is essential for evaluating design solutions and choosing existing mechanisms for redesign.

To compare two mechanisms, we compare their behav­ iors, rather than their structure. For example, the two crank mechanisms in Fig. 5 are structurally very differ­ ent; however, they both transform a continuous rotation into a reciprocating translation. But many of the details of this transformation are different: the number of parts, the motion ratios, etc. Thus, a direct comparison of the mechanisms' region diagrams will also indicate that they are different.

The comparison algorithm uses the simplification and abstraction operators to match the descriptions. First, the region diagrams of both mechanisms are computed, incorporating the kinematic and dynamic constraints. Then, the Relevance-Set operator is applied to discard unnecessary behavioral information. The other opera­ tors are then applied in the order indicated in sections 3 and 4. After each application, the region diagrams are compared, and a parameterized match between their regions is attempted. Whe~ the two diagrams ~a~ch the algorithm stops, producmg a common descnpt10n for both region diagrams, and the list of operators neces­ sary to achieve the equivalence. This list, establishes the smallest set of conditions necessary to determine when two mechanisms are equivalent (see [Joskowicz, 89b]).

The two crank mechanisms in Fig. 5 can be considered equivalent when: (1) input motions are only applied t_o the driving wheel; due to friction, the second assembly IS not reversible, i.e., the translation of the slider will not cause the rotation of the wheel (kinematic and dynamic constraints) (2) the only behaviors of interest are those of the slider and the driving wheel (Relevance-Set); (3) the motion relations between the driving wheel and the slider are qualitatively similar (Qualitative Abstraction) ( 4) the gears backlash are negli~ible (�ap-Closin~ ~b­ straction) and (5) both sliders' displacements a~e 1~s1de the desired operating range (Interval Parametenzatlon).

5 Conclusion

Future Intelligent CAD systems must be able to problem-solve using qualitative descriptions at different levels of resolution. This paper presented a set of op­ erators to simplify and abstract kinematic descriptions derived from configuration spaces. To illustrate their use, we showed how mechanism comparison can be done with these operators.

The need for abstracting kinematic descriptions de­ rived from configuration spaces was recognized indepen­ dently by Nielsen (1988b) 4 . He developed and implemented a number of local abstractions very similar to the ones presented in this paper: Linearization, Qualita­ tive and Gap-closing abstraction. His treatment of force and,motion is similar to our concept of input motion. No global abstractions are proposed.

4 1 am grateful to the anonymous reviewers for bringing this work to my attention.

Producing qualitative descriptions at multiple levels of resolution is an important problem. Recently, [Falken­ hainer and Forbus, 88] described a scheme to build large-scale qualitative models; [Murthy, 88] proposed a scheme for dynamically adjusting the level of resolu­ tion in which a device is analyzed. Our research shares many of their goals; however, their techniques are inad­ equate for kinematic behaviors _because their qualita_tive states are defined as n-dimens10nal rectangular regwns of quantity spaces. This distinction is too crude to_ ac­ count for CS-boundaries that partition the space mto non-rectangular regions. Moreover, their characteriza­ tion does not account for different approximations to the exact CS-boundaries.

Possible extensions and future work include: (1) im­ plementing the operators; (2) applying the opera~ors to domains were the problem can be formulated w1th pa­ rameter spaces, e.g., dynamics; (3) expl<?ring the ro~e of the operators in design, and; ( 4) class1fymg mechamsms for redesign.