# Synthesis and Application of Planar Multi-link Mechanism ## 平面多連桿機構之合成與應用 --- 指導教授:嚴家銘 學生:張元
# 大綱 --- + 動機、方法論與文獻比較 + 構造合成 (Structural Synthesis) **[程式演示]** + 機構表達式 (Mechanism Expression) + 尺寸合成 (Dimensional Synthesis) **[程式演示]** + 結論
# 程式實作 --- 本研究中的程式實作命名為 Pyslvs,源自於 "Python" 與 "Solvers"。
# 程式架構 ---
# 動機、方法論與文獻比較 --- + 動機 + 方法論 + 文獻比較 - 構造合成 + 文獻比較 - 尺寸合成 + 文獻比較 - 機構表達式 + 程式架構
# 動機 - (1) ---
+ 根據 A. Chakrabarti et al., “Computer-based design synthesis research: An overview,” 2011 所作的**電腦輔助合成設計**文獻回顧,**合成設計**可分為三種: 1. Function-based Synthesis:為了**功能性**而作的合成。 1. Grammar-based Synthesis:依設計需求作**表示法**的合成。 1. Analogy-based Synthesis:推演**過去設計**所作的合成。 + 本研究定位為 **Function-based** and **Analogy-based** Synthesis。
# 動機 - (2) --- 1. 將已存在機構重新設計的概念是將機構通過**創意性機構設計方法 (Creative Design Method of Mechanism {1})** 的流程。 1. 機構中含有兩種功能性外觀,**構造**以及**尺寸**。 + **構造**:機構中部件組成的方式。 + **尺寸**:部件組合處 (接頭) 的相對距離與朝向。 1. 藉由**元啟發式隨機演算法 (Metaheuristic Random Algorithms)**、**數值分析 (Numerical Methods)** 或**列舉演算法 (Enumeration Algorithms)**,可以透過電腦協助,應用現實約束下的各種收斂策略來解決設計問題。 1. 平面機構的合成過程和應用用於不同的環境。 在本研究中,構造和尺寸約束可以通過計算機輔助過程設計,並具有**通用設計文法 (Generic Design Grammar)**。 --- + {1}: 本研究中通稱為「創意性設計 (Creative Design)」。
# 方法論 - (1) --- + 正向合成:源自**創意性機構設計方法**,用**結構合成**找到新的機構類型,將此一般化鏈**尺寸合成**後,輸出成**機構表達式**。 + 反向分析:將**機構表達式**轉化為一般化鏈,並取得其圖譜分類。
# 方法論 - (2) ---
+ **創意性機構設計方法**: + **構造合成**:{Ph.D} 邱于庭, "On the Number Synthesis of Generalized Kinematic Chains," 2015 + **尺寸合成**:{Master Thesis} 李孟恭, "Django 網際框架在平面四連桿尺寸合成系統上的應用," 2015 + **機構表達式**:{Ph.D} P. Radhakrishnan, "Automated Design of Planar Mechanisms," 2014
# 方法論 - (3) --- 本研究中預想必須設計的資料轉換流程:
# 文獻比較 - 構造合成 - (1) --- 與 "On the Number Synthesis of Generalized Kinematic Chains" 比較。 | 方法 | 對照文獻 | 本研究 | |:----|:-------|:------| | 圖形表示法 | 鄰接矩陣 (Adjacency Matrix) | 邊集合 (Edge Set) | | 一般化鏈 | 無向圖 (Undirected Graph) | 相同 | | 縮圖 | 多重圖 (Multigraph) | 相同 | | 連桿類配 | 笛卡爾積 ({1}) 解不定方程式非負數整數解 | 相同 | | 縮桿類配 | 同上 | 方程式修正 | | 縮圖合成 | 同上 | 相同 | | 正規圖列舉 | 排列組合 (Permutation and Combination) | 相同 | | 特殊化流程 | 未包含 | 合併至標號列舉 | | 截斷桿檢查 | 截斷桿 (Cut-link) 檢查 | 相同 | + {1}: Cartesian product
# 文獻比較 - 構造合成 - (2) --- | 方法 | 對照文獻 | 本研究 | |:----|:--------|:------| | 退化檢查 | 退化 (Degenerate) 檢查 ({2}) | 相同 | | 平面圖檢查 | 庫拉托夫斯基定理 (Kuratowski's Theorem) | 左右平面測試 ({3}) | | 同構檢查 | 法蘭克簡易標記 ({4}) | VF2 演算法 ({5}) | | 圖形繪製 | 超圖 (Hyper Graph) 與線圖 (Line Graph) | 外環佈圖法 | | 程式實現 | C# | Python / Cython | | 使用者介面 | 單機 (Microsoft Windows Forms) | 單機 (PyQt) | | 公開原始碼 | 無 | 有 (Pyslvs) | + {2}: W.-M. Hwang and Y.-W. Hwang, “An algorithm for the detection of degenerate kinematic chains,” 1991. + {3}: Ulrik Brandes's Left-Right Planarity Test + {4}: Franke's Condensed Notation + {5}: "A (Sub)graph Isomorphism Algorithm for Matching Large Graphs," 2004
# 文獻比較 - 尺寸合成 --- 與 "Django 網際框架在平面四連桿尺寸合成系統上的應用" 比較。 | 方法 | 對照文獻 | 本研究 | |:----|:-------|:------| | 演算法 | 元啟發式隨機演算法 ({1}) | 相同 | | 機構類型 | 平面四連桿機構 | 平面連桿機構 | | 驗證式 | PLAP、PLLP | PLAP、PLLP、**PLPP**、**PXY** | | 驗證式配置 | 直接驗證式 | 自動配置機制與數值方法 | | 程式實現 | Python / Cython | Python / Cython | | 使用者介面 | 網際 (Django) | 單機 (PyQt) | | 公開原始碼 | 有 | 有 (Pyslvs) | + {1}: Metaheuristic Random Algorithm + 實數基因演算法 (Real-coded Genetic Algorithm) + 差分演化法 (Differential Evolution) + 螢火蟲演算法 (Firefly Algorithm)
# 文獻比較 - 機構表達式 --- 與 "Automated Design of Planar Mechanisms" 中的機構表達式比較。 | 方法 | 對照文獻 | 本研究 | |:----|:-------|:------| | 圖形 | 超圖 (Hypergraph) | 相同 | | 維度 | 平面 | 平面 | | 已實現的接頭種類 | R、P、RP ({1}) | 相同 | | 字面表達式 | 編碼、網址 | 字串、YAML | | 屬性簡化 | 無 | 有定義預設值、連桿名稱 | | 輸入接頭種類 | R | R、P、RP | | 程式實現 | C# | Python / Cython | | 使用者介面 | 網際 (Microsoft Silverlight) | 單機 (PyQt) | | 公開原始碼 | 有 (PMKS) | 有 (Pyslvs) | + {1}: 旋轉對、滑動對、旋轉滑動對
# 程式架構 ---
# 構造合成 --- + 連桿類配 (Link Assortment) 與縮桿類配 (Contracted Link Assortment) + 縮桿類配方程式修正 + 縮圖列舉 (Enumeration of Contracted Graphs) + 正規圖列舉 (Enumeration of Conventional Graphs) + 圖形過濾 (Graph Filter) + 外環佈圖法 (External Loop Layout) + 一般化 (Generalization) + **[程式演示]**
# 連桿類配與縮桿類配 --- + 一般化鏈轉為無向圖 (Undirected graph),其中連桿 (Links) 對應頂點 (Vertices, 又稱節點 Nodes); 接頭 (Joints) 對應邊 (Edges)。
+ 連桿類配 $[L_2, L_3, L_4, ...]$ 意指一般化鏈擁有 $L_2$ 個雙接頭連桿、 $L_3$ 個三接頭連桿、$L_4$ 個四接頭連桿,以此類推。 + 縮桿類配 $[C_1, C_2, C_3, ...]$ 意指一般化鏈擁有 $C_1$ 個獨立雙接頭連桿、 $C_2$ 個串列雙接頭連桿、$C_3$ 個串列雙接頭連桿,以此類推。
# 縮桿類配方程式修正 - (1) --- 原定義: + $i_{\max}$ 為縮桿類配的最大數目。 + $J_m$ 為多連桿之間的接頭數。 + **$J_m'$ 兩個多連桿間的接頭數。** + $J_m - J_m'$ 可確保連接數在範圍中。 $$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}$$
# 縮桿類配方程式修正 - (2) --- 本研究中修正了以下的方程式及定義: + $i$ 的搜尋範圍**不可超過**雙接頭桿的數量 $N_{L_2}$。 + $J_m'$ 為**平面圖中最大的連接數**,源自庫拉托夫斯基定理 $E = 3(V - 2)$。
$$i\_{\max} = \min(N\_{L\_2}, N\_{L\_2} - N_C + 2)$$
# 縮圖列舉 --- + 透過約束條件式可以使用笛卡爾積列舉 (Cartesian Product Enumeration) 取得連桿類配與縮桿類配的非負整數 ({$0, \mathbb{Z}^+$}) 之解。 + 縮圖 (Contracted Graph) 為一種平面多重圖 (Multigraph),兩對節點之間可以有多個邊,**只包含多連桿**。 + 每個節點不存在 3 以下的連接數,即不考慮雙接頭連桿。 + 由連桿類配 (忽略首項) 產生。如 $[x, 2, 1]$ 的縮圖為:
# 正規圖列舉 --- + 透過縮圖進行縮桿類配的列舉。 + 如連桿類配 $[4, 2, 1]$ 對縮桿類配 $[2, 1]$ 的列舉:
# 圖形過濾 - (1) --- 本研究中實作了下列演算法: + 平面圖檢查:Ulrik Brandes's Left-Right Planarity Test + 退化檢查:退化檢查演算法 (An Algorithm for the Detection of Degenerate Kinematic Chains, Hwang Wen-Miin and Yii-Wen Hwang) + 同構檢查:VF2 Algorithm + 反向分析連桿類配、縮桿類配
# 圖形過濾 - (2) --- + Ulrik Brandes's Left-Right Planarity Test 利用深度優先搜尋檢查同向與異向。 + VF2 Algorithm 利用完全圖 $K_5$ 進行子圖嵌入檢查。
# 外環佈圖法 --- + 本佈圖法為等分節點配置方式。 + 以搜尋最大路徑為基礎,逐一排入節點。
# 一般化 --- 此演算法將機構表示式 (Mechanism Expression) 轉化為一般化鏈的圖形。
# **[程式演示]** ---
# 機構表達式 --- + Planar Mechanism Kinematic Simulator + 定義 + Pyslvs
# Planar Mechanism Kinematic Simulator --- + 本研究中的機構表達式改良自前述文獻的實作 Planar Mechanism Kinematic Simulator (PMKS) 的表達式。 + 此表達式視連桿為節點 (Node),視接頭為邊 (Edge),與一般化鏈圖形**相同**。 + 此表達式為**超圖 (Hypergraph)**,邊可連接多個節點,簡化多重接頭的表示法。
# 定義 --- 每個點 (Point) 包含下列屬性: + 連桿 (Links):包含的連桿,使用連桿標籤 (Label) 標記。 + 類型 (Type):接頭的類型,可使用 R、P、RP。 + XY 位置 (X and Y position):在暫態中的位置,代表尺寸。 + 當前位置 (Current position):在當前狀態中的位置(模擬用)。 + 角度 (Angle):滑動接頭的滑槽傾斜角。
# Pyslvs - (1) --- + 本研究實作的系統 Pyslvs 中使用的字串表達式。 ```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) --- 機構表示法的泛用約束模式:
多連桿
滑動接頭
# 尺寸合成 --- + 驗證機制 - 幾何約束求解核心 + 驗證機制 - 幾何模組 + 自動配置機制 (Automatic Configuration Mechanism) + 一般化鏈配置 (Configuration of Generalized Chain) + 元啟發式隨機演算法 (Metaheuristic Random Algorithm) + **[程式演示]**
# 驗證機制 - 幾何約束求解核心 --- 本研究中採取的數值方法源自於兩個 CAD 核心: | 特性 | Solvespace | Sketch Solve | |:----|:-----------|:-------------| | 數值方法 | Newton-Raphson Method | BFGS Algorithm ({1}) | | 圖形介面 | GTK-- and OpenGL | 無 | | 程式語言 | C++ | C++ | | 端口 | SWIG / Cython ({2}) | Cython | + {1}: Broyden-Fletcher-Goldfarb-Shanno Algorithm + {2}: 本研究最後採用易於維護的 Cython。
# 驗證機制 - 幾何模組 --- 本研究中沿用 PLAP 與 PLLP 模組,加入了 PLPP 與 PXY 以解決部分滑動接頭。
PLAP
PLLP
PLPP
PXY
# 自動配置機制 - (1) --- 此演算法將構建表達式堆棧 (Expression Stack) 來指示求解步驟。
# 自動配置機制 - (2) --- + **完全配置**:可完全求得位置。 + **部分配置**:無法搭配輸入軸在 5 連桿以上的迴路,其餘部分以數值方法求得。
# 一般化鏈配置 --- 拓樸設定: 1. 接地桿 (Grounded link) 1. 輸入列表 (Input list) 1. 自定點 (Custom points) 1. 多重接頭 (Multiple joints) 1. 目標點 (Target points) 1. 初始位置 (Initial positions) 1. 上限與下限 (Upper and lower bounds) 基因資訊: 1. 接地接頭 (Grounded joints) 1. 連桿長 (Length of links) 1. 輸入列表 (Input list)
# 元啟發式隨機演算法 --- + 實數基因演算法 (Real-coded Genetic Algorithm) + 差分演化法 (Differential Evolution) + 螢火蟲演算法 (Firefly Algorithm) 其中差分演化法具有較好的收斂性能。 --- + 經實測,**完全配置**的驗證式運算速度較**部分配置**的方案更快速。 + 以下為相同設定與運行環境的**差分演化法**在 8 個路徑目標點計算 1000 代所需的時間。 | 計算結果 | **完全配置**的八連桿 | **部分配置**的六連桿 | |:------:|:-----------------:|:------------------:| | 節點位置數量 | 6 | 1 + 3 (數值方法) | | 花費時間 | 22.11s | 110.62s |
# **[程式演示]** ---
# 結論 --- + 結論 + 未來目標
# 結論 - (1) --- 1. 本研究的目的是將**構造合成**和**尺寸合成**的設計流程與一種**機構表示法**相結合。其中包括適用於旋轉關節的平面連桿機構輸入的通用尺寸合成設計流程。 1. 本研究中的機構表達基於 PMKS 表示法的語法。通過在尺寸合成配置中的通用演算法和資訊選擇,可以對現有機構重新設計部分特徵,而不是對創意設計流程進行整體操作。 1. 在尺寸合成過程中,自動配置演算法是一種新型的通用路徑求解機制,而非特定的位置分析方法。自動解析機制可以通過構建表達式堆棧找到解決方案步驟,這比手動重新設計分析方法更通用。
# 結論 - (2) --- 本研究最後實現的設計流程:
# 未來目標 --- 本研究未來可延伸的項目: + **網際平台**:透過網際分享資訊,支援多人協作設計。 + **支援更多類型的接頭種類**:加入其他平面接頭,如齒輪對。 + **一般化鏈的合併與簡化**:愈龐大的圖形需要愈久的列舉時間,較大的結構可藉由兩個較小的子圖獲得。 + **圖譜資料庫**:基於編號過的圖譜資料庫,能夠結合大數據應用於分析結構應用的廣泛程度。 + **拓撲描述**:機構結構的描述能應用於產品文檔或專利描述的解釋性文本,並可自動生成。 + **相依性尺寸合成**:連桿的長度可作為相依參數,設計出更好的配置。 + **平面連桿機構的輔助組裝**:在空間應用中,輔助層配置可以幫助其他桿件的避障。