Using Mountain Gazelle and Slime Mould Algorithms to Solve the Path Planning Problem

Document Type : Original Article

Authors

1 Associate Professor, Yazd University, Yazd, Iran

2 Master's degree, Yazd University, Yazd, Iran

3 PhD Student, Yazd University, Yazd, Iran

Abstract

Path planning is one of the important parts of robotics, so studying the path of the robot is considered one of the most important subjects. The mobile robot must move from the start position to the goal position, while avoiding obstacles   in an obstacle environment. The route should be optimal based on some criteria such as shortness of the path, smoothness of the path and security of the path. In this study, the main goal is to solve the path planning problem for a robot in the form of a discrete, static and known, which meet the criteria of shortest distance, path security and path smoothness. Path planning problem is a NP-complete problem and various methods and algorithms have been proposed, which include exact and meta-heuristic algorithms. Meta-heuristic algorithms can be used to solve this problem with less computational load. In this study genetic algorithm,  mountain gazelle algorithm, and Slime mould algorithm are used. In implementations, in addition to the operators of the algorithms themselves, three simplification, revision and replacement operators have been used, as well as a new evaluation function has been presented and after generating the initial population of three operators node repair, line segment repair and node improvement to create paths up to feasible path has been used. The results show that these algorithms have high efficiency and also have less computational complexity to solve this problem

Keywords

Main Subjects

Smiley face

 

References

   [1]      Canny, J.; Reif, J. “New lower bound techniques for robot motion planning problems”; Int. J.  Found. Comput. Sci. 28th Annual Symp. on, 1987, 49–60. DOI: 10.1109/SFCS.1987.42
   [2]      Nearchou, A. C. “Path planning of a mobile robot using genetic heuristics”; Cambridge University Press, 1998, 16, 575–588. DOI: 10.1017/S0263574798000289
   [3]      Hussein, A.; Mostafa, H.; Badrel-din, M.; Sultan, O.; Khamis, A.; “Metaheuristic optimization approach to mobile robot path planning”; Int. Conf. on, 2012, 1–6. DOI: 10.1109/ICEngTechnol.2012.6396150
   [4]      Choset, H.; Lynch, K.; Hutchinson, S.; Kantor, G.; Burgard, W.; Kavraki, L.; Thrun, S. “Principles of robot motion: Theory, algorithms, and implementation errata”; 2007, 1–150.
   [5]      Berg, M. d.; Cheong, O.; Kreveld, M.v.; Overmars, M. “Computational geometry: algorithms and applications”; Springer-Verlag TELOS, 2008. DOI: 10.1007/978-3-540-77974-2
   [6]      Latombe, J.-C. “Robot motion planning”; Springer Science & Business Media, 2012, 124. DOI: 10.1007/978-1-4615-4022-9
   [7]      LaValle, S. M. “Planning algorithms”; Cambridge university press, 2006.
   [8]      Van, J. P.; Berg, D. “Path planning in dynamic environments”; PhD thesis, Utrecht University, 2007.
   [9]      Liao, W. “Genetic Algorithm based robot path planning”; In Intelligent Computation Technology and Automation, Int. Conf. on, 2008, 1, 56–59. DOI: 10.1109/ICICTA.2008.216
[10]      Leena, N.; Saju, K. “A survey on path planning techniques for autonomous mobile robots”; IOSR J. of Mechanical and Civil Eng. 2014, 8, 76–79.
[11]      Victerpaul, P.; Saravanan, D.; Janakiraman, S.; Pradeep, J. “Path planning of autonomous mobile robots: A survey and comparison”; Journal of Advanced Research in Dynamical and Control Systems, 2017, 9, 1535–1565.
[12]      Svestka, P.; Latombe, J.; Overmars Kavraki, L. “Probabilistic roadmaps for path planning in high-dimensional configuration spaces”; IEEE T.  Robotics Autom. 1996, 12, 566–580. DOI: 10.1109/70.508439
[13]      LaValle, S. M. “Rapidly-exploring random trees:  A new tool for path planning. 1998”, 1998.
[14]      Ismail, A.; Sheta, A.; Al-Weshah, M. “A mobile robot path planning using genetic algorithm in static environment”; Journal of Computer Science, 2008, 4, 341–344.
[15]      Buckley, S. J. “Fast motion planning for multiple moving robots”;  IEEE Int. Conf. Robot. Autom. 1989, 322–326.
[16]      Ni, J., Wang, K., Huang, H., Wu, L. and Luo, C., 2016, August. Robot path planning based on an improved genetic algorithm with variable length chromosome. In 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD) (pp. 145-149). IEEE.
[17]      Abdollahzadeh, B.; Gharehchopogh, F. S.; Khodadadi, N.; Mirjalili, S. “Mountain gazelle optimizer: a new nature-inspired metaheuristic algorithm for global optimization problems”; Adv. Eng. Softw. 2022, 174, 103282. DOI :10.1016/j.advengsoft.2022.103282
[18]      Seini, T., Yussif, A.S. and Katali, I.M. Enhancing Mountain Gazelle Optimizer (MGO) with an Improved F-Parameter for Global Optimization. Int. Res. J. Eng. Technol, 2023, 10(6), pp.921-930.
[19]      Sarangi, P. and Mohapatra, P.,. Evolved opposition-based mountain gazelle optimizer to solve optimization problems. Journal of King Saud University-Computer and Information Sciences, 2023,  35(10), p.101812.
[20]      Houssein, E. H.; Mahdy, M. A.; Shebl, D.; Manzoor, A.; Sarkar, R.; Mohamed, W.M. “An effcient slime mould algorithm for solving multi-objective optimization problems”; Expert Syst.- Appl. 2021, 187, 115870.DOI: 10.1016/j.eswa.2021.115870
Journal of Advanced Defense Science & Technology
Volume 14, Issue 4 - Serial Number 54
January 2024
Pages 223-233

Files

History

  • Receive Date: 16 November 2023
  • Revise Date: 21 December 2023
  • Accept Date: 04 January 2024
  • Publish Date: 21 January 2024

Share

How to cite

Statistics