**Abstract**Abstract

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.

**Introduction**Introduction

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.

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.

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.

- Every link should be connected to a string. This rule checks for any vertices with degree equal to zero (Figure 4).

*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
*

- 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.

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).:

*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.

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 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.

**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.

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.

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.

N/A - Not applicable

**
**TABLE 1

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," *4 ^{th}
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