A New Algorithm for Unique Representation and Isomorphism Detection of Planar Kinematic Chains with Simple and Multiple Joints

Abstract

In this work, a new algorithm is proposed for a unique representation for simple and multiple joint planar kinematic chains (KCs) having any degree of freedom (DOF). This unique representation of KCs enhances the isomorphism detection during the structural synthesis process of KCs. First, a new concept of joint degree is generated for all joints of a given KC based on joint configuration. Then, a unified loop array (ULA) is obtained for each independent loop. Finally, a unified chain matrix (UCM) is established as a unique representation for a KC. Three examples are presented to illustrate the proposed algorithm procedures and to test its validity. The algorithm is applied to get a UCM for planar KCs having 7–10 links. As a result, a complete atlas database is introduced for 7–10-link non-isomorphic KCs with simple or/and multiple joints and their corresponding unified chain matrix.

1. Introduction

The structural synthesis of kinematic chains (KCs) usually starts with an enumeration of all candidates of KCs. During that, KCs should be represented in such a way to facilitate the synthesis process. The structural representation of KCs may be classified into graphical or numerical methods. Then, isomorphism detection is to be performed to exclude isomorphic KCs. Consequently, many techniques are available for isomorphism detection in KCs with either simple or multiple joints.

The matrix representation for the structural synthesis of both single and two degrees of freedom of simple-jointed chains was used by Mruthyunjaya and Balasubramanian [1,2,3]. They also used the characteristic polynomial of the degree matrix of the corresponding graph to detect the isomorphism of simple-jointed KCs up to 10 links with one, two and three degrees of freedom (DOF). Jin-Kui and Wei-Qing [4] proposed the concept of a link’s adjacent-chain table to detect the topological relationships between links and isomorphism in KCs. Summation polynomials for isomorphism detection in single freedom and multi-DOF planar KCs were introduced by Shende and Rao [5]. A computer-aided method, based on the concept of multiplicity distance, was presented by Yadav et al. [6] for detecting isomorphism among planar binary KCs. Rao et al. [7,8] used fuzzy logic and chain loop string to investigate isomorphism among planar KCs with simple joints. The concept of eigenvalues and eigenvectors of an adjacent matrix was developed for the detection of graph isomorphism [9,10,11].

A stratified representation to enumerate planar simple-jointed KCs that does not require isomorphism testing on the final set of KCs was proposed by Butcher and Hartman [12]. Pucheta and Cardona [13] offered a systematic technique to find topological alternatives for certain kinematic problems based on graph theory, the initial graph concept and a combinatorial analysis in a non-isomorphic way. New two basic loop operations for the topological structure analysis of KCs and isomorphism identification were proposed by Huafeng Ding and Huang [14,15,16]. New concepts of the perimeter loop, maximum perimeter degree sequence, perimeter topological graph and canonical perimeter graph were presented for isomorphism identification of KCs. Hasan and Khan [17] used a weighted physical connectivity matrix (WPCM) and characteristic polynomial to detect distinct mechanisms in all types of simple-jointed one DOF planar KCs up to ten links. Dargar et al. [18,19] proposed the first adjacency chain link string [FACLS] and the second adjacency chain link string [SACLS] as a composite identification number of KCs of single or multi-DOF with simple or multiple joints. Then extended adjacency link value (EALV) and link total loop size (TLS) were developed to detect distinct mechanisms of simple-jointed KCs. Galán-Marín et al. [20] designed a multivalued neural network to enable a simplified formulation of the graph isomorphism problem.

A technique of adding sub-chains to get the identification code and formation code of a topological structure was presented by Deng et al. [21]. Then, isomorphic structures could be eliminated according to the certain DOF and link-joining properties of planar closed-chain mechanisms. Ding et al. [22,23,24,25] established a whole atlas database of two DOF 11-link KCs and one DOF planar KCs with 6, 8, 10, 12 and 14 links. The concept of bicolor graphs in graph theory was adopted to represent the topological structures of multiple-joint KCs, and a characteristic number of strings was proposed to detect isomorphism. The whole families of multiple-joint KCs with up to 16 links were synthesized. A new method using incident matrices was developed by Yang et al. [26] to identify the isomorphism of topological graphs. Rizvi et al. [27,28,29] used a unique chain code based on the degree of links as an identifier of a KC to detect isomorphism in all types of KCs of single or multi-DOF with simple joints. Then, a fuzzy similarity index was proposed to identify isomorphism in planer KCs. Moreover, some tests were presented for KCs of one DOF, with 8, 9 and 10 links having two DOF. The link identification number (LIN) and chain identification number (CIN) were obtained from adjacency matrices of KCs for isomorphism detection. Ping Yang [30,31,32] proposed a Dividing and Matching Algorithm (DMA) and a hybrid immune genetic algorithm model for the isomorphism identification in KCs.

