進階搜尋


下載電子全文  
系統識別號 U0026-0501201210261300
論文名稱(中文) 推廣式蟻群最佳化演算法及其於最佳路徑規劃之應用
論文名稱(英文) General Multi-Ant Colony Optimization Algorithm and its Applications in Optimal Path Planning
校院名稱 成功大學
系所名稱(中) 電機工程學系碩博士班
系所名稱(英) Department of Electrical Engineering
學年度 100
學期 1
出版年 100
研究生(中文) 阮德顯
研究生(英文) Duc-Hien 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 Best-Worst Ant System 18
3.3.4 Multiple Ant Colony Optimization 18
3.4 Summary 20
Chapter 4 GENERAL MULTI-ANT 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 sub-colony 26
4.5 Method of ranking sub-colonies: 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 A-star method, in IEEE International Conference on Robotics and Automation, pp.662-667, 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. 729-736, 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. 192-197, 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. 164-166, 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 rank-based version of the ant system: a computational study, Central European Journal of Operations Research and Economics, vol 7, no. 1, pp. 25-38, 1999.
[10] O. Cordon, I. F. Viana, and F. Herrera, A new ACO model integrating evolutionary computation concepts: the best-worst ant system, in The Third International Workshop on Ant Algorithm, pp. 22-29, 2000.
[11] M. Middendorf, F. Reischle, and H. Schmeck, Multi colony ant algorithm, Journal of Heuristics (special issue on Parallel Meta-heuristics), vol. 8, no. 3, pp. 305-320, 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 Computer-Human Interaction, pp. 285-289, 2008.
[13] A. Aljanaby, K. R. Ku-Muhamud, 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. 29-34, 2010.
[14] C. Niederberger, D. Radovic, and M. Gross, Generic path planning for real-time applications, in Proceedings of International Conference on Computer Graphics, pp. 299-306, 2004.
[15] F. A. Kolushev and A. A. Bogdanov, Multi-agent 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. 503-510, 2000.
[16] A. Stentz, Optimal and efficient path planning for partially-known environments, in IEEE International Conference on Robotics and Automation, pp. 3310-3317, 1994.
[17] P. Leven and S. Hutchinso, A framework for real-time path planning in changing environment, Journal of Robotics Research, vol. 21, no. 12, pp. 999-1030, 2002.
[18] J. V. D Berg and M. Overmar, Planning time-minimal safe paths amidst unpredictably moving obstacles, Journal of Robotics Research, vol. 27, no. 11, pp. 1274-1294, 2008.
[19] O. Khatib, Real time obstacle avoidance for manipulators and mobile robots, Journal of Robotics Research, vol. 5, no. 1, pp. 90-98, 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. 185-189, 2004.
[21] J. C. Latombe, Robot motion planning, Kluwer Academic, 1991.
[22] A. Sarmiento, R. M. Cid, and S. Hutchinson, An efficient motion strategy to compute expected-time 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. 298-351, 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. 1058-1063, 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. 29-41, 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. 1145-1149, 2009.
[31] M. Dorigo, Ant colony optimization, MIT Press, 2004.
[32] D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning, Addison-Wesley Longman, 1989.
[33] P. V. S. Z. Capriles, L. G. Fonseca, H. J. C. Barbosa, and A. C. C. Lemonge, Rank-based ant colony algorithms for truss weight minimization with discrete variables. Journal of Communications in Numerical Methods in Engineering, vol. 23, no. 6, pp. 553-575, 2007.
[34] M. Luisa and P. Delgado, Rank-based ant system to solve the undirected rural postman problem, in Proceedings of the Tenth International Conference on Artificial Neural Networks, pp. 507-514, 2009.
[35] J. Liu, Rank-based ant colony optimization applied to dynamic traveling salesman problems, Journal of Engineering Optimization, vol. 37, no. 8, pp. 831-847, 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. 645-652, 2000.
[37] S. C. Chu, J. F. Roddick, and J. S. Pan, Ant colony system with communication strategies, Journal of Information Science-Informatics and Computer Science, vol. 167, no. 1, pp. 63-76, 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. 371-379, 2000.
[39] L. Gambardella, E. Taillard, and G. Agozzi, MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows, New Ideas in Optimization, McGraw-Hill, 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. 182-187, 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. 1248-1264, 2007.
[42] Z. J. Lee, C. Y. Lee, and S. F. Su, Parallel ant colonies with heuristics applied to weapon-target assignment problems, in The Seventh International Conference on Artificial Intelligence and Application, pp. 201-206, 2002.
[43] J. D. Jong and M. Wiering, Multiple ant colony system for the bus stop allocation problem, in Proceedings of the Thirteenth Belgium-Netherlands Conference on Artificial Intelligence, pp. 141-148, 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. 237-243, 2002.
[45] K. M. Han, Collision free path planning algorithms for robot navigation problem, Master Thesis, August 2007.

論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2014-01-09起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2014-01-09起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw