應用類電磁演算法於路徑規劃

An Electromagnetism-like Mechanism Algorithm for Path Planning

黃仕華(Huang Shih-Hua)

指導教授 ： 呂藝光

國立臺灣師範大學/科技與工程學院/電機工程學系/碩士(2016年)

https://doi.org/10.6345/NTNU202204083

摘要

本論文提出一個新的類電磁路徑規劃演算法，透過類電磁演算法的改造與改良使該演算法可以應用在路徑規劃上。本研究使用不同的地圖編碼處理方式來解決傳統路徑規劃問題在預處理步驟會遇到的權衡問題。為了避免路徑規劃演算法產生使載具無法順利通行的尖銳角度路徑，本研究採用三次樣條插值方法來平滑路徑，同時亦比較了貝茲曲線以及三次樣條插值方法，以找出較適當整合至類電磁演算法的方法。最後，將本研究所提出的類電磁路徑規劃演算法和同是啟發式演算法的粒子群集路徑規劃演算法來進行比較，以驗證所提出的演算法之效能。

關鍵字

類電磁演算法 ； 路徑規劃 ； 路徑平滑 ； 三次樣條插值

並列摘要

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.

並列關鍵字

Electromagnetism-like Mechanism Algorithm ； path planning ； path smoothing ； Cubic Splines Interpolation

參考文獻

[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