CHAPTER 1

INTRODUCTION

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.


CHAPTER 2

DEVELOPMENT OF A UNIFIED CODING 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.

Figure 2.1: Basic Kinematic Chain of a 10 bar 1 Degree of Freedom Mechanism

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.2: Contracted Graph of Basic Kinematic Chain shown in Figure 2.1

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.

Figure 2.3: Contracted Graph after 2 loops

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

Figure 2.4: Basic Kinematic Chain after adding 2 loops

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.

Figure 2.5: Contracted Graphs of two 10 bar 1 Degree of Freedom Mechanism

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

Figure 2.6: Sketches of Basic Kinematic Chains drawn using the Automatic Sketcher Program

CHAPTER 3

ENUMERATION AND AUTOMATIC SKETCHING 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.

Figure 3.1: Contracted Graph for a 10 bar, 3 Degree of Freedom Kinematic Chain

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.

Figure 3.2: Basic Kinematic Chain for 10 bar 1 Degree of Freedom

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.

Figure 3.3: An invalid Contracted Graph of a 8 bar 1 Degree of Freedom 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 3.4).

Figure 3.4: An invalid Contracted Graph violating rule d

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

Figure 3.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 3.6). A fused vertex technique (Mruthyunjaya, 1979) has been adapted to check this condition in contracted graphs.

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

Figure 3.8: Basic Kinematic Chain for a 8 bar,1 Degree of Freedom system violating rule1

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.

Figure 3.9: Basic Kinematic Chains for a 8 bar, 1 Degree of Freedom system violating rule 2

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 as the number of links increase. Figure 3.10 shows the simplest occurrence where the rule is violated.

Figure 3.10: Basic Kinematic Chains for a 8 bar, 1 Degree of Freedom system violating rule 3

Figure 3.11: Basic Kinematic Chains for a 8 bar, 1 Degree of Freedom system violating rule 4

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.12: F = 0 sub chain in 10 link, 1 Degree of Freedom system

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.

Figure 3.13: F = 0 sub chain in 12 link, 1 Degree of Freedom system

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

Figure 3.14: Image of a contracted graph produced by the sketching program.

3.5 Results and Discussion

Number of Contracted Graphs
No. of Links
DOF = 1
6
1
7
N/A
8
4
9
N/A
10
17
11
N/A
12
118

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

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 3.2: Results of enumeration of basic kinematic chains

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.

Figure 3.16: Sketches of 9, 10, 11 and 12 bar 1 Degree of Freedom systems

CHAPTER 4

APPLICATION OF UNIFIED STANDARD CODES: CASE STUDIES

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:

  1. Design of a punching mechanism [Midha et al., 1984]
  2. 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.

  1. 4.2 Procedure for Type Synthesis

Figure 4.1: Schematic of Type Synthesis using Enumeration and Sketching routines

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.

  1. Minimum relative slider displacement of 1.5 in. between the dwell and rise period
  2. Linkage contained 4 6 1.25 in. volume (excluding the crank, punch, and the indexing device)
  3. Mechanism speed of 2000 rpm
  4. 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

  1. The maximum number of prismatic pairs should be one.
  2. 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:

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

  1. The designers limit their search to in-line configurations, so that only plane single-degree of freedom mechanisms need to be considered.
  2. 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).
  3. 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.
  4. 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.
  5. 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

  1. The maximum number of prismatic pairs cannot exceed two.
  2. The ground link of all six-link structures should be ternary, that is, it must have three joints.
  3. All eight-link structures, which do not have at least one link with four joints are excluded.
  4. All eight-link structures with one prismatic pair are excluded since two sliders are needed to achieve control.
  5. No prismatic pair may exist in the drive loop.
  6. Each piston must be connected to a binary link.
  7. Each crank must be a binary link.
  8. The crank cannot be directly connected to the connecting rod.
  9. Crank cannot be connected to the slider
  10. Connecting rod cannot be connected to the slider (coupler controlled output is not desirable)
  11. The crank cannot be part of the control loop, the loop which is connected for stroke adjustment.
  12. 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].

Figure 4.4: Schematic of Mechanism Enumeration process

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 8C3 ) 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.

Figure 4.6a: Sketches of the mechanisms obtained from the 6 basic kinematic chains shown in Figure 4.5.

Figure 4.6b: Sketches of the mechanisms obtained from the 6 basic kinematic chains shown in Figure 4.5.

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.


CHAPTER 5

CONCLUSIONS

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.


BIBLIOGRAPHY

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

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