Isomorphism, Inversions and Symmetry in Single Degree 8 Links 16 Kinematic Chains using Application of Fuzzy Logic

Isomorphism, Inversions and Symmetry in Single Degree 8 Links 16 Kinematic Chains using Application of Fuzzy Logic

Dr.S.R.Madan(1) Er. Sushant Mahendru (2) Er. Anjali Mahendru(3)

Abstract

Through the use of fuzzy logic, an efficient methodology has been developed for the investigation of isomorphism among the kinematic chains. In this paper, necessary and sufficient conditions are specified and numerical measures are proposed to study the isomorphism, inversions and symmetry of single degree 8 links 16 k-chains.

1. Introduction

   To detect the isomorphism in generation of planner kinematic chain is one of the major problems for kinematicians and researchers nowadays. A lot of time and effort has been devoted for developing a reliable and computational effiecent technique. Mruthyunjaya and Balasubramaniam [7] proposed a degree matrix method which was later reported to be not unqiue by Hwang and Hwang [8]. The Maxcode method proposed by Ambekar and Agarwal [2] needs greater computational effort. Uicker and Raicu [5] have presented a characteristic polynomial method which was considered reliable for quite some time. Rao and Raju [1] developed the Hamming number technique which is reliable and computational efficient as confirmed by Pennestri [4]. Pennestri suggested a method to improve the reliability of Hamming number technique unaware of the fact that the authors themselves have discovered the deficiency and published the corrections as a corrigendum.

   A recent review by Tischler et al.

   [3] includes a good number of references on

   the subject of Isomorphism and hence no attempt is made here to repeat those.

   However, almost all the methods reported so far are based on an adjacency of links. These methods do not specify necessary and sufficient conditions. Consequently, counter examples are found in almost all the methods. The author believes that the earlier methods deal only with first adjacency. First adjacency of a link deals with the links that are directly joined to it. The methods proposed may thus isolate the chains up to first adjacency and may fail in some cases due to no control on the second or higher order adjacency of links.

   Any method that deals logically with all the adjacencies (first, second, etc.) will not fail and test isomorphism uniquely.

   Fuzzy logic is used in this work as its advantage lies in the fact that beyond detecting isomorphism among chains and inversions it has the ability to reveal practically important but less explored characteristics like symmetry, parallelism.

   1:- Prof. in Mech. Engineering Depdt., M.I.T.M.UJJAIN, (M.P.), INDIA,

   2:-Inspection Engineer, Kuwait National Petroleum Company, MAB, KUWAIT

   3:- Estimation Engineer, Alghanim International, Kuwait

2. Theory

A closed kinematic chain with a specified number of links and degrees of freedom is considered as a parallel chain, the

nc

(N-1)

, ——————(1)

extent of parallelism depending upon its structure. Each chain can be represented by a graph in which the links become vertices and the joints become edges. A graph of N vertices is considered fully connected or completely parallel if every vertex is connected to every other vertex. Such a graph or the corresponding chain will have negative degrees of freedom i.e. highly redundant but is considered ideally parallel. The fact that the chain corresponding to such a graph is highly immobile should not impede the comparison of the actual chains (F1) for parallelisms as all the chains to be compared retain the same features such as number of links, joints, loops, etc. but differ in structure only. Thus, it is possible to compare these chains against a standard chain or a fully connected graph. The actual chains with N links and specified degrees of freedom (d.o.f. =1, 2, 3, …) deviate considerably from the ideal or fully connected graph in the matter of (i) number of edges and (ii) their adjacency.

The degree of a vertex of the fully connected or idea N-vertex graph being (N- 1), each vertex of the actual chain-graph can be assigned a fuzzy number in the scale 0 to

1. The crisp number 0, zero in the scale represents a link (vertex) isolated from the structure while another crisp number one (1) means that the vertex is fully connected. For a closed kinematic chain, both the crisp numbers cannot exist and the actual links (vertices) have intermediate values. The number assigned to a vertex or the link of an actual chain is

where, nc is the number of other links to which the links under consideration is directly joined and N the total number of links in the chain. For example, the value of nc for a binary link is 2 while that for a quaternary link is 4.

