本論文探討以蟻群演算法(Ant Colony Optimization, ACO)和增強型蟻群演算法(Enhanced Ant Colony Optimization, EACO)對行動機器人做三維全域最佳化路徑之規劃。ACO演算法最早由Dorigo所提出，其中之轉換機率乃是由費洛蒙濃度和兩點線段長度的倒數所組成。本研究為改良三維地圖中，因懸崖所造成的死點問題(Deadlock)、探索率不足以及收斂速度較慢，所採用的EACO則是針對轉換機率的兩個參數進行修正： (a) 在兩點線段長度公式中，加強海拔參數的比重，(b) 在費洛蒙濃度公式中，加強局部費洛蒙更新機制，(c) 在判斷式中加入了爬坡角度限制。EACO與ACO相較之下，EACO收斂速度較快、路徑最多縮短了10個百分比，而在探索率則平均提高了10個百分比。經電腦模擬證明，EACO能在複雜三維地圖的機器人路徑規劃環境中，可準確的求解出最短全域路徑最佳解。

This study discusses the planning of a three-dimensional global optimization path for robots through the Ant Colony Optimization (ACO) and the Enhanced Ant Colony Optimization (EACO). In ACO, which was first proposed by Dorigo, the transition probability is composed of pheromone concentration and the length of two segments. This study intended to improve the deadlock caused by the cliffs, insufficient exploration rates, and slower convergence rates in the three-dimensional map, while the EACO targeted the correction of two parameters in transition probability: (a) Using the formula of the length of two segments, the weight of the altitude parameter was strengthened; (b) Using the pheromone concentration formula, the local pheromone updating mechanism was strengthened; (c) Using the determination formula, the ramp angle restrictions were added. A comparison of EACO and ACO shows that EACO has the advantages including faster convergence rates, shortening the path by up to 10%, and increasing the exploration rate by 10%. Evidence from computer simulation shows the EACO can accurately derive the best solution (i.e., the shortest global path) in the complex three-dimensional robot path planning environment.

