01.12.2020  Original Article  Ausgabe 1/2020 Open Access
A Computational Synthesis Approach of Mechanical Conceptual Design Based on Graph Theory and Polynomial Operation
 Zeitschrift:
 Chinese Journal of Mechanical Engineering > Ausgabe 1/2020
1 Introduction
As an early and the most creative phase of engineering design, the basic task of conceptual design is developing and synthesizing the building blocks to generate meaningful concept solutions that meet design requirements. In all the feasible design candidates, the optimal and novel one is pursued in this design phase. However, because of the limitation of bias and shorten of knowledge or experienced to the designers, it is always difficult to identify all the feasible design candidates and furthermore to find out the optimal one in them. Therefore, numerous researchers have focused their study on the computer aided design synthesis, and many models and approaches have been developed.
Based on physical working principles, Kota proposed a FunctionStructure model and implemented it in the design of hydraulic systems [
1]. Besides, a matrix methodology to the design synthesis was developed by him and Chiou on the basis of that model [
2,
3]. Another two famous models are FunctionBehaviorStructure and FunctionBehaviorState [
4–
6]. The common character of these functional models is that they describe objects or design problems and solutions in terms of their known functions, and regard the design process as a function decomposition process. Therefore, the associated synthesis approaches are socalled functionbased synthesis [
7–
11]. There exist other kinds of synthesis approaches, e.g., the grammarbased synthesis [
12–
16] and the graphbased synthesis [
17–
21]. In grammarbased synthesis, the generative grammars, which are a class of production systems that capture design knowledge by defining a vocabulary and ruleset, are constructed and used to generate design alternatives [
22]. In graphbased synthesis, the graph theory is used to represent a product and define the relationships between its components, and the graph concepts and theorems are employed to generate design candidates [
23]. For now, graphbased synthesis approaches have been widely used in the synthesis, analysis and optimization process of linkage systems [
24–
26] and epicyclic gear trains [
27,
28]. Moreover, Bin proposed a computational conceptual design synthesis model based on space matrix [
29], and he also integrated the functional synthesis of mechanisms with mechanical efficiency and cost to find out the optimal solution [
30,
31]. Similarly, Masakazu proposed an integrated optimization for supporting functional and layout designs during conceptual design phase [
32].
Anzeige
With the help of above considerable researches, the paper proposes a novel and more computable synthesis approach of mechanisms. The advantage of this approach is that it builds up the mathematical structure of the design synthesis of mechanisms based on graph theory, and makes the design candidates are calculated by the induced polynomial operation formulas. Besides, each design candidate is finally represented by a matrix form, which will be conducive to the analysis and optimization of the design candidates in the future research. The rest of the paper is outlined as follows. Section
2 describes some basic concepts of the graph theory that will be used in the proposed synthesis approach. Section
3 builds up the graph framework of the synthesis approach. The polynomial operations including the polynomialwalk operation, edge sequence operation and vertex sequence operation are presented in Section
4. The computational flowchart of the synthesis approach is summarized in Section
5. In Section
6, the proposed synthesis approach is applied to figure out all the feasible design candidates of a mechanical system. Some concluding remarks are made in Section
7.
2 Basic Concepts on the Used Graph Theory
As a branch of mathematics, graph theory has gotten numerous applications in many fields of engineering for its ability to concisely represent and handle the relationships between different objects. In this section, some fundamental concepts of graph theory that are essential for the paper proposed synthesis approach are introduced briefly. The detailed descriptions of these concepts can be found in Ref. [
33].
The mathematical structure of a directed graph or digraph
D, as illustrated in Figure
1(a), is an ordered triple
\(\left( {V(D),E(D),\varPsi_{D} } \right)\). Where
V(
D) is a nonempty set of vertices, e.g., {
V
_{1},
V
_{2},
V
_{3},
V
_{4}},
E(
D) is a set of edges, e.g., {
e
_{1},
e
_{2},
e
_{3},
e
_{4},
e
_{5},
e
_{6}}, that disjoints from
V(
D), and
\(\psi_{D}\) is an incidence function that assigns every edge
e an initial vertex
init(
e) and a terminal vertex
ter(
e). The edge
e is said to be directed from
init(
e) to
ter(
e), e.g., the direction of
e
_{1} is from
init(
e
_{1})
=
V
_{1} to
ter(
e
_{1})
=
V
_{2}. Usually, an edge is always written as a twotuple style, e.g., the twotuple of
e
_{3} is
e
_{3}(
V
_{1},
V
_{4}).
×
In a digraph, if the vertices of several edges are the same, such edges are called
multiple edges, e.g.,
e
_{5} and
e
_{6}; if an edge whose initial vertex
init(
e) equals to its terminal vertex
ter(
e), such edge is called a
loop, e.g.,
e
_{2}. A directed walk
W in
D is a finite nonnull sequence, e.g.,
W
= (
V
_{1},
e
_{3},
V
_{4},
e
_{6},
V
_{3},
e
_{5},
V
_{4},
e
_{6},
V
_{3},
e
_{4},
V
_{2}), whose terms are alternately vertices and edges. A walk is called a path if all the vertices and edges are distinct, e.g.,
P
= (
V
_{1},
e
_{3},
V
_{4},
e
_{6},
V
_{3}), and the length of it is the number of edges between the starting and ending vertices. A path of
D is also a subgraph of
D, for all its vertices and edges contained in
D.
Anzeige
The topological structure, or in other words the connection relationships between vertices, can be conveniently represented in matrix form. A vertextovertex adjacency matrix to a digraph is defined as
\(A(D) = [a_{ij} ]\), where
\(a_{ij} = \mu (V_{i} ,V_{j} )\) is the number of directededges whose
init(
e) =
V
_{i} and
ter(
e)
=
V
_{j}, e.g., Figure
1(b). Let
A
^{k}(
D) be the
kth power of
A(
D), where
k is a positive integer number. Then an adjacency matrix theorem can be described as follows.
Adjacency Matrix Theorem: The number of walks of length n from vertex
V
_{i} to vertex
V
_{j} in a digraph
D is given by the (
i,
j) element of
A
^{n} (
D).
For example, the third power of
A(
D) in Figure
1(b) is
\(A^{3} (D) = \left[ {\begin{array}{*{20}c} 0 & 2 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ \end{array} } \right]\).
Then, the number of walks of length 3 from
V
_{1} to
V
_{2} is
A
^{3}(
D)(1, 2) = 2, and they are
W
_{1} = (
V
_{1},
e
_{1},
V
_{2},
e
_{2},
V
_{2},
e
_{2},
V
_{2}) and
W
_{2} = (
V
_{1},
e
_{3},
V
_{4},
e
_{6},
V
_{3},
e
_{4},
V
_{2}).
3 Graph Framework
3.1 Kinematic Function Unit
A mechanical system, which is made up by variety mechanisms, is designed to transform the power or motion from the system input to the system output. Therefore, each mechanism has the function of transferring and transforming the power or motion that pass through it. In this paper, the function representation of a mechanism is called a kinematic function unit (KFU). It has four fundamental features: (1) structure type (crankrocker, spur gear, etc.), (2) motional type (rotation, translation or swing), (3) continuous or intermittent motion, (4) reciprocating motion or not. The relationship between a specific mechanism and the KFU belonging to it is onetoone or onetomany, for the kinematic transformation between the input and output members of a specific mechanism may be interchangeable.
For example, if the crank is the driving member in a slidercrank mechanism displayed in Figure
2(a), the slidercrank is able to transform the crank’s continuous rotational motion into the slider’s reciprocating translational motion. While, if slider is the driving member, the slidercrank is able to transform the slider’s reciprocating translational motion into the crank’s continuous rotational motion. Therefore, the slidercrank mechanism has two different KFUs. To describe these KFUs in a general way and make it easy to be applied and recognized in computer, a general mathematical structure of KFU is given by
where
\(C_{i}^{F}\) is the identification of a KFU, and it includes three different symbols, i.e.,
C,
F,
i, that have diverse values and meanings. The value of
C is the abbreviation for the name of a mechanism to which KFU is subordinate, e.g.,
SC in Figure
2(b) is the abbreviation of slidercrank. The value of
F is the motional transformation type of a KFU, e.g.,
F
=
RT in Figure
2(b) represents a rotational motion is transformed into a translational motion, while
F
=
TR represents a translational motion is transformed into a rotational motion. The value of
i is a positive number and represents the serial number of a KFU in a design candidate generated through the synthesis process, in case a KFU is used more than once in that solution. The initial value of it to all KFUs are set to 1. MI and MO are two 1 × 3 row vectors and represent the input and output motions of the KFU respectively. The elements
x1,
x2 and
x3 of these vectors are encoded symbols or numerals, and the encoded values and meanings of them are illustrated in Table
1.
$$KFU = \{ C_{i}^{F} ,MI,MO\} ,$$
(1)
Table 1
Meanings and coded values to the elements
x1,
x2 and
x3 of vectors MI and MO
Elements

Meanings

Coded values


x1

Rotational motion

R

Translational motion

T


Swinging motion

S


x2

Continuous motion

1

Intermittent motion

−1


x3

Reciprocating motion

1

Nonreciprocating motion

−1

×
3.2 Kinematic Link Graph
The kinematic link graph (KLG) is a directed graph and constructed by looking each KFU as a vertex and the kinematic relationship between two KFUs as an edge. Through KLG, the synthesis problem of mechanisms are transformed from mechanical domain into graph domain, so that the feasible design candidates can be represented and calculated by the methods and theorems of graph theory.
When building a KLG, the first task is to extract KFUs from mechanisms. Table
2 illustrates
eight KFUs from
seven mechanisms. Here, the input and output of a mechanism system are abstracted as two virtual mechanisms that named as “System Input” and “System Output” respectively. Specially, it should be noticed that “System Input” only has the function to send out the power or motion, while “System Output” only has the function to incept power or motion. Thus, the values of MI of “System Input” as well as the values of MO of “System Output” are set to (0, 0, 0). Since the input and output motions of a mechanism system are various according to different design requirements, the KFUs of them illustrated in Table
2 are only for a simple instance.
Table 2
Eight KFUs from seven mechanisms
Mechanisms

KFUs


Crankrocker

\(\{ CR_{1}^{RS} ,(R,1,  1),(S,1,1)\}\)

\(\{ CR_{1}^{SR} ,(S,1,1),(R,1,  1)\}\)


Spur gear

\(\{ SG_{1}^{RR} ,(R,1,  1),(R,1,  1)\}\)

Geneva wheel

\(\{ GW_{1}^{RR} ,(R,1,  1),(R,  1,  1)\}\)

Camfollower

\(\{ CF_{1}^{RT} ,(R,1,  1),(T,1,1)\}\)

PawlRatchet wheel

\(\{ PRW_{1}^{SR} ,(S,1,1),(R,  1,  1)\}\)

System input

\(\{ SI_{1}^{R} ,(0,0,0),(R,1,  1)\}\)

System output

\(\{ SO_{1}^{R} ,(R,  1,  1),(0,0,0)\}\)

The second task when building a KLG is to establish the rules about how the KFUs connect with each other to form the directed edges. Here, two connection rules are defined and presented below.
Connection Rule 1: If one KFU’s MO is equal to another KFU’s MI, a directed edge will be formed between them and the direction is from former to latter.
Connection Rule 2: If a KFU’MI is equal to its MO, a directed loop will be formed around it.
Based on the KFUs illustrated in Table
2 and the two connection rules, a kinematiclink graph is built and named as KLG(T2) as Figure
3 shows. The labels of vertices in KLG(T2) are the identifications of the corresponding KFUs. Specially, the vertices that represent the KFUs of “System Input” and “System Output” in a KLG are called
inputvertex (e.g.,
\(SI_{1}^{R}\)) and
outputvertex (e.g.,
\(SO_{1}^{R}\)), respectively. To distinguish them with other vertices, they are marked by “
” in KLG(T2).
×
3.3 Graph Representation of Design Candidate
There are two different graph representations of design candidate, i.e., the walk representation and the path representation. They have different application backgrounds and meanings in the synthesis process.
3.3.1 Walk Representation
The walk representation adopts the vertex sequence and edge sequence of a walk to represent the mechanisms and their kinematic relationships in a design candidate. This kind of representation is mainly used in the calculation part of synthesis process.
The walk representation directly derives from KLG, for each walk whose head is inputvertex and tail is outputvertex in a KLG can be looked as a design candidate. For instance, Figure
4(a) displays a walk in KLG(T2) and the design candidate it represents is shown in Figure
4(b). Basically, the constitute of a walk can be divided into four parts: (I) vertex terms (VT), (II) edge terms (ET), (III) vertex sequence (VS), and (IV) edge sequence (ES). Where, VT and ET are two unordered sets that made up by the vertices and edges of a walk respectively, while VS and ES are the ordered sets of VT and ET respectively. Thus, the mathematical model of walk representation is defined as
$$W = \{ VS(W),ES(W)\} .$$
(2)
×
Figure
4(c) shows the VS(W) and ES(W) of the walk W in Figure
4(a). In a walk, the terms adjacent to one edge are two vertices, and these two vertices are exactly the initial vertex and terminal vertex of that edge. Thus, once the ET and ES of a walk are specified, the VT and VS of that walk are determined. Based on this, the key issues of the proposed computational synthesis approach is to compute the ET and ES of the walks whose head is inputvertex and tail is outputvertex in a KLG firstly, and then figure out their VT and VS.
3.3.2 Path Representation
The path representation is used as the final storage representation of a design candidate, and it is transformed by the walk representation. The transformation relationship between them is onetoone. Since a path is a subgraph of the graph it belongs to, it can be described by an adjacency matrix. Therefore, the general mathematical model of path representation to a design candidate is defined as
where
VS
^{P}(
W) is the vertex sequence of the path representation and it is generated by recoding the subscript index of the vertex who is used more than once in the VS of corresponding walk representation. Figure
4(d) shows the path representation of Figure
4(c). Here, the vertex
\(SG_{1}^{RR}\) is used twice in VS(
W), so the second
\(SG_{1}^{RR}\) is recoded into
\(SG_{2}^{RR}\) in
VS
^{P}(
W).
A
^{P}(
W) is the adjacency matrix of the path representation. This matrix representation is very helpful to analysis, optimize and furthermore to find out the optimal solution in the design candidates generated through the synthesis process in the future research. That is why the path representation is more suitable than the walk representation to be the final storage representation.
$$P(W) = \{ VS^{P} (W),A^{P} (W)\},$$
(3)
3.4 Weight Matrix Theorem
The weighted matrix theorem is a theorem to determine the ET of a walk with the aid of weighted graph and weighted matrix. In graph theory, the weighted graph, which exerts a weighted value on each edge of it, has a wide application in many practical problems. The forms of weighted value are arbitrary according to the practical problem, such as numerals, functions, symbols, etc. The weighted matrix
\(A_{\omega } = [a_{ij} ]\) is an extension of adjacency matrix to describe the weighted graph in a matrix way. Here, the elements
a
_{ij} are the weighted values of the corresponding edges.
Let edge labels
\(e_{i} (i = 1,2, \ldots ,16)\) be the weighted values of
KLG(
T2) in Figure
3. Then,
KLG(
T2) becomes a weighted graph and its weighted matrix is
$$A_{\omega } (KLG(T2)) = \left[ {\begin{array}{*{20}c} 0 & {e_{1} } & {e_{2} } & 0 & {e_{3} } & 0 & {e_{4} } & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & {e_{5} } \\ 0 & 0 & 0 & {e_{6} } & 0 & {e_{7} } & 0 & 0 \\ 0 & {e_{8} } & {e_{9} } & 0 & {e_{10} } & 0 & {e_{11} } & 0 \\ 0 & {e_{12} } & {e_{13} } & 0 & {e_{14} } & 0 & {e_{15} } & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & {e_{16} } \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right].$$
It is an 8 × 8 symbolic matrix, where its rows and columns are associated with the vertices of
KLG(
T2), e.g., the first row and first column are associated with the vertex
\(SI_{1}^{R}\), while the last (8th) row and last column are associated with the vertex
\(SO_{1}^{R}\). As mentioned above, the adjacency matrix theorem gives a way to determine the number of walks of length
k from one vertex to another in a directed graph. Based on it, a weighted matrix theorem is defined as follows.
Weighted Matrix Theorem: The edge terms(ET) of walks of length
k from vertex
V
_{i} to vertex
V
_{j} in a weighted graph
G
_{w}, who regards the edge labels as the weighted values of each edge, are given by the (
i,
j) element of
\(A_{\omega }^{k} (G_{w} )\).
Let
W(
k,
V
_{i},
V
_{j}) be the walks of length
k from
V
_{i} to
V
_{j} in
G
_{w}. Based on mathematical inductive method, the theorem can be proved as follows:
Proofs
When
k = 1, the edge term of
W(1,
V
_{i},
V
_{j}) is the edge
e(
V
_{i},
V
_{j}). Thus, the theorem is definitely correct according to the definition of weighted matrix. Let
\(a_{i,j}^{k  1}\) and
\(a_{i,j}^{k}\) be the (
i,
j) elements of
\(A_{\omega }^{k  1} (G_{w} )\) and
\(A_{\omega }^{k} (G_{w} )\) respectively. Assuming that the edge terms (ET) of
W(
k −1,
V
_{i},
V
_{j}) are given by
\(a_{i,j}^{k  1}\). Since
\(A_{\omega }^{k} (G_{w} ) = A_{\omega }^{k  1} (G_{w} )A_{\omega }\),
where
N
_{v} is the dimension of the weighted matrix and equals to the number of vertices of
G
_{w}. As we known, each
W(
k,
V
_{i},
V
_{j}) is constructed by connecting an edge
e(
V
_{m},
V
_{j}) with
W(
k − 1,
V
_{i},
V
_{m}). In Eq. (
4), the value of
a
_{m,j} is 0 or the edge label of
e(
V
_{m},
V
_{j}), while the value of
\(a_{i,m}^{k  1}\) is 0 or a polynomial that made up by one or several monomials. Based on the assumption,
\(\sum\nolimits_{m = 1}^{{N_{v} }} {a_{i,m}^{k  1} }\) is the ET to all the walks of
W(
k − 1,
V
_{i},
V
_{m}). Thus, Eq. (
4) can be looked as the polynomial operation to construct
W(
k,
V
_{i},
V
_{j}), and
\(a_{i,j}^{k}\) is the ET to all the walks of
W(
k,
V
_{i},
V
_{j}).
$$a_{i,j}^{k} = \left( {\sum\limits_{m = 1}^{{N_{v} }} {a_{i,m}^{k  1} } } \right) \cdot a_{m,j} ,$$
(4)
In Eq. (
4), the value of
\(a_{i,j}^{k}\) is also 0 or a polynomial. When
\(a_{i,j}^{k}\) is 0, there is not a walk of length
k from
V
_{i} to
V
_{j} in the weighted graph. When
\(a_{i,j}^{k}\) is a polynomial, the alphabetic items of each monomial of it are the ET of a walk of
W(
k,
V
_{i},
V
_{j}) in the weighted graph. For example, the (1,8) element of
\(A_{\omega }^{4} (KLG(T2))\) is
$$a_{1,8}^{4} = e_{2} e_{5} e_{6} e_{8} + e_{3} e_{5} e_{12} e_{14} + e_{3} e_{7} e_{13} e_{16}.$$
(5)
It can be found that
\(a_{1,8}^{4}\) is made up by three different monomials, and the alphabetic items of each monomial are the ET of a walk of
W(4,
V
_{1},
V
_{8}) in
KLG(
T2) as Figure
5 shows. Here,
V
_{1} =
\(SI_{1}^{R}\) and
V
_{8} =
\(SO_{1}^{R}\) as
\(A_{\omega } (KLG(T2))\) shows.
×
As mentioned above, each walk in
KLG(
T2) whose head is
inputvertex (i.e.,
\(SI_{1}^{R}\)) and tail is
outputvertex (i.e.,
\(SO_{1}^{R}\)) can be looked as a design candidate. Therefore, the three monomials in polynomial
\(a_{1,8}^{4}\) can be looked as three different design candidates. To highlight this kind of monomial and polynomial, they are named as
monomialwalk and
polynomialwalk respectively in this paper. Thus, it can be said that the synthesis process of mechanical conceptual design is transformed into polynomial operations through the weighted matrix theorem.
4 Polynomial Operations
4.1 PolynomialWalk Operation
The
polynomialwalk operation is used to calculate the ET to all the walk representations of design candidates in a
KLG. Based on the weighted matrix theorem, a formula is given as
where
\(P_{W}^{{N_{\text{max} } }} (KLG)\) is the computed
polynomialwalk, while
\(A_{\omega } (KLG)\) is the weighted matrix of KLG.
N
_{max} is a positive number that denotes the maximum number of mechanisms a mechanical system may have without considering the virtual mechanisms of “System Input” and “System Output”. The value of it is given by the design specifications. Moreover,
m and
n are the row index or column index of
inputvertex and
outputvertex of
\(A_{\omega } (KLG)\) respectively. Thus,
a and
b are the row vector and column vector of
inputvertex and
outputvertex in
\(A_{\omega } (KLG)\) respectively.
$$\left\{ {\begin{array}{*{20}l} {P_{W}^{{N_{\text{max} } }} (KLG) = \sum\limits_{k = 2}^{{N_{\text{max} } + 1}} {aA_{\omega }^{k  2} (KLG)b} }, \hfill \\ {a = A_{\omega } (KLG)(m,:)}, \hfill \\ {b = A_{\omega } (KLG)(:,n)}, \hfill \\ \end{array} } \right.$$
(6)
For example, in the weighted matrix
\(A_{\omega } (KLG(T2))\) of
KLG(
T2),
m = 1 and
n = 8. Then,
a = (
0,
e
_{1},
e
_{2}, 0,
e
_{3}, 0,
e
_{4}, 0) and
b = (0,
e
_{5}, 0, 0, 0,
e
_{16}, 0, 0)
^{T}. Set
N
_{max} = 3, the
polynomialwalk
\(P_{W}^{3} [KLG(T2)]\) calculated by Eq. (
7) is
$$\begin{aligned} P_{W}^{3} [KLG(T_{2} )] & = e_{1} e_{5} + e_{12} e_{3} e_{5} + e_{16} e_{2} e_{7} + e_{12} e_{14} e_{3} e_{5} \hfill \\ & \quad + e_{13} e_{16} e_{3} e_{7} + e_{2} e_{5} e_{6} e_{8}. \hfill \\ \end{aligned}$$
(7)
Let
N
_{m} be the number of mechanisms in a design candidate and
N
_{e} be the number of degree to the corresponding
monomialwalk. Then,
N
_{m}
=N
_{e} − 1. Therefore, Eq. (
7) illustrates the ET to the walk representations of six feasible design candidates with the number of mechanisms of them from
N
_{m} = 1 to
N
_{m} = 3.
4.2 Edge Sequence Operation
Generally, every
monomialwalk is made up by two parts, i.e., the numeral item and the alphabetic items. In the
monomialwalks of the polynomialwalks
\(a_{1,8}^{4}\) and
\(P_{W}^{3} [KLG(T2)]\), the value of their numeral items are all equal to 1. However, sometimes the value of numeral item of a
monomialwalk may be larger than 1. For example, Figure
6(a) shows the composition of
\(M_{1}^{Kw}\), who is a
monomialwalk of the (1,8) element of
\(A_{\omega }^{8} (KLG(T2))\). Here, the value of the numeral item of
\(M_{1}^{Kw}\) is 2. As mentioned above, the alphabetic items of a
monomialwalk are the ET (edge terms) to the walk of a
KLG. However, it should be noticed that several different walks of a
KLG might have the same ET, while a walk is uniquely determined by its ES (edge sequence). It means that the ET of a
monomialwalk may be sorted into several different ES to several different walks. Since the numeral item of a
monomialwalk is generated by merging homogeneous monomials in the polynomial operation of Eq. (
5) and Eq. (
6), the value of it reveals that how many ES the ET of a
monomialwalk can be sorted.
×
In Figure
6(a), the ET of
\(M_{1}^{Kw}\) is
ET(
\(M_{1}^{Kw}\)) = {
e
_{10},
e
_{13},
e
_{16},
e
_{2},
e
_{6},
e
_{6},
e
_{7},
e
_{9}}. It can be sorted into two different edge sequences
\(ES_{1} (M_{1}^{Kw} )\) and
\(ES_{2} (M_{1}^{Kw} )\) (see Figure
6(b)) according to the connection relationship between the edges shown in Figure
6(c). In fact, Figure
6(c) is also the graph representation of two different walks in
KLG(
T2) from
\({\text{SI}}_{ 1}^{\text{R}}\) to
\({\text{SO}}_{ 1}^{\text{R}}\). Both of these two walks have the same edge terms
ET(
\(M_{1}^{Kw}\)), and
\(ES_{1} (M_{1}^{Kw} )\) and
\(ES_{2} (M_{1}^{Kw} )\) are exactly the ES of them respectively.
Based on above analysis, the key issue of edge sequence operation is how to figure out all the edge sequences of a
monomialwalk
\(M^{Kw}\), i.e.,
\(ES_{\ell } (M^{Kw} )(\ell = 1,2, \ldots ,N_{n} )\), according to its edge terms
ET(
\(M^{Kw}\)) and the connection relationship between the edges. Here,
N
_{n} is the value of numeral item of
\(M^{Kw}\).
Let
e
_{i} and
e
_{j} be any two edges in ET (
\(M^{Kw}\)), if
ter(
e
_{i}) =
init(
e
_{j}), then
e
_{i} and
e
_{j} may be adjacent in
\(ES_{\ell } (M^{Kw} )\). Besides, let
e
_{in} and
e
_{out} be the first and last edge of
\(ES_{\ell } (M^{Kw} )\) respectively, then
init(
e
_{in}) equals to the
inputvertex of KLG while
ter(
e
_{out}) equals to the outputvertex of KLG. According to above statements, an edge sequence sorting algorithm is presented below.
Edge Sequence Sorting Algorithm:
×
Here,
\(S_{k  set}^{in}\) is a set in which each item
\(s_{i,k  set}^{in}\) is an ordered set of
k edges that starting with
e
_{in}. While,
\(S_{k  set}^{out}\) is a set in which each item
\(s_{m,k  set}^{out}\) is an ordered set of
k edges that ending with
e
_{out}.
\(S_{(k + )  set}^{in}\) and
\(S_{(k + 1)  set}^{out}\) have the similar meanings with
\(S_{k  set}^{in}\) and
\(S_{k  set}^{out}\) respectively, instead that the items in them contain
k + 1 edges. The value of function
Ter() equals to the terminal vertex of the last edge in corresponding ordered set, while the value of function
Init() equals to the initial vertex of the first edge in corresponding ordered set. For example, assuming an ordered set of edges is {
e
_{2},
e
_{6},
e
_{9}}, then
Ter({
e
_{2},
e
_{6},
e
_{9}}) =
ter(
e
_{9}) =
\(CR_{1}^{RS}\) and
Init({
e
_{2},
e
_{6},
e
_{9}})=
init(e
_{2})=
\(SI_{1}^{R}\). The values of functions
First() and
Last() equal to the first edge and last edge in the corresponding ordered set respectively, e.g.,
First({
e
_{2},
e
_{6},
e
_{9}})=
e
_{2} and
Last({
e
_{2},
e
_{6},
e
_{9}})=
e
_{9}. To explain the steps of edge sequence sorting algorithm clearer,
\(M_{1}^{Kw}\) is taken as an example to show the execution process of the algorithm as illustrated in Table
3.
Table 3
Execution steps and execution results for each step of edge sequence algorithm with
\(M_{1}^{Kw}\)acting as an example
Execution steps

Results for each step

k = 1,
k + 1 = 2 < (8/2 = 4)

\(e_{in} = e_{2}\),
\(e_{out} = e_{16}\), thus
\(S_{1  set}^{in} = \{ \{ e_{2} \} \}\),
\(S_{1  set}^{out} = \{ \{ e_{16} \} \}\), then
\(S_{2  set}^{in} = \{ \{ e_{2} ,e_{6} \} ,\{ e_{2} ,e_{7} \} \}\),
\(S_{2  set}^{out} = \{ \{ e_{7} ,e_{16} \} \}\)

k = 2, (
k + 1 = 3) < (8/2 = 4)

\(S_{3  set}^{in} = \{ \{ e_{2} ,e_{6} ,e_{9} \} ,\{ e_{2} ,e_{6} ,e_{10} \} \}\),
\(S_{3  set}^{out} = \{ \{ e_{9} ,e_{7} ,e_{16} \} ,\{ e_{13} ,e_{7} ,e_{16} \} \}\)

k = 3, (
k + 1 = 4) = (8/2 = 4)

\(S_{4  set}^{in} = \{ \{ e_{2} ,e_{6} ,e_{9} ,e_{6} \} ,\{ e_{2} ,e_{6} ,e_{10} ,e_{13} \} ,\)
\(\{ e_{2} ,e_{6} ,e_{9} ,e_{7} \} \}\),
\(S_{4  set}^{out} = \{ \{ e_{6} ,e_{9} ,e_{7} ,e_{16} \} ,\{ e_{10} ,e_{13} ,e_{7} ,e_{16} \} \} .\)
Since
\(Ter(\{ e_{2} ,e_{6} ,e_{9} ,e_{6} \} ) = Init(\{ e_{10} ,e_{13} ,e_{7} ,e_{16} \} )\)
=
\(CR_{1}^{SR}\), and
\(Ter(\{ e_{2} ,e_{6} ,e_{10} ,e_{13} \} ) = Init(\{ e_{6} ,e_{9} ,e_{7} ,e_{16} \} )\) =
\(CR_{1}^{RS}\),
\(ES_{1} (M_{1}^{Kw} )\)
=
\(\{ e_{2} ,e_{6} ,e_{9} ,e_{6} \} \cup \{ e_{10} ,e_{13} ,e_{7} ,e_{16} \}\)
=
\(\{ e_{2} ,e_{6} ,e_{9} ,e_{6} ,e_{10} ,e_{13} ,e_{7} ,e_{16} \},\)
\(ES_{2} (M_{1}^{Kw} )\)
=
\(\{ e_{2} ,e_{6} ,e_{10} ,e_{13} \} \cup \{ e_{6} ,e_{9} ,e_{7} ,e_{16} \}\)
=
\(\{ e_{2} ,e_{6} ,e_{10} ,e_{13} ,e_{6} ,e_{9} ,e_{7} ,e_{16} \}\)

4.3 Vertex Sequence Operation
The relationship between the vertex sequence
\(VS_{\ell } (M^{Kw} )\) and edge sequence
\(ES_{\ell } (M^{Kw} )\) of a
monomialwalk M
^{Kw} is onetoone. Here, the task of vertex sequence operation is to figure out all the
\(VS_{\ell } (M^{Kw} )\) of
M
^{Kw} based on its
\(ES_{\ell } (M^{Kw} )\). In order to complete this task, a formula is given as
where
init(
e
_{i}) is the initial vertex of the
ithedge
e
_{i} in
\(ES_{\ell } (M^{Kw} )\), while
ter(
e
_{f}) is the terminal vertex of the final edge
e
_{f} in
\(ES_{\ell } (M^{Kw} )\).
N
_{E} is the number of edges in
\(ES_{\ell } (M^{Kw} )\). For example,
\(ES_{1} (M_{1}^{Kw} )\) and
\(ES_{2} (M_{1}^{Kw} )\) are two edge sequences of
\(M_{1}^{Kw}\) (see Figure
6(b)), and the final edge of both of them is
e
_{16}. Based on Eq. (
8), the two vertex sequences
\(VS_{1} (M_{1}^{Kw} )\) and
\(VS_{2} (M_{1}^{Kw} )\) of
\(M_{1}^{Kw}\) are
$$VS_{\ell } (M^{Kw} ) = [\bigcup\limits_{i = 1}^{{N_{E} }} {init(e_{i} )] \cup ter(e_{f} )\begin{array}{*{20}c} {} & {(e_{i} ,e_{f} \in ES_{\ell } (M^{Kw} ))}, \\ \end{array} }$$
(8)
$$\left\{ {\begin{array}{*{20}c} \begin{aligned} VS_{1} (M_{1}^{Kw} ) = \{ SI_{1}^{R} ,CR_{1}^{RS} ,CR_{1}^{SR} ,CR_{1}^{RS} ,CR_{1}^{SR} ,SG_{1}^{RR} ,CR_{1}^{RS} , \hfill \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} PRW_{1}^{SR} ,SO_{1}^{R} \}, \hfill \\ \end{aligned} \\ \begin{aligned} VS_{2} (M_{1}^{Kw} ) = \{ SI_{1}^{R} ,CR_{1}^{RS} ,CR_{1}^{SR} ,SG_{1}^{RR} ,CR_{1}^{RS} ,CR_{1}^{SR} ,CR_{1}^{RS} , \hfill \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} PRW_{1}^{SR} ,SO_{1}^{R} \}. \hfill \\ \end{aligned} \\ \end{array} } \right.$$
(9)
5 Computational Flowchart of Synthesis Approach
The proposed computational synthesis approach begins with the userspecified design requirements that including the input motion, output motion and the maximum number of mechanisms
N
_{max} in the design candidates to be generated. Then, the graph framework is built and different polynomial operations are adopted to figure out the walk representations and path representations to all the feasible design candidates. The computational flowchart of the synthesis approach is illustrated in Figure
7. To summarize and explain this figure, the steps to the computational process are:

Step 1: Set design requirements and extract KFUs from the chosen mechanisms.

Step 2: Construct KLG based on the two connection rules, and generate its vertices set V( KLG) and weighted matrix \(A_{\omega } (KLG)\) so that the KLG can be recognized and used in computer.

Step 3: Run polynomialwalk operation to compute polynomialwalk \(P_{W}^{{N_{\text{max} } }} (KLG)\), and then separate and save all its monomialwalks \(M_{i}^{Kw}\)in set \(S_{{M^{Kw} }}\).

Step 4: Run edge sequence operation for each \(M_{i}^{Kw}\) to figure out all its edge sequences \(ES_{\ell } (M_{{^{i} }}^{Kw} )\), and then save them in set S _{ES}.

Step 5: Run vertex sequence operation for each \(ES_{\ell } (M_{{^{i} }}^{Kw} )\) to figure out its vertex sequence \(VS_{\ell } (M_{{^{i} }}^{Kw} )\). Then, a walk representation \(W_{\ell }\) of \(M_{i}^{Kw}\) is formulated.

Step 6: Generated and save the vertex sequence \(VS^{P} (W_{\ell } )\) and adjacency matrix A ^{P}( \(W_{\ell }\)) to the path representation of \(W_{\ell }\).
×
6 Design Example
The task here is to figure out all the feasible design candidates of a mechanical system, who is able to transform the input continuous rotational motion into the output reciprocating translational motion, from the chosen mechanisms. The maximum number of mechanisms in the mechanical system
N
_{max} is set to 3.
6.1 Extract and Formulate the KFUs
Due to space consideration of the paper, only four kinds of mechanisms, i.e., slidercrank, worm gear, camfollower and spur gear, from the 43 identified mechanisms in Ref. [
3] are chosen as the building blocks to construct the mechanical system. The KFUs extracted from these four mechanisms and two virtual mechanisms, i.e., “System Input” and “System Output”, are illustrated in Table
4.
Table 4
Seven KFUs of the design example
Mechanisms

KFUs


Slidercrank

\(\{ SC_{1}^{RT} ,(R,1,  1),(T,1,1)\}\)

\(\{ SC_{1}^{TR} ,(T,1,1),(R,1,  1)\}\)


Spur gear

\(\{ SG_{1}^{RR} ,(R,1,  1),(R,1,  1)\}\)

Wormgear

\(\{ WG_{1}^{RR} ,(R,1,  1),(R,1,  1)\}\)

Camfollower

\(\{ CF_{1}^{RT} ,(R,1,  1),(T,1,1)\}\)

System input

\(\{ SI_{1}^{R} ,(0,0,0),(R,1,  1)\}\)

System output

\(\{ SO_{1}^{R} ,(T,1,1),(0,0,0)\}\)

6.2 Construct Kinematic Link Graph KLG
The structure of
KLG is up to the types of KFUs and their kinematic relationship. Based on Table
4, the graph representation to the
KLG of design example, i.e.,
KLG(
T4), is shown in Figure
8(a). It is a directed graph that has seven vertices and twenty edges, and the
inputvertex is
\(SI_{1}^{R}\) while the
outputvertex is
\(SO_{1}^{T}\). The vertices set
V(
KLG(
T4)) and weighted matrix
\(A_{\omega } (KLG(T4))\) of
KLG(
T4) are shown in Figure
8(b) for subsequent computing applications.
×
6.3 Compute PolynomialWalk
In the weighted matrix
\(A_{\omega } (KLG(T4))\), the row index of
\(SI_{1}^{R}\) is
m=1 while the column index of
\(SO_{1}^{T}\) is
n = 7. Then, the row vector of
\(SI_{1}^{R}\) is
a = (
0,
e
_{1},
e
_{2},
0,
e
_{3},
e
_{4},
0) while the column vector of
\(SO_{1}^{T}\) is
b = (
0,
0,
e
_{10},
0,
0,
e
_{20},
0)
^{T}. Run polynomialwalk operation and substitute the values of
m,
n,
a,
b,
N
_{max} and
\(A_{\omega } (KLG(T4))\) into Eq. (
6), the computed
polynomialwalk
\(P_{W}^{3} [KLG(T4)]\) is
$$\begin{aligned} P_{W}^{3} [KLG(T4)] = e_{2} e_{10} + e_{4} e_{20} + e_{1} e_{6} e_{10} + e_{1} e_{8} e_{20} + e_{3} e_{10} e_{16} + \hfill \\ e_{3} e_{18} e_{20} + e_{1} e_{5} e_{6} e_{10} {\kern 1pt} + e_{2} e_{9} e_{10} e_{12} + e_{1} e_{5} e_{8} e_{20} + \hfill \\ e_{1} e_{7} e_{10} e_{16} + e_{3} e_{6} e_{10} e_{15} + e_{2} e_{9} e_{14} e_{20} + e_{4} e_{10} e_{12} e_{19} + \hfill \\ e_{1} e_{7} e_{18} e_{20} + e_{3} e_{8} e_{15} e_{20} + e_{3} e_{10} e_{16} e_{17} + \hfill \\ e_{4} e_{14} e_{19} e_{20} + e_{3} e_{17} e_{18} e_{20}. \hfill \\ \end{aligned}$$
(10)
It can be found that there are 18 different
monomialwalks
\(M_{i}^{Kw} (i = 1,2, \ldots ,18)\) in
\(P_{W}^{3} [KLG(T4)]\), whose numeral item are all equal to 1. Thus, it can be said that there are a total of 18 different design candidates that are assembled by the four different mechanisms in accordance with the design requirements.
6.4 Compute the Walk Representations and Path Representations to the Design Candidates
Run edge sequence operation and vertex sequence operation for each
\(M_{i}^{Kw}\) in turn, the achieved edge sequences and vertex sequences of the walk representations to all design candidates are illustrated in Table
5, Column 3. To each walk representation, its path representation is transformed and illustrated in Table
5, Column 4. Furthermore, the design candidate that corresponds to the walk representation and path representation is displayed by a twodimensional motion sketch and illustrated in Table
5, Column 5.
Table 5
The monomialwalks, walk representations and path representations to the 18 design candidates
ID

Monomialwalks

Walk representations

Path representations

Design candidates


\(M_{1}^{Kw}\)

\(e_{2} e_{10}\)

\(W_{1} (M_{1}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{1}^{Kw} ) = \{ SI_{1}^{R} ,SC_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{1}^{Kw} ) = \{ e_{2} ,e_{10} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{1}^{Kw} )) = \{ SI_{1}^{R} ,SC_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{1}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{2}^{Kw}\)

\(e_{4} e_{20}\)

\(W_{1} (M_{2}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{2}^{Kw} ) = \{ SI_{1}^{R} ,CF_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{2}^{Kw} ) = \{ e_{4} ,e_{20} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{2}^{Kw} )) = \{ SI_{1}^{R} ,CF_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{2}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{3}^{Kw}\)

\(e_{1} e_{6} e_{10}\)

\(W_{1} (M_{3}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{3}^{Kw} ) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{3}^{Kw} ) = \{ e_{1} ,e_{6} ,e_{10} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{3}^{Kw} )) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{3}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{4}^{Kw}\)

