Mechanism *type synthesis *refers to the determination of
structural properties such as degrees of freedom, the number and
type of links, the number and type of joints, the number of loops,
the nature of motion (planar and spatial), and the interconnections
between links and joints. While some of these properties can be
readily obtained from basic mechanism equations, there exists
no mathematical model that can be used to determine completely
the interconnections of links and joints, or to find suitable
mechanism types uniquely. The number of possible mechanisms for
a given problem increases rapidly as the number of links increases,
and they become more drastic if different types of joints are
included. As a result, the main tasks associated with *type
synthesis *are (1) enumeration of candidate mechanisms and
(2) identification of non-isomorphic mechanisms.

Recent interest in the development of an expert-systems approach in mechanism design [Kota et al., 1987; Hoeltzel 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; Manolescu, 1977; Mruthyunjaya, 1979; Mruthyunjaya and Raghavan, 1979] mainly due to its adaptability to computer implementation.

Of these two, the process of identifying non-isomorphic mechanisms constitutes the most difficult step. This is due to the fact that the enumeration process will always result in many duplicate mechanisms. These duplicates or isomorphic mechanisms arise due to different numbering for the different links and due to symmetry in the system. Many traditional methods either fail to either identify isomorphism always, or lack in their applicability to different types of mechanisms. The Standard Code theory (SC) 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.

The second major task in *type synthesis *deals with the
enumeration of non-isomorphic mechanisms. The enumeration process
can be achieved either by storing various kinds of numerous kinematic
chains and mechanisms in the memory, or by completely generating
them for each given problem. However, the most efficient strategy
will be one that best compromises between memory and computing
time, by storing certain classification of mechanisms and using
them to generate all possible mechanisms.

Fang and Freudenstein (1988) have shown that structural abstraction based on contracted graphs can be a viable and robust technique in mechanism design process. The objective of this research is to develop and implement a classification scheme based on the contracted graphs towards automating the mechanism enumeration and sketching process. A major task of this project is to develop a unique representation scheme for contracted graphs that can then be used in all subsequent stages of enumeration. Unique decodable codes for contracted graphs are developed using the SC method. Such a classification scheme and the use of the resulting classification codes as seed table provides an efficient and compact method for enumerating kinematic chains and its off-springs with relative ease. In such a scenario it is enough to store tables of contracted graphs, and using this, candidate kinematic chains and mechanisms can be enumerated for individual problems.

For this purpose, modified standard codes are developed to identify non-isomorphic contracted graphs as well as a unique numbering for the higher order links in them. In this coding scheme, the numbering of higher order links corresponding to a parent contracted graph is propagated to all its child basic kinematic chains and mechanisms. In addition to providing a consistent coding scheme for all classes of mechanisms, the utilization of this scheme in mechanism enumeration will have the added benefit of improving the overall efficiency. Furthermore, using this approach, only a relatively small database of codes corresponding to contracted graphs needs to be stored, which can then serve as the starting point for enumerating subsequent basic kinematic chains and mechanisms. This approach can be expected to offer the best compromise between memory and computational time as it will eliminate the need for storing complete mechanism information in a large database, or, generating all candidate mechanisms from basic link and degree of freedom information alone for every problem.

This will provide a basis for the development of an enumeration and automatic sketching technique applicable to all classes of mechanisms (from contracted graphs to mechanisms). 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.

Finally, the results of the two problems namely: the design of
the dwell mechanism for punching operation and the design of a
variable stroke engine are investigated to study the effectiveness
of the scheme.

**2.1 Introduction**

This chapter deals with the development of a coding scheme for representing kinematic chains at all levels of abstraction, from contracted graphs to mechanisms. The usefulness of using standard codes for uniquely identifying mechanisms, and its subsequent advantage in mechanism type synthesis has been previously established (Shin and Krishnamurty, 1994). However, application of the method in mechanism enumeration process for a given problem will require either a large database for storing all the mechanisms, or a computationally intensive enumeration process for generating on-line. This necessitates a quicker and more robust technique that enhances the computational efficiency of the enumeration process by storing certain classes of mechanism types and using them to generate candidate mechanisms.

Towards this end, a modified standard code procedure is presented.
This chapter presents a combinatorial approach that is based on
standard code method for identifying mechanism uniqueness, and
utilizes the concept of contracted graph abstraction for computationally
efficient mechanism enumeration. The result is an efficient strategy
that provides the best compromise between memory and computing
time. This is achieved by storing certain classification of mechanisms,
namely, contracted graphs, and using them to generate all possible
mechanisms. In this approach, unique decodable codes for contracted
graphs are developed using the standard code method. This information
serves as the seed table, and its utilization in subsequent steps
will lead to an efficient and compact method for enumerating kinematic
chains and its off-spring with relative ease. The following sections
detail the salient features of the new scheme of coding, and its
application in automated mechanism synthesis.

**2.2 Standard Code**

The standard code developed for the identification and canonical numbering of pin-jointed kinematic chains is a computerized code based method using graph theory representation (Shin and Krishnamurty, 1994). In subsequent papers, its successful application to different types of mechanisms including planar and gear trains have been demonstrated (Shin and Krishnamurty, 1993 and 1994). However, in its present form, the standard code procedure does not offer a consistent numbering of higher order links at the contracted graph and basic kinematic chain (BKC) levels. As such, this failure to facilitate the inclusion of parent contracted graph information in the codes for the basic kinematic chains makes the approach computationally ill-suited in mechanism enumeration. A preferred method is one that reflects the parent-child relationship of the contracted graph and kinematic chains, and then uses that information effectively to make the enumeration process computationally efficient.

To achieve this, we present a modified standard code approach that yields unique numbering for higher order links in the contracted graph, a numbering system that will then be propagated to all the kinematic chains in the subsequent stages of enumeration. In addition to providing consistent numbering it is expected that the modified method will also reduce the number of operations involved in the mechanism enumeration and the code generation process. The salient features of the method for finding unique higher order link numbering of the parent contracted graphs and its utilization in generating the code for the child kinematic chains are described below.

**2.3 Modified Standard Code**

The underlying principle that there cannot exist similar codes between two basic kinematic chains corresponding to two different contracted graphs plays a pivotal role in the proposed modified standard code method. On the basis of this principle, we first develop a unique code for representing the contracted graph utilizing only the higher order links. Here, we represent contracted graphs as colored graphs and adopt the colored code system to include representation of vertex and edge properties (Shin and Krishnamurty, 1994). In subsequent steps, the established numbering of the higher order links from the contracted graph phase is maintained, and unique codes are obtained by the remaining binary links according to their symmetric properties.

A salient feature of this modified standard code algorithm lies
in its rearrangement of the vertices (links) in the decreasing
order of their *N *th power. Here, *N* refers to either
the number of links or the number of links minus one, depending
on whether the number is odd or even. This process automatically
rearranges the links according to the degree of vertex and connectivity
properties. As a result, the first two steps of the original standard
code algorithm become redundant. The various steps for generating
the modified standard code are illustrated with a 10 bar single
degree-of-freedom kinematic chain and its contracted graph shown
in Figure 2.1.

*Contracted Graph phase:*

Figure 2 shows the contracted graph for the kinematic chain shown in Figure 2.1. Contracted graphs are given codes according to rules for a colored graph. Colored graphs to represent kinematic chains are generated by coloring either the vertices or the edges. An example of this representation is shown in Figure 2.2. The colored code for this particular example corresponding to the link-link interconnections and the number of connections between links is:

C = (26279, 111111111)

Figure 2.3 shows the results at the end of the looped code stage.
It is apparent that all the links are symmetric and no rearranging
of links is necessary. The details of these steps can be found
in Shin and Krishnamurty (1994). The numbering for the six higher
order links corresponds to the link-link interrelationship at
the contracted graph level. It does not, however, reflect the
connectivity status of the higher order links with respect to
binary links. To achieve a consistent numbering of the higher
order links as well as to reflect the contracted graph information
in all subsequent corresponding kinematic chains, this procedure
forces this set of higher order link numbering to remain the same
throughout the enumeration process. Accordingly, the higher order
link numbering obtained at the contracted graph level is propagated
to the child kinematic chains.

