Functional synthesis of mechanisms under cost consideration

Abstract

Functional synthesis of mechanisms plays a crucial role in mechanical product design, which has an essential effect on the product innovation and cost. However, current functional synthesis algorithms of mechanisms are either inextensible to achieve complex mechanism solutions or prone to a loss of optimal solutions without consideration of cost. This article proposed a systematic kinematic state-based methodology for functional synthesis of mechanisms under cost consideration. After a general functional representation model based on the kinematic state pair is proposed with a result of the kinematic state space, an exhaustive functional synthesis of the kinematic state pair with the lowest cost algorithm is then proposed to produce solutions with K-lowest cost. The functional synthesis of a feeding mechanism device for cold heading machine is given as an example, which demonstrates that the methodology is obviously helpful to produce valuable functional chain solutions with low cost.

Introduction

As functional synthesis of mechanisms plays a crucial role in mechanical product design, many researches have been focused on it in recent decades with many valuable contributions. Since the aim of mechanism design is to satisfy certain functions, functionality is essential in the design process, whose representation and synthesis are essential for supporting design activity. There are three main approaches in functional representation, as follows: ¹

1. Verb-noun pair, stemming from Value Engineering,^2,3 such as “to transfer motion”;

2. Input/output flow transformations, describing the general relationship between the input and output of a system to meet design requirements;^4,5

3. Transformation between input and output situations. ⁶

In contrast to functional representation, functional synthesis of mechanisms is a more complex process.^7,8 Pahl et al. ⁴ believed that functional design is composed of two tasks: one is how to obtain sub-functions by decomposition of overall function and the other is how to obtain function structure by synthesis of sub-functions. ⁹ Current methods for the functional synthesis of mechanisms can be classified into two categories: refinement-based synthesis approaches and composition-based synthesis approaches.

The refinement-based synthesis approaches tried to retrieve, transform, update, or modify the initial mechanism design specifications to obtain final mechanisms for a given design specification, which achieves the functional synthesis through the refinement of mechanism prototypes. Case-based approach^10,11 or design-by-analogy approach^12,13 is widely used for reusing previous design solutions in the functional synthesis of mechanisms. Yan and Chiu ¹⁴ discussed generalized kinematic chains-based mechanism synthesis algorithm in detail. Soong and Chang ¹⁵ proposed function generation method for a four-bar linkage. Welch and Dixon ¹⁶ presented a bond graph-based approach for design synthesis of electro-mechanical devices, using some pre-defined electro-mechanical elements, for example, resistance and capacitance.

While in compositional approaches, basic functional elements are synthesized to compose a desired mechanism by decomposing a given specification into sub-specifications, without attempts to change a given specification. These approaches synthesized desired functions with several functional elements. Some results from this research include morphological matrix generation,^17,18 relational matrices, ¹⁹ and graph grammar rules, ²⁰ which combined with some synthesis algorithms to obtain design solutions. Tang ²¹ achieved an automated conceptual design of mechanical systems using kinematic functions. Stanković et al. ²² proposed a computational design synthesis approach with directed multi-graph and graph grammar-based models of technical processes and technical process synthesis. After they proposed the representation for design problems and solutions using five basic elements, Chakrabarti and Bligh^23,24 presented a single input and single output (SISO) functional synthesis method. Chiou and Kota ²⁵ proposed a building block-based functional model and corresponding reasoning approach to automated synthesis of mechanisms. Subramanian and Wang ²⁶ presented a compositional kinematic synthesis algorithm grounded on configuration spaces. An improved morphological matrix-based synthesis approach was developed for achieving conceptual design of mechanisms. ²⁷