A loop analysis was investigated by Pozhbelko [33] to obtain a unified structure theory for open, closed and mixed KCs with simple and multiple joints. Ding et al. [34,35] used contracted graphs to synthesize the whole set of planar non-fractionated KCs with up to six independent loops. Characteristic codes of topological graphs of KCs were presented to increase the efficiency of isomorphism identification. By transforming multiple links into multiple joints, planar non-fractionated KCs with two multiple joints were generated from KCs with one multiple joint. Therefore, a family of planar KCs with two multiple joints was established. Venkata et al. [36] suggested “net distance” to test isomorphism in planar KCs and geared KCs. This technique was applied to 8, 10 and 12-link KCs with one DOF and 15-link KCs with four DOF. Eleashy [37] proposed the Joint Sorting Code (JSC) and Kinematic Chain Structural Matrix (KCSM) to solve the problem of isomorphism in planar eight-bar KCs with up to three prismatic pairs. Yang et al. [38] presented a vertex degree and edge weight as a reliable method for the synthesis and isomorphism detection of KCs with prismatic pairs. Therefore, revolute-prismatic (RP) chains with 6–14 links were established.

The concepts of link connectivity number and entropy neglecting tolerance and clearance were proposed by Rai and Punjabi [39,40] for detecting isomorphism among simple-joint KCs of single and multi-DOF. Then, a maximum binary code was presented based on links labeling to detect isomorphism in simple and multiple-joint KCs and epicyclic gear trains with 4–6 links. A molecular topological index was proposed by Deng et al. [41] to identify isomers in KCs as used in organic chemistry. Therefore, the adjacency identification index, which fits for the isomorphism detection of KCs, was detected. This method was applied to all 230 ten-bar one DOF KCs. Li et al. [42] used a combinatorial graph to represent geared linkage kinematic chains (GLKCs). Then, the powers of a combinatorial matrix were used to detect isomorphism in GLKCs. Chu. et al. [43,44] introduced a new representation for mechanisms using a double color graph (DCG) that was applied for the structural synthesis of planar 10-link three DOF simple and multiple-joint KCs.

From the above literature, isomorphism detection is still a challenge in the mechanism synthesis process. Graphical and numerical techniques were investigated. The best of these techniques include complicated mathematical concepts based on link-adjacency matrices or their modifications. In this work, a simple method is presented for the unique representation of KCs that facilitate isomorphism detection among KCs. This paper will be discussed in four main parts: (1) basic definitions, (2) algorithm procedures, (3) examples to validate the algorithm and (4) results and conclusion.

2. Basic Definitions

Definition 1.

Topological structure of KCs: a schematic representation of KCs that include (1) the number and type of joints. (2) Number and type of links (such as binary, ternary, quaternary or quinary links). (3) Connection relations among these joints and links, as shown in Figure 1. These KCs may have open or closed loops. Topological graphs of KCs can be categorized into planar and nonplanar graphs. A planar graph can be drawn in the plane without edge crossing, whereas a nonplanar graph contains at least one edge crossing [45]. In this work, the KCs of planar graphs with closed loops were considered, as shown in Figure 1.

Definition 2.

Simple and Multiple joints: a simple joint is formed when two links are connected together. As shown in Figure 1, joints a–c,e–j) are simple joints. Multiple joints are formed when more than two links are connected together. Joint (d) in Figure 1 is a multiple joint that connects three binary links—namely, links 3–5.

Definition 3.

Independent loop: any closed path through a KC in which no link or joint is encountered more than once. Moreover, an independent loop should not contain internal loops or link crossing. For the KC shown in Figure 1, loop (1) is formed by the connection of links (1, 2, 3, 5, 7 and 9). In other words, loop (1) is formed by joints (b–d,h–j) So that, loop of a KC represents the connectivity among its links.

Definition 4.

Loop Joint size: number of simple or multiple joints forming a loop in a KC. For the KC shown in Figure 1, loop (1) has six joints.

3. Proposed Algorithm Steps

The proposed method for the generation of a unique representation of a KC depends on (1) the number of independent loops that form a KC and (2) the joint configuration. The algorithm can be summarized in the following steps:

Step 1 Modified Link Assortment Array (LAA):

Number and type of links forming a KC with specified DOF are defined as a link assortment [46]. The modified link assortment array (LAA) of a N-link KC with any -DOF KC is given by:

LAA = [N, NB, NT, NQ, NP]

where N, N_B, N_T, N_Q and N_P are the number of total, binary, ternary, quaternary and quinary links in the KC, respectively.

Step 2 Joint Assortment Array (JAA)

Type and number of joints connecting different links in a KC are defined as a joint assortment array [47]. The joint assortment array (JAA) of an N-link KC with any DOF is given by:

JAA = [J_t, S, M]

where J_t, S and M are the total number of joints, number of simple joints and number of multiple joints in the KC, respectively.

