研究生: |
黃仕華 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.
[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.