It is obvious that a particular link- assortment will have a particular set of fuzzy-numbers called fits.

Using these fits, matrices can be formed for every chain. Each such matrix corresponds to the level of adjacency of links (vertices).

For example, consider a eight-link singled .o.f chain (Fig.1a). its graph is shown in fig.1b

The fuzzy numbers or fits for vertices 1, 2, etc. are, respectively

3/7, 2/7, 3/7, 3/7, 2/7, 2/7, 3/7

Or

0.429, 0.286, 0.429, 0.429, 0.285, 0.285,

0.429

Since the degree of each vertex in the fully connected graph with eight vertices is 7 Fig.1(c).

2.1.First adjacency matrix (C1)

First adjacency matrix consists of the fuzzy elements or numbers which correspond to the links that are directly connected or separated by one joint. For example, the first row of the elements represents the fuzzy number of the links that are directly jointed to the link 1.

If there is no direct connection between links, e.g. links 1 and 4, the corresponding matrix element will be zero. Also each diagonal element will be zero since a link cannot connect to itself. For the chain, Fig 1(a);

2.3.Higher adjacency matrices: (C3,C4)

In chains with large number of links, adjacency of links separated by three joints, four joints etc. by shortest path, exists and the corresponding matrices need be formed on the lines of C1 and C2.

C1=

———-(2)

2.2.Second adjacency matrix (C2)

Second adjacency matrix consists of the fits of the links that are separated just by two joints. For example, row-1 which correspnds to link 1 consists of fits corresponding to link 3,4,6and 7 which are separated by two joints. All other fit values will be zero. For the chain, Fig. 1(a)

1. Fuzzy vector

   The ith row of fits of the C1, matrix in that order, is the fuzzy vector of first adjacency of the ith vertex or links. Similarly, the ith row of fits of the C2 matrix, in the proper order, is the fuzzy vector of second adjacency of the ith link.

   For example,

   The fuzzy vector of the first adjacency of link 2 from the matrix in (2) is

   0.429,0, 0.429,0,0,0,0,0. ———-(4)

   And fuzzy vector of second adjacency of

   C1=

   0	0	0.429	0.429	0	0.286	0.286	0
   0	0	0	0.429	0.286	0	0.286	0.429
   0.286	0	0	0	0	0286	0	0.429
   0	0.286	0	0	0.286	0	0.286	0.429
   0.429	0	0	0.429	0	0	0	0
   0	0	0	0.429	0	0	0	0.429
   0	0	0.429	0	0	0	0	0.429
   0.429	0	0	0	0	0.286	0.286	0

   C2 =

   ————-(3)

   link 3 from C2-matrix (3) is

   0.286,0,0,0,0,0.286,0,0, 0.429 ——–(5)

   1. Isomorphism: criteria

      The criteria proposed to test isomorphism among kinematic chains is explained below.

      Consider two fuzzy vectors fuzzy A and B from the same space. It is possible to vector. It is necessary to establish the extent to which vector B is a subset of A and vice versa.

      The following expressions can be used to know the membership of one set within another [6].

      A is a subset of B to the extent S(A,B)

      M(AB)

      = ————– ———-(6) M(A)

      matrix(S). Replacing vectors A and B by numbers 1,2 etc. to represent vectors of links 1, 2, , etc., respectively and using Eqs. (6)

      Where M(A) means the cardinality of set A defined as the sum of all the fits of the vector A.A B is the intersection of vectors A and B.

      The intersection of two vectors A and B is given by another vector whose fits are component by component the smaller of the fits of A and B.

      For example,

      Intersection of the fuzzy vector (5) and (6) is

      0,0,0,0.429,0,0,0,0

      And its cardinality, the sum of all its fits is 0.429

      It is now easy to understand that B is a subset of A to the extent S(B,A)

      In general,

      M ( A B) M(A B)

      —————— ————– —–(7) M(A) M(B)

      A higher value of the element S(A,B) means that the two sets of vectors have more in common, i.e. more parallel connections between the links representing vectors.

      Since the rows of the matrices C1 and C2 are considered as vectors, it is possible to estimate the membership of one vector within the other and use the resulting values to construct a matrix called sub-set

      and (7) we can compute the elements of the sub-set matrix(S)

      S= [Sij]

      Where Sij is the extent to which vector i is a subset of the vector j. the elements of the second row, for example, of the S-matrix Reveal the extent to which vector of link 2 is a subset of vectors of other links.

      With the above understanding, the subset matrix (S1) corresponding to C1 matrix (2) is constructed and is given below.

      1 0 .286 .286 0 .429 .429 .429

      0 1 0 .5 .5 0 . 5 .83

      .286 0 1 0 .429 .429 0 .286

      S1 = .286 .429 0 1 0 0 .429 .715

      0 . 5 . 5 0 1 . 5 0 . 5

      . 5 0 . 5 0 .5 1 .5 0

      . 5 . 5 0 . 5 0 . 5 1 0

      0 .429 .286 .286 .429 0 0 1

      ——————-(8)

      A string numbers for each row can be written in the following manner for each adjacency matrix.

      Sum up all the elements in the row.

      Then write the sum followed by the elements of the row in descending manner. For example, for link 2 from the matrix in

      (8) the string is

      3.33-(1), (.83), 3(.5), 3( 0)

      In the above string appearance of 2(0.5) indicates that the element 0.5 occurs twice in that row.

      Similarly, the string for every row can be written and all of them can be arranged in the descending order of their sums to give the row string of the chain. From the matrix (8), we can write

      /[3.33-(1), (.83),3(.5),3(0)]/ 3[3-(1),4(.5),

      3(0)]/[2.859-(1), (.715), 2(.429),(.286),3(0)]

      /[2.859-(1) 3(.429),2(.286),2(0)]/[2.43-(1), 2(.429),2(.286),3(0)]/

      Where 3 before the square brackets indicates that there are two rows with the same strings.

      Working similarly on each column string (b) gives the first the first adjacency chain-string.

      Now the subset matrix S2 for the second adjacency can be written from the matrix C2.

      Row and column strings and finally the second adjacency chain string can be written on the lines similar to that of the matrix S1.