Definition 5.

Degree of Freedom (F) of a planar KC: describes the relation between F (DOF), N (number of links) and J (number of simple joints). Therefore, referring to the Grübler equation, the DOF is given by [48].

F = 3(N − 1) − 2

Step 3 Independent loop

Definition 6.

Independent loop: the inner loop of a KC inside which there is no other closed loop. Planar KCs satisfy the equation

2 L = N − F − 1

where: L, N and F are, respectively, the number of independent loops, number of links and number of DOF [44]. For most planar KCs, independent loops can be determined by visual inspection. Each independent loop must contain at least one joint that does not appear in other loops. However, each joint must appear in at least one of the independent loops. The number of independent loops is a significant factor in KC representation, as it indicates the number of rows in the generated matrix illustrated in step 7.

Step 4 Joint Degree (JD)

Joints between links in a KC may be simple or multiple. The joint symbol can be detected according to type of connected link at this joint.

Definition 7.

Joint Symbol: an abbreviation code derived from the first letters of links types that are connected at the considered joint.

Definition 8.

Joint Degree (JD): a numerical value for each joint in a KC that can be generated based on joint type and its connectivity.

Table 1. Joint degree (JD) for simple and multiple joints according to their connectivity.

Simple Joints			Multiple Joints (3-Links)			Multiple Joints (4-Links)
Connected Links	Joint Symbol	Joint Degree (JD)	Connected Links	Joint Symbol	Joint Degree (JD)	Connected Links	Joint Symbol	Joint Degree (JD)
binary–binary	bb	1	binary–binary–binary	bbb	11	binary–binary–binary–binary	bbbb	20
binary–ternary	bt	2	binary–binary–ternary	bbt	12	binary–binary–binary–ternary	bbbt	21
binary–quaternary	bq	3	binary–ternary–ternary	btt	13	binary–binary–binary–quaternary	bbbq	22
ternary–ternary	tt	4	ternary–ternary–ternary	ttt	14	binary–binary–ternary–ternary	bbtt	23
ternary–quaternary	tq	5	binary–binary–quaternary	bbq	15	binary–binary–ternary–quaternary	bbtq	24
quaternary–quaternary	qq	6	binary–ternary–quaternary	btq	16	binary–binary–quaternary–quaternary	bbqq	25
binary–pentagonal	bp	7	binary–quaternary–quaternary	bqq	17	binary–ternary–ternary–ternary	bttt	26
ternary–pentagonal	Tp	8	ternary–quaternary–quaternary	tqq	18	binary–ternary–ternary–quaternary	bttq	27
quaternary–pentagonal	qp	9	quaternary–quaternary–quaternary	qqq	19	ternary–ternary–ternary–ternary	tttt	28
pentagonal–pentagonal	pp	10				ternary–ternary–ternary–quaternary	tttq	29

indicates joint degrees for simple and multiple joints with the most commonly used types of connection. Hence, all joints in the considered KC can be defined by their degrees. As illustrated in Table 1, joints are classified into simple and multiple joints formed by three links and multiple ones formed by four links.

For the KC shown in Figure 1, the loops (1 and 2) can be analyzed to generate their joint symbols and joint degrees. This will be based on the values of joint degrees (JD) extracted from Table 1, as shown in Figure 2.

Step 5 Joint Degree Array (JDA):

Definition 9.

Joint Degree Array (JDA): is an initial array for a certain loop in a KC. The elements of JDA are represented by joint degrees of joints forming the considered loop. Therefore, Joint Degree Array (JDA) for a loop-i that has joints (a, b, c, d, …) is given by:

JDA (i) = [JD _a, JD _b, JD _c, ……]

Joint degrees sequence in JDA is usually in a clockwise direction starting from any joint degree. Therefore, the same loop may have more than one JDA depending on the starting joint. For loop (1) in KC shown in Figure 2, JDA can be expressed as [11,1,2,2,3,3] starting from joint “d” or [2,2,3,3,11,1] starting from joint “b”, etc. However, the arrangement of joint degrees inside the array must be unified to ensure that a similar loop must generate the same array.

Step 6 Unified Loop Array (ULA):

In order to enhance the reliability of the joint degree array, it is important to have a unified loop joint degree array regardless the starting joint. In other words, each loop should have a unique array. A MATLAB code [49] was established to rearrange the elements of the joint degree array to start from a specific joint degree and continue in a specific loop direction. This arrangement depends on the concept of the “master joint” and “neighbor joint”, as described below.

Definition 10.

Master joint: a joint that has the least joint degree (JD) in a certain loop. Generally, each loop may contain single master joint or multiple master joints.

Case 1: Single master joint:

For a given loop, all joint degrees can be determined according to the Table 1. If there is a single master joint, a unified loop array, “ULA” can be generated as follows:

