簡易檢索 / 詳目顯示

研究生: 黃仕華
Huang, Shih-Hua
論文名稱: 應用類電磁演算法於路徑規劃
An Electromagnetism-like Mechanism Algorithm for Path Planning
指導教授: 呂藝光
Leu, Yih-Guang
學位類別: 碩士
Master
系所名稱: 電機工程學系
Department of Electrical Engineering
論文出版年: 2016
畢業學年度: 104
語文別: 中文
論文頁數: 65
中文關鍵詞: 類電磁演算法路徑規劃路徑平滑三次樣條插值
英文關鍵詞: Electromagnetism-like Mechanism Algorithm, path planning, path smoothing, Cubic Splines Interpolation
DOI URL: https://doi.org/10.6345/NTNU202204083
論文種類: 學術論文
相關次數: 點閱:87下載:13
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 本論文提出一個新的類電磁路徑規劃演算法,透過類電磁演算法的改造與改良使該演算法可以應用在路徑規劃上。本研究使用不同的地圖編碼處理方式來解決傳統路徑規劃問題在預處理步驟會遇到的權衡問題。為了避免路徑規劃演算法產生使載具無法順利通行的尖銳角度路徑,本研究採用三次樣條插值方法來平滑路徑,同時亦比較了貝茲曲線以及三次樣條插值方法,以找出較適當整合至類電磁演算法的方法。最後,將本研究所提出的類電磁路徑規劃演算法和同是啟發式演算法的粒子群集路徑規劃演算法來進行比較,以驗證所提出的演算法之效能。

    In this thesis, we propose a new path planning method by using an electromagnetism-like mechanism algorithm. We use different encoding methods to solve a trade-off problem which the traditional path planning method always deal with. In order to make vehicles move around in the safe way, a path smoothing method is integrated with the electromagnetism-like mechanism algorithm. Moreover, we compare two path smoothing methods, including Bezier Curve and Cubic Splines Interpolation, to find the better method which makes the vehicle turn smoothly and move around in the effective way. Finally, to demonstrate the efficiency of the proposed approach, we compare the proposed path planning algorithm with particle swarm optimization algorithm, which is a well-known heuristic algorithm.

    摘 要 I ABSTRACT II 致謝 III 目錄 IV 圖目錄 VII 表目錄 IX 第一章 緒論 1 1.1研究背景與動機 1 1.2研究目的 2 1.3研究方法 3 1.4研究架構 4 第二章 文獻探討與回顧 5 2.1路徑規劃起源 5 2.2Dijkstra演算法 5 2.3A*演算法 6 2.4螞蟻演算法 7 2.5快速隨機搜尋樹 8 2.6啟發式演算法 9 2.7基因演算法 10 2.8粒子群集演算法 11 2.9類電磁演算法 13 第三章 類電磁演算法應用於路徑規劃 15 3.1前言 15 3.2類電磁演算法 16 3.3類電磁演算法應用於路徑規劃的改進 24 3.3.1地圖編碼方式 24 3.3.2初始化加速方法 26 3.3.3控制點過度聚集之問題處理 26 3.3.4加速疊代計算次數方法 28 3.3.5預防碰撞之處理方式 29 第四章 路徑平滑 31 4.1前言 31 4.2貝茲曲線 31 4.3三次樣條插值 33 第五章 實驗結果 39 5.1實驗介紹 39 5.2參數比較實驗 43 5.3效能比較實驗 47 5.3.1實驗地圖1 49 5.3.2實驗地圖2 52 5.3.3實驗地圖3 55 5.4收斂過程比較實驗 58 第六章 結論與未來展望 60 6.1結論 60 6.2未來展望 60 參考文獻 61 自傳 65 學術成就 65

    [1] E. W. Dijkstra, "A note on two problems in connexion with graphs", Numerische Mathematik. 1, June 1959, pp. 269–271.
    [2] P. E. Hart, N. J. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," in IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, July 1968.
    [3] Yanrong Hu, S. X. Yang, Li-Zhong Xu and M. Q. H. Meng, "A Knowledge Based Genetic Algorithm for Path Planning in Unstructured Mobile Robot Environments," Robotics and Biomimetics, 2004. ROBIO 2004. IEEE International Conference on, Shenyang, 2004, pp. 767-772.
    [4] Ş. İ. Birbil and S.-C. Fang, "An Electromagnetism-like Mechanism for Global Optimization," Journal of Global Optimization, vol. 25, pp. 263-282, 2003
    [5] Janet Heine Barnett, "Early Writings on Graph Theory: Euler Circuits and The K¨onigsberg Bridge Problem An Historical Project" Colorado State University – Pueblo,8 December 2005
    [6] M. Held and R. M. Karp, "A dynamic programming approach to sequencing problems," Journal of the Society for Industrial and Applied Mathematics, pp. 196-210, 1962.
    [7] M. Dorigo, V. Maniezzo and A. Colorni, "Ant system: optimization by a colony of cooperating agents," in IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 26, no. 1, pp. 29-41, Feb 1996.
    [8] 孫仕勳,“基於能量螞蟻演算法之路徑規劃與其在雲端平台運算的實現”,國立台灣師範大學電機工程學系,碩士論文,2015
    [9] S. M. LaValle, "Rapidly-exploring random trees: A new tool for path planning," 1998.
    [10] A. E. Eiben, P.-E. Raue, and Z. Ruttkay, "Genetic algorithms with multi-parent recombination," in International Conference on Parallel Problem Solving from Nature, 1994, pp. 78-87.
    [11] Yang Linquan, Luo Zhongwen, Tang Zhonghua and Lv Weixian, "Path planning algorithm for mobile robot obstacle avoidance adopting Bezier curve based on Genetic Algorithm," 2008 Chinese Control and Decision Conference, Yantai, Shandong, 2008, pp. 3286-3289.
    [12] J. Kennedy, "Particle Swarm Optimization," in Encyclopedia of Machine Learning, C. Sammut and G. I. Webb, Eds., ed Boston, MA: Springer US, 2010, pp. 760-766.
    [13] Sheetal and G. K. Venayagamoorthy, "Unmanned vehicle navigation using swarm intelligence," Intelligent Sensing and Information Processing, 2004. Proceedings of International Conference on, 2004, pp. 249-253.
    [14] Q. z. Ma and X. j. Lei, "The application of hybrid orthogonal particle swarm optimization in robotic path planning," 2010 Sixth International Conference on Natural Computation, Yantai, Shandong, 2010, pp. 3536-3540.
    [15] Ş. İ. Birbil, S.-C. Fang, and R.-L. Sheu, "On the Convergence of a Population-Based Global Optimization Algorithm," Journal of Global Optimization, vol. 30, pp. 301-318, 2004.
    [16] C. Y. Tsai, H. L. Hung and S. H. Lee, "Electromagnetism-like method based blind multiuser detection for MC-CDMA interference suppression over multipath fading channel," 2010 International Symposium on Computer, Communication, Control and Automation (3CA), Tainan, 2010, pp. 470-475.
    [17] J. C. Chen, "Partial transmit sequences for PAPR reduction of OFDM signals with stochastic optimization techniques," in IEEE Transactions on Consumer Electronics, vol. 56, no. 3, pp. 1229-1234, Aug. 2010.
    [18] Qing Wu, Chun-Jiang Zhang, L. Gao and X. Li, "Training neural networks by electromagnetism-like mechanism algorithm for tourism arrivals forecasting," Bio-Inspired Computing: Theories and Applications (BIC-TA), 2010 IEEE Fifth International Conference on, Changsha, 2010, pp. 679-688.
    [19]Wu, Peitsang, Kung-Jiuan Yang, and Yung-Yao Hung. "The study of electromagnetism-like mechanism based fuzzy neural network for learning fuzzy if-then rules." Knowledge-Based Intelligent Information and Engineering Systems. Springer Berlin Heidelberg, 2005.
    [20] W. Yaonan, Y. Yimin, Y. Xiaofang, Y. Feng and W. Shuning, "A Model Predictive Control Strategy for Path-Tracking of Autonomous Mobile Robot Using Electromagnetism-Like Mechanism,"Electrical and Control Engineering (ICECE), 2010 International Conference on, Wuhan, 2010, pp. 96-100.
    [21] C. L. Kuo, C. H. Chu, Y. Li, X. Li and L. Gao, "Optimized tool path planning in 5-axis flank machining using electromagnetism-like algorithms," 2014 IEEE International Conference on Industrial Engineering and Engineering Management, Bandar Sunway, 2014, pp. 973-977.
    [22] F. K. Chang and C. H. Lee, "Design of Fractional PID Control via Hybrid of Electromagnetism-Like and Genetic Algorithms," 2008 Eighth International Conference on Intelligent Systems Design and Applications, Kaohsiung, 2008, pp. 525-530.
    [23] P. Wu, K. J. Yang and B. Y. Huang, "A Revised EM-like Mechanism for Solving the Vehicle Routing Problems," Innovative Computing, Information and Control, 2007. ICICIC '07. Second International Conference on, Kumamoto, 2007, pp. 181-181.
    [24] C. C. Chang, C. Y. Chen, C. W. Fan, H. C. Chao and Y. H. Chou, "Quantum-Inspired Electromagnetism-Like Mechanism for Solving 0/1 Knapsack Problem," Information Technology Convergence and Services (ITCS), 2010 2nd International Conference on, Cebu, 2010, pp. 1-6.
    [25] S. Yun, "Research of Big Data Analysis on Rough Set and Electromagnetism-Like Mechanism Algorithm," Computer and Information Technology (CIT), 2014 IEEE International Conference on, Xi'an, 2014, pp. 923-926.
    [26] Y. H. Chou, C. Y. Chen, C. H. Chiu and H. C. Chao, "Classical and quantum-inspired electromagnetism-like mechanism and its applications," in IET Control Theory & Applications, vol. 6, no. 10, pp. 1424-1433, July 5 2012.
    [27] A. R. Soltani, H. Tawfik, J. Y. Goulermas, and T. Fernando, "Path planning in construction sites: performance evaluation of the Dijkstra, A∗, and GA search algorithms," Advanced Engineering Informatics, vol. 16, pp. 291-303, 2002.
    [28] C. T. Cheng, K. Fallahi, H. Leung and C. K. Tse, "Cooperative path planner for UAVs using ACO algorithm with Gaussian distribution functions," 2009 IEEE International Symposium on Circuits and Systems, Taipei, 2009, pp. 173-176.
    [29] N. Ganganath and C. T. Cheng, "A 2-Dimensional ACO-Based Path Planner for Off-Line Robot Path Planning," Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), 2013 International Conference on, Beijing, 2013, pp. 302-307.
    [30] A. R. Forrest, "Interactive interpolation and approximation by Bézier polynomials," The Computer Journal, vol. 15, pp. 71-79, 1972.
    [31] S. McKinley and M. Levine, "Cubic spline interpolation," College of the Redwoods, vol. 45, pp. 1049-1060, 1998.

    下載圖示
    QR CODE