*Kinematic Chain Phase:*

In this phase the operations are done towards identifying a unique numbering for the binary links of the kinematic chain. Figure 2.1 shows a 10 bar 1 degree of freedom mechanism with arbitrary numbering. Since the higher order links are found to be symmetric at the contracted graph level, the six ternaries are given arbitrary numbering from 1 to 6. No further operation is done on these six links during the basic kinematic chain code generation step, thus preserving the parent information. Figure 2.4 shows the final graph at the end of looped code stage. It can be seen that this final numbering of the higher order links is consistent with the final numbering of the contracted graph (Fig 2.3). This kinematic chain has two symmetry sets [(7 8)(9 10)] and the final code for this chain is found to be (19207552, 114736).

**2.4 Results **

The modified standard code algorithm was tested on several cases to study the effect of preserving the order of the higher order links, on codes for the kinematic chains. These included contracted graphs with all symmetric higher order links at the contracted graph level, Figure 2.2, as well as contracted graphs with non-symmetric higher order links as in Figure 2.5.

In all the cases the algorithm never failed to give unique codes to all the kinematic chains belonging to a given contracted graph. For example, the contracted graph shown in Figure 2.5a has an order [1 3 4 5 2] at the contracted graph level, with the links 4 and 5 found to be truly symmetric. Figures 2.6a-c show illustrations of three of the 43 kinematic chains of the parent contracted graph in Figure 2.5a drawn using the Automatic Sketching program (Mauskar and Krishnamurty, 1995). Similarly, unique codes were obtained for the 42 kinematic chains of the contracted graph in Figure 2.5b, and sketches of three such cases are shown in Figures 2.6d-f.

Thus, the modified standard codes for the kinematic chains provide
unique numbering system by preserving the order obtained at the
contracted graph level. Since the codes have the intrinsic property
of being decodable, the codes for the kinematic chains can be
used to get information about their parent contracted graphs and
vice-versa. Furthermore, this process requires only 3 to 5 operations,
each involving the calculation of the *N*th power, corresponding
to the symmetric property of the 4 binary links. In contrast,
solving the problem with the standard code algorithm requires
7 or more operations as it needs to consider all the 10 links
in the system. This reduction in the number of computations will
result in a faster and more efficient mechanism enumeration algorithm.

**2.5 Unified Coding Scheme Used In Automated Mechanism Synthesis**

Traditionally information about the topological constraints has been obtained by using a set of rules to find the number and type of links, joints and degrees of freedom. This information is used to search for the best solution to the problem. This design search space for a problem is a function of the number of links and degrees of freedom, and as such, increases combinatorially with the number of links and degrees of freedom. For example, an 8 bar 1 degree of freedom has 4 contracted graphs and 16 basic kinematic chains resulting in 128 mechanisms. However, an 12 bar 1 degree of freedom has 118 contracted graphs and 6856 kinematic chains and a large number of mechanisms. Thus any design tool using standard codes for the kinematic chains will have to have either a huge database to store all the information, or this information needs to be generated on-line at considerable computational burden.

Instead, a manageable trade-off between database storage (memory) and computational efficiency is a preferred characteristic in an automated mechanism design tool. Structural abstraction based on contracted graphs suggests that storing a small and manageable seed table of modified standard codes for the contracted graphs can be expected to be an ideal setup. This seed table can then be used to enumerate the kinematic chains for a given contracted graph, thus achieving the desired trade-off between memory and efficiency. This forms the basis for the use of modified standard code enumeration process in automated mechanism synthesis process.

In this framework, once the number of links and degrees of freedom
are selected for a given problem, the candidate contracted graphs
can be chosen for further enumeration by applying appropriate
set of rules. Using a sketching utility such as the automatic
sketcher, the user can generate the proper graphical representations
of the enumerated kinematic chains and mechanisms (Mauskar and
Krishnamurty).

**2.6 Summary**

