A Hybrid Approach Based on ACO and Ga for Multi Objective Mobile Robot Path Planning


Article Preview

In this study, we developed an Ant Colony Optimization (ACO) - Genetic Algorithm (GA) hybrid approach for solving the Multi objectives Optimization global path planning (MOPP) problem of mobile robot. The ACO optimization algorithm is used to find the sub-optimal collision free path which then used as initial population for GA. In the proposed modified genetic algorithms, specific genetic operator such as deletion operator is proposed, which is based on domain heuristic knowledge, to fit the optimum path planning for mobile robots. The objective of this study is improving GA performance for efficient and fast selection in generating the Multi objective optimal path for mobile robot navigation in static environment. First we used the proposed approach to evaluate its ability to solve single objective problem in length term as well as we compared it with traditional ACO and simple GA then we extended to solve Pareto optimality ideas based on three criteria: length, smoothness and security, and making it Multi objective Hybrid approach. The proposed approach is tested to generate the single and multi objective optimal collision free path. The simulation results show that the mobile robot travels successfully from one location to another and reaches its goal after avoiding all obstacles that are located in its way in all tested environment and indicate that the proposed approach is accurate and can find a set Pareto optimal solution efficiently in a single run.



Edited by:

Abdel Hamid Ismail Mourad and József Kázmér Tar




B. K. Oleiwi et al., "A Hybrid Approach Based on ACO and Ga for Multi Objective Mobile Robot Path Planning", Applied Mechanics and Materials, Vol. 527, pp. 203-212, 2014

Online since:

February 2014




* - Corresponding Author

[1] H. Zhang, R. Zhen and Y. Cen: Present situation and future development of mobile robot path planning technology, J. of System Simulation, Vol. 17, (2005), pp.439-443.

[2] D.K. Qu, Z.J. Du, D.G. Xu and F. Xu: Research on planning for a mobile robot, Robot, Vol. 30, (2008), pp.97-101.

[3] P. D. Wang, Z. H. Feng and X. Huang: An improved ant colony algorithm for mobile robot path planning, Robot, Vol. 30, (2008), pp.554-560.

[4] J. Li, Y. Feng and C.A. Zhu: Novel path planning method based on certainty grids map for mobile robot", in Proceedings of the 26th Chinese Control Conference, Beijing: Beihang University Press, (2007), pp.185-188.

DOI: https://doi.org/10.1109/chicc.2006.4347345

[5] D. Marco and D.C. Gianni: Ant colony optimization: A new meta-heuristic, IEEE, Evolutionary Computation Congress on  Vol. 2, (1999), pp.1470-1477.

[6] B. Christian: Ant colony optimization: Introduction and recent trends, Physics of Life Reviews, Vol. 2, (2005), pp.353-373.

DOI: https://doi.org/10.1016/j.plrev.2005.10.001

[7] N. Sariff and N. Buniyamin: An overview of autonomous mobile robot path planning algorithms, In Proceedings of 4th Student Conference on Research and Development, Shah Alam, Malaysia, (2006).

DOI: https://doi.org/10.1109/scored.2006.4339335

[8] M. Ellips and S. Davoud: Classic and heuristic approaches in robot motion planning – a chronological review, World Academy of Science, Engineering and Technology, (2007), pp.101-106.

[9] K. Mohammad, R. T. Mohammad, E.S. Ahmed and E. Mahdiyeh: A survey on meta-heuristic global optimization algorithms, Research Journal of Applied Sciences, Engineering and Technology, Vol. 3(6), (2011), pp.569-578.

[10] P. Raja and S. Pugazhenthi: Optimal path planning of mobile robots: a review, International Journal of Physical Sciences, Vol. 7(9), (2012), pp.1314-1320.

[11] S. Chunxue, B. Yingyong, L. Ziguang and T. Jun: Solving path planning problem by an ACO-PSO hybrid algorithm, International Conference on Intelligent Systems and Knowledge Engineering (ISKE), (2007).

DOI: https://doi.org/10.1109/icicta.2008.207

[12] S. Zhao and M. Li: Path planning of inspection robot based on ant colony optimization algorithm, IEEE, International Conference on Electrical and Control Engineering, (2010), pp.1474-1477.

DOI: https://doi.org/10.1109/icece.2010.1438

[13] G. Meijuan, X. Jin and T. Jingwen: Mobile robot global path planning based on improved augment ant colony algorithm, IEEE, Second International Conference on Genetic and Evolutionary Computer, (2008), pp.273-276.

