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.
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.
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.
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 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).
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.
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.
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.
The authors gratefully
acknowledge the support of the National Science Foundation under
Grant No. CMS-9402608.
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.