A UNIFIED CODING SCHEME FOR EFFICIENT MECHANISM

ENUMERATION


Srinath Jonnalagadda

Graduate Research Assistant

Sundar Krishnamurty

Associate Professor

Department of Mechanical Engineering

University of Massachusetts

Amherst, MA 01003





ABSTRACT

This paper presents a unified coding scheme for consistent mechanism representation. 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 basic children 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.


INTRODUCTION

This paper 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. Fang and Freudenstein (1988) have shown that structural abstraction based on contracted graph can be a viable and robust technique in mechanism design process. This paper presents a combinatorial approach that is based on standard code method for identifying mechanism uniqueness, and utilises 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.

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 yeilds 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 1: BKC OF A 10 BAR 1 DOF MECHANISM

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. Based on 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 verticies (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 1.

Contracted Graph phase :

Figure 2 shows the contracted graph for the kinematic chain shown in Figure 1. Contracted graphs are given codes acording 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 3. The colored code for this particular example corresponding to the link-link interconnections and the number of connectins between links is:

C = ( 26279, 111111111 )

FIGURE 2: CONTRACTED GRAPH OF BKC SHOWN IN FIGURE 1

FIGURE 3: CONTRACTED GRAPH AFTER 2 LOOPS

Figure 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 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 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 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 4: BKC AFTER ADDING TWO LOOPS

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, as well as contracted graphs with non-symmetric higher order links as in Figure 5.

FIGURE 5: CONTRACTED GRAPHS OF TWO 10 BAR 1 DOF 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 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 6a-c show illustrations of three of the 43 kinematic chains of the parent contracted graph in Figure 5a drawn using the Automatic Sketcher program (Mauskar and Krishnamurty, 1995). Similarly, unique codes were obtained for the 42 kinematic chains of the contracted graph in Figure 5b, and sketches of three such cases are shown in Figures 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.

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 acheiving 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). Figure 7 shows the schematics of this enumeration framework for an 8 bar 1 degree of freedom mechanism.

FIGURE 6: SKETCHES OF BKCS DRAWN USING THE AUTOMATIC SKETCHER PROGRAM

FIGURE 7: SCHEMATICS OF MECHANISM ENUMERATION PROCESS

CONCLUSION

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

ACKNOWLEDGEMENT

The authors gratefully acknowledge the support of the National Science Foundation under Grant No. CMS-9402608.

REFERENCES

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

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

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

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

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

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

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

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