本論文所提出一改良型螞蟻演算法應用於路徑規劃，解決規劃最佳路徑時容易出現區域最佳解的問題。原先的蟻群系統演算法(Ant Colony System , ACS)雖收斂快速，卻極易陷入區域解，因此，本論文將提出一種改良型螞蟻演算法，透過所提出之費洛蒙更新機制，包含部分費洛蒙更新以及反向費洛蒙更新，使得螞蟻具有更多探索新路徑的能力，減少只追隨同一路徑的機會。為了驗證論文中所提出之方法可以確實提升路徑規劃之精確度，將會與傳統ACS比較，以多種不同路徑進行規劃與比較其性能。為了縮短運算時間，提升計算的效率，本論文所提出之改良型螞蟻演算法將以DE2-70多媒體開發平台，利用FPGA電路加以實現。實驗結果證明以全硬體設計方式可以用較少的處理時間獲得路徑規劃結果，確實提升嵌入式應用系統之效能。

Although traditional ant colony system (ACS) has the ability of fast convergence, it tends to fail into local optima. To solve this problem, this thesis proposes an improved ant colony system algorithm for path planning by establishing two new mechanisms for pheromone updating, including partial pheromone updating and opposite pheromone updating. As a result, the ability of global searching of the improved ACS can be significantly enhanced in comparison to the traditional ACS algorithms in deriving an optimal path. Simulation results show the proposed approach has a better performance in terms of shortest distance, mean distance, and successful rate of the optimal paths than those obtained by the traditional ACS algorithms. To further reduce the computation time, the improved ant colony system algorithm for path planning is realized on FPGA circuit using a DE2-70 multimedia development board to verify the practicability of the proposed algorithm. Experimental results show that the execution efficiency of path planning is significantly improved by the full hardware design for embedded applications.

