MODIFIED STANDARD CODES IN ENUMERATION AND AUTOMATIC SKETCHING OF MECHANISMS

Srinath Jonnalagadda

Graduate Research Assistant

Sundar Krishnamurty

Associate Professor

Department of Mechanical Engineering

University of Massachusetts

Amherst, MA 01003

Ph: (413) 545-0297

Fax: (413) 545-1027

Email: skrishna@ecs.umass.edu


AbstractAbstract

This paper presents the application of modified standard codes in the systematic enumeration and graphical display of non-isomorphic mechanisms. A two-stage enumeration procedure is presented that involves the identification and generation of contracted graphs using modified standard codes. In this scheme, unique numbering reflecting the symmetry properties of the higher order links deduced from these contracted graphs is propagated to the second stage in which all the non-isomorphic kinematic chains corresponding to each contracted graph are enumerated. The integration of the resulting numerical code values with a robust automatic sketching algorithm provides the basis for the systematic enumeration and pictorial displays of basic kinematic chains. Illustrative examples from the enumeration of basic kinematic chains with up to 12 bar 3 degree of freedom system are presented, and the results are discussed.

IntroductionIntroduction

Recent interest in the development of an expert-systems approach in mechanisms design [Sridhar Kota et al., 1987; Hoetzel et al., 1987; Wu, 1987] has led to an increased effort towards finding an efficient and reliable method for identification and enumeration of mechanisms. The use of graph theory for identification and enumeration of mechanisms has become popular in the recent past [Crossley, 1965; Woo, 1967; Manolesu, 1977; Mruthyunjaya, 1979; Mruthyunjaya and Raghavan, 1979] mainly due to its adaptability to computer implementation.

A recurring problem in mechanism enumeration is the detection of isomorphic kinematic chains. The standard code theory developed by Shin and Krishnamurty (1994a) has addressed this issue with considerable success. In subsequent works [1993, 1994b], they have established that this method can be applied to identify isomorphism in different classes of kinematic chains including planar and spatial as well as epicyclic gear trains. Salient features of this method include an efficient and robust algorithm for the formulation of a unified procedure to conduct symmetry analysis in kinematic chains and the utilization of symmetry properties in the coding process resulting in a unique well-arranged numbering of links. However, this method does not address isomorphism in contracted graphs nor does it capture the interrelationship between parent contracted graphs and child basic kinematic chains. The recently developed modified standard code approach (Jonnalagadda and Krishnamurty, 1995) established a new coding procedure for contracted graphs and showed that it can be employed to process all classes of kinematic chains.

For mechanism enumeration, Fang and Freudenstein (1988) have suggested a model of a classification scheme in which mechanisms represented at various levels of abstraction share common information. This information can be utilized in enumeration to extract an advantage from the strong relationship that ties basic kinematic chains with chains at higher levels of abstraction (simplified graphs and contracted graphs). On the basis of this principle, we present the implementation of a two stage enumeration procedure using modified standard codes. In this work, modified standard codes are employed to uniquely identify and enumerate non-isomorphic contracted graphs along with their symmetric properties that are then propagated and effectively utilized in the enumeration of all corresponding basic kinematic chains.

A salient feature of this work is the coupling of the enumeration procedure with a robust automatic sketching scheme (Mauskar and Krishnamurty, 1995) to convert corresponding numerical code results into visual displays of contracted graphs and basic kinematic chains without link-crossing or loop-crossing defects.

Mechanism Enumeration using Modified Standard Codes

The modified standard code procedure developed for the identification and canonical numbering of all classes of pin-jointed kinematic chains is a code based method using graph theory. A salient feature of this method is its ability to identify a unique numbering for the higher order links at the contracted graph level. This numbering reflecting the symmetry properties of the higher order links at the contracted graph stage is then propagated to the kinematic chains. Note that the symmetry status of the higher order links for the parent contracted graph does not always guarantee the same symmetry status for all the child kinematic chains. To achieve a consistent numbering, in the subsequent steps, the established numbering of the higher order links from the contracted graph is maintained, and unique codes are obtained for the remaining binary links according to their symmetric properties. However, if the symmetry status of higher order links changes at the basic kinematic chain level, they are rearranged in a manner that reflects their new status.