2. Check for isomorphism

   1. it is only necessary to check for isomorphism among chains with the same link assortments.

      for every kinematic chain, first adjacency and second adjacency matrices should be formulated and higher order

      adjacency matrices, if any, should also be written.

      From these matrices, the extent to which each set (vector) forms a subset of the other can be determined and another matrix called subset-matrix can be written. From the above, a numerical string corresponding to each adjacency can be written for every chain.

   2. If the strings pertaining to two different chains are identical, component by component, then the chains are isomorphic, otherwise distinct.

   3. The strings up to N/2 adjacency for an N-link are necessary and sufficient to test isomorphism completely and uniquely.

   4. Besides uniqueness, computation of N/2 adjacency strings is simpler compared to the other methods, viz. characteristic polynomial.

   5. Chains such as in Fig. 2a and b, which are greatly alike in the matter of adjacency, also prove the reliability of the proposed method.

   6. the extent to which a vector A forms a subset of another vector B need not be the same as the extent to which B forms A subset A. hence, row of elements in the S matrix can be different form the column elements,

      i.e. this S matrix is not symmetric. For isomorphism of two graphs, all the elements of the C matrix of a graph necessarily have to be the same as those of other chain. This is possible only when the graphs are exactly identical.

   7. Relabeling of links doses not alter the results.

   8. Different identification strings for 1- F, 8 links 16 K-chain shown in Fig. 3 are presented in Table 1 .

   1. Inversions

      The distinct inversions of a chain can be decided from the C matrices and the row and column strings. From each of the adjacency matrices C1, C2 etc. a numerical string for every link can be written in the following manner.

      The sum of the elements of a row ith followed by the row in descending order consists of the row string.

      Similarly, the sum of the elements of the ith column followed by the column in descending order consists of the column string.

      Now the complete string for a particular link(2) is given by the row string followed by the column string.

      /[3.33-(1),1(.83)3(. 5), 3(0)]/

      For example, for link 2 of the chain Fig. 1a, the row string is/[3.33-(1),1(.83),3(.5),3(0)] / and the column string is /[2.859- (1),2(.429),2(.5),3(0)]/ .hence, the link-string is

      /[3.33-(1),2(.83),3(.5),3(0)]/[2.859 (1),2(.429),2(. 5), 3(0)/

      In order to know the distinct inversions of a chain, it is necessary to compare the strings of all the links. If the strings are identical, the corresponding inversions are identical, otherwise distinct.

      Such link-strings should be formed from each adjacency matrix(second and higher order adjacency, if any) and they should also be checked. Any difference in the strings of any adjacency will result in distinct inversions.

      Symmetry

      Identical location of a pair of identical links (j and k) with respect to another link (i) is considered as the symmetry about the link i. In section 4.1, it was explained how to decide identical or distinct links of a chain. For deciding the symmetry it is only necessary to scan the subset matrices.

      Let us consider ith row and if there are two elements corresponding to columns say, j and k with equal numerical values, then check the ith column for the elements in the rows j and k, if they are also equal, then the links j and k are symmetrically located about the links i. in other words, for symmetry of links j and k about the link I the following conditions need to be satisfied.

      Sij=Sik and Sji=Ski

3. Conclusions

1. Each link of a kinematic chain is assigned a fuzzy membership (fits). A fuzzy vector is developed in terms of fits for each links, depending upon its adjacency, i.e. for every link separate vectors for first adjacency, second adjacency and so n are proposed. Thus, there are as many vectors for each adjacency as the number of links in the chain and the extent to which each link- Vector forms a subset of the other link- vectors are estimated and a sub-set matrix is formed. Subsequently, based on the elements of this matrix, a numerical string is formed for every chain. Comparisons of such strings of different chains reveals isomorphism, if any, i.e. if the strings of both the chains are identical (component to component), then they are isomorphic , otherwise, distinct.

   Since the comparisons of the numerical strings upto last adjacency of links are necessary to detect isomorphism uniquely, adjacency wise isomorphism may be attributed. For example, two chains may have their first and second adjacency string identical, but differ in their third adjacency

   strings, and then the chains may be considered as first and second adjacency isomorphic. This indicates the extent to which two chains are identical.

2. Relabeling of links dose not changes the subset values.

3. Distinct inversions of a chain can also be detected without additional effort.

   Rererences:-

   1. A.C.Rao, D.Varada Raju, Application of Hamming number technique to deduct isomorphism among kinematic chains and inversions,Mchanism and Machine Theory 26(1)(1991) 55-75.

   2. A.G.Ambekar, V.P.Agrawal, On Canonical numbering of kinematic Chains and Isomorphism problem:Max Code, papr No.86- DET-169 Design Engg., Technical conf. of A.S.M.E., Oct. 5-8,1986.

   3. C.R.Tichler, A.E. Samuel, K.H.Hunt, Kinematic chains for robot hands.1,Orderly number synthesis, Mechanism and Machine Theory 35(1995),1193-1215.

   4. E.Pennestri, Mechanism and Machine Theory 28 (1993), 721-724.

   5. J.J. Uicker Jr,A.Raicu, Mechanism and Machin Theory 10(1975) 375- 383.

   6. M.Chester, Neural Networks: a Tutorial, PTR Prentice Hall, Englewood Cliffs, NJ1993.

   7. T.S.Mruthyunjaya,B.R.Balasubrama niam, In quest of reliable and efficient computational test for diction of isomorphism in kinematic chains, Mechanism and Machine Theory 22 (2) (1987) 131-139.

   8. W.M. Hwang, Y.W. Hwang, Computer-aided structural synthesis of planar kinematic chains with simple joints, Mechanism and

MACHINE Theory 27(2) (1992)

189-197.

Figure-2. Ten-link chain without(a) and with (b) crossed links.

International Journal of Engineering Research & Technology (IJERT)

10

ISSN: 2278-0181

Vol. 1 Issue 4, June – 2012

www.ijert.org 10

International Journal of Engineering Research & Technology (IJERT)

11

ISSN: 2278-0181

Vol. 1 Issue 4, June – 2012

www.ijert.org 11