臺灣博碩士論文加值系統

本研究應用結構合成 (Structural Synthesis)、尺寸合成 (Dimensional Synthesis) 及運動模擬 (Kinematic Simulation) 等設計方法，實做一套平面多連桿機構設計分析軟體系統，以開源模式釋出，並命名為 Pyslvs。核心程式架構採用修改後的 Planar Mechanism Kinematic Simulator (PMKS) 作為設計結果的資料表示法，可同時表達拓樸構造與尺寸關係。因此在 Pyslvs 中可以系統化地匯入與匯出所評估的機構表達式。

結構合成部分採用邊集合 (Edge Set) 表示法，設計一種圖形列舉演算流程，以建立一般化鏈的圖譜。而尺寸合成過程則可使用三種演化運算法中的一種，進行最佳化機構路徑生成 (Path Generation)。運動路徑模擬部份採用 Solvespace 與 Sketch Solve 兩款開源電腦輔助繪圖軟體程式庫，藉由牛頓-拉夫森法 (Newton-Raphson method) 與 BFGS 演算法進行數值分析運算。

本研究最後透過堆棧表示法進行位置分析模組的配置，產生通用的平面連桿機構驗證模型。並利用多個範例展示所完成軟體套件的相關功能。

In this research, the design methods of structural synthesis, dimensional synthesis, and kinematic simulation for planar multi-link mechanism were investigated and implemented as an open-source software package named Pyslvs. The core program architecture uses the improved Planar Mechanism Kinematic Simulator (PMKS) as the data representation for design results, which can simultaneously express the topological structure and dimensional relationship. Therefore, Pyslvs can import and export the evaluated mechanism expression systematically.

For the structural synthesis part, the Edge Set of the graph was enumerated to construct the atlas of generalized chain. While in the dimensional synthesis process, one of three evolutionary computation methods can be applied to optimize the requested path generation. As for kinematic simulation of the mechanism is based on two different open source geometric constraint solver libraries, Solvespace and Sketch Solve, which the Newton-Raphson method and BFGS algorithm were used accordingly.

To the end of this thesis, the configuration of the position analysis module is performed by stack representation to generate a verification model for the associated planar linkage mechanism, and multiple examples are used to demonstrate the relevant functionality of the accomplished software package.