FIGURE 1. CONTRACTED GRAPH FOR A 10 BAR, 3 DEGREE OF FREEDOM KINEMATIC CHAIN

For example, Figure 1 shows the contracted graph for a 10 bar three degree of freedom system, where all four higher order links (T1 - T4) were found to be symmetric at the contracted graph level. However, a basic kinematic chain corresponding to the present contracted graph (Figure 2) has two links (T1 and T4) which are not symmetric at this level. In such cases, renumbering of the higher order links according to the looped code step (Shin and Krishnamurty, 1992a) becomes necessary. However, it should be noted that such a numbering at basic kinematic chain level does not in any way alter the code value or the symmetric properties of the parent contracted graph. The number of such cases encountered is small and hence, it does not effect the overall efficiency of the enumeration process. For example, the kinematic chain shown in (Figure 2 ) was the only case among the 74, 10 bar three degree of freedom chains enumerated.

FIGURE 2. BKC FOR 10, BAR 1 DOF

Using this approach, a seed table for contracted graphs can be created which can be used to enumerate corresponding kinematic chains. Consequently, enumeration of the basic kinematic chains will be faster because the subsequent operations need to be done on the binary links alone.

Enumeration of Basic Kinematic Chains

The enumeration process for planar kinematic chains can be broadly classified into two steps. In the first step, once the number of links and degrees of freedom are selected for a given problem, the candidate contracted graphs are enumerated. In the second step, the unique numbering of higher order links obtained from the contracted graphs is used to enumerate corresponding basic kinematic chains.

Step 1. Enumeration of parent contracted graphs

In this step, different possible combinations of higher order link connections are determined for each solution obtained from the kinematic link set solution (KLSS). Vertices are permuted to obtain several combinations using the best-only search method (Fang and Freudenstein, 1988). The best-only-search procedure, permutes vertices while choosing a permutation which is best in terms of connection. Here it is worth mentioning that the valid contracted graphs are screened from all the possible graphs using the following set of rules :

a. The contracted graph should have the required number of independent loops as determined by the condition :

1 = (1)

where l is the mobility number ( l = 3 for planar motion and 6 for spatial motion ), n is the number of links and F the number of degrees of freedom.

b. The connections between the higher order links should be such that all the degrees of each higher order link are satisfied. This sets a limit on the number of connections or strings possible between the higher order links.

c. All contracted graphs should be completely connected. This rule ensures the sum of the entries in a row of a matrix would correspond to the degree of the link associated with the row. Figure 3 shows a contracted graph violating this rule.

FIGURE 3. AN INVALID CG OF A 8 BAR 1 DOF SYSTEM WITH 4 TERNARY LINKS (T)
  1. Every link should be connected to a string. This rule checks for any vertices with degree equal to zero (Figure 4).

FIGURE 4. AN INVALID CONTRACTED VIOLATING RULE d

e. Every string should connect two different links. This rule checks for any non-zero diagonal elements ( Figure 5).

FIGURE 5. A CONTRACTED GRAPH VIOLATING RULE e

  1. It should not be possible to cut a contracted graph into two disjoint parts by cutting one link or a string. This rule checks for cut-vertices in a contracted graph that can result in a separable graph (Figure 6). A fused vertex technique (Mruthyunjaya, 1979) has been adapted to check this condition in contracted graphs.

FIGURE 6. CONTRACTED GRAPH FOR A 10 LINK, 1 DEGREE OF FREEDOM CASE VIOLATING RULE f

A major component in the enumeration process is the identification and elimination of isomorphic contracted graphs. This is achieved using modified standard codes (Jonnalagadda and Krishnamurty, 1995).:

