# An Algorithm for Identifying the Isomorphism of Planar Multiple Joint and Gear Train Kinematic Chains.

1. IntroductionIsomorphism identification is one of indispensable steps in the structural synthesis of kinematic chains, so a lot of studies have been done in this field. Until now, many methods have been presented for planar simple joint kinematic chains, such as the characteristic polynomial methods, which were developed in the papers [1-8] for detecting isomorphic kinematic chains by typical topological graphs. Although most of these methods are efficient, counterexamples have been found against them [8]. The max-(min-) code [9, 10], degree-code [11], and standard-code methods [12, 13] which are based on code number may be effective, but they are inadequate in efficiency. The Hamming number approach [14-16] is introduced for isomorphism identification, but the counterexamples also are found against them. The adjacent chain table method [17] seems hard to be realized by computer. The fuzzy logic method [18] also displays some new ideas for isomorphism identification and structural analysis of simple joint kinematic chains, but it needs more storage space. The method of eigenvectors and eigenvalues of adjacency matrices [19-22] detects isomorphism through computation of eigenvectors and eigenvalues as well as some permutation operations. The method of finding a unique representation of graphs to identify isomorphism kinematic chains is presented by Ding and Huang [23, 24]. In addition, some unconventional methods, such as genetic algorithm [25] and artificial neural network approach [26], are also introduced to pursue the issue.

So far, isomorphism identification of kinematic chains studied most is about those planar simple joint chains, and identification technique for this kind of chains is comparatively mature. However, besides simple joint chains, planar kinematic chains also include multiple joint kinematic chains and gear train kinematic chains. The two special types of kinematic chains can be used in a lot of mechanism design problems. As we know, isomorphism identification methods used in the simple joint chains are always not satisfying these two specific types of kinematic chains. In the field of isomorphism identification of multiple joint kinematic chains, adjacent chain table method was introduced in the paper [27]. Song et al. [28] presented the spanning tree method of identifying isomorphism and topological symmetry for multiple joint kinematic chains, but this method was not easily achieved by computer. Liu and Yu [29] presented a representation and isomorphism identification of planar multiple joint kinematic chains based on the converted adjacent matrix, but converted adjacent matrix not only increased the order of matrix but also added the complexity of isomorphism identification process. In the structural synthesis process of gear train kinematic chains, correctly identifying graph isomorphism is an important step which generates new structural types. Papers [30-32] try to do the structural synthesis of gear train kinematic chains. One of the main reasons for the incorrect identification or inconsistency in results is that there is a lack of efficient isomorphism tests. The purpose of paper [33] is to present an efficient methodology through using the loop and hamming number concept to detect the isomorphism of gear train kinematic chains in an unambiguous way. So, from the researches above, finding a useful method to solve the problem of isomorphism identification of planar multiple joint and gear train kinematic chains is the existing research content and further study is necessary.

In this paper, a new algorithm based on the equivalent circuit analysis for isomorphism identification of planar multiple joint and gear train kinematic chains is presented. Firstly, weighted-double-color-contracted-graph (WDCCG) and corresponding weighted adjacency matrix (WAM) are introduced to describe the two special types of kinematic chains, respectively. Corresponding equivalent circuit model (ECM) of the WDCCG is established, which uses circuit analysis method to obtain the node voltages of every vertex in WDCCG. The solved node voltage sequence (NVS) is used to determine correspondence vertices of two isomorphism identification kinematic chains. Then, a new algorithm to determine isomorphism of the two types of kinematic chains is proposed.

2. Topological Model of Kinematic Chains

2.1. Topological Model of Multiple Joint Kinematic Chains. Before further discussion, the following common concepts are introduced as follows.

Simple Joint. If two links are connected by a revolute joint, then a simple joint is formed. For example, a simple joint e is formed by connecting links 5 and 6, which is shown in Figure 1(a).

Multiple Joint. If there are more than two links connected by revolute joints at the same location, then a multiple joint is formed. A multiple joint composed by k links contains (k - 1) revolute joints. For example, a multiple joint a is formed by connecting links 1, 2, and 9, as shown in Figure 1(b), and it contains 2 revolute joints.

A planar simple joint kinematic chain is a kinematic chain only composed of simple joints, if there is a kinematic chain containing multiple joint, called a multiple joint kinematic chain, for example, a multiple joint kinematic chain which is shown in Figure 2(a).

In a multiple joint kinematic chain, because a multiple joint i composed of k links contains (k - 1) simple joints, defined multiple joint factor [p.sub.i] of a multiple joint i is as follows:

[p.sub.i] = k - 2. (1)