However, the current functional synthesis approaches have not taken the cost into consideration. As the cost of the product is one of the key contributions to success in the market, ²⁸ the manufacturing companies produce low-cost and high-quality products to maintain their competitiveness. ²⁹ As over 70% of the production cost of a product is determined during the conceptual design stage, reducing the cost of a product at the conceptual design stage is an effective way.^30,31 The above approaches could achieve combinatorial exhaustive solutions, in the absence of cost of mechanisms. However, how to produce optimal solutions of mechanisms with low cost is an important issue in the current product design. One of the most difficult tasks undertaken by designers is to evaluate the cost of a design solution. To ensure the product price is appropriate, the cost estimate should be available in the design process as early as possible in order to provide valuable information to product designers. ³² Therefore, if the mechanism solution with lower cost can be optimized during functional synthesis, mechanism solutions achieve a proper performance as well as a reasonable cost. Therefore, it still makes great sense to develop a new methodology for the functional synthesis of complex mechanisms under the consideration of cost.

This article is devoted to a new weighted directed graph-based functional synthesis approach under cost consideration of mechanism. The rest of the article is organized as follows: “A kinematic state pair-based kinematic functional representation model” section proposes a kinematic state pair-based kinematic functional representation model. “Graph-based representation model for functional synthesis of mechanisms” section proposes weighted directed graph-based model for the functional synthesis of mechanisms. “Functional synthesis algorithms of kinematic state pairs with the K-lowest cost” section proposes a weighted directed graph-based functional synthesis approach under the consideration of cost. “System implementation” section introduces computer-aided functional synthesis software developed with the proposed methodology. With the functional synthesis of new devices for cold heading machine as an example, “Application” section is shown to demonstrate the methodology proposed in this article. Then, “Conclusion” section concludes this article.

A kinematic state pair-based kinematic functional representation model

Kinematic state model

The function can usually be formally represented as the relationships between the input and output state of a system to meet user’s requirements. The kinematic function can always be regarded as the transformation between the input kinematic state and output kinematic state, involving in many kinematic features, such as type, direction, magnitude, constancy, orientation, continuity, intermittence, and reciprocation. ³³ A vector including five kinematic features is used to represent the basic kinematic states as follows

$${[\mathrm{Kinematic\; type},\mathrm{Direction},\mathrm{Constancy},\mathrm{Continuity},\mathrm{Reciprocator}]}^{\mathrm{T}}$$

The features almost include all the important functional attributes of mechanism elements. The meanings of the features are given as follows:

1. Kinematic type. A kinematic type can be classified into rotation, translation, and helix, referring to the kinematic type of the input and output of a mechanism, coding with R, T, H, respectively.

2. Direction. The orientation of a translation can be defined as ±X-axis, ±Y-axis, or ±Z-axis in the Cartesian coordinate, while that of a rotation or a helix can be defined as its X-axis, Y-axis, or Z-axis counterclockwise.

3. Constancy. Whether the velocity of translation, rotate, or helix keeps constant or not, coded as 0, 1.

4. Continuity. Whether the translation, rotate, or helix keeps continuity or not, coded as 0, 1.

5. Reciprocator. Whether the input/output kinematic state is back and forth or not, coded as 0, 1.

Kinematic state pair-based functional representation model

As shown in Figure 1, a kinematic function can be formally represented as the transformation of kinematic state, named as a kinematic state pair. A kinematic state pair is composed of input kinematic state and output kinematic state. The solution has different levels depending on the granularity of kinematic function in the kinematic state.

Figure 1.

Kinematic state pair-based kinematic functional model.

It should be mentioned that a mechanism may have several representations with several kinematic state pairs; at the same time, there are always several mechanisms with the same representation. For instance, the function of a crank–slider mechanism and cam–follower mechanism, as shown in Figure 2, can be represented as [R,+X,0,1,1]^T → [T,+Y,1,0,0]^T.

Figure 2.

Representation of a function achieved by a crank–slider mechanism.

Graph-based representation model for functional synthesis of mechanisms

Definitions

Node

In Figure 3, the node v_i represents a kinematic state of the mechanisms.

Figure 3.

Foundations of graph-based representation model for mechanism synthesis.

Directed edges

A directed edge is achievable from the source node (source kinematic state node v_i) to the destination node (destination kinematic state node v_j), which is used to be declared as a mechanism to achieve the kinematic state transformation from a certain source kinematic state to destination kinematic state.

Weight