FIGURE 7. CONTRACTED GRAPH FOR 8 BAR, 1 DEGREE OF FREEDOM

Formulation of the modified standard code is shown with the aid of the contracted graph shown in Figure 7 :

C = (P, V, E) = (51, 0000, 2112)

Here, P refers to the modified standard code for the non-colored graph, where all connections of degree greater than two are replaced with binary connections. This code is obtained by concatenating the upper diagonal elements of the adjacency matrix and finding the decimal equivalent of the binary string so obtained. Similarly, V represents the standard vertex code and is obtained by concatenating the diagonal terms of the adjacency matrix. E refers to the edge code and is obtained by concatenating the non-zero terms of the upper diagonal matrix.

Step 2. Enumerating the kinematic chains

The objective of this step is to find all the valid graphs which satisfy the degree of freedom equation 3l - 2p = 4 (where l and p are the number of links and joints respectively) and satisfy the kinematic requirement of every partial sub-graph (Woo, 1967). Towards this end, kinematic chains for each contracted graph are enumerated by permuting binaries between strings of higher order links in all possible ways. In order to obtain valid kinematic chains, this distribution of binary links is subject to the following conditions imposed by graph theory. The number of binary links in a string or connection gives the string length (s.l.) of the connection.

1. For any given string, s.l. £ F+1

2. Between any two higher order links, the number of strings with s.l. = 0 should not be greater than one.

3. Between any three higher order links, the number of strings with s.l. = 0 should not be greater than two.

4. There should not be any F=0 sub chains in the kinematic chain.

Rule 1 places a restriction on the number of links that can be contained in a string between the higher order links. This will ensure that there is no sub chain in the mechanism that violates the degree of freedom of the mechanism. Part (i) of Figure 8 shows a valid distribution of binary links on the strings of a contracted graph and the associated kinematic chain. Part (ii) of Figure 8 shows an invalid distribution of 3 binary links on a string producing a sub chain with 2 degrees of freedom.

FIGURE 8. BASIC KINEMATIC CHAIN FOR A 8 BAR, 1 DOF SYSTEM VIOLATING RULE 1

Rules 2 and 3 stipulate the number of higher order links that can be connected together directly. Rule 2 maintains that between two higher order links, there cannot be more than one string with a string length of zero. If this is violated, the two links would act like a single link. In Part (ii) of Figure 9, the two strings between the ternary and the quaternary link have no binary links between them. Hence they fuse to act like a single link. Rule 3 requires that between three higher order links, there should not be more than two strings with string length zero. Violation of this rule will result in a F = 0 sub chain. Figure 10 portrays this rule. Part (i) shows a correct distribution of binary links between three ternary links. Part(ii) of Figure 10 shows a F = 0 sub chain formed between 3 ternary links. The fourth rule also attempts to prevent a F = 0 sub chain between combinations of higher order links and binary links. As the number of links increase, the implementation of this rule changes. Figure 10 shows the simplest occurrence where the rule is violated. In Part (ii) of Figure 11, two ternary links combine with a binary link to form an F = 0 sub chain. Figure 12 shows an invalid 10 link, 1 degree of freedom system in which the links 2, 7, 8, 9 and 10 form an F = 0 sub chain.

FIGURE 9. BASIC KINEMATIC CHAINS FOR A 8 BAR, 1 DOF SYSTEM VIOLATING RULE 2

FIGURE 10. BASIC KINEMATIC CHAINS FOR A 8 BAR, 1 DOF SYSTEM VIOLATING RULE 3

Figure 13 shows an F = 0 sub chain in a 12 link, 1 degree of freedom system. The sub chain is comprised of 7 links and 9 joints forming 3 loops. Once again as in contracted graph step modified standard codes are used for identifying isomorphic kinematic chains.

FIGURE 11. BASIC KINEMATIC CHAINS FOR A 8 BAR, 1 DOF SYSTEM VIOLATING RULE 4


FIGURE 12. F=0 SUB CHAIN IN 10 LINK, 1 DOF SYSTEM

FIGURE 13. F=0 SUB CHAIN IN 12 LINK, 1DOF SYSTEM

Automatic Sketching

The successful utilization of any enumeration process in type synthesis is highly contingent upon its integration with a automatic sketching process that can facilitate visual display and selection of appropriate mechanism types. Towards this end, we present an integrated enumeration and automatic sketching process using our modified standard code technique. Here, the scope of the automatic sketching routine (Mauskar and Krishnamurty, 1995) that was developed for basic kinematic chains alone has been expanded to include all classes of kinematic chains. Modified standard codes through their unique numbering for higher order links offer a common representation scheme for all classes of kinematic chains. The new sketching routine utilizes modified standard codes to effectively display the different classes of kinematic chains with no link-crossing or loop-crossing defects.

Results and Discussion

Table 1 shows the results of enumeration for contracted graphs up to 12 bar 1 degree of freedom system. Table 2 shows the results of the enumeration of the corresponding basic kinematic chains. The enumeration results of the 8 bar, 1 degree of freedom system and 10 bar, 1 degree of freedom were found to be consistent with the results published by Crossley (1965) and Woo (1967) respectively. However, our result of 1964 chains for 12 bar, 1 degree of freedom system differs from the result (1962 chains) published by Tuttle (1989a). The results show the utility of the standard code technique in the enumeration and automatic sketching of mechanisms. The intrinsic decodable property of these codes can be used to get information about contracted graphs given kinematic chains, and vice-versa. This facilitates the creation of a seed table for contracted graphs that can then be used as a starting point for subsequent enumeration of kinematic chains and mechanisms. Consequently, a manageable tradeoff between computational efficiency required for generating all the candidate mechanisms on-line and storage of all the possible cases can be achieved. Thus, this approach forms the basis for a systematic automated type synthesis procedure as shown in Figure14. Shown here is an interfaced automatic sketching routine which serves the dual purpose of displaying the results of enumeration as well as facilitating the selection of suitable chains from the displayed results. Figures 15 and 16 show the pictorial representations of basic kinematic chains up to the 12 bar 3 degree of freedom system, drawn using such an automatic sketching routine.

Conclusion

This paper presents the integration of enumeration and automatic sketching of mechanisms using a robust and efficient algorithm (modified standard code) for identification of non-isomorphic mechanisms. This algorithm establishes a unique and consistent numbering for higher order links which facilitates the creation of a seed table for contracted graphs. This table can be used for enumerating the basic kinematic chains and subsequent mechanisms. Using this method, unique codes for contracted graphs and kinematic chains up to the 12 bar 3 degree of freedom system are enumerated. Visual representations of these kinematic chains without loop-crossing or link-crossing defects are displayed using a robust automatic sketching routine.

Acknowledgement

The authors gratefully acknowledge the support of the National Science Foundation under Grant No. CMS-9402608.
Number of Contracted Graphs
No. of Links
DOF = 1
6
1
7
N/A
8
2
9
N/A
10
17
11
N/A
12
118

N/A - Not applicable

TABLE 1

Number of Basic Kinematic Chains
Degrees of Freedom
No.of Links
1
2
3
4
5
6
2
N/A
1
N/A
N/A
7
N/A
3
N/A
1
N/A
8
16
N/A
5
N/A
1
9
N/A
35
N/A
6
N/A
10
230
N/A
74
N/A
8
11
N/A
753
N/A
126
N/A
12
6856
N/A
1964
N/A
N/A

N/A - Not applicable

TABLE 2

FIGURE 14. SCHEMATIC OF TYPE SYNTHESIS USING ENUMERATION AND SKETCHING ROUTINES
FIGURE 15. SKETCHES OF BKC FOR 8 BAR, 1DOF SYSTEM FIGURE 16. SKETCHES OF 9, 10, 11 AND 12 BAR 1 DOF SYSTEMS

References