And the total multiple joint factors P of a kinematic chain can be obtained by adding all multiple joint factors of a kinematic chain together as follows:

P = [summation][p.sub.i]. (2)

So as for a multiple joint kinematic chain as shown in Figure 2(a), it has two multiple joints a and b; these joints c, d, e, f, h, i, j, and k are simple joints. Multiple joint a is formed by connecting four links, 6, 7, 8, and 10, so its corresponding multiple joint factor is [p.sub.a] = 2. Multiple joint b is formed by connecting three links, 4, 5, and 10, so its corresponding multiple joint factor is [p.sub.a] = 1. And the total multiple joint factors of this kinematic chain is P = 3.

As we know, topological model (TM) of multiple joint kinematic chain can be represented by the double color graph (DCG) as shown in Figure 2(b) [23]. But it has too many vertices (number of vertices equal to the number of links and joints of a kinematic chain), so more storage space is needed in the process of structural analysis by computer. In this paper, a weighted double color contracted graph (WDCCG) is introduced to represent the topological structure of kinematic chains. The WDCCG model which wiped off all of the simple joints and simple joint links form the multiple joint kinematic chain can improve the efficiency of isomorphism identification. The graph is established as follows: solid vertices "*" denote multiple joint links and hollow vertices "**" denote multiple joints. If two multiple joint links are connected by simple joints and simple joint links, connect two corresponding solid vertices with a weighted edge (weighted value equal to the number of simple joints between two vertices). If one multiple joint link is connected with one multiple joint or two multiple joints are connected by simple joints and simple joint links, connect them with a weighted edge as well (weighted value also equal to the number of simple joints between two vertices). For example, Figure 2(c) is the WDCCG of multiple joint kinematic chain as shown in Figure 2(a).

2.2. Topological Model of Gear Train Kinematic Chain. In this paper, topological model (TM) of gear train kinematic chains can be represented by two topological graphs. Firstly, double color graph (DCG) is established as follows: represent the gears and planet carrier with solid vertices "*," gear joints with hollow vertices "[DELTA]," and revolute joint with hollow vertices "**." And connect corresponding solid vertex and hollow vertex with an edge when a gear or a planet carrier is connected with a gear joint or a revolute joint. For example, Figure 3(b) is the DCG corresponding to gear train kinematic chain as shown in Figure 3(a). But it also has too many vertices; then, a weighted double color contracted graph (WDCCG) is introduced to represent gear train kinematic chain. Because the gear train kinematic chain contains two types of kinematic pairs, namely, revolute joint and gear joints, the WDCCG model wiped off all of the simple joints and can be established as follows: solid vertices "*" denote gears of chain, hollow vertices "[DELTA]" denote gear joints, and hollow vertices "**" denote multiple revolute joints. If two gears are connected directly by a revolute joint, connect two corresponding solid vertices with a 2-weighted edge. If two gears are connected directly by a gear joint, connect two corresponding solid vertices with a 3-weighted edge. If a gear is connected with a multiple revolute joint, also connect corresponding solid vertex and hollow vertex with a 1-weighted edge. For example, Figure 3(c) is the WDCCG of the gear train kinematic chain as shown in Figure 3(a).

2.3. Weighted Adjacency Matrix. Obviously, a multiple joint or gear train kinematic chain and its WDCCG are one-to-one correspondent to each other. The WDCCG of a kinematic chain can be represented by a vertex-vertex weighted adjacency matrix (WAM) while the elements of WAM are defined as follows:

[mathematical expression not reproducible], (3)

where n is the number of vertices in WDCCG.

When i = j, if vertex is hollow vertex, then [d.sub.ij] = 0; otherwise, the vertex is solid vertex; then, [d.sub.ij] = 1.

When i [not equal to] j, if two vertices are not connected directly, then [d.sub.ij] = 0; otherwise, the two vertices are connected directly by k weighted edges; then, [d.sub.ij] = [m.sub.ij1], [m.sub.ij2], ..., [m.sub.ijk], ([m.sub.ij1] [greater than or equal to] [m.sub.ij2] [greater than or equal to] ... [greater than or equal to] [m.sub.ijk], [m.sub.ijk] is the weighted value of kth edge).

For example, the WAM A of a multiple joint kinematic chain as shown in Figure 2(c) can be expressed as follows:

[mathematical expression not reproducible]. (4)

The WAM A corresponding to a gear train kinematic chain as shown in Figure 3(c) can be expressed as follows:

[mathematical expression not reproducible]. (5)

3. Isomorphism Identification Algorithm