\(e_{1} e_{8} e_{20}\)

\(W_{1} (M_{4}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{4}^{Kw} ) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,CF_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{4}^{Kw} ) = \{ e_{1} ,e_{8} ,e_{20} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{4}^{Kw} )) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,CF_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{4}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{5}^{Kw}\)

\(e_{3} e_{10} e_{16}\)

\(W_{1} (M_{5}^{Kw} ) =\left\{ {\begin{array}{*{20}l} {VS_{1} (M_{5}^{Kw} ) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{5}^{Kw} ) = \{ e_{3} ,e_{16} ,e_{10} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{5}^{Kw} )) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{5}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{6}^{Kw}\)

\(e_{3} e_{18} e_{20}\)

\(W_{1} (M_{6}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{6}^{Kw} ) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,CF_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{6}^{Kw} ) = \{ e_{3} ,e_{18} ,e_{20} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{6}^{Kw} )) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,CF_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{6}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{7}^{Kw}\)

\(e_{1} e_{5} e_{6} e_{10}\)

\(W_{1} (M_{7}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{7}^{Kw} ) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,WG_{1}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{7}^{Kw} ) = \{ e_{1} ,e_{5} ,e_{6} ,e_{10} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{7}^{Kw} )) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,WG_{2}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{7}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{8}^{Kw}\)