The chapter presents the development of an efficient, and robust algorithm for identification and unique representation of contracted graphs and basic kinematic chains using modified standard codes. Using this method, unique codes for contracted graphs are first developed, that are then used to generate modified standard codes for the corresponding kinematic chains. A salient feature of this technique is that it results in a consistent numbering system for the higher order links at all stages of mechanism enumeration. This aspect of the modified standard code method makes it uniquely well suited in mechanism enumeration, as it provides the basis for achieving an optimal trade-off between memory, storage, and computational efficiency. As a result, it can be expected to play a significant role in the development of a powerful automated mechanism design procedure. Towards the development of an automated mechanism design procedure, chapter 3 presents the use of modified standard codes for the development of an efficient and reliable tool for enumeration and automatic sketching of all classes of mechanisms.

**3.1 Introduction**

Enumeration consists of identifying the valid non-isomorphic basic kinematic chains. Most of the approaches followed rely on graph theory representation of kinematic chains. These approaches started from the kinematic link set solution, the set of higher order link combinations. The number of kinematic chains to be enumerated increases in an exponential fashion as the number of links increase. This made the identification of valid kinematic chains a computationally tedious and inefficient process.

Another approach has been to enumerate non-isomorphic contracted graphs first and then valid kinematic chains are enumerated next. Since there are far fewer contracted graphs than kinematic chains, it would be faster and more efficient to store contracted graphs and enumerate kinematic chains from the contracted graphs. 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, this chapter presents 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.

**3.2 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 3.1 shows the contracted graph for a 10 bar 3 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 3.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 3.2) was the only case among the 74, 10 bar 3 degree of freedom chains enumerated.

**3.3 Enumeration of Basic Kinematic Chains**

The enumeration process for planar kinematic chains can be broadly classified into two steps. In the first step, the number of links and degrees of freedom are first selected for a given problem, and then 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 that
is best in terms of connection. The work on enumeration of contracted
graphs has been adopted from a masters' project by Ramakrishnanand
Chilukuri, submitted to the department of mechanical engineering
at the University of Massachusetts, Amherst. 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

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

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

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

Formulation of the modified standard code is shown with the aid of the contracted graph shown in Figure 3.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 that
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. The work on enumeration of basic kinematic chains
has been adopted from a masters' project by Thomas Mattapallil,
submitted to the department of mechanical engineering at the University
of Massachusetts, Amherst.

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 3.8 shows a valid distribution of binary links on the strings of a contracted graph and the associated kinematic chain. Part (ii) of Figure 3.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 3.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
3.10 portrays this rule. Part (i) shows a correct distribution
of binary links between three ternary links. Part(ii) of Figure
3.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. The implementation
of this rule changes a**s** the number of links increase. Figure
3.10 shows the simplest occurrence where the rule is violated.

In Part (ii) of Figure 3.11, two ternary links combine with a
binary link to form an F = 0 sub chain. Figure 3.12 shows an invalid
10 link, 1 degree of freedom system in which the links 2, 7, 8,
9 and 10 form a F = 0 sub chain.

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

**3.4 Automatic Sketching**

The successful utilization of any enumeration process in *type
synthesis *is highly contingent upon its integration with an
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.** **

The automatic sketching routine has been used for contracted graphs by inputting the modified standard code for non-colored version of the contracted graph into the program. The non-colored version would have adjacency matrix of only 1 and 0's and thus is a valid basic kinematic chain. The loop sequences for vertices information obtained from the automatic sketching routine for basic kinematic chains are then used as an input to the program for sketching contracted graphs. The sketching routine for contracted graphs also needs the link-link adjacency matrix in addition to the loop sequence information. The program for sketching contracted graphs was written in Borland C++ environment on a Pentium machine running at 133MHz. An example contracted graph sketch produced by the program is shown in Figure 3.14. The inputs for this contracted graph are:

Loop Sequences: 1 4 5 2, 1 3 6 2, 1 4 5 6 2, 1 3 4 5 2 and the link - link adjacency matrix .

**3.5 Results and Discussion**

N/A -- Not applicable

TABLE 3.1

Table 3.1 shows the results of enumeration for contracted graphs up to 12 bar 1 degree of freedom system. Table 3.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. Figures 3.15 and 3.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.