• Select the master joint in the given loop.
• Compare joint degrees of the 1st neighbor joints on both sides of the master joint and select the least value.
• ULA starts from the master joint and continues in the direction of the selected neighbor joint. In Figure 3a, the shown loop has a single master joint of JD = 1. The least 1st neighbor joint has JD = 3. Therefore, the given loop has ULA = [1 3 5 3 2 3 2 4].
• If the 1st neighbor joint degrees are similar, then compare between the 2nd neighbor joints. Therefore, the ULA will be continued in direction of the least 2nd neighbor joint degree starting from the master joint. In Figure 3b, the given loop has ULA = [1 3 2 3 2 3 4 3].
• If the 2nd neighbor joint degree is similar, then compare between the 3rd neighbor joints and so on. Then, “ULA” will be continued in direction of the least 3rd neighbor joint degree starting from the master joint. In Figure 3c, the given loop has ULA = [1 3 2 3 2 4 2 3].

Case 2: Multiple master joints

For a given loop, all joint degrees can be determined according to Table 1. In this case, multiple master joints can be detected in the same loop so that the ULA can be generated as follows:

• Check each master joint for its 1st-neighbor joint degrees.
• If there is one master joint that has the least 1st-neighbor joint degree, then the ULA for this loop will be continued in direction of that least 1st-neighbor joint degree starting from its associated master joint. In Figure 4, the given loop has a master joint of JD = 2 (indicated by yellow in Figure 4), and its 1st-neighbor joint has JD = 3, which is the least value of joint degrees among all 1st-neighbor joints for all master joints. Hence, ULA = [2 3 4 4 2 5].
• If the least 1st-neighbor joint degrees are equal in all master joints, check each master joint for its 2nd-neighbor joint degree and select the least 2nd-neighbor joint degree. Hence, the ULA will be continued in the direction of the least 2nd-neighbor joint degree starting from its associated master joint, indicated by yellow in Figure 5, therefore, the given loop has ULA = [2 3 3 4 2 3 4 5].
• If the least 2nd-neighbor joint degrees are equal in all master joints, check each master joint for its 3rd-neighbor joint degree and select the least 3rd-neighbor joint degree. Hence, the ULA will be continued in direction of the least 3rd-neighbor joint degree starting from its associated master joint, indicated by yellow in Figure 6, therefore, the given loop has ULA = [2 3 2 4 3 4 2 5].
• If there exist multiple consequent master joints, check the 1st-neighbor joint degree of the first and last master joints. If they are equal, check the 2nd-neighbor joint degree for the first and the last master joints. Therefore, the ULA will be continued in the direction of the least neighbor joint degree starting from the outmost master joint. As shown in Figure 7a, the given loop has ULA = [2 2 2 4 3 4 2 5].
• If all joints in a certain loop are master joints, then the ULA will start from any joint degree and continue in a clockwise direction. As shown in Figure 7b, the given loop has ULA = [2 2 2 2 2 2 2 2].

Moreover, all previous steps are included in the developed MATLAB code to obtain the unified loop array for a given loop. General rules for both cases of single and multiple master joints, as illustrated in Figure 8, are utilized to establish the MATLAB code, as shown in Algorithms 1 and 2.

Algorithm 1. Code structure for determining the unified loop array, ULA, for single master joints.

L = [J2, J4, J7, J1, J5,…….] // initial loop array M = min (J2, J4, J7, J1, J5,……….) Mid array = [b4, b3, b2, b1, M, a1, a2, a3, a4] case: a1 < b1, ULA = [M,a1,a2,a3,……b1] case: b1 < a1; ULA = [M,b1,b2,b3,……,a1] case: a1 = b1, case: a2 < b2; ULA = [M,a1,a2,……,b1] case: b2 < a2; ULA = [M,b1,b2,……,a1] case a2 = b2; case: a3 < b3; ULA = [M,a1,a2,………,b1] case: b3 < a3; ULA = [M,b1,b2,………, a1] case: a3 = b3; case: a4 < b4; ULA = [M,a1,a2,………,b1] case: b4 < a4; ULA = [M,b1,b2,………, a1] case: a4 = b4; ULA = [M,a1,a2,………,b1] or ULA = [M,b1,b2,………, a1]

Algorithm 2. Code structure for determining the unified loop array, ULA, for multiple master joints.

L = [J2, J4, J7, J1, J5,…….] // initial loop array Mo = min (J2, J4, J7, J1, J5,……….) Mo = X, Y, Z X: Xmin = min (Xa1, Xb1) Y: Ymin = min (Ya1, Yb1) Z: Zmin = min (Za1, Zb1) M = min (Xmin, Ymin, Zmin)

