The design synthesis is the key issue in the mechanical conceptual design to generate the design candidates that meet the design requirements. This paper devotes to propose a novel and computable synthesis approach of mechanisms based on graph theory and polynomial operation. The graph framework of the synthesis approach is built firstly, and it involves: (1) the kinematic function units extracted from mechanisms; (2) the kinematic link graph that transforms the synthesis problem from mechanical domain into graph domain; (3) two graph representations, i.e., walk representation and path representation, of design candidates; (4) a weighted matrix theorem that transforms the synthesis process into polynomial operation. Then, the formulas and algorithm to the polynomial operation are presented. Based on them, the computational flowchart to the synthesis approach is summarized. A design example is used to validate and illustrate the synthesis approach in detail. The proposed synthesis approach is not only supportive to enumerate the design candidates to the conceptual design of a mechanical system exhaustively and automatically, but also helpful to make that enumeration process computable.
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 Function-Structure 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 Function-Behavior-Structure and Function-Behavior-State [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 so-called function-based synthesis [7‐11]. There exist other kinds of synthesis approaches, e.g., the grammar-based synthesis [12‐16] and the graph-based synthesis [17‐21]. In grammar-based synthesis, the generative grammars, which are a class of production systems that capture design knowledge by defining a vocabulary and rule-set, are constructed and used to generate design alternatives [22]. In graph-based 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, graph-based 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].
Advertisement
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 polynomial-walk 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., {V1, V2, V3, V4}, E(D) is a set of edges, e.g., {e1, e2, e3, e4, e5, e6}, 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 e1 is from init(e1) =V1 to ter(e1) =V2. Usually, an edge is always written as a two-tuple style, e.g., the two-tuple of e3 is e3(V1,V4).
Figure 1
A digraph and its adjacency matrix
×
In a digraph, if the vertices of several edges are the same, such edges are called multiple edges, e.g., e5 and e6; if an edge whose initial vertex init(e) equals to its terminal vertex ter(e), such edge is called a loop, e.g., e2. A directed walk W in D is a finite non-null sequence, e.g., W= (V1, e3, V4, e6, V3, e5, V4, e6, V3, e4, V2), whose terms are alternately vertices and edges. A walk is called a path if all the vertices and edges are distinct, e.g., P= (V1, e3, V4, e6, V3), 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.
Advertisement
The topological structure, or in other words the connection relationships between vertices, can be conveniently represented in matrix form. A vertex-to-vertex adjacency matrix to a digraph is defined as \(A(D) = [a_{ij} ]\), where \(a_{ij} = \mu (V_{i} ,V_{j} )\) is the number of directed-edges whose init(e) = Vi and ter(e) =Vj, e.g., Figure 1(b). Let Ak(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 Vi to vertex Vj in a digraph D is given by the (i, j) element of An (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 V1 to V2 is A3(D)(1, 2) = 2, and they are W1 = (V1, e1, V2, e2, V2, e2, V2) and W2 = (V1, e3, V4, e6, V3, e4, V2).
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 (crank-rocker, 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 one-to-one or one-to-many, 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 slider-crank mechanism displayed in Figure 2(a), the slider-crank 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 slider-crank is able to transform the slider’s reciprocating translational motion into the crank’s continuous rotational motion. Therefore, the slider-crank 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
$$KFU = \{ C_{i}^{F} ,MI,MO\} ,$$
(1)
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 slider-crank. 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.
Figure 2
Representation of a slider-crank and its KFUs
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
Non-reciprocating 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
Crank-rocker
\(\{ 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)\}\)
Cam-follower
\(\{ CF_{1}^{RT} ,(R,1, - 1),(T,1,1)\}\)
Pawl-Ratchet 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 kinematic-link 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 input-vertex (e.g., \(SI_{1}^{R}\)) and output-vertex (e.g., \(SO_{1}^{R}\)), respectively. To distinguish them with other vertices, they are marked by “
” in KLG(T2).
Figure 3
Graph representation of 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 input-vertex and tail is output-vertex 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
Relationship between the walk representation and path representation of a mechanical system
×
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 input-vertex and tail is output-vertex 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 one-to-one. 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
$$P(W) = \{ VS^{P} (W),A^{P} (W)\},$$
(3)
where VSP(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 VSP(W). AP(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.
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 aij 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
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 Vi to vertex Vj in a weighted graph Gw, 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,Vi,Vj) be the walks of length k from Vi to Vj in Gw. Based on mathematical inductive method, the theorem can be proved as follows:
Proofs
When k = 1, the edge term of W(1,Vi,Vj) is the edge e(Vi,Vj). 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,Vi,Vj) are given by \(a_{i,j}^{k - 1}\). Since \(A_{\omega }^{k} (G_{w} ) = A_{\omega }^{k - 1} (G_{w} )A_{\omega }\),
where Nv is the dimension of the weighted matrix and equals to the number of vertices of Gw. As we known, each W(k,Vi,Vj) is constructed by connecting an edge e(Vm,Vj) with W(k − 1,Vi,Vm). In Eq. (4), the value of am,j is 0 or the edge label of e(Vm,Vj), 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,Vi,Vm). Thus, Eq. (4) can be looked as the polynomial operation to construct W(k,Vi,Vj), and \(a_{i,j}^{k}\) is the ET to all the walks of W(k,Vi,Vj).
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 Vi to Vj 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,Vi,Vj) in the weighted graph. For example, the (1,8) element of \(A_{\omega }^{4} (KLG(T2))\) is
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,V1,V8) in KLG(T2) as Figure 5 shows. Here, V1 = \(SI_{1}^{R}\) and V8 = \(SO_{1}^{R}\) as \(A_{\omega } (KLG(T2))\) shows.
Figure 5
Three walks in KLG(T2) corresponding to the three monomials in \(a_{1,8}^{4}\)
×
As mentioned above, each walk in KLG(T2) whose head is input-vertex (i.e., \(SI_{1}^{R}\)) and tail is output-vertex (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 monomial-walk and polynomial-walk 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 Polynomial-Walk Operation
The polynomial-walk 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 polynomial-walk, while \(A_{\omega } (KLG)\) is the weighted matrix of KLG. Nmax 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 input-vertex and output-vertex of \(A_{\omega } (KLG)\) respectively. Thus, a and b are the row vector and column vector of input-vertex and output-vertex in \(A_{\omega } (KLG)\) respectively.
For example, in the weighted matrix \(A_{\omega } (KLG(T2))\) of KLG(T2), m = 1 and n = 8. Then, a = (0, e1, e2, 0, e3, 0, e4, 0) and b = (0, e5, 0, 0, 0, e16, 0, 0)T. Set Nmax = 3, the polynomial-walk\(P_{W}^{3} [KLG(T2)]\) calculated by Eq. (7) is
Let Nm be the number of mechanisms in a design candidate and Ne be the number of degree to the corresponding monomial-walk. Then, Nm=Ne − 1. Therefore, Eq. (7) illustrates the ET to the walk representations of six feasible design candidates with the number of mechanisms of them from Nm = 1 to Nm = 3.
4.2 Edge Sequence Operation
Generally, every monomial-walk is made up by two parts, i.e., the numeral item and the alphabetic items. In the monomial-walks of the polynomial-walks \(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 monomial-walk may be larger than 1. For example, Figure 6(a) shows the composition of \(M_{1}^{Kw}\), who is a monomial-walk 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 monomial-walk 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 monomial-walk may be sorted into several different ES to several different walks. Since the numeral item of a monomial-walk 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 monomial-walk can be sorted.
Figure 6
Composition of monomial-walk \(M_{1}^{Kw}\)and its two edge sequences
×
In Figure 6(a), the ET of \(M_{1}^{Kw}\) is ET(\(M_{1}^{Kw}\)) = {e10, e13, e16, e2, e6, e6, e7, e9}. 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 monomial-walk\(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, Nn is the value of numeral item of \(M^{Kw}\).
Let ei and ej be any two edges in ET (\(M^{Kw}\)), if ter(ei) = init(ej), then ei and ej may be adjacent in \(ES_{\ell } (M^{Kw} )\). Besides, let ein and eout be the first and last edge of \(ES_{\ell } (M^{Kw} )\) respectively, then init(ein) equals to the input-vertex of KLG while ter(eout) equals to the output-vertex 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 ein. 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 eout. \(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 {e2, e6, e9}, then Ter({e2, e6, e9}) = ter(e9) = \(CR_{1}^{RS}\) and Init({e2, e6, e9})= init(e2)=\(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({e2, e6, e9})= e2 and Last({e2, e6, e9})= e9. 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
The relationship between the vertex sequence \(VS_{\ell } (M^{Kw} )\) and edge sequence \(ES_{\ell } (M^{Kw} )\) of a monomial-walk MKw is one-to-one. Here, the task of vertex sequence operation is to figure out all the \(VS_{\ell } (M^{Kw} )\) of MKw based on its \(ES_{\ell } (M^{Kw} )\). In order to complete this task, a formula is given as
where init(ei) is the initial vertex of the ith-edge ei in \(ES_{\ell } (M^{Kw} )\), while ter(ef) is the terminal vertex of the final edge ef in \(ES_{\ell } (M^{Kw} )\). NE 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 e16. Based on Eq. (8), the two vertex sequences \(VS_{1} (M_{1}^{Kw} )\) and \(VS_{2} (M_{1}^{Kw} )\) of \(M_{1}^{Kw}\) are
The proposed computational synthesis approach begins with the user-specified design requirements that including the input motion, output motion and the maximum number of mechanisms Nmax 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:
Figure 7
Computational flowchart of the synthesis approach
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 polynomial-walk operation to compute polynomial-walk\(P_{W}^{{N_{\text{max} } }} (KLG)\), and then separate and save all its monomial-walks\(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 SES.
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 AP(\(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 Nmax 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., slider-crank, worm gear, cam-follower 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
Slider-crank
\(\{ 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)\}\)
Worm-gear
\(\{ WG_{1}^{RR} ,(R,1, - 1),(R,1, - 1)\}\)
Cam-follower
\(\{ 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 input-vertex is \(SI_{1}^{R}\) while the output-vertex 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.
Figure 8
Graph representation, vertices set and weighted matrix of KLG(T4)
×
6.3 Compute Polynomial-Walk
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,e1,e2,0,e3,e4,0) while the column vector of \(SO_{1}^{T}\) is b = (0,0,e10,0,0,e20,0)T. Run polynomial-walk operation and substitute the values of m, n, a, b, Nmax and \(A_{\omega } (KLG(T4))\) into Eq. (6), the computed polynomial-walk\(P_{W}^{3} [KLG(T4)]\) is
It can be found that there are 18 different monomial-walks\(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 two-dimensional motion sketch and illustrated in Table 5, Column 5.
Table 5
The monomial-walks, walk representations and path representations to the 18 design candidates
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 input-vertex and ending at the output-vertex 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 two-dimensional 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 graph-based approach, there is no pseudo-isomorphic 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 computer-aided 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/.
” in KLG(T2).
