||General Multi-Ant Colony Optimization Algorithm and its Applications in Optimal Path Planning
||Department of Electrical Engineering
Optimal Path Planning
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.
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
 C. W. Warren, Fast path planning using modified A-star method, in IEEE International Conference on Robotics and Automation, pp.662-667, 1993.
 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.
 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.
 S. Candido, Autonomous robot path planning using a genetic algorithm, working paper.
 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.
 E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm intelligence: From natural to artificial systems, Oxford University Press, 1999.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 A. Stentz, Optimal and efﬁcient path planning for partially-known environments, in IEEE International Conference on Robotics and Automation, pp. 3310-3317, 1994.
 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.
 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.
 O. Khatib, Real time obstacle avoidance for manipulators and mobile robots, Journal of Robotics Research, vol. 5, no. 1, pp. 90-98, 1986.
 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.
 J. C. Latombe, Robot motion planning, Kluwer Academic, 1991.
 A. Sarmiento, R. M. Cid, and S. Hutchinson, An efﬁcient 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.
 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.
 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.
 S. Behnke, Local multiresolution path planning, in Proceedings of the Seventh RoboCup International Symposium, 2004.
 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.
 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.
 M. Dorigo, Ant colony optimization, MIT Press, 2004.
 D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning, Addison-Wesley Longman, 1989.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 K. M. Han, Collision free path planning algorithms for robot navigation problem, Master Thesis, August 2007.