case: M = Xmin, Xmin = Xb1; ULA = [X, Xb1, Xb2,……Xa1] case: M = Ymin; Ymin = Ya1; ULA = [Y, Ya1, Ya2,……, Yb1] case: M = Zmin; Zmin = Zb1; ULA = [Z, Zb1, Zb2,……, Za1] case: M = Xmin = Xb1 & M = Ymin = Ya1; case: Xb2 < Ya2; ULA = [X, Xb1,Xb2,…… Xa1] case: Ya2 < Xb2; ULA = [Y, Ya1, Ya2,……Yb1] case: Xb2 = Ya2; case: Xb3 < Ya3; ULA = [X, Xb1,Xb2,……,Xa1] case: Ya3 < Xb3; ULA = [Y, Ya1, Ya2,……,Yb1] case: Xb3 = Ya3; ULA = [X, Xb1,Xb2,……,Xa1] or, ULA = [Y, Ya1, Ya2,……,Yb1]

Step 7 Unified chain matrix (UCM)

After generating the ULA for all loops, the whole chain can be represented by the unified chain matrix.

Definition 11.

Unified chain matrix: a unique V × K matrix representing a given KC where V is the number of loops forming the considered KC, and K is the number of joints in the largest loop size.

However, the first row represents the ULA for the 1st loop, and the second row represents the ULA for the 2nd loop, etc. Any missing elements are represented as zero elements in the unified chain matrix.

$$UnifiedChainMatrix=\left[\begin{array}{c}ULA for 1st loop\\ ULA for 2nd loop\\ \dots \\ \dots \\ ULA for loop V\end{array}\right]$$

Using the unified chain matrix, a complete atlas database is established for planar 7, 8, 9 and 10-links KCs with simple and multiple joints (given in Appendix A).

Step 8 Isomorphism Detection

Isomorphism detection is the most important step in the structural synthesis of KCs. Isomorphic KCs are structurally identical chains that should be detected so as not to duplicate the enumeration or synthesis results. A reliable isomorphism detection process can be carried out using the UCM.

Definition 12.

Isomorphic KCs: Two KCs are said to be isomorphic if each row in the UCM of the first KC has a corresponding row in the UCM of the second KC, regardless of the row’s order.

Therefore, the previous algorithm can be applied to any planar KC. Different configurations of a KC should generate the same UCM. In other words, all configurations are isomorphic KCs.

4. Algorithm Validation Tests

In this section, some examples are given to illustrate the algorithm clearly with more detail and to test its validity. The selected examples present KCs with different DOF and different types of joints, either simple or multiple.

4.1. Example One: 11-Link KCs of Two DOF with Simple Joints

Consider a pair of 11-link simple-joint KCs with two DOF, shown in Figure 9a,b.

The link assortment array (LAA) and joint assortment array (JAA) for KCs shown in Figure 9a,b are illustrated in

Table 2. Link Assortment Array and Joint Assortment Array for kinematic chains in Figure 9.

Kinematic Chain (a)			Kinematic Chain (b)
Total links	11	LAA = [11 1 4 6 ]	11	LAA = [11 1 4 6 ]
Quaternary links	1		1
Ternary links	4		4
Binary links	6		6
Total Joints	14	JAA = [14 14 0]	14	JAA = [14 14 0]
Simple joints	14		14
Multiple joints	0		0
DOF		2		2

.

The joint degree for all joints of each KC can be determined according to Table 1 based on the joint type and its associated connected links. The joint degrees for the KCs shown in Figure 9a,b are listed in

Table 3. Values of Joint degrees for kinematic chains in Figure 9a,b.

	Kinematic Chain (a)			Kinematic Chain (b)
Joint	Joint Symbol	Joint Degree	Joint	Joint Symbol	Joint Degree
a	bt	2	a	bq	3
b	bt	2	b	tq	5
c	tq	5	c	bt	2
d	tq	5	d	bt	2
e	bt	2	e	bt	2
f	bt	2	f	bt	2
g	bt	2	g	bt	2
h	bt	2	h	bq	3
i	bt	2	i	tq	5
j	bq	3	j	bt	2
k	tq	5	k	bt	2
l	bt	2	l	bt	2
m	bt	2	m	bt	2
n	bb	1	n	bt	2

. Furthermore, Figure 9 illustrates all the joint labels and their corresponding joint degrees.

The number of independent loops for each KC is IL = J − N + 1 = 14 − 11 + 1 = 4. Therefore, there are four independent loops besides the peripheral loop. Hence, both KCs have five loops. The joint degrees are then detected for each loop. However, the initial joint degree array (JDA) for each loop can be obtained. Then, the unified loop array (ULA) for each loop is generated, as shown in

Table 4. Unified Loop Array for KC in Figure 9a,b.

Kinematic Chain (a)													Kinematic Chain (b)
Loop	No. of Joints												Loop	No. of Joints
loop 1	5	joints	m	n	a	b	l						loop 1	4	joints	e	c	d	f
		Symbol	bt	bb	bt	bt	bt								Symbol	bt	bt	bt	bt
		Joint Degree	2	1	2	2	2								Joint Degree	2	2	2	2
	Unified Loop Array		1	2	2	2	2	0	0	0	0	0		Unified Loop Array		2	2	2	2	0	0	0	0	0	0