The specific weight ${\mathrm{w}}_{\mathrm{ij}}^{\mathrm{n}}$ in these directed edges between source and destination nodes is used to represent the cost of the corresponding mechanism. For instance, ${\mathrm{w}}_{\mathrm{ij}}^{\mathrm{n}}$ is used to represent the cost of the nth mechanism solution from the source node (source kinematic state node v_i) to the destination node (destination kinematic state node v_j). As there are several mechanisms to fulfill the transformation from the source node to the destination node, there might have several ${\mathrm{w}}_{\mathrm{ij}}^{\mathrm{n}}$ in the directed edges, defined as ${\mathrm{W}}_{\mathrm{ij}}=\{{\mathrm{w}}_{\mathrm{ij}}^1,{\mathrm{w}}_{\mathrm{ij}}^2,{\mathrm{w}}_{\mathrm{ij}}^3,\dots ,{\mathrm{w}}_{\mathrm{ij}}^{\mathrm{n}}\}$ .

For instance, the function of a mechanism is [T,+Z,0,0,1] → [R,+X,0,1,1]; thus, node v_i represents source kinematic state [T,+Z,0,0,1], and its destination kinematic state v_j is [R,+X,0,1,1]. And the corresponding weight in the directed edge is noted with 120, which means the cost of the mechanism prototype is US$120. As there are many solutions to achieve from two kinematic state nodes, there might have an edge with several data $({\mathrm{w}}_{\mathrm{ij}}^1,{\mathrm{w}}_{\mathrm{ij}}^2,\dots ,{\mathrm{w}}_{\mathrm{ij}}^{\mathrm{n}})$ .

Modeling the kinematic state space

In order to enable functional synthesis of mechanism, a kinematic state space should be constructed at first, integrated with knowledge of mechanism prototypes. As each kinematic state has limited variables, such as R, T,+X, 0, and 1, it is easy to list all possible kinematic states to establish a kinematic state space in an exhaustive way, as shown in Figure 4. Then these kinematic states with a directed edge and corresponding costs are linked. For instance, the edge from the input kinematic state [R,+X,0,0,1]^T to the output kinematic state [T,+Y,1,1,0]^T represents the corresponding kinematic function: [R,+X,0,0,1]^T → [T,+Y,1,1,0]^T. If there is any mechanism that can achieve the transformation of each kinematic state pair in potential mechanism solutions, these two corresponding nodes in the kinematic state space with cost as weight are linked. While there might have many potential mechanism solutions in these transformations of a kinematic state pair, thus there might have directed edges with a set of costs W_ij in a kinematic state pair. For instance, knowledge engineers check all mechanisms in mechanism repository and find that the function [R,+X,0,0,1]^T → [T,+Y,1,1,0]^T can be achieved by some mechanism prototypes, such as crank–slider mechanism and perpendicular cam–follower mechanism; then they link the corresponding nodes [R,+X,0,0,1]^T and [T,+Y,1,1,0]^T and add the ${\mathrm{w}}_{\mathrm{ij}}^1$ and ${\mathrm{w}}_{\mathrm{ij}}^2$ in the directed edge of the corresponding kinematic state pair. Obviously, kinematic state space will facilitate the subsequent design synthesis in that it has encapsulated explicit input and output kinematic states.

Figure 4.

Kinematic state space (partial) (all the edges have weights).

When a desired function is defined as the input and output kinematic states, the simplest approach to accessing its solutions is to check whether the two corresponding nodes in the kinematic state space are linked. If true, retrieve the solution list indexed by the function. However, it is often the truth that the two corresponding nodes from the initial node (input kinematic state) to the desired node (output kinematic state) are not linked, which means that there are no mechanism prototypes that can achieve the desired function directly. In such situations, the functional synthesis approach should be employed to generate possible functional combinations for the desired function.

Functional synthesis algorithms of kinematic state pairs with the K-lowest cost

Definitions

• G: weighted directed graph,^34–37 also named as kinematic state space;

• V: node set in kinematic state space, V = {v₁, v₂, v₃,…, v_n};

• E: directed edge set in the kinematic state space;

• L^initial: a sequence of G links {b₁, b₂,…, b_G}, in which b₁ is a node in the graph;

• L^exclude: a sequence of H links {c₁, c₂,…, c_H}, in which c₁ is a node in the graph;