\(e_{2} e_{9} e_{10} e_{12}\)

\(W_{1} (M_{8}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{8}^{Kw} ) = \{ SI_{1}^{R} ,SC_{1}^{RT} ,SC_{1}^{TR} ,SC_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{8}^{Kw} ) = \{ e_{2} ,e_{9} ,e_{12} ,e_{10} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{8}^{Kw} )) = \{ SI_{1}^{R} ,SC_{1}^{RT} ,SC_{1}^{TR} ,SC_{2}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{8}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{9}^{Kw}\)

\(e_{1} e_{5} e_{8} e_{20}\)

\(W_{1} (M_{9}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{9}^{Kw} ) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,WG_{1}^{RR} ,{\kern 1pt} {\kern 1pt} CF_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{9}^{Kw} ) = \{ e_{1} ,e_{5} ,e_{8} ,e_{20} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{9}^{Kw} )) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,WG_{2}^{RR} ,CF_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{9}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{10}^{Kw}\)

\(e_{1} e_{7} e_{10} e_{16}\)

\(W_{1} (M_{10}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{10}^{Kw} ) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,SG_{1}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{10}^{Kw} ) = \{ e_{1} ,e_{7} ,e_{16} ,e_{10} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{10}^{Kw} )) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,SG_{2}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{10}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{11}^{Kw}\)