loop 2	4	joints	b	l	k	c							loop 2	5	joints	f	d	bt	h	g
		Symbol	bt	bt	tq	tq									Symbol	bt	bt	tq	bq	bt
		Joint Degree	2	2	5	5									Joint Degree	2	2	5	3	2
	Unified Loop Array		2	2	5	5	0	0	0	0	0	0		Unified Loop Array		2	2	2	3	5	0	0	0	0	0
loop 3	5	joints	d	f	h	i	j						loop 3	5	joints	i	j	m	n	a
		Symbol	tq	bt	bt	bt	bq								Symbol	tq	bt	bt	bt	bq
		Joint Degree	5	2	2	2	3								Joint Degree	5	2	2	2	3
	Unified Loop Array		2	2	2	3	5	0	0	0	0	0		Unified Loop Array		2	2	2	3	5	0	0	0	0	0
loop 4	4	joints	e	g	h	f							loop 4	4	joints	l	m	j	k
		Symbol	bt	bt	bt	bt									Symbol	bt	bt	bt	bt
		Joint Degree	2	2	2	2									Joint Degree	2	2	2	2
	Unified Loop Array		2	2	2	2	0	0	0	0	0	0		Unified Loop Array		2	2	2	2	0	0	0	0	0	0
loop 5	10	joints	a	c	d	e	g	i	j	k	m	n	loop 5	10	joints	h	i	k	l	n	a	b	c	e	g
		Symbol	bt	tq	tq	bt	bt	bt	bq	tq	bt	bb			Symbol	bq	tq	bt	bt	bt	bq	tq	bt	bt	bt
		Joint Degree	2	5	5	2	2	2	3	5	2	1			Joint Degree	3	5	2	2	2	3	5	2	2	2
	Unified Loop Array		1	2	5	3	2	2	2	5	5	2		Unified Loop Array		2	2	2	3	5	2	2	2	3	5

Master joint.

, using the MATLAB code.

The unified chain matrix for each KC is derived as shown in Figure 10. However, there is no complete correspondence in both matrices. Therefore, the two KCs in Figure 9a,b are not isomorphic.

4.2. Example Two: Eight-Link KCs of One DOF with Two Multiple Joints

Consider a pair of eight-link KCs of one DOF with one multiple joint, shown in Figure 11a,b.

The link assortment array (LAA) and joint assortment array (JAA) for the KCs shown in Figure 11a,b are illustrated in

Table 5. Link Assortment Array and Joint Assortment Array for kinematic chains in Figure 11a,b.

Kinematic Chain (a)			Kinematic Chain (b)
Total links	8	LAA = [8 0 2 6 ]	8	LAA = [8 0 2 6 ]
Quaternary links	0		0
Ternary links	2		2
Binary links	6		6
Total Joints	8	JAA = [8 6 2]	8	JAA = [8 6 2]
Simple joints	6		6
Multiple joints	2		2
DOF		1		1

.

The joint degree for all joints of each KC can be determined according to Table 1 based on the joint type and its associated connected links. The joint degrees for the KCs shown in Figure 11a,b are listed in

Table 6. Values of Joint degrees for kinematic chains in Figure 11a,b.

	Kinematic chain (a)			Kinematic chain (b)
Joint	Joint Symbol	Joint Degree	Joint	Joint Symbol	Joint Degree
a	bbb	11	a	bt	2
b	bt	2	b	tt	4
c	bt	2	c	bt	2
d	bt	2	d	bbb	11
e	bt	2	e	bb	1
f	bb	1	f	bbt	12
g	bbt	12	g	bt	2
h	bt	2	h	bb	1

. Furthermore, Figure 11 illustrates all the joint labels and their corresponding joint degrees.

The number of independent loops for each KC is IL = J − N + 1 = 10 − 8 + 1 = 3. Therefore, there are three independent loops besides the peripheral loop. Hence, both KCs have four loops. The joint degrees are then detected for each loop. However, the initial joint degree array (JDA) for each loop can be obtained. Then, the unified joint array (ULA) for each loop is generated, as shown in

Table 7. Unified Joint Degree Array for KCs in Figure 11a,b.

Kinematic Chain (a)									Kinematic Chain (b)
Loop	No. of Joints								Loop	No. of Joints
loop 1	4	joints	a	b	h	g			loop 1	4	joints	e	a	f	d
		Symbol	bbb	bt	bt	bbt					Symbol	bb	bt	bbt	bbb
		Joint Degree	11	2	2	12					Joint Degree	1	2	12	11
	Unified Loop Array		2	2	11	12	0	0		Unified Loop Array		1	2	12	11	0