[1] J. Barraquand, B. Langois, and J. C. Latombe, “Numerical potential field techniques for robot path planning,” IEEE Trans. on System, Man and Cybernetics, vol. 22, no. 2, pp. 224-241, 1992.
[2] M. Bennewitz, W. Burgard, and S. Thrun, “Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots,” Robotics and Autonomous Systems, vol. 41, pp. 89-99, 2002.
[3] J. Guo, L. Liu, Q. Liu, and Y. Qu, “An improvement of D* algorithm for mobile robot path planning in partial unknown environment,” in Proc. of the Second International Conference on Intelligent Computation Technology and Automation, Wuhan, China, 10-11 Oct. 2009, vol. 3, pp. 394-397.
[4] S. Liu, Y. Tian, and J. F. Liu, “Multi mobile robot path planning based on genetic algorithm,” Intelligent Control and Automation, WCICA, China, 2004, pp. 4706-4709.
[5] C. H. Fan, W. D. Chen, and Y. Xi, “Hopfield neural networks for path planning in dynamic and unknown environments,” Control Theory and Applications, vol. 21, no. 3, pp. 345-350, 2004.
[6] M. Dorigo, “The ant system: Optimization by a colony of cooperating agents,” IEEE Trans. on Systems, Man, and Cybernetics Part B: Cybernetics, vol. 26, no. 2, pp. 1-13, 1996.
[7] M. Dorigo and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Trans. on Evolutionary Computation, vol. 1, no. 1, pp. 53-66, 1997.
[8] J. P Laumond, “Finding collision-free smooth trajectories for a non-holonomic mobile robot,” in Proc. of the 10th Int. Joint Conf. Artificial Intelligence, France, 1987, pp. 1120-1123.
[9] D. Gong and X. Ruan, “A hybrid approach of GA and ACO for TSP,” in Proc. of the World Congress on Intelligent Control and Automation, Beijing, China, Jun. 2004, pp. 2068-2072.
[10] S. Zhao and M. Li, “Path planning of inspection robot based on ant colony optimization algorithm,” in Proc. of the International Conference on Electrical and Control Engineering (ICECE), China, Jun. 2010, pp. 1474-1477.
[11] M. Yuan, S. Wang, and P. Li, “A model of ant colony and immune network and its application in path planning,” Industrial Electronics and Applications, China, Jun. 2008, pp. 102-107.
[12] Y. Z. Cong and S. G. Ponnambalam, “Mobile robot path planning using ant colony optimization,” in Proc. of the International Conference on Advanced Intelligent Mechatronics, Singapore, July 14-17, 2009, pp. 851-856.
[13] http://sjchen.im.nuu.edu.tw/MachineLearning/final/Opt_AntAlgo.pdf
[14] H. D. Pour and N. Mostafa, “Solving the facility and layout and location problem by ant-colony optimization-meta heuristic,” International Journal of Production Research, vol. 44, no. 23, pp. 5187-5196, Dec, 2006.
[15] B. Bullnheimer, R. F. Hartl, and C. Strauss, “An improved ant system algorithm for vehicle routing problem,” Sixth Viennese workshop on Optimal Control Dynamic Games, Nonlinear Dynamics and Adaptive Systems, Vienna, Austria, May 1999, pp.319-328.
[16] K. M. Sim and W. H. Sun, “Ant colony optimization for routing and load-balancing: Survey and new directions,” IEEE Trans. on Systems, Man, and Cybernetics Part A: Systems and Humans, vol. 33, no.5, pp. 560-572, Sep. 2003
[17] S. Y. Lee, E. K. Kim, and H. G. Yun “DNA computing adopting DNA coding method for Hamiltonian path problem,” in Proc. of the International Conference on Artificial Intelligence IC-AI 2003, Las Vegas, Nevada, USA, 2003, pp. 154-157.
[18] 黃建富，以蟻群演算法為基礎之群組機器人路徑規劃，國立雲林科技大學電機工程系碩士班碩士論文，2008。
[19] 林玟玲，以軟硬體協同設計之混合型即時影像物體追蹤系統，淡江大學電機工程學系碩士班碩士論文，2011。
[20] Altera Corporation, SOPC Builder User Guide, 2003.
[21] Altera Corporation, Designing With Nios & SOPC Builder, 2003。
[22] 李世安、翁仲緯、賴鈺婷、翁慶昌，“影像硬體加速器之設計”，2009 中華民國系統科學與工程研討會，淡江大學，2009年6月。
[23] C. C. Hsu, S. A. Li, and W. L. Lin “Real-time object tracking based on hardware/software co-design,” in Proc. of the 2011 International conference on Service and Interactive Robotics (SIRCON 2011), Taichung, Taiwan, Dec. 20-21, 2011, pp. 167-170.
[24] C. C. Hsu, R. Y. Hou, and W. Y. Wang “Path planning for mobile robots based on improved ant colony optimization,” in Proc. of the 2013 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Manchester, Oct. 13-16, 2013, pp. 2777-2782.
[25] 李世安，即時目標影像追蹤之SoPC設計，淡江大學電機工程學系博士班博士論文，2008。
[26] C. C. Tsai, H. C. Huang, and C. K. Chan “Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation” IEEE Trans. on industrial electronics, vol. 58, no. 10, pp. 4813-4821, 2011.
[27] M. Danesh and M. R. Abazari “Optimize path planning of a planar parallel robot to avoid obstacle collision using genetic algorithm,” in Proc. of the 2014 Iranian Conference on Intelligent Systems, Bam, Feb. 4-6, 2014, pp. 1-4.
[28] Altera多媒體發展平台DE2-70網址，網址: http://www.altera.com/education/univ/materials/boards/de2-70/unv-de2-70-board
[29] Altera Corporation, URL:http://www.terasic.com.tw/tw/
[30] Terasic, THDB_LTM_User Manual, Document Version 1.4.1, 2011.
[31] K. Sugihara and J. Smith “Genetic algorithms for adaptive motion planning of an autonomous mobile robot,” in Proc. of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation, Monterey, Jul. 10-11, 1997, pp.138-143.