\(e_{3} e_{6} e_{10} e_{15}\)

\(W_{1} (M_{11}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{11}^{Kw} ) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,WG_{1}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{11}^{Kw} ) = \{ e_{3} ,e_{15} ,e_{6} ,e_{10} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{11}^{Kw} )) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,WG_{2}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{11}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{12}^{Kw}\)

\(e_{2} e_{9} e_{14} e_{20}\)

\(W_{1} (M_{12}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{12}^{Kw} ) = \{ SI_{1}^{R} ,SC_{1}^{RT} ,SC_{1}^{TR} ,CF_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{12}^{Kw} ) = \{ e_{2} ,e_{9} ,e_{14} ,e_{20} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{12}^{Kw} )) = \{ SI_{1}^{R} ,SC_{1}^{RT} ,SC_{1}^{TR} ,CF_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{12}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{13}^{Kw}\)

\(e_{4} e_{10} e_{12} e_{19}\)

\(W_{1} (M_{13}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{13}^{Kw} ) = \{ SI_{1}^{R} ,CF_{1}^{RT} ,SC_{1}^{TR} ,SC_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{12}^{Kw} ) = \{ e_{4} ,e_{19} ,e_{12} ,e_{10} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{13}^{Kw} )) = \{ SI_{1}^{R} ,CF_{1}^{RT} ,SC_{1}^{TR} ,SC_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{13}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{14}^{Kw}\)