• S: set of acyclic paths between origin o and destination d that all start with L^initial and exclude L^exclude;

• S_{<K>,<Subsetnumber>}: the Subsetnumberth subset of the set that contains the Kth shortest path;

• S_0,1: set of all paths;

• P(S): shortest path within each subset S, consisting of the links $\{\{{\mathrm{L}}^{\mathrm{initial}}\},{\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{q}}\}$ , in which a_i is a node in the graph;

• S_i: set of acyclic paths between o and d that start with the sequence of links ${\mathrm{L}}_{\mathrm{i}}^{\mathrm{initial}}=\{\{{\mathrm{L}}^{\mathrm{initial}}\},{\mathrm{a}}_1,{\mathrm{a}}_2,\dots ,{\mathrm{a}}_{\mathrm{i}-1}\}$ and exclude the links ${\mathrm{L}}_{\mathrm{i}}^{\mathrm{exclude}}=\{\{{\mathrm{L}}^{\mathrm{exclude}}\};{\mathrm{a}}_{\mathrm{i}}\}$ .

• f: first link (if any) in this path that does not satisfy the constraint (f = Φ∨f∈{1, 2,…, q}).

• R: set of rejected paths, ${\mathrm{L}}_{\mathrm{i}}^{\mathrm{exclude}}=\{\{{\mathrm{L}}^{\mathrm{exclude}}\};{\mathrm{a}}_{\mathrm{i}}\}$ , in which a_i is a node in the graph.

Functional synthesis algorithms of kinematic state pairs with the K-lowest cost

In Figure 4, kinematic state space, a weighted directed graph G(V, E), is given with a weight function set ${\mathrm{W}}_{\mathrm{ij}}=\{{\mathrm{w}}_{\mathrm{ij}}^1,{\mathrm{w}}_{\mathrm{ij}}^2,\dots ,{\mathrm{w}}_{\mathrm{ij}}^{\mathrm{n}}\}$ , that maps each edge (v_i, v_j) to a real-valued weight, which is a cost of the corresponding mechanism prototype. A minimum weight path from the output kinematic state node u to the input kinematic state node v in G(V, E) is to be found to solve the mechanism design for every pair of kinematic state nodes u, v∈V, where the cost of a mechanism prototype is the sum of the transformed weights of its constituent edges.

Matrix-based approach was widely used approach for functional synthesis, ³¹ which is always the lack of a uniform interface representation model, such as kinematic state pair-based functional model proposed in this article, to enable functional synthesis with a general interface representation model. At the same time, cost is an important factor in mechanism transmission, so how to integrate functional synthesis of mechanisms with cost is also an important issue. In mechanism design, it is desirable to determine a set of alternative solutions, such as the lowest cost mechanism prototype solutions, the second-lowest cost mechanism prototype solutions, and the third-lowest cost mechanism prototype solutions, up to the kth lowest cost mechanism prototype solutions between input kinematic state and output kinematic state. In this way, the functional synthesis of mechanism integrated with cost is transferred into a k-shortest path with the constraint of the weighted directed graph. The algorithms used for determining paths beyond just the shortest paths are generally referred to as functional synthesis algorithm of two kinematic states with the K-lowest cost.

After a desired function with the input and output kinematic states is clarified, the functional synthesis based on the above kinematic state space, a weighted directed graph, is with a result of possible functional chains for the achievement of the desired function. After modifying the k-shortest path with the constraint of weighted directed graph, ³⁵ functional synthesis algorithms of kinematic state pairs with the K-lowest cost are fulfilled in details in the following:

• Step 1. Since there are many solutions to achieve from two kinematic state nodes, there might have an edge with several cost data $({\mathrm{w}}_{\mathrm{ij}}^1,{\mathrm{w}}_{\mathrm{ij}}^2,\dots ,{\mathrm{w}}_{\mathrm{ij}}^{\mathrm{n}})$ , simplify the graph with the lowest cost in each kinematic state pair.

• Step 2. Find the shortest path within S_0,1 (the set of all paths from the input kinematic state node to output kinematic state node) using Dijkstra’s algorithm, ³⁸ which solves the single-source shortest path problem for a graph, and denote it with P(S_0,1).