Figure 3.15: Sketches Of Basic Kinematic Chain for 8 bar, 1 Degree
of Freedom system

**3.6 Summary**

This chapter 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 that 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. Chapter 4 illustrates the use of the enumeration and automatic sketching routines through two case studies in mechanism design.

**4.1 Introduction**

The use of the modified standard codes for the development of
an integrated enumeration and automatic sketching scheme for mechanism
synthesis has been discussed in chapter 3. Two problems of kinematic
design of mechanisms that have already been solved by manual techniques
were chosen to test the unified standard code approach. The results
obtained from *type synthesis *conducted using the unified
standard code approach were compared with those obtained using
the conventional technique.

The two probelms are:

*Design of a punching mechanism*[Midha et al., 1984]*Design of an Optimum Variable-Stroke Internal Combustion Engine mechanism*[Freudenstein et al., 1983]

Principal steps in the in the *type synthesis *process are
topological synthesis and topological analysis. Topological synthesis
comprises of enumerating basic kinematic chains that satisfy topological
requirements and enumerating mechanisms derivable from each basic
kinematic chain. The topological properties of the mechanism include
the degrees of freedom, the number of links and their types, the
number of joints and their types, and the inter-connection between
the links and joints. Topological analysis consists of determining
the distinct ways of applying input(s), identifying the possible
outputs(s), and assigning joint types based on the functional
requirements. To a certain extent, topological synthesis and analysis
can be done during the enumeration of mechanisms by applying suitable
rejection criteria to eliminate mechanisms that do not satisfy
the requirements. Consequently the rejection criteria would vary
from extremely simple to complex depending on the application.

The rejection criteria suggested by the authors for these two
unrelated problems have been used to search for suitable mechanisms
using the unified standard code approach. The following section
details the procedure followed for type synthesis of the two problems.

**4.2 Procedure for Type Synthesis**

Type synthesis of the two problems was conducted on the lines of the procedure detailed in Figure 4.1. The tables of results obtained from enumeration of contracted graphs and basic kinematic chains are already available (shown in chapter 3). Using this information database, appropriate contracted graphs and kinematic chains were chosen. Once a basic kinematic chain was chosen, the various links necessary to formulate the mechanism were permuted and the appropriate mechanisms were chosen after applying suitable rejection criteria.

A program was implemented to automate the process of choosing a basic kinematic chain, permuting links and choosing the potentially acceptable mechanisms. The adjacency matrices and symmetry information of the basic kinematic chains were used as inputs. This program was written in Visual C++ environment for a Pentium machine running at 133MHz. The program also interfaces with the modified standard code routine which checks for isomorphism in the selected mechanisms. Here it should be noted that the program utilizes the symmetry properties of links while permuting all possible links. This makes the program more efficient and avoids unnecessary calls to the modified standard code routine. The automatic sketching routine was used to view the various basic kinematic chains obtained from the search.

**4.3 Problem 1 -- Design of a Punching Mechanism**

**4.3a Design Specifications **

1. The punching mechanism requires 40 to 60 % dwell for every cycle of crank rotation.

2. An indexing mechanism to position the work piece under the punch once per cycle.

- Minimum relative slider displacement of 1.5 in. between the dwell and rise period
- Linkage contained 4 6 1.25 in. volume (excluding the crank, punch, and the indexing device)
- Mechanism speed of 2000 rpm
- Maximum punch force of 250 lb. occurring approximately at the bottom dead center.

The design specifications 1 and 2 determine the nature of motion
and can be used for type synthesis of the mechanism. The specifications
from 3 to 6 determine the mechanism dimensions and thus should
be used for dimensional synthesis. Since the mechanism requires
dwell, the problem can be reformulated as the design of a dwell
mechanism and the indexing linkage (a dyad) can be added to the
dwell mechanism obtained from the search. The search is limited
to six-link mechanisms with seven joints, all joints being turning
pairs (R) or straight-line sliding pairs (P) and all mechanisms
obey the general degree of freedom equation. The reason for this
being that only six or higher even number of links (8, 10, etc.)
can be used to give dwell in a single degree of freedom mechanism.
Six link mechanisms were chosen to limit the amount of complexity
and inertia due to excessive number linkages.