\(e_{1} e_{7} e_{18} e_{20}\)

\(W_{1} (M_{14}^{Kw} ) =\left\{ {\begin{array}{*{20}l} {VS_{1} (M_{14}^{Kw} ) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,SG_{1}^{RR} ,{\kern 1pt} CF_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{14}^{Kw} ) = \{ e_{1} ,e_{7} ,e_{18} ,e_{20} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{14}^{Kw} )) = \{ SI_{1}^{R} ,WG_{1}^{RR} ,SG_{1}^{RR} ,CF_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{14}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{15}^{Kw}\)

\(e_{3} e_{8} e_{15} e_{20}\)

\(W_{1} (M_{15}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{15}^{Kw} ) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,WG_{1}^{RR} ,CF_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{15}^{Kw} ) = \{ e_{3} ,e_{15} ,e_{8} ,e_{20} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{15}^{Kw} )) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,WG_{1}^{RR} ,CF_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{15}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{16}^{Kw}\)

\(e_{3} e_{10} e_{16} e_{17}\)

\(W_{1} (M_{16}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{16}^{Kw} ) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,SG_{1}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{16}^{Kw} ) = \{ e_{3} ,e_{17} ,e_{16} ,e_{10} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{16}^{Kw} )) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,SG_{2}^{RR} ,SC_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{16}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{17}^{Kw}\)