Crossley, F. R. E., 1965, "The permutations of Kinematic Chains of Eight Members or Less from Graph Theoretic Viewpoint," Developments in Theoretical and Applied Mechanics, Vol. 2, pp. 467-487

Davies, T.H. and Crossley, F. R. E., 1966, "Structural Analysis of Plane Linkages," Journal of Mechanisms, Vol. 1., pp. 171-183

Fang, W. E., and Freudenstein, F., 1988, "The Stratified representation of Mechanisms," Trends and Developments in Mechanisms, Machines and Robotics- 1988, 1988 ASME Design Technology Conference, Kissimmee, FL, DE, Vol. 15-1, pp. 115-123.

Freudenstein, F., and Maki, E. R., 1983, "Development of an Optimum Variable-Stroke Internal Combustion Engine Mechanism from the Viewpoint of Kinematic Structure," ASME Journal of Mechanisms, Transmissions, and Automation in Design, Vol. 105, pp. 259-266

Hoetzel, D. A., Chieng, W. H., and Zissimides, J., "Knowledge Representation and Planning Control in an Expert System for the Creative Design of Mechanisms," AI EDAM, Vol. 1, No. 2, 1987, pp. 119-137

Jonnalagadda, S., and Krishnamurty, S., 1995, "A Unified Coding Scheme for Efficient Mechanism Enumeration," 4th National Applied Mechanisms and Robotics Conference, Vol. 2, pp. 95-066-01-04

Kota, S. and Erdman A. G. and Riley, D. R., "An Expert System for Initial Selection of Dwell Linkages," ASME Design Technology Conference, Boston, pp. 399-407, Sept. 27-30, 1987

Manolescu, N. I., 1977, "A Method based on Baranov Trusses and Using Graph Theory to find the Set of Plane Jointed Kinematic Chains and Mechanisms," Mechanisms and Machine Theory, Vol. B, pp. 3-22

Mauskar, S., and Krishnamurty, S., 1995, "A loop configuration approach to automatic sketching of mechanisms," In Press.

Mruthyunjaya, T. S., 1979, "Structural Synthesis by Transformation of Binary Chains," Mechanisms and Machine Theory, Vol. 14, pp. 221-231

Mruthyunjaya, T. S. and Raghavan, M. R., 1979, "Structural Analysis of Kinematic Chains and Mechanisms based on Matrix Representation,' Journal of Mechanical Design, Vol. 101, pp. 484-494

Mruthyunjaya, T. S., and Balasubramanian, H. R., 1987, " In quest of a reliable and Efficient Computational Test for detection of Isomorphism in Kinematic Chains," Mechanism and Machine Theory, Vol. 22, No. 2, pp. 131-139.

Shin, J. K., and Krishnamurty, S., 1994, " On identification and Canonical Numbering of Pin-Jointed Kinematic Chains," ASME Journal of Mechanical Design, Vol. 116, pp. 182-188.

Shin, J. K., and Krishnamurty, S., 1994, " Development of a Standard code for Colored Graphs and its Application to Kinematic Chains," ASME Journal of Mechanical Design, Vol. 116, pp. 189-196.

Shin, J. K., and Krishnamurty, S., 1993, "Application of standard codes to the enumeration of epicyclic gear trains," Mechanism and Machine theory, Vol. 28, No. 3, pp. 347-355.

Tuttle. E. R., Peterson, S. W., and Titus, J. E., 1989a, "Enumeration of Basic Kinematic Chains Using the Theory of Finite Groups," ASME Journal of Mechanisms, Transmissions, and Automation in Design, Vol. 111, pp. 498-503.

Woo, L. S., "Type Synthesis of Plane Linkages," ASME Journal of Engineering for Industry, Feb. 1967, pp. 159-172

Wu, Y. M., "Automated Design and Sketching of Mechanisms Based on Specified Design Requirements by Employing Expert System Methodologies," Ph.D. Thesis, Department of Mechanical Engineering and Applied Mechanics, University of Rhode Island, 1987