loop 2	4	joints	a	g	e	f			loop 2	5	joints	d	c	g	h	f
		Symbol	bbb	bbt	bt	bb					Symbol	bbb	bt	bt	bb	bbt
		Joint Degree	11	12	2	1					Joint Degree	11	2	2	1	12
	Unified Loop Array		1	2	12	11	0	0		Unified Loop Array		1	2	2	11	12
loop 3	4	joints	g	d	c	h			loop 3	4	joints	f	h	g	b
		Symbol	bbt	bt	bt	bt					Symbol	bbt	bb	bt	tt
		Joint Degree	12	2	2	2	0	0			Joint Degree	12	1	2	4
	Unified Loop Array		2	2	2	12	0	0		Unified Loop Array		1	2	4	12	0
loop 4	6	joints	a	b	c	d	e	f	loop 4	5	joints	e	a	b	c	d
		Symbol	bbb	bt	bt	bt	bt	bb			Symbol	bb	bt	tt	bt	bbb
		Joint Degree	11	2	2	2	2	1			Joint Degree	1	2	4	2	11
	Unified Loop Array		1	2	2	2	2	11		Unified Loop Array		1	2	4	2	11

Master joint.

.

The unified chain matrix for each KC is derived as shown in Figure 12. However, there is no complete correspondence in both matrices. Therefore, the two KCs in Figure 11a,b are not isomorphic.

4.3. Example Three: 15-Link KCs of Four DOF with Simple Joints

Consider a pair of 15-link simple joints KCs with four DOF, shown in Figure 13a,b.

The link assortment array (LAA) and joint assortment array (JAA) for the KCs shown in Figure 13a,b are illustrated in

Table 8. Link Assortment Array and Joint Assortment Array for kinematic chains in Figure 13.

Kinematic Chain (a)			Kinematic Chain (b)
Total links	15	LAA = [15 0 8 7 ]	15	LAA = [18 0 8 7 ]
Quaternary links	0		0
Ternary links	8		8
Binary links	7		7
Total Joints	19	JAA = [19 19 0]	19	JAA = [19 19 0]
Simple joints	19		19
Multible joints	0		0
DOF		4		4

. Furthermore, Figure 13 illustrates all the joint labels and their corresponding joint degrees.

The joint degree for all joints of each KC can be determined according to Table 1 based on the joint type and its associated connected links. The joint degrees for the KCs shown in Figure 13a,b are listed in

Table 9. Values of Joint degrees for kinematic chains in Figure 13a,b.

	Kinematic Chain (a)			Kinematic Chain (b)
Joint	Joint Symbol	Joint Degree	Joint	Joint Symbol	Joint Degree
a	bt	2	a	bt	2
b	bb	1	b	bb	1
c	bt	2	c	bt	2
d	tt	4	d	tt	4
e	tt	4	e	tt	4
f	bt	2	f	bt	2
g	bt	2	g	bt	2
h	bt	2	h	bt	2
i	bt	2	i	bt	2
j	tt	4	j	bt	2
k	tt	4	k	tt	4
l	tt	4	l	bt	2
m	bt	2	m	bt	2
n	bt	2	n	tt	4
o	bt	2	o	tt	4
p	bt	2	p	bt	2
q	tt	4	q	bt	2
r	bt	2	r	tt	4
s	bt	2	s	bt	2

. Furthermore, Figure 13 illustrates all the joint labels and their corresponding joint degrees.

The number of independent loops for each KC is IL = J − N + 1 = 19 − 15 + 1 = 5. Therefore, there are five independent loops besides the peripheral loop. Hence, both KCs have six loops. The joint degrees are then calculated for each loop. However, the initial joint degree array (JDA) for each loop can be obtained. Then, the unified joint array (ULA) for each loop is generated, as shown in

Table 10. Unified Loop Array for KCs in Figure 13a,b.

Kinematic Chain (a)													Kinematic Chain (b)
Loop	No. of Joints												Loop	No. of Joints
loop 1	5	joints	a	bt	c	l	k						loop 1	5	joints	a	b	c	n	o
		Symbol	bt	bb	bt	tt	tt								Symbol	bt	bb	bt	tt	tt
		Joint Degree	2	1	2	4	4								Joint Degree	2	1	2	4	4
	Unified Loop Array		1	2	4	4	2	0	0	0	0	0		Unified Loop Array		1	2	4	4	2	0	0	0	0	0
loop 2	4	joints	m	n	j	k							loop 2	10	joints	s	q	p	n	d	m	l	j	i	h
		Symbol	bt	bt	tt	tt									Symbol	bt	bt	bt	tt	tt	bt	bt	bt	bt	bt
		Joint Degree	2	2	4	4									Joint Degree	2	2	2	4	4	2	2	2	2	2
	Unified Loop Array		2	2	4	4	0	0	0	0	0	0		Unified Loop Array		2	2	2	2	2	2	2	2	4	4