Chinese Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
English Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Table of Content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .viii
List of Figures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii
Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Statement of Research . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Project Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Organization of Thesis . . . . . . . . . . . . . . . . . . . . . . . . 5
Chapter 2 Related Works. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 Creative Design Methodologies of Mechanism . . . . . . . . . . . . 6
2.2 Dimensional Synthesis Methodologies . . . . . . . . . . . . . . . . 7
2.3 Design Grammar and Mechanism Expression . . . . . . . . . . . . . 8
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Chapter 3 Terminologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1 Mechanism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.1 Links and Joints . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.2 Multiple Joints . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.3 Generalized Chain . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.1 Nodes and Edges of Graphs . . . . . . . . . . . . . . . . . . 12
3.2.2 Expression . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2.3 Walks, Paths, Loops and Cycles . . . . . . . . . . . . . . . . 14
3.2.4 Isomorphism and Homeomorphism . . . . . . . . . . . . . . 15
3.2.5 Planar Graph . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 Information Technology . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3.1 Environment and Dependencies . . . . . . . . . . . . . . . . 16
3.3.2 Desktop and Web Based Application . . . . . . . . . . . . . 16
3.3.3 Programming Languages . . . . . . . . . . . . . . . . . . . 16
3.3.4 Markup Language . . . . . . . . . . . . . . . . . . . . . . . 17
3.3.5 Expression Matching and Parsing . . . . . . . . . . . . . . . 17
Chapter 4 Structural Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.1 Number and Type Synthesis . . . . . . . . . . . . . . . . . . . . . . 18
4.1.1 Generalized Chain . . . . . . . . . . . . . . . . . . . . . . . 19
4.1.2 Number and Type Synthesis . . . . . . . . . . . . . . . . . . 19
4.2 Graph Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2.1 Generalized Chain Enumeration . . . . . . . . . . . . . . . . 24
4.2.2 Cut-links Check . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.3 Planar Check . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.4 Degenerate Check . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.5 Isomorphic Check and Labeled Enumeration . . . . . . . . . 29
4.2.6 Backward Analysis Method of Generalized Chain . . . . . . 31
4.2.7 Outer Loop Layout . . . . . . . . . . . . . . . . . . . . . . 31
4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Chapter 5 Application of Open Source CAD Libraries . . . . . . . . . . . . . . . . 35
5.1 Solvespace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.1.1 Features Design . . . . . . . . . . . . . . . . . . . . . . . . 35
5.1.2 Geometric Constraint Solver . . . . . . . . . . . . . . . . . 36
5.1.3 Scripting Rules . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Sketch Solve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.2.1 Geometric Constraint Solver . . . . . . . . . . . . . . . . . 40
5.2.2 Scripting Rules . . . . . . . . . . . . . . . . . . . . . . . . 42
5.3 Binding Method of Python Programming Language . . . . . . . . . 44
5.3.1 Simplified Wrapper and Interface Generator . . . . . . . . . 44
5.3.2 Cython . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Chapter 6 Mechanism Expression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.1 Planar Mechanism Kinematic Simulator . . . . . . . . . . . . . . . 48
6.1.1 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
6.1.2 Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
6.1.3 Input Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.2 Topological Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.2.1 Degrees of Freedom . . . . . . . . . . . . . . . . . . . . . . 51
6.2.2 Contract Joints Operation . . . . . . . . . . . . . . . . . . . 51
6.2.3 Mapping to Geometric Constraint Solver . . . . . . . . . . . 52
6.2.4 Generalization Algorithm . . . . . . . . . . . . . . . . . . . 54
6.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Chapter 7 Dimensional Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
7.1 Position Analysis Methodology . . . . . . . . . . . . . . . . . . . . 57
7.1.1 PLAP Function . . . . . . . . . . . . . . . . . . . . . . . . 57
7.1.2 PLLP Function . . . . . . . . . . . . . . . . . . . . . . . . 58
7.1.3 PLPP Function . . . . . . . . . . . . . . . . . . . . . . . . 59
7.1.4 PXY Function . . . . . . . . . . . . . . . . . . . . . . . . . 61
7.1.5 Scripting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
7.2 Examples of Expression Stack . . . . . . . . . . . . . . . . . . . . 62
7.2.1 Crank Rocker . . . . . . . . . . . . . . . . . . . . . . . . . 62
7.2.2 Jansen’s Linkage . . . . . . . . . . . . . . . . . . . . . . . 63
7.2.3 Triple Ball Lifter . . . . . . . . . . . . . . . . . . . . . . . 66
7.2.4 Crank Slider (RP Joint) . . . . . . . . . . . . . . . . . . . . 68
7.2.5 Crank Slider (P Joint) . . . . . . . . . . . . . . . . . . . . . 70
7.2.6 Two DOF Arm . . . . . . . . . . . . . . . . . . . . . . . . 71
7.3 Automatic Configuration Algorithm . . . . . . . . . . . . . . . . . 73
7.3.1 Main Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.3.2 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.4 Metaheuristic Random Algorithms . . . . . . . . . . . . . . . . . . 77
7.4.1 Configuration of Generalized Chain . . . . . . . . . . . . . . 78
7.4.2 Real-coded Genetic Algorithm . . . . . . . . . . . . . . . . 79
7.4.3 Differential Evolution . . . . . . . . . . . . . . . . . . . . . 80
7.4.4 Firefly Algorithm . . . . . . . . . . . . . . . . . . . . . . . 84
7.5 Example of Dimensional Synthesis . . . . . . . . . . . . . . . . . . 85
7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Chapter 8 Summary and Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . 89
8.1 Contributions and Conclusion . . . . . . . . . . . . . . . . . . . . . 89
8.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Reference. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Appendix I Grammar of Mechanism Expression . . . . . . . . . . . . . . . . . . . . 97
Extended Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