•  Step 2.1. Label the input kinematic state node as 0.

•  Step 2.2. Box this number (permanent label).

•  Step 2.3. Label each kinematic state node that is connected to the input kinematic state node with its cost (temporary label).

•  Step 2.4. Box the smallest number.

•  Step 2.5. From this kinematic state node, consider the cost to each connected kinematic state node.

•  Step 2.6. If a cost is less than a cost already at this kinematic state node, cross out this cost and write in the new cost. If there was no cost at the kinematic state node, write down the new cost.

•  Step 2.7. Repeat from Step 2.4 until the output kinematic state node is boxed.

• Step 3. Divide S_0,1−P(S_0,1) into q(1) mutually exclusive subsets S_1,1, S_1,2,…, S_1,q(1) with feasible initial links and a set of rejected paths R₁.

• Step 4. Set m = 1.

• Step 5. Compute the shortest paths for subsets S_m,1, S_m,2,…, S_m,q(m) and denote these paths with P(S_m,1), P(S_m,2),…, P(S_m,q(m)).

• Step 6. Find the (m + 1)th shortest path within all subsets that have been identified until now, in {P(S_1,1),…, P(S_1,q(1)), P(S_2,1),…, P(S_2,q(2)),…, P(S_m,1),…, P(S_m,q(m))}.

• Step 7. Let S_a,j be the set that contains the (m + 1)th shortest path (feasible or not). Divide S_a,j−P(S_a,j) into q(m + 1) mutually exclusive subsets S_m+1,1, S_m+1,2,…, S_m+1,q(m+1) with feasible initial links and a set of rejected paths R_m.

• Step 8. Set m = m + 1, repeat Step 5 until m = k.

• Step 9. Output the functional chains solutions with maximal functional synthesis step N ranked by cost.

By this way, several feasible functional chains with mechanism solutions are arranged in sequence according to their costs. While ensuring the reliability and efficiency of mechanisms, the maximal functional synthesis step N is usually set as smaller as possible.

System implementation

Based on the methodology proposed above, functional synthesis system of mechanism under cost consideration (FSSMCC) has been developed with C# development tool and a commercial database system. The framework of FSSMCC has three layers: knowledge layer, system layer, and interface layer, as shown in Figure 5:

1. The lowest layer is the knowledge layer, which is used to store functional knowledge repository, solution knowledge repository, reasoning rules repository, and so on.

2. The next layer is the system layer, which is used to deal with the request to complete the functional synthesis of mechanisms under cost consideration, and provides services to access and deal with the modeling repository of the kinematic state space.

3. The highest layer is the interface layer, through which engineers complete the inter-operation within systems.

Figure 5.

Framework of FSSMCC.

FSSMCC includes three main menus, such as design requirement, functional synthesis of mechanism, and help. After clicking “design requirement” menu, FSSMCC will popup a dialog that all designers define the input kinematic state and output kinematic state, including kinematic type, direction, constancy, continuity, and reciprocator. After clicking “functional synthesis of mechanism” menu, FSSMCC will then popup a dialog that will allow designers to define the maximal functional synthesis step N and the maximal number of functional synthesis K and then begin the functional synthesis process based on the design requirement. FSSMCC will yield all possible combinations of existing mechanism prototypes for all functional chains obtained. As a result, the outcomes of functional synthesis chains, ranked by cost, will be shown on the right part of the main window, as shown in Figure 6.

Figure 6.

Main window of FSSMCC.

Application

To achieve the functional synthesis of mechanical transmission system, a cold heading machine is given as an example to illustrate the proposed methodology. Cold heading is a process that uses die forms and punches to produce shaped parts from metal wire, which uses force driven by a punch to push material through a die into a new shape. High strength wire is used as the raw material in the cold heading process. Therefore, it is necessary to develop a feeding mechanism to transfer the high strength wire into the cold heading machine accurately.

Clarifying design tasks

