Two-Dimension Path Planning Method Based on Improved Ant Colony Algorithm

Rong Wang^*, Hong Jiang

Southwest University of Science and Technology, Mianyang, China.

DOI: 10.4236/apm.2015.59053                

Abstract

Nowadays, path planning has become an important field of research focus. Considering that the ant colony algorithm has numerous advantages such as the distributed computing and the characteristics of heuristic search, how to combine the algorithm with two-dimension path planning effectively is much important. In this paper, an improved ant colony algorithm is used in resolving this path planning problem, which can improve convergence rate by using this improved algorithm. MAKLINK graph is adopted to establish the two-dimensional space model at first, after that the Dijkstra algorithm is selected as the initial planning algorithm to get an initial path, immediately following, optimizing the select parameters relating on the ant colony algorithm and its improved algorithm. After making the initial parameter, the authors plan out an optimal path from start to finish in a known environment through ant colony algorithm and its improved algorithm. Finally, Matlab is applied as software tool for coding and simulation validation. Numerical experiments show that the improved algorithm can play a more appropriate path planning than the origin algorithm in the completely observable.

Keywords

Path Planning, Dijkstra, Improved Ant Colony Algorithm

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Chu, K., Kim, J., Jo, K. and Sunwoo, M. (2015) Real-Time Path Planning of Autonomous Vehicles for Unstructured Road Navigation. International Journal of Automotive Technology, 16, 653-668.
[2]	Wahle, J., Annen, O., Schuster, Ch., Neubert, L. and Schreckenberg, M. (2001) A Dynamic Route Guidance System Based on Real Traffic Data. European Journey of Operational Research, 131, 302-308.
[3]	Liu, S. and Sun, D. (2014) A Dynamic Priority Based Path Planning for Cooperation of Multiple Mobile Robots in Formation Forming. Robotic and Computer-Integrated Manufacturing, 30, 589-596. http://dx.doi.org/10.1016/j.rcim.2014.04.002
[4]	Nikolos, I.K. and Valavanis, K.P. (2003) Evolutionary Algorithm Based Offline/Online Pathplanner for UAV Navigation. IEEE Transactions on System, Man, and Cybernetics—Part B. Cybernetics, 33, 898-912. http://dx.doi.org/10.1109/TSMCB.2002.804370
[5]	Saska, M. and Macas, M. (2006) Robot Path Planning Using Particle Swarm Optimization of Ferguson Splines. IEEE Conference on Emerging Technologies and Factory Automation, Prague, 20-22 September 2006, 833-839. http://dx.doi.org/10.1109/etfa.2006.355416
[6]	Althoefer, K. (1997) Neuro-Fuzzy Motion Planning for Robotic Manipulators. Ph.D. Thesis, King’s College, London,
[7]	Yang, B. and Liu, W.J. (2009) A Improved Method of Robot's Path Planning Based Visibilty Graph. Computer Knowledge and Technology, 5, 434-435.
[8]	Fan, X. and Luo, X. (2003) Optimal Path Planning for Mobile Robots Based on Intensified Ant Colony Optimization Algorithm. Proceedings of IEEE International Conference on Robotics, Intelligent Systems and Signal Processing, 1, 131-136.
[9]	Zhang, Y.L. and Niu, X.M. (2011) Simulation Research on Mobile Robot Path Planning Based on Ant Colony Optimization. Computer Simulation, 28, 231-234.
[10]	Dorigo, M. and Gambardella, L.M. (1997) Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1, 53-66. http://dx.doi.org/10.1109/4235.585892
[11]	Mandloi, M. and Bhatia, V. (2015) Congestion Control Based Ant Colony Optimization Algorithm for Large MIMO Detection. Expert Systems with Applications, 42, 3662-3669. http://dx.doi.org/10.1016/j.eswa.2014.12.035
[12]	Dorigo, M. (1992) Optimization Learning and Natural Algorithms. Dipartimento di Elettronica, Politecnico di Milano, Milano.
[13]	Ruiz, E. and Albareda-Sambola, M. (2015) A Biased Random-Key Genetic Algorithm for the Capacitated Minimum Spanning Tree Problem. Computers and Operations Research, 57, 95-108. http://dx.doi.org/10.1016/j.cor.2014.11.011
[14]	Fischer, A. and Helmberg, C. (2013) The Symmetric Quadratic Traveling Salesman Problem. Mathematical Programming, 142, 205-254. http://dx.doi.org/10.1007/s10107-012-0568-1
[15]	Wu, W.T. and Song, Y.C. (2012) Chaotic Prediction of Network Traffic Based on Neural Network Optimized by Ant Colony Optimization Algorithm. Computer Engineering and Applications, 97-101.
[16]	Chen, K.-Y. (2014) Development of Optimal Path Planning Based on Ant Colony and Wireless Sensor Network Localization Techniques for an Autonomous Mobile Service Robot. Electronics and Electrical Engineering, 953-958.
[17]	Bullnheimer, B. and Hartl, R.F. (1999) A New Rank Based Version of the Ant System: A Computational Study. Central European Journal for Operations Research and Economics, 25-38.