A Hybrid Genetic Algorithm for Mobile Robot Shortest Path Problem

Abstract

This paper proposes an algorithm to solve the problem of shortest path planning for a mobile robot in a static environment with obstacles. The proposed algorithm is a Hybrid Genetic Algorithm (HGA) which includes Genetic and Dijkstra Algorithms together. The Genetic Algorithm (GA) is preferred since the structure of robot path planning problem is very convenient to apply genetic algorithm’s coding and operators such as permutation coding, crossover and mutation. GA provides diversification while searching possible global solutions, but Dijkstra Algorithm (DA) makes more and more intensification in local solutions. The simulation results show that the mobile robot can plan a set of optimized path with an efficient algorithm.

Keywords

• Robot path planning,genetic algorithm,Dijkstra algorithm,Shortest path

References

1. E. W. Dijkstra (1959). A note on two problems in connexion with graphs. Numerische Mathematik. Vol.1. Pages. 269-271.
2. R. Bellman (1958). On a routing problem. Quarterly Applied Mathematics. Vol.16. Pages. 87 – 90.
3. P. E. Hart, N.J. Nilsson and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, vol.4, 2, pp. 100–107, 1968.
4. X. Chen and Y. M. Li (2006). Smooth path planning of a mobile robot using stochastic particle swarm optimization. In Proceedings of IEEE International Conference on Mechatronics and Automation. Pages. 1722–1727.
5. X. Z. Hu and Q. G. Xu (2007). Robot path planning based on artificial immune network. In Proceedings of the 2007 IEEE International Conference on Robotics and Biomimetics. Pages. 1053-1058.
6. Y. Huang (2012). Intelligent Technique for Robot Path planning Using Artificial Neural Network and Adaptive Ant Colony Optimization. JCIT. Vol.7. Pages. 246 - 252.
7. H. W. Mo and Z. Z. Li (2012). Biogeography based differential evolution for robot path planning. In Proceedings of International Conference on Information and Automation, Pages. 1 - 6.
8. J. C. Mohanta, D. R. Parhi and S. K. Patel (2011). Path planning strategy for autonomous mobile robot navigation using Petri-GA optimization. Computers & Electrical Engineering. Vol.37. Pages. 1058-1070.

9. E. Bogar (2016). A Hybrid Optimization Method for Single and Multi Objective Robot Path Planning Problem. Master's thesis. Pamukkale University Institute of Science and Technology.
10. J. Holland (1975). Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press.
11. J. Cao (2006). Robot Global Path Planning Based on an Improved Ant Colony Algorithm. Journal of Computer and Communications. Vol.4. Pages. 11-19.
12. B. K. Oleiwi, H. Roth and B. I. Kazem (2014). Modified Genetic Algorithm based on A* Algorithm of Multi Objective Optimization for Path Planning. Jounal of Automation and Control Engineering. Vol.2. Pages. 357-362.