**4.3b Rejection Criteria**

- The maximum number of prismatic pairs should be one.
- The ground link of all six-link structures should be ternary, i.e., it should have three joints .

**4.3c Results**

The search for a suitable six-link dwell mechanism produced one contracted graph that has two basic kinematic chains (Watt and Stevenson shown in Figure 4.2). By varying the location of the slider nine mechanisms were obtained for these two basic kinematic chains. The sketches for these mechanisms are given in Figure 4.3.

Figure 4.2: Two basic kinematic chains belonging to the six-bar
1 degree of freedom class of mechanisms.

In the nine mechanisms obtained from the search five mechanisms belong to [Figures 4.3a, b, c, d and e] the Stevenson six-link chain and four belong to [Figures 4.3g, h, i] the Watt six-link chain. After further consideration, mechanisms [Figures 4.3b, g, h, i] were considered unfit due to the presence of a passive dyad which reduces these mechanisms crank-slider mechanisms.

Type Synthesis of a single or double dwell six-link mechanism is typically conducted by choosing a four-link mechanism which has a coupler curve with a circular portion during a part of the crank rotation. The output dyad with the slider is then attached to the output crank of the four-link mechanism so that the slider forms the center of the circular portion of the coupler curve. Thus, the topological requirement of a six-bar dwell mechanism would be:

- the output slider should not be a part of the drive or input loop containing the crank.

On applying this rejection criterion, mechanisms c, d and e belonging to the Stevenson six-bar chain which have the output slider as a part of the drive loop were deemed unfit for the synthesis of a single dwell mechanism. The output dyad of the mechanism shown in Figure 4.3f is connected to a ternary link. The ternary link is directly connected to the ground and hence describes a circular motion for the entire crank rotation. Consequently, the output slider will have dwell during the entire duration of crank rotation. Since the output slider should have a dwell during a portion of the crank rotation and translation for the remaining portion, mechanism shown in figure 4.3f is considered unfit as a dwell mechanism. Hence the search for a dwell mechanism results in one six-bar mechanism (Figure 4.3a) belonging to Stevenson class of six-bar kinematic chains.

Figure 4.3: Nine mechanisms obtained from the basic kinematic
chains for six-bar 1 degree of freedom class of mechanisms

**4.3d Discussion of Results**

Although the search space for this problem is small incorporating
only nine valid mechanisms and does not merit the use of computer
resources, this exercise was conducted to assess the ability of
the enumeration and automatic sketching tools (chapter 3), for
the synthesis of simple mechanisms. The next problem deals with
the synthesis of a mechanism of greater complexity and thus requires
a more complex search procedure. **4.4 Problem 2 -- Design of
a Variable-Stroke Piston Engine**

**4.4a Design Specifications**

- The designers limit their search to in-line configurations, so that only plane single-degree of freedom mechanisms need to be considered.
- Due to their high load-carrying capability, the admissible joints are limited to those with surface contact, such as revolute (R) pairs and prismatic pairs (P).
- Gear and cam pairs are both excluded for the above reason and due to their high cost and potential noise. Circular arc sliders are also excluded to avoid unnecessary complexity.
- The case of mechanisms with one independent loop is not considered. This is because such mechanisms are not suitable for variable-stroke operations and there is no way of controlling the stroke.
- Even though a greater number of links could facilitate better stroke control, at the same time they would introduce increased mass and correspondingly greater inertia forces. High inertia forces being detrimental to the search for light-weight, fuel-efficient power plants, the search is restricted to mechanisms with two and three independent loops only.

**4.4b Rejection Criteria**

- The maximum number of prismatic pairs cannot exceed two.
- The ground link of all six-link structures should be ternary, that is, it must have three joints.
- All eight-link structures, which do not have at least one link with four joints are excluded.
- All eight-link structures with one prismatic pair are excluded since two sliders are needed to achieve control.
- No prismatic pair may exist in the drive loop.
- Each piston must be connected to a binary link.
- Each crank must be a binary link.
- The crank cannot be directly connected to the connecting rod.
- Crank cannot be connected to the slider
- Connecting rod cannot be connected to the slider (coupler controlled output is not desirable)
- The crank cannot be part of the control loop, the loop which is connected for stroke adjustment.
- Stroke variation cannot be achieved at the expense of requiring variation of the proportion of links in the drive loop.

