
系統識別號 
U00260501201210261300 
論文名稱(中文) 
推廣式蟻群最佳化演算法及其於最佳路徑規劃之應用 
論文名稱(英文) 
General MultiAnt Colony Optimization Algorithm and its Applications in Optimal Path Planning 
校院名稱 
成功大學 
系所名稱(中) 
電機工程學系碩博士班 
系所名稱(英) 
Department of Electrical Engineering 
學年度 
100 
學期 
1 
出版年 
100 
研究生(中文) 
阮德顯 
研究生(英文) 
DucHien Nguyen 
學號 
N26997031 
學位類別 
碩士 
語文別 
英文 
論文頁數 
77頁 
口試委員 
指導教授莊智清 口試委員余國瑞 口試委員鄭銘揚

中文關鍵字 
none

英文關鍵字 
Optimal Path Planning
Ant Algorithms
Obstacle Avoidance

學科別分類 

中文摘要 
動物的行為經常啟發科學思維。許多研究人員藉由觀察以及模擬動物的行為進而找出有效的方法解決許多艱難的工程與科學問題，其中一個問題便是路徑規畫。本篇論文呈現機器人路徑規劃演算法之概觀，並著重於蟻群演算法之探討與推廣。蟻群演算法為利用模擬蟻群行為來規劃最佳路徑問題。為了解決路徑規畫問題，蟻群最佳化演算法利用螞蟻尋找食物的行為以及策略來找尋最佳化路徑之規劃。除此之外，本篇論文亦提出新的改良型蟻群演算法，此演算法整合數種現行的蟻群演算法並以多蟻群演算法為主。本論文提出的演算法提供使用者靈活性來結合現行演算法的優點使路徑規畫的問題能更有效的解決，並經由模擬分析來證明此改善的演算法能更有效率的解決最佳化路徑規畫問題。

英文摘要 
Animal behaviors are sources of inspiration for science. By observing animals, capturing them and mimicking their behaviors, many scientists have found effective methods to solve many hard problems in science and engineering. One of the problems is path planning problem. The thesis presents an overview of path planning algorithms for mobile robots. The thesis then focuses on the ant colony algorithm family, which is a kind of path planning algorithm and is a method applying animal behaviors in science. To solve the path planning problem, Ant Colony Optimization (ACO) algorithms apply real ant’s behavior and strategy in finding food and modify these manners scientifically to find out solutions. In addition, in the thesis, a new refined ACO algorithm is presented. The algorithm attempts to integrate several existing approaches of ACO algorithm, with Multiple Ant Colony Algorithm playing the main role. The algorithm offers flexibility for users to combine the merits of existing methods so that problems such as path planning can be solved more efficiently and effectively. The thesis performs some simulation analyses to show the improved performance of the proposed algorithm in solving the optimal path planning problem.

論文目次 
摘要 I
ABSTRACT II
ACKNOWLEDGMENTS III
TABLE OF CONTENTS IV
LIST OF TABLES VI
LIST OF FIGURES VII
Chapter 1 INTRODUCTION 1
1.1 Motivation 1
1.2 Contribution 2
Chapter 2 OPTIMAL PATH PLANNING ALGORITHMS 4
2.1 Path Planning Approaches and its evolution 4
2.2 Environment Models 6
2.3 Map representation 8
Chapter 3 ANT COLONY OPTIMIZATION ALGORITHMS 10
3.1 Swarm Intelligence 10
3.2 Ant Colony Optimization algorithm 10
3.3 Modified ACO Algorithms 15
3.3.1 Elitist Ant System(EAS) 15
3.3.2 Rank Based Ant Algorithm 17
3.3.3 The BestWorst Ant System 18
3.3.4 Multiple Ant Colony Optimization 18
3.4 Summary 20
Chapter 4 GENERAL MULTIANT COLONY OPTIMIZATION ALGORITHM 21
4.1 GMACO Algorithm 21
4.2 Interaction among colonies in Great Colony 24
4.3 Next position choice rule 25
4.4 Pheromone trails updating rule in subcolony 26
4.5 Method of ranking subcolonies: Elitist and Worst ACO update 26
4.6 General pheromone updating rule 27
Chapter 5 SIMULATION RESULTS AND DISCUSSION 28
5.1 Define set of next possible positions 28
5.2 Parameter Settings 28
5.3 Simulation 32
5.3.1 Circular Obstacles Map 32
5.3.2 2I &U Obstacles Map 45
5.3.3 Complex Obstacles Map 50
Chapter 6 CONCLUSION AND FUTURE WORK 58
6.1 Conclusion 58
6.2 Future Work 59
REFERENCES 60
APPENDIX 65