3.1. Equivalent Circuit Model. As we know, when two multiple joint kinematic chains or two gear trains kinematic chains are isomorphic, their WDCCGs are exactly the same, their vertices and edges are in one-to-one correspondence with each other, and the vertices and edges in correspondence keep the same incidence and weighted relation. According to this definition, the necessary and sufficient condition for isomorphism of the two types of kinematic chains is that they have the same WAM; that is, A = A'.

Equivalent circuit model (ECM) of WDCCG is established by its each edge, which is replaced by conductance equal to the weighted value of corresponding edge [m.sub.ij].

Theorem 1. If two WDCCGs corresponding to the same type kinematic chains are isomorphic, then their corresponding ECMs are identical.

For example, two isomorphism multiple joint kinematic chains are shown in Figures 4(a) and 4(b); their WDCCGs are shown in Figures 4(c) and 4(d), respectively. According to the description above, their corresponding ECMs are shown in Figures 5(a) and 5(b), respectively. There are two identical circuits and nodes of these two ECMs are in one-to-one correspondence.

Complete excitation (CE) of an ECM is established as follows: in an ECM with n nodes, firstly, set a node (n + 1) to be a reference node; then, connect the reference node (n + 1) with every other node [n.sub.i] (i = 1, 2, ..., n) of the ECM whose conductance values are equal to the sum of weighted values of the node edges. Secondly, apply the same current source 1A between node (n + 1) and other nodes [n.sub.i] (i = 1, 2, ..., n) of the ECM, respectively, in directions of the currents going from node (n + 1) to other nodes [n.sub.i], (i = 1, 2, ..., n), respectively.

According to circuit theory, two identical circuits under the same CE have the same response. And their node voltages can be solved by the nodal method of circuit analysis. The nodal method of circuit analysis can be expressed as follows: in a circuit network, choose a node as a reference node; the voltage difference between each node and the reference node is known as the node voltage of the node. For a circuit network with n nodes, which has (n - 1) node voltages, if the node n is the reference node, the nodal voltage equation can be expressed as

[mathematical expression not reproducible], (6)

where [G.sub.ii] (i = 1, 2, ..., n - 1) is called the self admittance of a node i, the value of which is the sum of the admittance of all branches that are connected to the node i; [G.sub.ij] (i = 1, 2, ..., n - 1; j = 1, 2, ..., n - 1) is called the mutual admittance of node i and node j, whose value is the sum of the branch admittance between node i and node j; and [I.sub.sni] (i = 1, 2, ..., n - 1) is called the algebraic sum of the current source for the inflow node i (inflow is positive; outflow is negative).

For example, an ECM with 4 nodes is shown in Figure 6(a). Apply the CE of reference node 5 as shown in Figure 6(b). By nodal method of circuit analysis equations (6), node voltages [v.sub.1], [v.sub.2], [v.sub.3], and [v.sub.4] can be expressed as follows:

[mathematical expression not reproducible]. (7)

Then, the node voltages [v.sub.1], [v.sub.2], [v.sub.3], and [v.sub.4] can be obtained by solving the above equations (7). Therefore, the following conclusion can be obtained.

Theorem 2. If two WDCCGs corresponding to the same type of kinematic chains are isomorphic, their two corresponding ECMs N and N' can be established and excited by the same CE as above, respectively. Then, the node voltages of each correspondence node of two ECMs N and N' are the same.

For example, two identical ECMs N and N' with 5 nodes are shown in Figures 5(a) and 5(b). Apply the same CE of reference node 6 which is shown in Figures 7(a) and 7(b), respectively. And their corresponding WAMs A and A' can be obtained as follows:

[mathematical expression not reproducible]. (8)

By nodal method of circuit analysis, equations of node voltages [v.sub.1], [v.sub.2], [v.sub.3], [v.sub.a], and [v.sub.b] can be expressed, respectively, as follows:

[mathematical expression not reproducible], (9)

[mathematical expression not reproducible]. (10)

Then, node voltages [v.sub.1], [v.sub.2], [v.sub.3], [v.sub.a], and [v.sub.b] of two ECMs can be obtained by solving the above (9) and (10), respectively, as shown in Table 1.

From Theorem 2, node voltages of each correspondence node in these two ECMs are the same as follows: [v.sub.a] = [v.sub.b] = 0.1627, [v.sub.b] = [v.sub.a] = 0.1691, [v.sub.1] = [v.sub.3] = 0.1839, [v.sub.2] = [v.sub.1] = 0.1691, and [v.sub.3] = [v.sub.2] = 0.1537. When arranging the obtained node voltages in descending order with the same node voltages staying together, this set is called the node voltage sequence (NVS) and denoted as

[mathematical expression not reproducible], (11)

where the variables [mathematical expression not reproducible] represent node voltages of hollow vertex. The variables [mathematical expression not reproducible] represent node voltages of solid vertex.

If two identical ECMs are stimulated by the same CE as above, then the NVSs in correspondence are the same. For example, two identical ECMs as showed in Figures 5(a) and 5(b), the NVS and vertex codes can be obtained, respectively, as follows:

NVS (a)= [([v.sub.b], [v.sub.a]), ([v.sub.1], [v.sub.2], [v.sub.3])] = [(0.1691, 0.1627), (0.1839, 0.1691, 0.1537)], NVS (b)= [([v.sub.a], [v.sub.b]), ([v.sub.3], [v.sub.1], [v.sub.2])] = [(0.1691, 0.1537), (0.1839, 0.1691, 0.1627)]. (12)

If the NVSs of two ECMs are not the same, then the two WDCCGs are not isomorphic. On the contrary, if they are the same, correspondence vertices in these two WDCCGs can be determined by the element values of NVS. Then, perform the row exchanges of WAM A' to determine if they are isomorphic. Because the NVS can reduce the number of row exchanges to several ones or only just one, this is a very effective method. For example, by the NVS(a) and NVS(fc) of two ECMs shown in Figures 5(a) and 5(b), the vertices in correspondence are a-b, b-a, 1-3, 2-1, 3-2; then, through exchanging the row of WAM A', we obtain A = A', which are isomorphic.

For example, two gear train kinematic chains are shown in Figures 8(a) and 8(b), and their WDCCGs as shown in Figures 8(c) and 8(d), respectively. Their corresponding WAMs are A and A', as follows:

[mathematical expression not reproducible], (13)

According to the above method, their corresponding NVS and vertex codes can be obtained as follows:

NVS (a) = [([v.sub.b]), ([v.sub.6], [v.sub.5], [v.sub.4], [v.sub.1], [v.sub.2], [v.sub.3])] = [(0.2330), (0.2744, 0.2257, 0.2068, 0.1908, 0.1907, 0.1737)], NVS (b) = [([v.sub.b]), ([v.sub.3], [v.sub.4], [v.sub.5], [v.sub.1], [v.sub.6], [v.sub.2])] = [(0.2330), (0.2744, 0.2257, 0.2068, 0.1908, 0.1907, 0.1737)]. (14)

By the NVS(a) and NVS(b), the vertices of these two WDCCGs in correspondence can be obtained as follows: b-b, 1-1, 2-6, 3-2, 4-5, 5-4, 6-3, and through exchanging the row of WAM A' one time, we obtain isomorphic A = A'.

3.2. Algorithm. Here, a direct algorithm is given to determine isomorphism of planar multiple joint and gear train kinematic chains, and it can be expressed as follows.

Step 1. Input the vertex codes and WAMs A, A' of two WDCCGs corresponding to the same type of kinematic chains.

Step 2. Assign vertices codes of A and A' in two groups: the hollow vertexes to be the first group and the solid vertexes to be another group.

Step 3. Calculate NVS(a), NVS(b), and their vertex codes of the two ECMs with the same CE, respectively. Compare NVS(a) and NVS(b): if equivalence cannot be seen, it is determined that they are not isomorphic and program stops; otherwise, it is determined that they could be isomorphic. Then, check the NVS(a) and NVS(b) to see if the values in two vertex code groups are all distinct: if yes, go to Step 4; if no, go to Step 6.

Step 4. Take the NVS(a), NVS(b), and their vertex codes to determine the correspondence of vertices according to the values that are in correspondence.

Step 5. According to the corresponding vertices obtained and the vertex codes to form new WAM [A'.sub.1], rewrite WAM A'. If A = [A'.sub.1], it is determined that they are isomorphic; otherwise, they are not isomorphic and program stops.

Step 6. According to the corresponding vertices obtained, the NVS(a) and NVS(b) have the same values in the corresponding two vertex code groups. Just adjust the position order of vertices of the same group in A' to obtain vertex codes to from new adjacency matrix [A'.sub.1]. If A = [A'.sub.1], it is determined that they are isomorphic and program stops; if A [not equal to] [A'.sub.1], keep on adjusting the position order of the aforementioned vertices in A' of the vertex code groups for all possibilities. And if A [not equal to] [A'.sub.1] always, it is determined that they are not isomorphic and program stops.

4. Examples

Example 1. Two 10-link multiple joint kinematic chains are shown in Figures 9(a) and 9(b). Their corresponding WDCCGs are depicted in Figures 9(c) and 9(d), respectively.

The direct process to determine isomorphism of these two kinematic chains can be expressed as follows.

Step 1. Input their corresponding vertex codes and WAMs A, A' as follows:

[mathematical expression not reproducible]. (15)

Step 2. Evidently, A = A'. Assign vertices codes of A and A' in two groups (a) [(a, b, c, d), (1)] and (b) [(a, b, c, d), (1)].

Step 3. Calculate NVS(a), NVS(b), and their vertex codes of two ECMs with the same CE, respectively, as follows:

NVS (a)= [([v.sub.c], [v.sub.b], [v.sub.a], [v.sub.d]), ([v.sub.1])] = [(0.1551, 0.1546, 0.1451, 0.1275), (0.1700)], NVS (b)= [([v.sub.a], [v.sub.b], [v.sub.c], [v.sub.d]),([v.sub.1])] = [(0.1538, 0.1459, 0.1459, 0.1308), (0.1714)]. (16)

Compare NVS(a) and NVS(b) and equivalence cannot be seen. It is determined that they are not isomorphic and program stops.

Example 2. Two 11-link multiple joint kinematic chains are shown in Figures 10(a) and 10(b). Their corresponding WDC-CGs are described in Figures 10(c) and 10(d), respectively. The direct process to determine isomorphism of these two kinematic chains is as follows.

Step 1. Input their corresponding vertex codes and WAMs A, A' as follows:

[mathematical expression not reproducible]. (17)

Step 2. Evidently, A [not equal to] A'. Assign vertices codes of A and A' in two groups (a) [(a, b), (1, 2, 3, 4, 5, 6)] and (b) [(a, b), (1, 2, 3, 4, 5, 6)].

Step 3. Calculate NVS(a), NVS(b), and their vertex codes of two ECMs with the same CE, respectively, as follows:

NVS (a) = [([v.sub.a], [v.sub.b]), ([v.sub.5], [v.sub.4], [v.sub.2], [v.sub.6], [v.sub.1], [v.sub.3])] = [(0.2084, 0.2056), (0.743, 0.2727, 0.2348, 0.2347, 0.2023, 0.1995)], NVS (b) = [([v.sub.b], [v.sub.c]), ([v.sub.6], [v.sub.4], [v.sub.5], [v.sub.1], [v.sub.3], [v.sub.2])] = [(0.2084, 0.2056), (0.743, 0.2727, 0.2348, 0.2347, 0.2023, 0.1995)]. (18)

Compare NVS(a) and NVS(b) and equivalence can be seen. So the node voltages in two vertex code groups are all distinct; go to Step 4.

Step 4. Take the NVS(a), NVS(b), and their vertex codes to determine the corresponding vertices of two WDCCGs as follows: (a-b, b-a, 1-3, 2-5, 3-2, 4-4, 5-6, 6-1).