DOI: https://doi.org/10.1109/wgec.2008.39

[14] Z. Wang, X. Zhu and Q. Han: Mobile robot path planning based on parameter optimization ant colony algorithm, Procedia Engineering, Vol. 15, (2011), pp.2738-2741.

DOI: https://doi.org/10.1016/j.proeng.2011.08.515

[15] X. Zhu, Z. Wang and Q. Han: Mobile robot path planning based on multi-parameters optimization ant colony algorithm, Journal of Convergence Information Technology, Vol. 6(8), (2011).

[16] L. Qing, T. Xinhai, X. Sijiang and Z. Yingchun: Optimum path planning for mobile robots based on a hybrid genetic algorithm, IEEE, In Proceedings of the Sixth International Conference on Hybrid Intelligent Systems -HIS (2006).

DOI: https://doi.org/10.1109/his.2006.264936

[17] N.T. Mahmood, Mohammad and T. M. -S.: Efficient and safe path planning for a mobile robot using genetic algorithm, IEEE, Congress on Evolutionary Computation (CEC), (2009), p.2091-(2097).

DOI: https://doi.org/10.1109/cec.2009.4983199

[18] L. Yuming and X. Lihong: Global path planning for mobile robot based genetic algorithm and modified simulated annealing algorithm, (GEC), Shanghai, China, (2009), pp.303-308.

DOI: https://doi.org/10.1145/1543834.1543875

[19] H. Jun and Z. Qingbao: Multi-objective mobile robot path planning based on improved genetic algorithm, IEEE, International Conference on Intelligent Computation Technology and Automation, (ICICTA), (2010), pp.752-756.

DOI: https://doi.org/10.1109/icicta.2010.300

[20] S. Geetha, C.G. Muthu and V. Jayalakshmi: Multi objective mobile robot path planning based on hybrid algorithm, IEEE Electronics Computer Technology (ICECT), 3rd International Conference , Vol. 6, (2011), p.251 – 255.

DOI: https://doi.org/10.1109/icectech.2011.5942092

[21] O. Castillo , L. Trujillo, P. and Melin: Multiple objective genetic algorithms for path-planning optimization in autonomous mobile robots, Soft Computing- A fusion of Foundation, Methodologies and applications- Fuzzy-neural computation and robotics, Vol. 11, Issue 3, (2007).

DOI: https://doi.org/10.1007/s00500-006-0068-4

[22] S. Nafiseh: Mobile robot path planning by new structured multi-objective genetic algorithm, IEEE, International Conference of Soft Computing and Pattern Recognition (SoCPaR), (2011), pp.79-83.

DOI: https://doi.org/10.1109/socpar.2011.6089099

[23] Z. Wang, W. Zhang, J. Shi and Y. Han: UAV Route Planning using Multiobjective Ant Colony System, IEEE, Conference on Cybernetics and Intelligent Systems, (2008), pp.797-800.

DOI: https://doi.org/10.1109/iccis.2008.4670944

[24] D. W. Gong, J. H. Zhang, Y. Zhang: Multi-objective Particle Swarm Optimization for Robot Path Planning in Environment with Danger Sources, Journal of computers, Vol. 6, No. 8, (2011), pp.1554-1561.

DOI: https://doi.org/10.4304/jcp.6.8.1554-1561

[25] K.T. Hung, J.S. Liu, and Y. Z. Chang: A comparative study of smooth path planning for a mobile robot by evolutionary multi-objective optimization", Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation, (2007).

DOI: https://doi.org/10.1109/cira.2007.382857

[26] M. Ellips, S. Davoud: Multi-Objective PSO- and NPSO-based Algorithms for Robot Path Planning, Advances in Electrical and Computer Engineering, Vol. 10, No. 4, (2010), pp.69-76.

DOI: https://doi.org/10.4316/aece.2010.04011

[27] F. Ahmed and F. Deb: Multi-Objective Path Planning using Spline Representation, IEEE, International Conference on Robotics and Biomimetics (ROBIO), (2011), pp.1047-1052.

DOI: https://doi.org/10.1109/robio.2011.6181426

[28] C.M. Fonseca and P.J. Fleming: An overview of evolutionary algorithms in multiobjective optimization, Evolutionary Computing, Vol. 3, No. 1, (1995), pp.1-16.