參考文獻 
[1] http://en.wikipedia.org/wiki/Navigation.
[2] http://en.wikipedia.org/wiki/Mobile_robot_navigation.
[3] C. W. Warren, Fast path planning using modified Astar method, in IEEE International Conference on Robotics and Automation, pp.662667, 1993.
[4] J. H. Chuang and N. Ahuja, An analytically tractable potential field model of free space and its application in obstacle avoidance, IEEE Transactions on Systems, Man, Cybernetics, vol. 28, no. 5, pp. 729736, 1998.
[5] N. B. Sariff and N. Buniyamin, Ant colony system for robot path planning in global static environment, in Proceedings of the Ninth WSEAS International Conference on System Science and Simulation in Engineering, pp. 192197, 2010.
[6] S. Candido, Autonomous robot path planning using a genetic algorithm, working paper.
[7] A. Ghorbani, S. Shiry, and A. Nodehi, Using genetic algorithm for a mobile robot path planning, in Proceedings of the International Conference on Future Computer and Communication, pp. 164166, 2009.
[8] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm intelligence: From natural to artificial systems, Oxford University Press, 1999.
[9] B. Bullnheimer, R. F. Hartl, and C. Strauss, A new rankbased version of the ant system: a computational study, Central European Journal of Operations Research and Economics, vol 7, no. 1, pp. 2538, 1999.
[10] O. Cordon, I. F. Viana, and F. Herrera, A new ACO model integrating evolutionary computation concepts: the bestworst ant system, in The Third International Workshop on Ant Algorithm, pp. 2229, 2000.
[11] M. Middendorf, F. Reischle, and H. Schmeck, Multi colony ant algorithm, Journal of Heuristics (special issue on Parallel Metaheuristics), vol. 8, no. 3, pp. 305320, 2002.
[12] N. H. Viet, N. A. Vien, S. G. Lee, and T. C. Chung, Obstacle avoidance path planning for mobile robot based on multi colony ant algorithm, in The First International Conference on Advances in ComputerHuman Interaction, pp. 285289, 2008.
[13] A. Aljanaby, K. R. KuMuhamud, and N. M. Norwawi, Interacted multiple ant colonies optimization approach to enhance the performance of ant colony optimization algorithm, Journal of Computer and Information Science, vol. 3, no.1, pp. 2934, 2010.
[14] C. Niederberger, D. Radovic, and M. Gross, Generic path planning for realtime applications, in Proceedings of International Conference on Computer Graphics, pp. 299306, 2004.
[15] F. A. Kolushev and A. A. Bogdanov, Multiagent optimal path planning for mobile robots in environment with obstacles, in Proceedings of the Third International Andrei Ershov Memorial Conference on Perspectives of System Informatics, pp. 503510, 2000.
[16] A. Stentz, Optimal and efﬁcient path planning for partiallyknown environments, in IEEE International Conference on Robotics and Automation, pp. 33103317, 1994.
[17] P. Leven and S. Hutchinso, A framework for realtime path planning in changing environment, Journal of Robotics Research, vol. 21, no. 12, pp. 9991030, 2002.
[18] J. V. D Berg and M. Overmar, Planning timeminimal safe paths amidst unpredictably moving obstacles, Journal of Robotics Research, vol. 27, no. 11, pp. 12741294, 2008.
[19] O. Khatib, Real time obstacle avoidance for manipulators and mobile robots, Journal of Robotics Research, vol. 5, no. 1, pp. 9098, 1986.
[20] G. Nagib and W. Gharieb, Path planning for a mobile robot using genetic algorithm, in International Conference on Electrical, Electronic and Computer Engineering, pp. 185189, 2004.
[21] J. C. Latombe, Robot motion planning, Kluwer Academic, 1991.
[22] A. Sarmiento, R. M. Cid, and S. Hutchinson, An efﬁcient motion strategy to compute expectedtime locally optimal continuous search paths in known environment, Journal of Advanced Robotics, vol. 23, no. 12, pp. 1533–1560, 2009.
[23] J. Schwartz and M. Sharir, On the piano mover's problem II: General techniques for computing topological properties of real algebraic manifolds, Journal of Advances in Applied Mathematics, vol. 4, no. 3, pp. 298351, 1983.
[24] V. J. Lumelski and A. A. Stepanov, Dynamic path planning for a mobile automation with limited information on the environment. IEEE Transaction on Automatic Control, vol. 31, no. 11, pp. 10581063, 1986.
[25] S. Behnke, Local multiresolution path planning, in Proceedings of the Seventh RoboCup International Symposium, 2004.
[26] http://www.sce.carleton.ca/netmanage/tony/swarm.html.
[27] http://en.wikipedia.org/wiki/Swarm_intelligence.
[28] M. Dorigo, V. Maniezzo and A. Colorni, The ant system optimization by a colony of cooperating agents, IEEE Transaction on Systems, Man, and Cybernetics, vol. 26, no. 1, pp. 2941, 1996.
[29] http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms.
[30] D. R. Parhi, J. K. Pothal, and M. K. Singh, Navigation of multiple mobile robots using swarm intelligence, in World Congress on Nature and Biologically Inspired Computing, pp. 11451149, 2009.
[31] M. Dorigo, Ant colony optimization, MIT Press, 2004.
[32] D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning, AddisonWesley Longman, 1989.
[33] P. V. S. Z. Capriles, L. G. Fonseca, H. J. C. Barbosa, and A. C. C. Lemonge, Rankbased ant colony algorithms for truss weight minimization with discrete variables. Journal of Communications in Numerical Methods in Engineering, vol. 23, no. 6, pp. 553575, 2007.
[34] M. Luisa and P. Delgado, Rankbased ant system to solve the undirected rural postman problem, in Proceedings of the Tenth International Conference on Artificial Neural Networks, pp. 507514, 2009.
[35] J. Liu, Rankbased ant colony optimization applied to dynamic traveling salesman problems, Journal of Engineering Optimization, vol. 37, no. 8, pp. 831847, 2005.
[36] M. Middendorf, F. Reischle, and H. Schmeck, Information exchange in multi colony ant algorithms, in Proceedings of the 15 IPDPS Workshops on Parallel and Distributed Processing, pp. 645652, 2000.
[37] S. C. Chu, J. F. Roddick, and J. S. Pan, Ant colony system with communication strategies, Journal of Information ScienceInformatics and Computer Science, vol. 167, no. 1, pp. 6376, 2004.
[38] H. Kawamura, M. Yamamoto, K. Suzuki, and A. Ohuchi, Multiple ant colonies algorithm based on colony level interactions, IEICE Transaction on Fundamentals, vol. E83, no. 2, pp. 371379, 2000.
[39] L. Gambardella, E. Taillard, and G. Agozzi, MACSVRPTW: A multiple ant colony system for vehicle routing problems with time windows, New Ideas in Optimization, McGrawHill, 1999.
[40] A. Ahmmed, M. A. A. Rana, A. A. M. Haque, and M. A. Mamun, A multiple ant colony system for dynamic vehicle routing problem with time window, in The Third International Conference on Convergence and Hybrid Information Technology, pp. 182187, 2008.
[41] I. Ellabib, P. Calamai, and O. Basir, Exchange strategies for multiple ant colony system, Journal of Information Sciences, vol. 177, no. 5, pp. 12481264, 2007.
[42] Z. J. Lee, C. Y. Lee, and S. F. Su, Parallel ant colonies with heuristics applied to weapontarget assignment problems, in The Seventh International Conference on Artificial Intelligence and Application, pp. 201206, 2002.
[43] J. D. Jong and M. Wiering, Multiple ant colony system for the bus stop allocation problem, in Proceedings of the Thirteenth BelgiumNetherlands Conference on Artificial Intelligence, pp. 141148, 2001.
[44] D. A. L. Piriyakumar and P. Levi, A new approach to exploiting parallelism in ant colony optimization, in International Symposium on Micromechatronics and Human Science, pp. 237243, 2002.
[45] K. M. Han, Collision free path planning algorithms for robot navigation problem, Master Thesis, August 2007.

論文全文使用權限 
同意授權校內瀏覽/列印電子全文服務，於20140109起公開。同意授權校外瀏覽/列印電子全文服務，於20140109起公開。 