Step 5. According to the corresponding vertices obtained and the vertex codes to form new WAM [A'.sub.1], rewrite WAM A'. Then, we have A = [A'.sub.1] so they are isomorphic and program stops.

Example 3. Two 6-gear train kinematic chains are depicted in Figures 11(a) and 11(b) and their corresponding WDCCGs are described in Figures 11(c) and 11(d), respectively. The direct process to determine isomorphism of these two kinematic chains is as follows.

Step 1. Input their corresponding vertex codes and WAMs A, A' as follows:

[mathematical expression not reproducible]. (19)

Step 2. Evidently, A [not equal to] A'. Assign vertices codes of A and A' in two groups (a) [(a, c), (1, 2, 3, 4, 5, 6, 7)] and (b) [(a, c), (1, 2, 3, 4, 5, 6, 7)].

Step 3. Calculate NVS(a), NVS(b), and their vertex codes of two ECMs with the same CE, respectively, as follows:

NVS (a) = [([v.sub.b], [v.sub.a]), ([v.sub.7], [v.sub.5], [v.sub.6], [v.sub.1], [v.sub.4], [v.sub.3], [v.sub.2])] = [(0.2591, 0.2547), (0.3784, 0.2515, 0.2511, 0.2309, 0.2122, 0.2029, 0.1961)],

NVS (b) = [([v.sub.b], [v.sub.a]), ([v.sub.7], [v.sub.6], [v.sub.5], [v.sub.1], [v.sub.4], [v.sub.3], [v.sub.2])] = [(0.3156, 0.2607), (0.3940, 0.2601, 0.2551, 0.2394, 0.2367, 0.2110, 0.2001)]. (20)

Compare NVS(al) and NVS(b) and equivalence cannot be seen. So it is determined that they are not isomorphic and program stops.

Example 4. Two 9-gear train kinematic chains are shown in Figures 12(a) and 12(b). Their corresponding WDCCGs are depicted in Figures 12(c) and 12(d), respectively. The direct process to determine isomorphism of these two kinematic chains is as follows.

Step 1. Input their corresponding WAMs A and A', as follows:

[mathematical expression not reproducible]. (21)

Step 2. Evidently, A [not equal to] A'. Assign vertices codes of A and A' in two groups (a) [(a, b, c), (1, 2, 3, 4, 5, 6, 7, 8, 9)] and (b) [(a, b, c), (1, 2, 3, 4, 5, 6, 7, 8, 9)].

Step 3. Calculate NVS(a), NVS(b), and their vertex codes of two ECMs with the same CE, respectively, as follows:

[mathematical expression not reproducible]. (22)

Compare NVS(a) and NVS(b) and equivalence can be seen. And the node voltages in two vertex code groups are not all distinct, so go to Step 6.

Step 4. The vertices (1, 2) in Figure 12(a), vertices (6, 7) in Figure 12(b), the vertices (5,7) in Figure 12(a), and vertices (1, 2) in Figure 12(b) have the same values in the corresponding groups, so just adjust the position order of the vertices in A' to obtain a new adjacency matrix A'. And the corresponding vertices of two WDCCGs are (1-6, 2-7, 3-5, 4-8, 5-1, 6-4, 7-2, 8-3, 9-9, a-a, b-c, c-b) so we have A = [A'.sub.1]. It is determined that they are isomorphic and program stops.

5. Algorithm Complexity Analysis

This paper presents a relatively good algorithm for determination of kinematic chains isomorphism with multiple joint and gear train. It is feasible for introducing the WDCCG and WAM; to describe these two types of kinematic chains, they dramatically reduce the number of vertices and order of corresponding adjacency matrix A.

The analysis of computational complexity of this isomorphic identification algorithm is as follows: when there are no equivalent node voltages in NVS, time consumption is basically dedicated to solving the linear equation sets. If a kinematic chain possesses n vertices, the order of the node voltage equations is n - 1. Since the adjoint circuit is a linear resistance circuit, the node voltage equations form a linear algebra equation set of orders n - 1, which has a computational complexity of O([(n - 1).sup.3]) for its solution. Since it needs to solve at most 2n adjoint circuits in our proposed method, the computational complexity is of order O(2n[(n - 1).sup.3]) < O([n.sup.4]). Thus, the proposed method has a computational complexity of a polynomial order. When there are equivalent node voltages in NVS, the correspondence of only a part of the vertices cannot be determined. Thus, in the worst situation, the proposed method is more efficient than those where row/column exchanges are performed blindly.

In this paper, this algorithm is tested and compared with the internationally recognized faster method for planar simple joint kinematic chains isomorphic identification [20], and they are tested in the same software and hardware environment. The test results are shown in Figure 13 (the average time of each vertex is 20 times of the kinematic chain with multiple joints); test results show that when the vertex of the kinematic chain is increased, the algorithm proposed in this paper is more efficient than the algorithm proposed by He et al. The proposed algorithm by us is very suitable for the isomorphism of the topological graph of kinematic chains, and the algorithm is very efficient at the same time.

6. Conclusions

In this paper, an algorithm for topological isomorphism identification of planar multiple joint and gear train kinematic chains is introduced.

Firstly, a weighted-double-color-contracted-graph (WDCCG) and a weighted adjacency matrix (WAM) are introduced to describe the planar multiple joint and gear train kinematic chains, respectively. They dramatically reduce the number of vertices and order of the represented adjacency matrix.

Secondly, isomorphism identification method of these two types of kinematic chains is carried out by the equivalent circuit models (ECMs) of WDCCGs with the same complete excitation (CE) and then uses the solved node voltage sequence (NVS) to determine the corresponding vertices of two WDCCGs.

Finally, an algorithm to identify isomorphic kinematic chains is obtained. It is an efficient and easy method to be realized by computer. And this algorithm also can be used in the isomorphism identification of planar simple joint kinematic chains with minor changes.

Notations A, A': The incidence matrix of kinematic chain [d.sub.ij]: The elements of incidence matrix [G.sub.i]: Conductance value of edge in the ECM [m.sub.ijk]: The weighted value of kth edge N, N': Variable of equivalent circuit model n: The number of vertices in WDCCG [n.sub.i]: Node i in the ECM [v.sub.i]: Node voltages of the node i CE: Complete excitation DCG: Double color graph ECM: Equivalent circuit model NVS: Node voltage sequence TM: Topological model WAM: Weighted adjacency matrix WDCCG: Weighted double color contracted graph.

http://dx.doi.org/10.1155/2016/5310582

Competing Interests

The authors declare that they have no competing interests.

Acknowledgments

This work is supported by the Science and Technology Project of Quanzhou City, 2014G48 and G20140047.

References

[1] J. J. Uicker Jr. and A. Raicu, "A method for the identification and recognition of equivalence of kinematic chains," Mechanism and Machine Theory, vol. 10, no. 5, pp. 375-383, 1975.

[2] H. S. Yan and A. S. Hall, "Linkage characteristic polynomials: definitions, coefficients by inspection," Journal of Mechanical Design, vol. 103, no. 3, pp. 578-584, 1981.

[3] H. S. Yan and A. S. Hall, "Linkage characteristic polynomials: assembly theorems, uniqueness," Journal of Mechanical Design, vol. 104, no. 1, pp. 11-20, 1982.

[4] T. S. Mruthyunjaya, "A computerized methodology for structural synthesis of kinematic chains. Part 1. Formulation," Mechanism and Machine Theory, vol. 19, no. 6, pp. 487-495, 1984.

[5] T. S. Mruthyunjaya, "A computerized methodology for structural synthesis of kinematic chains: part 2--application to several fully or partially known cases," Mechanism and Machine Theory, vol. 19, no. 6, pp. 497-505, 1984.

[6] T. S. Mruthyunjaya, "A computerized methodology for structural synthesis of kinematic chains: part 3--application to the new case of 10-link, three- freedom chains," Mechanism and Machine Theory, vol. 19, no. 6, pp. 507-530, 1984.

[7] T. S. Mruthyunjaya and H. R. Balasubramanian, "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, 1987.

[8] W. J. Sohn and F. Freudenstein, "An application of dual graphs to the automatic generation of the kinematic structures of mechanisms," Journal of Mechanisms, Transmissions, and Automation, vol. 108, no. 3, pp. 392-398, 1986.

[9] A. Ambekar and V. Agrawal, "On canonical numbering of kinematic chains and isomorphism problem: MAX code," in Proceedings of the ASME Mechanisms Conference, pp. 1615-1622, 1986.

[10] A. G. Ambekar and V P. Agrawal, "Canonical numbering of kinematic chains and isomorphism problem: min code," Mechanism and Machine Theory, vol. 22, no. 5, pp. 453-461, 1987.

[11] C. S. Tang and T. Liu, "Degree code; a new mechanism identifier," Journal of Mechanical Design, vol. 115, no. 3, pp. 627-630, 1993.

[12] J. K. Shin and S. Krishnamurty, "On identification and canonical numbering of pin jointed kinematic chains," Journal of Mechanical Design, vol. 116, pp. 182-188, 1994.

[13] J. K. Shin and S. Krishnamurty, "Development of a standard code for colored graphs and its application to kinematic chains," Journal of Mechanical Design, vol. 116, no. 1, pp. 189-196, 1994.

[14] A. C. Rao and D. Varada Raju, "Application of the hamming number technique to detect isomorphism among kinematic chains and inversions," Mechanism and Machine Theory, vol. 26, no. 1, pp. 55-75, 1991.

[15] A. C. Rao and C. N. Rao, "Loop based pseudo hamming values-1. Testing isomorphism and rating kinematic chains," Mechanism and Machine Theory, vol. 28, no. 1, pp. 113-127, 1992.

[16] A. C. Rao and C. N. Rao, "Loop based pseudo hamming values-II inversions, preferred frames and actuators," Mechanism and Machine Theory, vol. 28, no. 1, pp. 129-143, 1993.

[17] J.-K. Chu and W.-Q. Cao, "Identification of isomorphism among kinematic chains and inversions using link's adjacent-chain-table," Mechanism and Machine Theory, vol. 29, no. 1, pp. 53-58, 1994.

[18] A. C. Rao, "Application of fuzzy logic for the study of isomorphism, inversions, symmetry, parallelism and mobility in kinematic chains," Mechanism and Machine Theory, vol. 35, no. 8, pp. 1103-1116, 2000.

[19] P. R. He, W. J. Zhang, Q. Li, and F. X. Wu, "A new method for detection of graph isomorphism based on the quadratic form," Journal of Mechanical Design, vol. 125, no. 3, pp. 640-642, 2003.

[20] P. R. He, W. J. Zhang, and Q. Li, "Some further development on the eigensystem approach for graph isomorphism detection," Journal of the Franklin Institute, vol. 342, no. 6, pp. 657-673, 2005.

[21] Z. Y. Chang, C. Zhang, Y. H. Yang, and Y. Wang, "A new method to mechanism kinematic chain isomorphism identification," Mechanism and Machine Theory, vol. 37, no. 4, pp. 411-417, 2002.

[22] J. P. Cubillo and J. B. Wan, "Comments on mechanism kinematic chain isomorphism identification using adjacent matrices," Mechanism and Machine Theory, vol. 40, no. 2, pp. 131-139, 2005.

[23] H. F. Ding and Z. Huang, "A unique representation of the kinematic chain and the atlas database," Mechanism and Machine Theory, vol. 42, no. 6, pp. 637-651, 2007.

[24] H. F. Ding and Z. Huang, "A new theory for the topological structure analysis of kinematic chains and its applications," Mechanism and Machine Theory, vol. 42, no. 10, pp. 1264-1279, 2007.

[25] A. C. Rao, "A genetic algorithm for topological characteristics of kinematic chains," Journal of Mechanical Design, vol. 122, no. 2, pp. 228-231, 2000.

[26] F. G. Kong, Q. Li, and W. J. Zhang, "An artificial neural network approach to mechanism kinematic chain isomorphism identification," Mechanism and Machine Theory, vol. 34, no. 2, pp. 271-283, 1999.

[27] J. K. Chu, The Structural and Dimensional Characteristics of Planar Linkages, Press of Beihang University of China, Beijing, China, 1992.

[28] L. Song, J. Yang, X. Zhang, and W. Q. Cao, "Spanning tree method of identifying isomorphism and topological symmetry to planar kinematic chain with multiple joint," Chinese Journal of Mechanical Engineering, vol. 14, no. 1, pp. 27-31, 2001.

[29] J. G. Liu and D. J. Yu, "Representations & isomorphism identification of planar kinematic chains with multiple joints based on the converted adjacent matrix," Chinese Journal of Mechanical Engineering, vol. 48, pp. 15-21, 2012.

[30] R. Ravisankar and T. S. Mruthyunjaya, "Computerized synthesis of the structure of geared kinematic chains," Mechanism and Machine Theory, vol. 20, no. 5, pp. 367-387, 1985.

[31] J. U. Kim and B. M. Kwak, "Application of edge permutation group to structural synthesis of epicyclic gear trains," Mechanism and Machine Theory, vol. 25, no. 5, pp. 563-573, 1990.

[32] G. Chatterjee and L.-W. Tsai, "Computer-aided sketching of epicyclic-type automatic transmission gear trains," Journal of Mechanical Design, vol. 118, no. 3, pp. 405-411, 1996.

[33] V. V. N. R. Prasadraju and A. C. Rao, "A new technique based on loops to investigate displacement isomorphism in planetary gear trains," Journal of Mechanical Design, vol. 12, pp. 666-675, 2002.

Quanzhou Institute of Equipment Manufacturing, Haixi Institutes, Chinese Academy of Science, Quanzhou 362200, China

Correspondence should be addressed to Yanhuo Zou; zouyh@fjirsm.ac.cn

Received 21 September 2015; Revised 4 February 2016; Accepted 1 March 2016

Academic Editor: Ibrahim Zeid

Caption: Figure 1: The structural of simple joint and multiple joint.

Caption: Figure 2: A multiple joint kinematic chain and its TM described.

Caption: Figure 3: A gear train kinematic chain and its TM described.

Caption: Figure 4: Two multiple joint kinematic chains and their WDCCG.

Caption: Figure 5: ECM corresponding to two WDCCGs of Figures 4(c) and 4(d), respectively.

Caption: Figure 6: An ECM with 4 nodes and its CE by reference node 5.

Caption: Figure 7: Two ECMs with the same CE, respectively.

Caption: Figure 8: Two gear train kinematic chains and their WDCCGs.

Caption: Figure 9: Two 10-link multiple joint kinematic chains and their WDCCGs.

Caption: Figure 10: Two 11-link multiple joint kinematic chains and their WDCCGs.

Caption: Figure 11: Two 6-gear train kinematic chains and their WDCCG.

Caption: Figure 12: Two 9-gear train kinematic chains and their WDCCGs.

Caption: Figure 13: The test results of the algorithm proposed in this paper and the algorithm proposed by He et al.

Table 1: Node voltages of two ECMs with the same CE. Vertex type Hollow vertex Solid vertex Figure 5(a) Vertex code a b 1 2 3 Node voltage 0.1627 0.1691 0.1839 0.1691 0.1537 Figure 5(b) Vertex code a b 1 2 3 Node voltage 0.1691 0.1627 0.1691 0.1537 0.1839

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Zou, Yanhuo; He, Peng |

Publication: | Mathematical Problems in Engineering |

Date: | Jan 1, 2016 |

Words: | 6207 |

Previous Article: | Parameter Identification Method for SINS Initial Alignment under Inertial Frame. |

Next Article: | Bearing-Only Formation Control for Cascade Multirobots. |

Topics: |