**4.4c The Search Procedure**

Even though the search space included six-link mechanisms, they were judged as unsuitable for this particular application since six-link mechanisms contain only two loops whereas the eight-bar mechanisms contain three loops. The three loops of the eight-link mechanisms are used as a drive loop (which includes the crank), a control loop to vary the stroke, and an output loop that includes the piston. Hence it implies that two functions of the eight-link mechanisms must be assigned to one six-bar loop. For this reason six-bar drive loops also include the control function and this is an important reason why none of the six-link variable-stroke mechanisms were considered provisionally acceptable [Freudenstein et al., 1983].

The search for a suitable eight-link variable stroke engine involved
enumerating all possible non-isomorphic mechanisms for the sixteen
basic kinematic chains. Figure 4.4 shows the schematics of this
enumeration framework for an 8 bar 1 degree of freedom mechanism.
After applying rejection criteria 3, only two of the four contracted
graphs shown in Figure 4.4 were found appropriate for further
enumeration. As shown in the figure, the chosen contracted graph
is then used to enumerate the corresponding basic kinematic chains.
For each basic kinematic chain various mechanisms were obtained
by permuting the ground, crank, slider and the piston according
to the rejection criteria. The mechanisms so obtained were then
checked for isomorphism. Visual representations of the mechanisms
were drawn to view the topological configuration of the links
in the selected mechanisms. Here it should be mentioned that even
though rejection criteria 11 and 12 could not be incorporated
in the program, the resulting mechanisms were manually tested
for these criteria. However, the loop information needed for these
rejection criteria can be obtained from the automatic sketching
program.

**4.4d Results**

The search space for this problem has approximately 896 (16 ^{8}C_{3}
) mechanisms. The search for eight-link variable stroke engine
mechanisms resulted in 69 mechanisms from six, 8 link basic kinematic
chains shown in Figure 4.5.

Figure 4.5: Six 8-bar 1 degree of freedom basic kinematic chains
found appropriate for synthesis of the variable stroke engine
mechanism.

After running an isomorphism check 23 non-isomorphic mechanisms
were obtained. These 23 mechanisms do not include 2, 15 and 22
from Freudenstein et al. [1983] since the rule since that the
connecting rod cannot be connected to the control slider was not
used by Freudenstein et al [1983]. Figure 4.6a and 4.6b give sketches
of all the 23 valid mechanisms obtained from the search.

**4.4e Discussion of Results**

Freudenstein et al. [1983] obtained 23 mechanisms after conducting a manual search. The authors selected three mechanisms 2c, 12f and 13a shown in Figures 4.6a and b, as potentially acceptable. Most of the mechanisms were rejected on the basis of excessive sliding in the drive loop (the control slider is present in the drive loop) or because the output is coupler connected (15a and c shown in Figure 4.4b). The manual search conducted by Freudenstein et al.[1983] ignored a valid basic kinematic chain (BKC 1 shown in Figure 4.5). However, this kinematic chain yields two valid mechanisms (1a and b shown in Figure 4.6a) none of which was considered potentially acceptable. The absence of the two kinematic chains in the search results [Freudenstein et al., 1983] was observed earlier [Yang et al., 1991] when the same problem was solved using an expert system known as DOMES. This goes to prove that manual search approach is laborious and prone to ignoring some valid mechanisms that may or may not yield practical solutions.

The results obtained from this search conducted using the unified
standard code approach included all the mechanisms considered
potentially acceptable by Freudenstein et al. [1983]. This indicates
that by applying appropriate design rules, the unified standard
code approach can be a viable tool for conducting systematic *type
synthesis* of mechanisms.

**4.5 Summary**