loop 3	10	joints	i	h	o	p	r	s	d	l	m	n	loop 3	4	joints	r	o	p	q
		Symbol	bt	bt	bt	bt	bt	bt	tt	tt	bt	bt			Symbol	tt	tt	bt	bt
		Joint Degree	2	2	2	2	2	2	4	4	2	2			Joint Degree	4	4	2	2
	Unified Loop Array		2	2	2	2	2	2	2	2	4	4		Unified Loop Array		2	2	4	4	0	0	0	0	0	0
loop 4	4	joints	s	r	q	e							loop 4	5	joints	g	i	j	k	f
		Symbol	bt	bt	tt	tt									Symbol	bt	bt	bt	tt	bt
		Joint Degree	2	2	4	4									Joint Degree	2	2	2	4	2
	Unified Loop Array		2	2	4	4	0	0	0	0	0	0		Unified Loop Array		2	2	2	2	4	0	0	0	0	0
loop 5	5	joints	o	g	f	q	p						loop 5	4	joints	l	m	e	k
		Symbol	bt	bt	bt	tt	bt								Symbol	bt	bt	tt	tt
		Joint Degree	2	2	2	4	2								Joint Degree	2	2	4	4
	Unified Loop Array		2	2	2	2	4	0	0	0	0	0		Unified Loop Array		2	2	4	4	0	0	0	0	0	0
loop 6	10	joints	a	b	c	d	e	f	g	h	i	j	loop 6	10	joints	d	e	f	g	h	s	r	a	b	c
		Symbol	bt	bb	bt	tt	tt	bt	bt	bt	bt	tt			Symbol	tt	tt	bt	bt	bt	bt	tt	bt	bb	bt
		Joint Degree	2	1	2	4	4	2	2	2	2	4			Joint Degree	4	4	2	2	2	2	4	2	1	2
	Unified Loop Array		1	2	4	2	2	2	2	4	4	2		Unified Loop Array		1	2	4	2	2	2	2	4	4	2

Master joint.

.

The unified chain matrix for each KC is generated as shown in Figure 14. However, each row in the unified joint degree matrix of Figure 14a has a corresponding row in the unified joint degree of Figure 14b. Therefore, the two KCs in Figure 13 are isomorphic.

5. Results

The proposed algorithm was successfully applied to detect isomorphic KCs during the structural synthesis of the mechanisms. Two or more KCs are said to be isomorphic if they have the same UCM. For any planar KC with single or multiple DOF, a unified chain matrix can be obtained based on the independent loop and unified loop array. The ULA are generated for each independent loop based on the joint degree concept using the developed MATLAB code. The proposed method was applied to the most common planar KCs of 7–10 links with simple or multiple joints. As a result, a complete atlas for 7–10 links of KCs and their corresponding UCM was constructed up to five independent loops. The selected types of KCs are various in DOF and a number of multiple joints to ensure the algorithm validity. Almost all of the presented KCs have no edge crossing that facilitate independent loop detection. Three examples were presented for the generation of the unified chain matrix and isomorphism detection in 8, 11 and 15-link KCs. The examples and constructed atlas verified that using the UCM is a simple and effective tool in the isomorphism detection process. The developed atlas is presented in Figure A1, Figure A2, Figure A3, Figure A4, Figure A5, Figure A6, Figure A7 and Figure A8 (given in Appendix A). The detailed results are listed below:

◾

18 eight links of one DOF KCs with two multiple joints

◾

22 eight links of one DOF KCs with one multiple joint

◾

five seven links of two DOF KCs with one and two multiple joints

◾

40 nine links of two DOF KCs with simple joints

◾

four seven links of two DOF KCs with simple joints

◾

83 nine links of two DOF KCs with one multiple joint

◾

16 eight links of one DOF KCs with simple joints

◾

219 ten links of one DOF KCs (without edge crossing) with simple joints

6. Conclusions

A new method to represent planar KCs was developed in this paper. The joint degree (JD) was introduced to represent all joints in a KC. Then, a MATLAB code was established to obtain the unified loop array (ULA) for each independent loop. Therefore, a unified chain matrix was generated to represent the considered KC. The proposed method was successfully tested for all KCs up to five independent loops. This algorithm was applied to planar KCs having single or multiple DOF with either simple or multiple joints. A complete atlas database was introduced for non-isomorphic 7, 8, 9 and 10-link KCs with simple or/and multiple joints with their corresponding UCM. Furthermore, isomorphic KCs can be easily identified using UCM. Some examples were presented for isomorphism detection in planar KCs. It was proven that the proposed method is a reliable approach to represent and detect isomorphism among KCs having closed planar graphs without edge crossing. In future works, KCs with edge crossing should be investigated. The proposed algorithm can also be extended to be applied for geared and spatial KCs. A MATLAB graphical user interface may be developed, including all algorithm steps, to facilitate the input and output data for users.