[1] A. Chakrabarti et al. , “Computer-based design synthesis research: An overview,” Journal of Computing and Information Science in Engineering , vol.11, no. 2, p. 021003, 2011.
[2] D.M.Beazley,“SWIG:An easy to use tool for integrating scripting languages with c and c++,” in Proceedings of the 4th conference on usenix tcl/tk workshop, 1996 - volume 4 , 1996, pp. 15–15.
[3] P. Fernique and C. Pradal, “AutoWIG: Automatic generation of python bindings for c++ libraries,” PeerJ Computer Science , vol. 4, p. e149, Apr. 2018.
[4] S. Behnel, R. Bradshaw, C. Citro, L. Dalcin, D. S. Seljebotn, and K. Smith, “Cython: The best of both worlds,” Computing in Science Engineering , vol. 13, no.
2, pp. 31–39, 2011.
[5] R. B. Computing, “SIP.” https://www.riverbankcomputing.com/software/sip [Online accessed 2018-06-12], 1998.
[6] Y. Chang, “Pyslvs-ui.” https://github.com/KmolYuan/Pyslvs-UI [Online accessed 2019].
[7] Y. Chang, “Pyslvs manual.” https://pyslvs-ui.readthedocs.io/ [Online accessed 2019], 2019.
[8] Y. Chang, “Pyslvs blog.” http://www.pyslvs.com/blog/index.html [Online accessed 2019], 2019.
[9] H. S. Yan, Creative design of mechanical devices . 1998.
[10] H. S. Yan, “A methodology for creative mechanism design,” Mechanism and Machine Theory , vol. 27, no. 3, pp. 235–242, 1992.
[11] H.-S. Yan and Y.-W. Hwang, “Number synthesis of kinematic chains based on permutation groups,” Mathematical and Computer Modelling , vol. 13, no. 8, pp. 29–42, 1990.
[12] S. C. Burgess, “A backwards design method for mechanical conceptual design,” Journal of Mechanical Design , vol. 134, p. 031002, Mar. 2012.
[13] M. Pucheta and A. Cardona, “Type synthesis of planar linkage mechanisms with rotoidal and prismatic joints,” Jan. 2005.
[14] B. Faltings and K. Sun, “Computer-aided creative mechanism design,” in IJCAI , 1993, pp. 1451–1459.
[15] Y.-C. Wu, M.-C. Tsai, and C.-T. Chan, “Creative mechanism design of magnetic gears integrated with continuously variable transmissions,” Advances in Mechanical Engineering , vol. 10, no. 5, p. 1687814018772680, 2018.
[16] J. L. Chen and P. Hajela, “OPSYN: A cad based expert system for optimum structural synthesis,” Engineering Optimization , vol. 14, no. 4, pp. 267–286, 1989.
[17] W. Yang, H. Ding, and A. Kecskeméthy, “A new method for the automatic sketching of planar kinematic chains,” Mechanism and Machine Theory , vol. 121, pp. 755–768, 2018.
[18] H. Ding, “Automatic structural synthesis of planar mechanisms and its application to creative design,” PhD thesis, 2016.
[19] H.-S. Yan and Y.-T. Chiu, “On the number synthesis of kinematic chains,” Mechanism and Machine Theory , vol. 89, Jul. 2015.
[20] W.-M. Hwang and Y.-W. Hwang, “An algorithm for the detection of degenerate kinematic chains,” Mathematical and computer modelling , vol. 15, no. 11, pp. 9–15, 1991.
[21] U. Brandes, “The left-right planarity test.” Department of Computer & Information Science, University of Konstanz, 2009.
[22] R. Franke, Vom aufbau der getriebe . VDI-Verlag, 1958.
[23] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “A (sub)graph isomorphism algorithm for matching large graphs,” Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol. 26, no. 10, pp. 1367–1372, 2004.
[24] A. Vasiliu and B. Yannou, “Dimensional synthesis of planar mechanisms using neural networks: Application to path generator linkages,” Mechanism and Machine Theory , vol. 36, no. 2, pp. 299–310, 2001.
[25] G. N. Sandor and A. G. Erdman, Advanced mechanism design: Analysis and synthesis, vol. II . Prentice Hall, 1984.
[26] S. K. Acharyya and M. Mandal, “Performance of eas for four-bar linkage synthesis,” Mechanism and Machine Theory , vol. 44, no. 9, pp. 1784–1794, 2009.
[27] A. Ortiz, J. A. Cabrera, F. Nadal, and A. Bonilla, “Dimensional synthesis of mechanisms using differential evolution with auto-adaptive control parameters,” Mechanism and Machine Theory , vol. 64, pp. 210–229, 2013.
[28] Z. Shen, G. Allison, and L. Cui, “An integrated type and dimensional synthesis method to design one degree-of-freedom planar linkages with only revolute joints for exoskeletons,” Journal of Mechanical Design , vol. 140, p. 092302, Jun. 2018.
[29] M. Pucheta and A. Cardona, “A decomposition method for modular dimensional synthesis of planar multi-loop linkage mechanisms,” vol. 11, pp. 365–381, Jan. 1994.
[30] J. Westhues, whitequark, and M-Labs, “Solvespace.” http://solvespace.com/ [Online accessed 2018-06-12], 2008.
[31] J. George, “Sketch solve.” https://code.google.com/archive/p/sketchsolve/ [Online accessed 2018-06-27], 2008.
[32] 李孟恭 , “Django 網際框架在平面四連桿尺寸合成系統上的應用 ,” Master’s thesis, 國立虎尾科大學 , 2015.
[33] P. Radhakrishnan, “Automated design of planar mechanisms,” PhD thesis, 2014.
[34] H. Ding, W. Yang, P. Huang, and A. Kecskemethy, “Automatic structural synthesis of planar multiple joint kinematic chains,” Journal of Mechanical Design , vol. 135, p. 091007, Sep. 2013.
[35] A. L. Research, “GraphViz.” http://graphviz.org/ [Online accessed 2018-05-20], 1991.
[36] A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using networkx,”in Proceedings of the 7th python in science conference , 2008, pp. 11–15.
[37] T.Nishizeki and M.S.Rahman, Planar graph drawing lecture notes series on computing , vol. 12. 2004.
[38] J. R. Ullmann, “An algorithm for subgraph isomorphism,” J. ACM , vol. 23, no. 1, pp. 31–42, Jan. 1976.
[39] V. Carletti, P. Foggia, A. Saggese, and M. Vento, “Introducing vf3: A new algorithm for subgraph isomorphism,” in Graph-based representations in pattern recognition , 2017, pp. 128–139.
[40] J.Riegel, W.Mayer, and Y.van Havre,“Freecad.” https://www.freecadweb.org/ [Online accessed 2018-06-12], 2002.
[41] D. Heeks, “Heeks cad.” https://sites.google.com/site/heekscad/ [Online accessed 2018-06-12], 2011.
[42] D. M. Beazley, “Simplified wrapper and interface generator.” http://www.swig.org [Online accessed 2018-06-12], 1996.
[43] BBBSnowball, “Python-solvespace.” https://github.com/BBBSnowball/python-solvespace [Online accessed 2018-06-12], 2013.
[44] R. Bradshaw, S. Behnel, D. S. Seljebotn, G. Ewing, and et al., “Cython.” https://cython.org/ [Online accessed 2018-06-12], 2003.
[45] G. Ewing, “Pyrex.” http://www.cosc.canterbury.ac.nz/greg.ewing/python/Pyrex/ [Online accessed 2018-06-12], 2003.
[46] D. E. Lab, “Planar mechanism kinematic simulator.” https://designengrlab.github.io/PMKS/ [Online accessed 2018-05-20], 2017.
[47] A. Cayley, “A theorem on trees,” in The collected mathematical papers, vol. 13, Cambridge University Press, 2009, pp. 26–28.
[48] J. H. Holland and others, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence . MIT press, 1992.
[49] D. Karaboğa and S. Ökdem, “A simple and global optimization algorithm for engineering problems: Differential evolution algorithm,” Turkish Journal of Electrical Engineering & Computer Sciences , vol. 12, no. 1, pp. 53–60, 2004.
[50] M. Y. bin, M. Tan-zhui, and Z. Qiao-yan, “Optimal choice of parameters for firefly algorithm,” Fourth international conference on digital manufacturing and automation (ICDMA) , pp. 887–892, 2013.
[51] X.-S. Yang, Nature-Inspired Metaheuristic Algorithms, 2010.
[52] X.-S. Yang, “Firefly algorithm: Recent advances and applications,” International Journal of Swarm Intelligence , pp. 36–50, 2013.