This chapter presents the use of the unified standard code technique
for the *type synthesis *of mechanisms. Two case studies
in *type synthesis *of mechanisms were presented. A program
was implemented to search for the mechanisms appropriate for the
application and the results were compared with those obtained
from the manual search previously conducted. Results obtained
for both the problems indicate that the search is complete and
they match the results previously obtained through manual techniques.
Furthermore, the search for the second problem yielded additional
designs that were not identified by the manual technique. Hence
it can be said that the unified standard code approach when combined
with an expert system environment can produce results comparable
or even better than those obtained by using manual techniques.

This project presents a novel coding scheme applicable to all
classes of mechanisms. The usefulness of this coding scheme in
the development of efficient enumeration and automatic sketching
routines has been shown. A scheme for the automation of the *type
synthesis *of mechanisms using the enumeration and automatic
sketching routines is proposed. The salient features of this scheme
are the quick generation of all mechanisms applicable to a given
design problem and the ability to visualize all classes of mechanisms
using a reliable automated sketching tool. The working of the
scheme is illustrated with the aid of two mechanism design examples.

An efficient algorithm for identification and unique representation of contracted graphs and basic kinematic chains using modified standard codes has been developed. A consistent numbering scheme that reflects the symmetry properties of higher order links of a contracted graph has been proposed. It has been shown that a two-stage enumeration scheme that uses the symmetry information from the contracted graphs to enumerate basic kinematic chains offers a good tradeoff between computation and memory.

The capabilities of the automatic sketching routine for representation
of basic kinematic chains have been extended to all classes of
mechanisms. Modified standard codes, due to their consistent representation
of all classes of mechanisms, provide a nice platform for integration
of enumeration and automatic sketching of mechanisms. A scheme
for automation of the *type synthesis *process, using an
integrated enumeration and automatic sketching approach has been
presented. This approach offers an efficient and reliable method
to search for a mechanism that meets the topological requirements
for an application.

Finally, the ability of the automated *type synthesis *process,
to synthesize a mechanism suitable for an application has been
illustrated by solving two mechanism design problems. Results
for both the problems were better than those obtained from the
manual search.

The *type synthesis* discussed in this project is restricted
to the synthesis of planar mechanisms with revolute and prismatic
type of joints. Since the unified standard code technique can
be applied for spatial mechanisms and also for mechanisms with
different kinds of joints like gears and cams the search method
can be extended to synthesize mechanisms with a variety of joint
types. Thus, it can be concluded that the unified standard code
approach is a general approach for the type synthesis of all classes
of mechanisms.

Future scope of this work could involve development of an expert
system for synthesizing mechanisms involving both planar and spatial
types of joints. The *type synthesis* approach discussed
in this project can be combined with a good dimensional synthesis
method like the exact gradient approach to develop a general software
for conducting mechanism synthesis.

Ambekar, A. G., and Agrawal, V. P., 1987a, " Canonical Numbering
of Kinematic Chains and Isomorphism Problem : min code" *Mechanism
and Machine Theory, *Vol. 22, No. 5, pp. 453-461

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.

Midha, A., Turcic, D. A., Bosnik, J. R., 1984, " Creativity in the Classroom - A Collection of Case Studies in Linkage Synthesis", Mechanism and Machine Theory, Vol. 19, No. 1, pp. 25-44

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

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

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.

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.

Turner, J., 1968, " Generalized Matrix Functions and the
Graph Isomorphism Problem," *SIAM Journal of Applied Mathematics*,
Vol. 22, No. 2, pp. 131-139.

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.

Uicker, J. J., Jr., and Raicu, A., 1975, " A Method for the
Identification and Recognition of Equivalence of Kinematic Chains,"
*Mechanism and Machine Theory*, Vol. 10, pp. 375-383.

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.

Yan, H. S., and Hall, A. S., 1981, " Linkage Characteristic Polynomials: Definitions, Coefficients by Inspections," ASME Journal of Mechanical Design, Vol. 103, pp. 578-584.

Yang, B., Datseris, P., Datta, U., Kowalski, J., March 1991, "
An Integrated System for Design of Mechanisms by an Expert System
- DOMES: Applications", Journal of Mechanical Design, Vol.
113, pp. 25-31