# Synthesis and Application of Planar Multi-link Mechanism --- Advisor: Chia-Ming Yen Student: Yuan Chang
# Outline --- + Motivation, Methodologies and Literature Comparison + Structural Synthesis **[Program Demo]** + Mechanism Expression + Dimensional Synthesis **[Program Demo]** + Conclusion
# Implementation --- The program implementation in this research named Pyslvs, which is came from "Python" and "Solvers".
# Architecture ---
# Motivation, Methodologies and Literature Comparison --- + Motivation + Methodologies + Literature Comparison - Structural Synthesis + Literature Comparison - Dimensional Synthesis + Literature Comparison - Mechanism Expression + Program Architecture
# Motivation - (1) ---
+ According to the overview of **Computer-Aided Synthesis Design** in A. Chakrabarti et al., “Computer-based design synthesis research: An overview,” 2011, **Synthesis Design** can be devided into three parts: 1. Function-based Synthesis: The synthesis required for **functionality**. 1. Grammar-based Synthesis:The synthesis required for **representation**. 1. Analogy-based Synthesis:The synthesis required for the improvement of **past design**. + This research was positioned as **Function-based** and **Analogy-based** Synthesis.
# Motivation - (2) --- 1. The concept of redesigning an existing mechanism is to pass the objective through the process of **Creative Design Method of Mechanism {1}**. 1. The mechanism contains two functional appearances, **structure** and **dimension**. + **Structure**: The way assembled the mechanism. + **Dimension**: The orientation and relative distance of the nodals (joints). 1. Through the **Metaheuristic Random Algorithms**, **Numerical Methods** and **Enumeration Algorithms**, with the computers and various convergence strategies under realistic constraints, to solve the design problems. 1. The synthesis process and application of planar mechanisms are used in different environments. In this research, structure and dimensional constraints can be designed by computer-aided process, which have **Generic Design Grammar**. --- + {1}: Generally called as "Creative Design" in this research.
# Methodologies - (1) --- + Forward Synthesis: Derived from **Creative Design Method**, the new mechanism type can be found by **Structural Synthesis**, after doing **Dimesional Synthesis** of the generalized chain, output as **Mechanism Expression**. + Backward Analysis: Transform **Mechanism Expression** to generalized chain, then determine its assortment data.
# Methodologies - (2) ---
+ **Creative Design Method**: + **Structural Synthesis**:{Ph.D} 邱于庭, "On the Number Synthesis of Generalized Kinematic Chains," 2015 + **Dimensional Synthesis**:{Master Thesis} 李孟恭, "Django 網際框架在平面四連桿尺寸合成系統上的應用," 2015 + **Mechanism Expression**:{Ph.D} P. Radhakrishnan, "Automated Design of Planar Mechanisms," 2014
# Methodologies - (3) --- The data conversion process that must be designed in this research is expected:
### Literature Comparison - Sturctural Synthesis - (1) --- The reference is "On the Number Synthesis of Generalized Kinematic Chains". | Method | Reference | This Research | |:-------|:----------|:--------------| | Graph Expression | Adjacency Matrix | Edge Set | | Generalized Chains | Undirected Graph | Same | | Contracted Graph | Multigraph | Same | | Link Assortment | Diophantine equations with Cartesian product | Same | | Contracted Link Assortment | Same as above | Equation Corrected | | Enumeration of Contracted Graphs | Same as above | Same | | Enumeration of Conventional Graphs | Permutation and Combination | Same |
### Literature Comparison - Sturctural Synthesis - (2) --- | Method | Reference | This Research | |:-------|:----------|:--------------| | Specialization | Not included | Merged to labeled enumeration | | Cut-link Checking | Cut-link Checking | Same | | Degenerate Checking | Degenerate Checking ({1}) | Same | | Planar Graph Check | Kuratowski's Theorem | Ulrik Brandes's Left-Right Planarity Test | | Isomorphism Checking | Franke's Condensed Notation | VF2 Algorithm ({2}) | + {1}: W.-M. Hwang and Y.-W. Hwang, “An algorithm for the detection of degenerate kinematic chains,” 1991. + {2}: "A (Sub)graph Isomorphism Algorithm for Matching Large Graphs," 2004
### Literature Comparison - Sturctural Synthesis - (3) --- | Method | Reference | This Research | |:-------|:----------|:--------------| | Graph Sketching | Hyper Graph and Line Graph | External Loop Algorithm | | Programming Implementation | C# | Python / Cython | | GUI | Stand-alone (Microsoft Windows Forms) | Stand-alone (PyQt) | | Open Source | No | Yes (Pyslvs) |
### Literature Comparison - Dimensional Synthesis - (1) --- The reference is "Django 網際框架在平面四連桿尺寸合成系統上的應用". | Method | Reference | This Research | |:-------|:----------|:--------------| | Algorithms | Metaheuristic Random Algorithm ({1}) | Same | | Type of Mechanisms | Planar Four bar Linkage Mechanism | Planar Linkage Mechanism | | Varification Formulas | PLAP、PLLP | PLAP、PLLP、**PLPP**、**PXY** | + {1}: + Real-coded Genetic Algorithm + Differential Evolution + Firefly Algorithm
### Literature Comparison - Dimensional Synthesis - (2) --- | Method | Reference | This Research | |:-------|:----------|:--------------| | Formulas Configuration | Direct Formulas | Automatic Configuration Algorithm | | Programming Implementation | Python / Cython | Python / Cython | | GUI | Server based (Django) | Stand-along (PyQt) | | Open Source | Yes | Yes (Pyslvs) |
### Literature Comparison - Mechanism Expression - (1) --- The reference is "Automated Design of Planar Mechanisms". | Method | Reference | This Research | |:-------|:----------|:--------------| | Grapg | Hypergraph | Same | | Dimension | Planar | Planar | | Implemented Joint Types | R, P, RP ({1}) | Same | | Literal String | Coded String, URL | Literal String, YAML | | Simplified Attributes | No | Redefined Default Values, Name of Links | | Input Joint Types | R | R、P、RP | + {1}: Revolute, Prismatic, Revolute-Prismatic
### Literature Comparison - Mechanism Expression - (2) --- | Method | Reference | This Research | |:-------|:----------|:--------------| | Programming Implementation | C# | Python / Cython | | GUI | Server based (Microsoft Silverlight) | Stand-along (PyQt) | | Open Source | Yes (PMKS) | Yes (Pyslvs) |
# Structural Synthesis --- + Link Assortment and Contracted Link Assortment + Corrected Equation of Contracted Link Assortment + Enumeration of Contracted Graphs + Enumeration of Conventional Graphs + Graph Filter + External Loop Layout + Generalization + **[Program Demo]**
### Link Assortment and Contracted Link Assortment --- + A generalized chain transformed into undirected graph, where the links are mapped to vertices (nodes); the joints are mapped to edges.
+ Link assortment $[L_2, L_3, L_4, ...]$ means that the chain has $L_2$ binary link(s), $L_3$ ternary link(s), $L_4$ quaternary link(s), and so on. + Contracted link assortment $[C_1, C_2, C_3, ...]$ means that the chain has $C_1$ single series binary link, $C_2$ double series binary links, $C_3$ triple series binary links, and so on.
#### Corrected Equation of Contracted Link Assortment - (1) --- Original definitions: + $i_{\max}$ is the max number of contracted links. + $J_m$ is the joint number between multiple links. + **$J_m'$ is the joint number between two multiple links.** + $J_m - J_m'$ make sure the number of connections is in the range. $$i\_{\max} = N\_{L\_2} - N_C + 2$$ $$\max(1, J\_M - J\_M') \leq N\_C \leq \min(N\_{L\_2}, J_M)$$ $$J\_M = \frac{1}{2} \sum\_{m=3}^{m\_{\max}} mN\_{L_m}$$
#### Corrected Equation of Contracted Link Assortment - (2) --- The following equations and definitions have been corrected in this research: + The range of $i$ **can't overflow** to the number of binary links $N_{L_2}$. + $J_m'$ is the **biggest connection number of planar graph**, according to Kuratowski's Theorem $E = 3(V - 2)$.
$$i\_{\max} = \min(N\_{L\_2}, N\_{L\_2} - N_C + 2)$$
# Enumeration of Contracted Graphs --- + The non-negative integer {$0, \mathbb{Z}^+$} solution of link assortment and contracted link assortment can be found by Cartesian Product Enumeration with constraint conditions. + Contracted Graph is a type of Multigraph, multiple edges can be connected between two vertices, which is **only include multiple links**. + The connection number less than 3 per node is not allowed, that is, the binary link is not considered. + Generated from link assortment (ignore first place). For $[x, 2, 1]$:
# Enumeration of Conventional Graphs --- + Enumeration of contracted link assortment by a contracted graph. + For example, the enumeration of $[4, 2, 1]$ with a case of contracted link assortment $[2, 1]$:
# Graph Filter - (1) --- The following algorithms were implemented in this research: + Planar graph checking: Ulrik Brandes's Left-Right Planarity Test + Degenerate checking: Degenerate checking algorithm (An Algorithm for the Detection of Degenerate Kinematic Chains, Hwang Wen-Miin and Yii-Wen Hwang) + Isomorphism checking: VF2 Algorithm + Backward analyzing link assortment and contracted link assortment.
# Graph Filter - (2) --- + Ulrik Brandes's Left-Right Planarity Test is using deep-first searching method to check the T-alike and T-opposite states. + VF2 Algorithm is using complete graph $K_5$ to check the expect embedded subgraph.
# External Loop Layout --- + This layout method is using aliquoted node strategy. + Based on searching the maximum length path, the nodes are placed one by one.
# Generalization --- This algorithm will transform the mechanism expression as an undirected graph represented generalized chain.
# **[Program Demo]** ---
# Mechanism Expression --- + Planar Mechanism Kinematic Simulator + Definitaion + Pyslvs
# Planar Mechanism Kinematic Simulator --- + The mechanism expression form in this research was modified from the implementation of the Planar Mechanism Kinematic Simulator (PMKS). + This form will treat the links as nodes and joints as edges, which is **same** as generalized chain. + This expression is based on **Hypergraph**, multiple nodes can be connected at the edge, which is simplify the representation of multiple joints.
# Definitaion --- Each Point contains following attributes: + Links: The contained links, marked as link labels. + Type: The type of the joint, R, P and RP can be used. + X and Y position: The position in the transient, representing the dimensions. + Current position: The position in the current state (for simulation). + Angle: The slot angle of the slider joint.
# Pyslvs - (1) --- + The literal expression used in the system of Pyslvs implemented in this research. ```python # Single line annotation. M[ J[R, color[Green], P[0.0, 0.0], L[ground, link_0]], J[R, color[Green], P[12.92, 32.53], L[link_0, link_1]], J[R, color[Green], P[73.28, 67.97], L[link_1, link_2]], J[R, color[Green], P[33.3, 66.95], L[link_1]], J[R, color[Green], P[90.0, 0.0], L[ground, link_2]], ] ```
# Pyslvs - (2) --- The general constraint mode of mechanism expression:
Multiple links
Slider joints
# Dimensional Synthesis --- + Verification mechanism - Geometric Constraint Solver + Verification mechanism - Geometric modules + Automatic Configuration Mechanism + Configuration of Generalized Chain + Metaheuristic Random Algorithm + **[Program Demo]**
#### Verification mechanism - Geometric Constraint Solver --- The numerical methods taken in this research is derived from two CAD kernels: | Features | Solvespace | Sketch Solve | |:---------|:-----------|:-------------| | Numerical Method | Newton-Raphson Method | BFGS Algorithm ({1}) | | GUI | GTK-- and OpenGL | No | | Programming Language | C++ | C++ | | Wrapper | SWIG / Cython ({2}) | Cython | + {1}: Broyden-Fletcher-Goldfarb-Shanno Algorithm + {2}: The research is ended with an easy-to-maintain Cython wrapper.
#### Verification mechanism - Geometric modules --- In this study, PLAP and PLLP modules were used, and PLPP and PXY were added to solve the partial slider joint.
PLAP
PLLP
PLPP
PXY
### Automatic Configuration Mechanism - (1) --- This algorithm builds an Expression Stack to indicate the solution step.
### Automatic Configuration Mechanism - (2) --- + **Fully configured**: The position can be completely determined. + **Incomplete configured**: It is not possible to match the case of when the input shaft on the 5 links loop or above, and the rest is obtained by numerical method.
# Configuration of Generalized Chain --- Topological settings: 1. Grounded link 1. Input list 1. Custom points 1. Multiple joints 1. Target points 1. Initial positions 1. Upper and lower bounds Gene information: 1. Grounded joints 1. Length of links 1. Input list
# Metaheuristic Random Algorithm --- + Real-coded Genetic Algorithm + Differential Evolution + Firefly Algorithm Among them, Differential Evolution method has better convergence performance. --- + After measurement, the speed of **fully configured** verifications is faster than **incomplete configured** case. + The following is the spent time of Differential Evolution with the same setting and environment, which needs to match 8 target points by calculated 1000 generations. | Result | **Fully configured** 8 bar | **Incomplete configured** 6 bar | |:------:|:--------------------------:|:-------------------------------:| | Solved nodes | 6 | 1 + 3 (numeric method) | | Time spent | 22.11s | 110.62s |
# **[Program Demo]** ---
# Conclusion --- + Conclusion + Future Plan
# Conclusion - (1) --- 1. The purpose of this research is to combine the design flow of **structural synthesis** and **dimensional synthesis** with a type of **mechanism expression**. Which includes a generic dimensional synthesis design flow that suitable for the planar linkage mechanism input of the rotate joints. 1. Mechanism expression in this research is based on the grammar of PMKS expression. Through the generalization algorithm and information picking in the configuration of dimensional synthesis, existing mechanism can be redesigned the partial features instead of doing whole the operations of Creative Design flow. 1. In the dimensional synthesis process, Automatic Configuration Algorithm is an opportunity to bring a new type of generic path solving mechanism instead of specific position analysis method. The auto parsing mechanism can find the solution step by building an expression stack, which is more general than manually redesigning analytical method.
# Conclusion - (2) --- The final design process of this research:
# Future Plan - (1) --- The projects that can be extended in the future of this research: + **Web platform**: The design flow needs to share the information in the web framework to support collaboration. + **Support more types of joints in mechanism expression**: The mechanism expression has no gear joints from the future work of PMKS. Other types of joints can support more complex path matching. + **Merge and simplify process of generalized chain**: After actual testing, the larger graph can be easily enumerated by merge multiple subgraphs. This process can be added into the graph enumeration algorithm of Creative Design Method. + **Atlas database**: A labeled generalized chain database can store and provide the usage experience of different graphs. These big data can use on artificial intelligence to improve the selection of generalized chains.
# Future Plan - (2) --- + **Topological description**: The description of mechanical structure were able applied to the explanatory text of product documentation or patent description, which can be generated automatically. + **Dependency dimensional synthesis**: Each length of links are independent variables in the synthesis algorithms. Dependent variable option will be able to generate specific appearance for the target mechanism. + **Aided assembly of planar linkage mechanism**: In spatial applications, the aided layers configuration can help for the obstacle avoidance of other link parts.