Since the input kinematic state can be [R,+Z,0,0,1]^T, the output kinematic state should be [T,+X,1,1,1]^T. Therefore, the desired feeding mechanism should be able to achieve the functions: [R,+Z,0,0,1]^T →[T,+X,1,1,1]^T. Here, [R,+Z,0,0,1]^T → [T,+X,1,1,1]^T is selected as the functional requirement.

Functional synthesis process

Set functional synthesis step N = 1 and the number of functional synthesis K = 6. FSSMCC directly checks the input kinematic state node and the output kinematic state node, corresponding to the functional requirement [R,+Z,0,0,1]^T → [T,+X,1,1,1]^T. However, there are no direct solutions.

Set functional synthesis step N = 2 and the number of functional synthesis K = 8. FSSMCC carries out exhaustive functional synthesis at first. And then output the functional chains ranked by cost, resulting in a set of possible functional chains, such as [R,+Z,0,0,1]^T → [R,+X,0,0,1]^T → [T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [R,+Y,1,0,1]^T → [T,+X,1,1,1]^T, [R,+Z,0,0,1]^T→ [R,−Z,1,0,1]^T → [T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [R,+Z,0,0,1]^T → [T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [T,+Z,0,0,1]^T → [T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [T,+X,0,0,1]^T → [T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [T,+Z,1,1,1]^T → [T,+X,1,1,1]^T, and [R,+Z,0,0,1]^T →[T,−Z,1,1,1]^T → [T,+X,1,1,1]^T. Then existing mechanism prototypes are synthesized based on the above functional chains, leading to a new set of combinatorial solutions.

Set the functional synthesis step N = 3 and the number of functional synthesis K = 12. FSSMCC performs functional synthesis again. And then output the functional chains ranked by cost, with a result of a set of new functional chains, such as [R,+Z,0,0,1]^T → [R,+X,0,0,1]^T → [R,+Y,1,1,1]^T →[T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [R,+X,0,0,1]^T → [T,+X,0,0,1]^T → [T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [R,+Y,1,0,1]^T → [R,+X,0,0,1]^T →[T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [R,+Y,0,0,1]^T → [R,+X,1,1,1]^T →[T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [T,+X,0,0,1]^T → [R,+X,0,0,1]^T →[T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [T,+Y,1,1,1]^T → [R,+X,0,0,1]^T →[T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [R,−Z,0,0,1]^T → [T,+X,0,0,1]^T →[T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [R,−Z,0,0,1]^T → [R,+X,0,0,1]^T →[T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [R,−Y,0,0,1]^T → [R,+X,0,0,1]^T → [T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [T,−Y,0,0,1]^T → [R,+X,1,1,1]^T →[T,+X,1,1,1]^T, [R,+Z,0,0,1]^T → [T,−Y,0,0,1]^T → [R,+X,1,1,1]^T →[T,+X,1,1,1]^T, and [R,+Z,0,0,1]^T → [R,−Y,0,0,1]^T → [R,+X,1,1,1]^T → [T,+X,1,1,1]^T. Then the existing mechanism prototypes are synthesized based on the above functional chains, leading to a new set of combinatorial solutions.

Figure 6 shows the portion of the above synthesis result. This combination is eventually developed as a measurement device prototype with its corresponding mechanism prototypes and functional structure, as shown in Figure 7.

Figure 7.

Sketch of feeding mechanisms for cold heading machine.

From the above design case, the advantages of this methodology can be demonstrated. By increasing the maximal synthesis step N, it can conveniently achieve the functional synthesis of complex mechanisms considering with cost. This methodology has also yielded a large number of solutions to the desired function through the exhaustive search with the K-lowest cost. Therefore, it can effectively assist designers in achieving conceptual design of mechanisms.

Conclusion

This article presents a new systematic kinematic state-based methodology for the functional synthesis of mechanisms with consideration of cost. After a general kinematic state model-based kinematic state pair is proposed with a result of the kinematic state space, an exhaustive functional synthesis algorithm of input/output kinematic states pair with the lowest cost is then proposed to produce solutions with K-lowest cost solutions. The functional synthesis of new devices of cold heading machine was given as an example, which demonstrates that the methodology is obviously helpful to produce valuable mechanism solutions for low cost.