\(e_{4} e_{14} e_{19} e_{20}\)

\(W_{1} (M_{17}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{17}^{Kw} ) = \{ SI_{1}^{R} ,CF_{1}^{RT} ,SC_{1}^{TR} ,{\kern 1pt} CF_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{17}^{Kw} ) = \{ e_{4} ,e_{19} ,e_{14} ,e_{20} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{17}^{Kw} )) = \{ SI_{1}^{R} ,CF_{1}^{RT} ,SC_{1}^{TR} ,CF_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{17}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


\(M_{18}^{Kw}\)

\(e_{3} e_{17} e_{18} e_{20}\)

\(W_{1} (M_{18}^{Kw} ) = \left\{ {\begin{array}{*{20}l} {VS_{1} (M_{18}^{Kw} ) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,SG_{1}^{RR} ,CF_{1}^{RT} ,SO_{1}^{T} \} } \hfill \\ {ES_{1} (M_{18}^{Kw} ) = \{ e_{3} ,e_{17} ,e_{18} ,e_{20} \} } \hfill \\ \end{array} } \right.\)

\(VS^{P} (W_{1} (M_{18}^{Kw} )) = \{ SI_{1}^{R} ,SG_{1}^{RR} ,SG_{2}^{RR} ,CF_{1}^{RT} ,SO_{1}^{T} \}\)
\(A^{P} (W_{1} (M_{18}^{Kw} )) = \left[ {\begin{array}{*{20}c} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{array} } \right]\)


7 Conclusions
This paper presents a novel computable synthesis approach of mechanical conceptual design. It employs the walk and path mathematical structures in graph theory to represent the design candidates. A kinematic link graph (KLG) is constructed by looking every kinematic function unit (KFU) extracted from the mechanisms as a vertex. Two connection rules are defined to build the edges between those vertices. In KLG, each walk starting from the
inputvertex and ending at the
outputvertex is looked as a design candidate. Since a walk is represented by its edge sequence (ES) and vertex sequence (VS), the synthesis problem of mechanisms is turned into figuring out all the specified walks’ ES and VS in KLG. Thus, a weighted matrix theorem is defined and proved. Based on this theorem, a formula is induced to compute the polynomial, in which every monomial’s alphabetic items are the edge terms (ET) to one or several different walks’ ES. Then, an edge sequence sorting algorithm is given to sort and split the alphabetic items into one or several different ES. Furthermore, a formula is given to compute the VS of a walk based on its ES. The proposed synthesis approach was successfully applied in figuring out all the feasible design candidates of a mechanical system, who is able to transform the input continuous rotational motion into the output reciprocating translational motion, from the four chosen mechanisms. All the walk representations, path representations and twodimensional motion sketches to the 18 design candidates of the design example are presented. Through the proposed synthesis approach, there is no need to search and match the mechanisms in the mechanisms library exhaustively to find out all the feasible solutions. All the feasible solutions can be figured out through one polynomial operation by the proposed approach. Besides, though the proposed approach is a graphbased approach, there is no pseudoisomorphic graph problem in it.
Authors’ contributions
GL was in charge of the whole trial; LH wrote the manuscript; XY and BH assisted with building up the framework of the research. All authors read and approved the final manuscript.
Authors’ Information
Lin Han, born in 1988, is currently a PhD candidate at
Shaanxi Engineering Laboratory for Transmissions and Controls, Northwestern Polytechnical University (NWPU), China. He received his bachelor degree from
Northwestern Polytechnical, China, in 2011. His research interests include computeraided design and optimization design of mechanical system.
Geng Liu, born in 1961, is currently a professor and a supervisor of PhD candidates and director of
Shaanxi Engineering Laboratory for Transmissions and Controls,
Northwestern Polytechnical University (
NWPU),
China. His research interests include mechanical transmissions; dynamics of mechanical systems; virtual and physical prototyping simulation and design technology of mechanical systems; finite element methods; contact mechanics.
Xiaohui Yang, born in 1970, is currently a professor at
Shaanxi Engineering Laboratory for Transmissions and Controls, Northwestern Polytechnical University (NWPU), China. His research interests include mechanical design, measurement and control technology and visualization in scientific computing.
Bing Han, born in 1981, is currently an engineer at
Shaanxi Engineering Laboratory for Transmissions and Controls, Northwestern Polytechnical University (NWPU), China. His research interests include collaborative design and simulation integration technology of mechanical system, data and process management of design process.
Competing Interests
The authors declare no competing financial interests.
Funding
Supported by State Key Program of National Natural Science Foundation of China (Grant No. 51535009), and 111 Project of China (Grant No. B13044).
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit
http://creativecommons.org/licenses/by/4.0/.