[1] Z. Q. Liu, Y. S. Zhang, Z. Q. Zhen, Z. P. Han, and W. Ni, “A novel broad beamwidth conformal antenna on unmanned aerial vehicle,” IEEE Antennas and Wireless Propagation Letters, vol. 11, pp. 196-199, 2012.
[2] B. Herisse, T. Hamel, R. Mahony, and F. X. Russotto, “Landing a VTOL unmanned aerial vehicle on a moving platform using optical flow,” IEEE Trans. Robotics, vol. 28, no. 1, pp. 77-89, 2012.
[3] V. Roberge, M. Tarbouchi, and G. Labonté, “Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning,” IEEE Trans. Industrial Informatics, vol. 9, no. 1, pp. 132-141, 2013.
[4] Y. Fu, M. Ding, C. Zhou, and H. Hu, “Route planning for unmanned aerial vehicle (UAV) on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization,” IEEE Trans. Systems, Man, and Cybernetics : system, vol. 43, no. 6, pp. 1451-1465, 2013.
[5] L. Paull, C. Thibault, A. Nagaty, M. Seto, and H. Li, “Sensor-driven area coverage for an autonomous fixed-wing unmanned aerial vehicle,” IEEE Trans. Cybernetics, vol. 44, no. 9, pp. 1605-1618, 2014.
[6] L. Lin and M. A. Goodrich, “Hierarchical heuristic search using a gaussian mixture model for UAV coverage planning,” IEEE Trans. Cybernetics, vol. 44, no. 12, pp. 2532-2544, 2014.
[7] K. Sundar and S. Rathinam, “Algorithms for routing an unmanned aerial vehicle in the presence of refueling depots,” IEEE Trans. Automation Science and Engineering, vol. 11, no. 1, pp. 287-294, 2014.
[8] S. Islam, P. X. Liu, and A. E. Saddik, “Robust control of four-rotor unmanned aerial vehicle with disturbance uncertainty,” IEEE Trans. Industrial Electronics, vol. 62, no. 3, pp. 1563-1571, 2015.
[9] X. Dong, B. Tu, Z. Shi, and Y. Zhong, “Time-Varying formation control for unmanned aerial vehicles: theories and applications,” IEEE Trans. Control Systems Technology, vol. 23, no. 1, pp. 340-348, 2015.
[10] B. Zhu and W. Huo, “3-D path following control for a model scaled autonomous helicopter,” IEEE Trans. Control Systems Technology, vol. 22, no. 5, pp. 1927-1934, 2014.
[11] D. Scaramuzza, M. C. Achtelik, L. Doitsidis, F. Friedrich, E. Kosmatopoulos, A. Martinelli, M. W. Achtelik, M. Chli, S. Chatzichristofis, L. Kneip, D. Gurdan, L. Heng, H. L. Gm, S. Lynen, M. Pollefeys, A. Renzaglia, R. Siegwart, J. C. Stumpf, P. Tanskanen, C. Troiani, S. Weiss, and L. Meier, “Vision controlled micro flying robots: from system design to autonomous navigation and mapping in GPS-denied environments,” IEEE Trans. Robotics & Automation Magazine, vol. 21, no. 3, pp. 26-40, 2014.
[12] S. Zhao, Z. Hu, M. Yin, K. Z. Y. Ang, P. Liu, F. Wang, X. Dong, F. Lin, B. M. Chen, and T. H. Lee, “A robust real-time vision system for autonomous cargo transfer by an unmanned helicopter,” IEEE Trans. Industrial Electronics, vol. 62, no.2 pp. 1210-1219, 2015.
[13] Y. Wang, W. Yan and J. Li, “Passivity-Based formation control of autonomous underwater vehicles,” IET Control Theory Appl, vol. 6, iss. 4, pp. 518-525, 2011.
[14] D. Zhu, H. Huang, and S. X. Yang, “Dynamic task assignment and path planning of multi-AUV system based on an improved self-organizing map and velocity synthesis method in three-dimensional underwater workspace,” IEEE Trans. Cybernetics, vol. 43, no. 2, pp. 504-514, 2013.
[15] L. Paull, S. Saeedi, M. Seto, and H. Li, “Sensor-Driven online coverage planning for autonomous underwater vehicles,” IEEE Trans. Mechatronics, vol. 18, no. 6, pp. 1827-1838, 2013.
[16] Y. S. Chen and Y. W. Lin, “Mobicast routing protocol for underwater sensor networks,” IEEE Sensors Journal, vol. 13, no. 2, pp. 737-749, 2013.
[17] M. F. Fallon, J. Folkesson, H. McClelland, and J. J. Leonard, “Relocating underwater features autonomously using sonar-based SLAM,” IEEE Journal of Oceanic Engineering, vol. 38, no. 3, pp.500-513, 2013.
[18] J. Han, J. Ok, and W. K. Chung, “An ethology-based hybrid control architecture for an autonomous underwater vehicle for performing multiple tasks,” IEEE Journal of Oceanic Engineering, vol. 38, no. 3, pp.514-521, 2013.
[19] G. Galben. “New three-dimensional velocity motion model and composite odometry inertial motion model for local autonomous navigation,” IEEE Trans. Vehicular Technology, vol. 60, no. 3, pp. 771-780, 2011.
[20] F. Belkhouche and B. Bendjilali, “Reactive path planning for 3-d autonomous vehicles,” IEEE Trans. Control Systems Technology, vol. 20, no. 1, pp. 249-256, 2012.
[21] A. Elfes, “Using occupancy grids for mobile robot perception and navigation,” IEEE Trans. Computer Society, vol. 22, no. 6, pp. 46-57, 1989.
[22] T. N. Nguyen, B. Michaelis, A. H. Ayoub, M. Tornow, and M. M. Meinecke, “Stereo-Camera-Based urban environment perception using occupancy grid and object tracking,” IEEE Trans. Intelligent Transportation Systems, vol. 13, no. 1, pp.154-165, 2012.
[23] M. Perrollaz, J. D. Yoder, A. Nègre, A. Spalanzani, and C. Laugier, “A visibility-based approach for occupancy grid computation in disparity space,” IEEE Trans. Intelligent Transportation Systems, vol. 13, no. 3, pp.1383-1393, 2012.
[24] H. Li, M. Tsukada, F. Nashashibi, and M. Paren, “Multivehicle cooperative local mapping: a methodology based on occupancy grid map merging,” IEEE Trans. Intelligent Transportation Systems, vol. 15, no. 5, pp. 2089-2100, 2014.
[25] T. Tsuji, Y. Tanaka, P. G. Norasso, V. Sanguineti, and M. Kaneko, “Bio mimetic trajectory generation of robots via artificial potential field with time base generator,” IEEE Trans. System Man and Cybernetic-part: C, vol. 32, no. 4, pp. 426-439, 2002.
[26] G. Zhu, Y. Li, and P. Wen, “Analysis and classification of sleep stages based on difference visibility graphs from a single channel EEG signal,” IEEE Journal of Biomedical and Health Infoematics, vol. 18, no. 6, pp. 1813-1821, 2014.
[27] K. Komeza, E. N. Juszczak, P. Di, Barba, P. Napieralski, J. P. Lecointe, and N. Hihat, “Using the identification of permeability in normal direction of anisotropic sheets,” IEEE Trans. Magnetic, vol. 48, no. 2, pp. 211-214, 2012.
[28] Y.Okamoto, Y. Tominaga, and S. Sato, “Topological design for 3D optimization using the combination of multistep genetic algorithm with design space reduction and nonconforming mesh connection,” IEEE Trans. Magnetics, vol. 48, no. 2, pp. 515-518, 2012.
[29] H. Duan, Q. Luo, Y. Shi, and G. Ma, “Hybrid particle swarm optimization and genetic algorithm for Multi-UAV formation reconfiguration,” IEEE Trans. Computational Intelligence Magazine, vol. 8, no. 3, pp. 16-27, 2013.
[30] H. Liang, S. An, J. Wang, Y. Zhou, H. Fan, P. Krebs, and J. Zhou, “Optimizing time multiplexing auto-stereoscopic displays with a genetic algorithm,” Journal of Display Technology, vol. 10, no. 8, pp. 695-699, 2014.
[31] J.Rayno, M. F. Iskander, and N. Celik, “Synthesis of broadband true 3d metamaterial artificial magnetic conductor ground planes using genetic programming,” IEEE Trans. Antennas and Propagation, vol. 62, no. 11, pp. 5732-5744, 2014.
[32] Y. Fu, M. Ding, and C. Zhou, “Phase angle encoded and quantum behaved particle swarm optimization applied to three-dimensional route planning for UAV,” IEEE Trans. System Man and Cybernetics Part A: Systems and Humans, , vol. 42, no. 2, pp. 511-526, 2012.
[33] S. Grubisic, W. P. Carpes, Jr., J. P. A. Bastos, and G. Santos, “Association of a PSO optimizer with a quasi 3D ray tracing propagation in indoor environments,” IEEE Trans. Magnetics, vol. 49, no. 5, pp. 1645-1648, 2013.
[34] W. Xu, B. Y. Duan, P. Li, N. Hu, and Y. Qiu, “Multiobjective particle swarm optimization of boresight error and transmission loss for airborne radomes,” IEEE Trans. Antennas and Propagation, vol. 62, no. 11, pp. 5880-5885, 2014.
[35] Z. L. Gaing, C. H. Lin, M. H. Tsai, M. F. Hesieh, and M. C. Tsai, “Rigorous design and optimization of brushless pm motor using response surface methodology with quantum behaved PSO operator,” IEEE Trans. Magnetics, vol. 50, no. 1, 2014.
[36] P. V. Krishna, V. Saritha, G. Vedha, A. Bhiwal, and Chawla, “Quality of service enabled ant colony-based multipath routing for mobile ad hoc networks,” IEEE Trans. Communications, vol. 6, no. 1, pp. 76-83, 2012
[37] W. Lu, W. Zhiliang, H. Siquan, and L. Lei, “Ant colony optimization for tank allocation in multi-agent system,” IEEE Trans. Communications, vol. 10, no. 3, pp. 125-132, 2013.
[38] C. H. Hsu and C. F. Juang, “Multi-Objective continuous ants colony optimized fc for robot wall-following control,” IEEE Trans. Computational Intelligence Magazine, vol. 8, no. 3, pp. 25-40, 2013.
[39] Z. Guanglei and J. Heming, “3D path planning of AUV based on improved ant colony optimization,” Proceedings of the 32nd Chinese Control Conference, pp. 5017-5022, 2013, Xi'an.
[40] C. F. Juang, C. W. Hung, and C. H. Hsu, “Rule based cooperative continuous ant colony optimization to improve the accuracy of fuzzy system design,” IEEE Trans. Fuzzy Systems, vol. 22, no. 4 , pp. 723-735, 2014.
[41] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant system: optimization by a colony of cooperating agents,” IEEE Trans. System Man and Cybernetics, vol. 26, no. 1, pp. 29-41, 1996.
[42] L. I. Manuel and S. Thomas, “The automatic design of multiobjective ant colony optimization algorithms,” IEEE Trans. Evolutionary Computation, vol. 16, no. 6, pp. 861-875, 2012.
[43] L. Ke, Q. Zhang, and R. Battiti, “A multiobjective evolutionary algorithm using decomposition and ant colony,” IEEE Trans. Cybernetics, vol. 43, no. 6, pp. 1845-1859, 2013.
[44] A. F. Alkaya and E. Duman, “Application of sequence-dependent traveling salesman problem in printed circuit board assembly,” IEEE Trans. Components, Packaging and Manufacturing Technology, vol. 3, no. 6, pp. 1063-1076, 2013
[45] Di. Perez, J. Togelius, S. Samothrakis, P. Rohlfshagen, and S. M. Lucas, “Automated map generation for the physical traveling salesman problem,” IEEE Trans. Evolutionary Computation, vol. 18, no. 5, pp. 708-720, 2014.
[46] D. Perez, E. J. Powley, D. Whitehouse, P. Rohlfshagen, S. Samothrakis, P. I. Cowling, and S. M. Lucas, “Solving the physical traveling salesman problem: tree search and macro actions,” IEEE Trans. Computational Intelligence and Ai In Games, vol. 6, no. 1, pp. 31-45, 2014.
[47] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Trans. Evolutionary Computation, vol. 1, no.1, pp. 53-66, 1997.
[48] Y. Shavitt and N. Zilberman, “ A geolocation databases study,” IEEE Journal on Selected Areas in Communications, vol. 29, no. 10, pp. 2044-2056, 2011.
[49] Y. C.Song, Y. D. Zhang, J. Cao, T. Xia, W. Liu, and J. T. Li, “Web video geolocation by geotagged social resources,” IEEE Trans. Multimedia, vol. 14, no. 2, pp. 456-470, 2012.
[50] Z. Zhou, Y. Nie, and G. Min, “Enhanced ant colony optimization algorithm for global path planning of mobile robots,” International Conference on Computational and Information Sciences (ICCIS)5th., pp. 698-701, 2013, Shiyang.
[51] 施添福 “高級中學地理第一冊,” 龍騰文化出版社, pp. 3, 1999.
[52] M. Dorigo and L. M. Gambardella, “Ant colonies for the travelling salesman problem,” Biosystems, vol. 43, pp. 73-81, 1997.
[53] C. C. Hsu, R. Y. Hou, and W. Y. Wang, “Path planning for mobile robots based on improved ant colony optimization,” IEEE International Conference on Systems, Man, and Cybernetics (SMC), Manchester, pp. 2777-2782, Oct. 13-16, 2013.