分群演算法應用於自動出入料裝置路徑規劃研究

NCUIR > Engineering College > Graduate Institute of Mechanical Engineering > Electronic Thesis & Dissertation > Item 987654321/87015

Please use this identifier to cite or link to this item: https://ir.lib.ncu.edu.tw/handle/987654321/87015

Title:	分群演算法應用於自動出入料裝置路徑規劃研究
Authors:	陳聖學;Sheng Shiue, Chen
Contributors:	機械工程學系
Keywords:	路徑規劃;分群演算法;K-平均演算法;Path Planning;Clustering Algorithm;K-means Algorithm
Date:	2021-10-06
Issue Date:	2021-12-07 13:43:06 (UTC+8)
Publisher:	國立中央大學
Abstract:	隨著高科技生產技術演進及高速網路基礎建設普及，以遠端網路控制及自動化電腦排程以降低生產及管理成本的現象，在現代工廠中越見普遍。當硬體設施趨於完備後，欲再降低時間以及金錢成本的方式不外為增進演算法效能，藉此降低硬體運算負擔及更快速的取得可接受的成果，若解決方案本身具有特有之限制條件，開發可適用特殊狀況之非傳統演算法便愈發重要。本文以受攜帶料件上限，且具有往復回程補充材料能力的數值加工機或機械手臂為討論目標，求其路徑規劃的序列解。由於此類問題運作環境近似特化的車輛途程問題(Vehicle Routing Problem, VRP)，無法在可預期的有限時間內取得最佳解，故本研究選擇透過優化既有分群演算法並結合遞迴之概念，以求得路徑選擇中之近似解，期望降低硬體計算負擔及時間複雜度，使之應用於各式設計上具有特殊限制之場域，減少運算時間並獲得更佳之結果。本研究利用C#語言撰寫程式，以K-means演算法為核心概念，設計二元離群值初始化方法，利用遞迴方式反覆迭代，直至遍歷所有工作點為止。在亂數產生資料集下，與貪婪演算法(Greedy algorithm)、z形排列法(Zipzap sorting method)、標準K-means演算法比較。本研究之演算方式在工作點數量於二位數以上時，計算出之路徑長度穩定低於與之比較的其他演算法，運算時間遠低於完全歸納法(Complete induction)；相較於現有的路徑規劃工具，亦具有運算時間優勢，適合部署於資源受限的SoC嵌入式裝置之上。 ;Owing to the universality of high-tech production technology and high-speed internet infrastructure, remote manufacturing and automatically process scheduling has been much more common these days in modern factory. To reduce both time and financial costs, we must improve the efficiency of algorithm, which can curtail both computing time and obtain majorized and operational path sequence. Hence, developing specialized solution algorithm for restricted condition can’t be more important nowadays. This research aims to discuss the sequential solution of computer numerical control machine or robotic arm that is subject to designed capacity, which requires suppling materials from one depot through reciprocating motion. Since this kind of problem is similar to the specialized Vehicle Routing Problem (VRP), it is impossible to obtain the best solution in non-deterministic polynomial time. Therefore, we decided to create an algorithm by improving exiting algorithm and combine it with other algorithms for this research. This algorithm should obtain approximate solution in all feasible path sequence and reduce both computational burden and time complexity. The core concept of this algorithm is based on K-means algorithm and is implemented by C# in this research. The initialized method this algorithm is a customized binary outliers’ method. After that, the algorithm will recursively pick appropriate nodes as clusters and renew the unsatisfied node list till the list is completely traversed. By comparison, this algorithm is confirmed to achieve better performance on path cost than Greedy algorithm, Zipzap sorting method, or typical K-means algorithms when the number of unsorted nodes is above a dozen. Furthermore, the computation time of this algorithm is also far below sorting nodes by complete induction method, which can be deemed as predictable finite time.
Appears in Collections:	[Graduate Institute of Mechanical Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	280	View/Open

社群 sharing

Loading...