Izgara Bazlı Yol Planlama için Matematik Tabanlı Metasezgisellerin Karşılaştırılması

Öz

Robot navigasyonunun en önemli bileşenlerinden biri olan yol planlama son yıllarda da araştırmacılar tarafından kapsamlı bir şekilde incelenmekte ve bu problem için birçok farklı metasezgisel algoritma kullanılmaktadır. Bu çalışmada ızgara tipi bir ortamda bir mobil robotun küresel yol planlaması ele alınmış ve bu problem için farklı matematik tabanlı metasezgisel algoritmalarının etkileri incelenmiştir. Öncelikle ızgara tipinde ve farklı zorluk derecelerinde üç farklı ortam tasarlanmıştır. Ardından, son yıllarda geliştirilen farklı matematik tabanlı algoritmalar kullanılarak robotun ortamlardaki optimum yolları hesaplanmıştır. Çalışmada metasezgisel algoritma olarak stokastik fraktal arama (Stochastic Fractal Search, SFS), aritmetik optimizasyon algoritması (Arithmetic Optimization Algorithm, AOA) ve sinüs kosinüs algoritması (Sine Cosine Algorithm, SCA) kullanılmıştır. Bulgular değerlendirildiğinde SFS algoritmasının en kısa mesafe ve engelden kaçınma açısından diğer algoritmalara göre daha iyi sonuçlar verdiği gözlemlenmiştir.

Anahtar Kelimeler

• Yol Planlama
• Metasezgisel
• Matematik Tabanlı Algoritmalar
• Optimizasyon

Comparison of Maths-Based Metaheuristics for Grid-Based Path Planning

Abstract

Path planning, one of the most important components of robot navigation, has been extensively studied by researchers in recent years and many different metaheuristic algorithms are used for this problem. In this study, the global path planning of a mobile robot in a grid-type environment is discussed and the effects of different maths-based metaheuristic algorithms for this problem are investigated. First, three different environments with grid type and different difficulty levels were designed. Then, the optimum paths of the robot in the environments were calculated by using different maths-based algorithms developed in recent years. Stochastic fractal search (SFS), arithmetic optimization algorithm (AOA) and sine cosine algorithm (SCA) were used as metaheuristic algorithms in the study. When the results were evaluated, it was observed that SFS algorithm has given better results than other algorithms in terms of shortest distance and obstacle avoidance.

Keywords

• Path Planning
• Metaheuristic
• Maths-Based Algorithm
• Optimization

Kaynakça

1. Abualigah, L., Diabat, A., Mirjalili, S., Abd Elaziz, M., & Gandomi, A. H. (2021). The Arithmetic Optimization Algorithm. Computer Methods in Applied Mechanics and Engineering, 376, 113609. https://doi.org/10.1016/j.cma.2020.113609
2. Abualigah, L. (2021). The Arithmetic Optimization Algorithm (AOA). MATLAB Central File Exchange. https://www.mathworks.com/matlabcentral/fileexchange/84742-the-arithmetic-optimization-algorithm-aoa
3. Adamu, P. I., Okagbue, H. I., & Oguntunde, P. E. (2019). Fast and Optimal Path Planning Algorithm (FAOPPA) for a Mobile Robot. Wireless Personal Communications, 106(2), 577–592. https://doi.org/10.1007/s11277-019-06180-w
4. Ajeil, F. H., Ibraheem, I. K., Sahib, M. A., & Humaidi, A. J. (2020). Multi-objective path planning of an autonomous mobile robot using hybrid PSO-MFB optimization algorithm. Applied Soft Computing Journal, 89, 106076. https://doi.org/10.1016/j.asoc.2020.106076
5. Ajeil, F. H., Ibraheem, I. K., Azar, A. T., & Humaidi, A. J. (2020). Grid-based mobile robot path planning using aging-based ant colony optimization algorithm in static and dynamic environments. Sensors (Switzerland), 20(7). https://doi.org/10.3390/s20071880
6. Akka, K., & Khaber, F. (2018). Mobile robot path planning using an improved ant colony optimization. International Journal of Advanced Robotic Systems, 15(3), 1–7. https://doi.org/10.1177/1729881418774673
7. Ali, H., Gong, D., Wang, M., & Dai, X. (2020). Path Planning of Mobile Robot With Improved Ant Colony Algorithm and MDP to Produce Smooth Trajectory in Grid-Based Environment. Frontiers in Neurorobotics, 14(July), 1–13. https://doi.org/10.3389/fnbot.2020.00044
8. Dai, X., Long, S., Zhang, Z., & Gong, D. (2019). Mobile robot path planning based on ant colony algorithm with a∗ heuristic method. Frontiers in Neurorobotics, 13(April). https://doi.org/10.3389/fnbot.2019.00015

9. Das, P. K. (2020). Hybridization of Kidney-Inspired and Sine–Cosine Algorithm for Multi-robot Path Planning. Arabian Journal for Science and Engineering, 45(4), 2883–2900. https://doi.org/10.1007/s13369-019-04193-y
10. Dolicanin, E., Fetahovic, I., Tuba, E., Capor-Hrosik, R., & Tuba, M. (2018). Unmanned combat aerial vehicle path planning by brain storm optimization algorithm. Studies in Informatics and Control, 27(1), 15–24. https://doi.org/10.24846/v27i1y201802
11. Elmi, Z., & Efe, M. O. (2018). Multi-objective grasshopper optimization algorithm for robot path planning in static environments. Proceedings of the IEEE International Conference on Industrial Technology, 2018-Febru, 244–249. https://doi.org/10.1109/ICIT.2018.8352184
12. Gabis, A. B., Meraihi, Y., Mirjalili, S., & Ramdane-Cherif, A. (2021). A comprehensive survey of sine cosine algorithm: variants and applications. In Artificial Intelligence Review (Vol. 54, Issue 7). Springer Netherlands. https://doi.org/10.1007/s10462-021-10026-y
13. Gul, F., Rahiman, W., Alhady, S. S. N., Ali, A., Mir, I., & Jalil, A. (2020). Meta-heuristic approach for solving multi-objective path planning for autonomous guided robot using PSO–GWO optimization algorithm with evolutionary programming. Journal of Ambient Intelligence and Humanized Computing, 12(7), 7873–7890. https://doi.org/10.1007/s12652-020-02514-w
14. Hosseininejad, S., & Dadkhah, C. (2019). Mobile robot path planning in dynamic environment based on cuckoo optimization algorithm. International Journal of Advanced Robotic Systems, 16(2), 1–13. https://doi.org/10.1177/1729881419839575
15. Huang, H. C., & Tsai, C. C. (2011). Global path planning for autonomous robot navigation using hybrid metaheuristic GA-PSO algorithm. Proceedings of the SICE Annual Conference, 1338–1343.
16. Lamini, C., Benhlima, S., & Elbekri, A. (2018). Genetic algorithm based approach for autonomous mobile robot path planning. Procedia Computer Science, 127, 180–189. https://doi.org/10.1016/j.procs.2018.01.113
17. Li, W., Sun, S., Li, J., & Hu, Y. (2018). Stochastic Fractal Search Algorithm and its Application in Path Planning. 2018 IEEE CSAA Guidance, Navigation and Control Conference, CGNCC 2018. https://doi.org/10.1109/GNCC42960.2018.9018694
18. Liang, X., Kou, D., & Wen, L. (2020). An Improved Chicken Swarm Optimization Algorithm and its Application in Robot Path Planning. IEEE Access, 8, 49543–49550. https://doi.org/10.1109/ACCESS.2020.2974498
19. Luo, Q., Wang, H., Zheng, Y., & He, J. (2020). Research on path planning of mobile robot based on improved ant colony algorithm. Neural Computing and Applications, 32(6), 1555–1566. https://doi.org/10.1007/s00521-019-04172-2
20. Mirjalili, S. (2016). SCA: A Sine Cosine Algorithm for solving optimization problems. Knowledge-Based Systems, 96, 120–133. https://doi.org/10.1016/j.knosys.2015.12.022
21. Mirjalili, S. (2021). SCA: A Sine Cosine Algorithm. MATLAB Central File Exchange. https://www.mathworks.com/matlabcentral/fileexchange/54948-sca-a-sine-cosine-algorithm
22. Muhammad, A., Ali, M., & Shanono, I. (2020). Path planning Methods for Mobile Robots: A systematic and Bibliometric Review. Journal of Electrical Engineering, 19(3), 14–34.
23. Patle, B. K., Parhi, D. R. K., Jagadeesh, A., & Kashyap, S. K. (2018). Matrix-Binary Codes based Genetic Algorithm for path planning of mobile robot. Computers and Electrical Engineering, 67, 708–728. https://doi.org/10.1016/j.compeleceng.2017.12.011
24. Salimi, H. (2015). Stochastic Fractal Search: A powerful metaheuristic algorithm. Knowledge-Based Systems, 75, 1–18. https://doi.org/10.1016/j.knosys.2014.07.025
25. Salimi, H. (2021). Stochastic Fractal Search (SFS). MATLAB Central File Exchange. https://www.mathworks.com/matlabcentral/fileexchange/47565-stochastic-fractal-search-sfs
26. Saraswathi, M., Murali, G. B., & Deepak, B. B. V. L. (2018). Optimal Path Planning of Mobile Robot Using Hybrid Cuckoo Search-Bat Algorithm. Procedia Computer Science, 133, 510–517. https://doi.org/10.1016/j.procs.2018.07.064
27. Tuba, E., Strumberger, I., Zivkovic, D., Bacanin, N., & Tuba, M. (2018). Mobile Robot Path Planning by Improved Brain Storm Optimization Algorithm. 2018 IEEE Congress on Evolutionary Computation, CEC 2018 - Proceedings. https://doi.org/10.1109/CEC.2018.8477928
28. Wang, B., Li, S., Guo, J., & Chen, Q. (2018). Car-like mobile robot path planning in rough terrain using multi-objective particle swarm optimization algorithm. Neurocomputing, 282, 42–51. https://doi.org/10.1016/j.neucom.2017.12.015
29. Wang, R. B., Wang, W. F., Xu, L., Pan, J. S., & Chu, S. C. (2021). An Adaptive Parallel Arithmetic Optimization Algorithm for Robot Path Planning. Journal of Advanced Transportation, 2021. https://doi.org/10.1155/2021/3606895
30. Yıldırım, M. Y., & Akay, R. (2021). A Comparative Study of Optimization Algorithms for Global Path Planning of Mobile Robots. Sakarya University Journal of Science, 25, 417–428. https://doi.org/10.16984/saufenbilder.800067
31. Yıldırım, M. Y., & Akay, R. (2021). Fast path planning in multi-obstacle environments for mobile robots. Journal of the Faculty of Engineering and Architecture of Gazi University, 36(3), 1551–1564. https://doi.org/10.17341/gazimmfd.802646
32. Zhang, J. H., Zhang, Y., & Zhou, Y. (2018). Path planning of mobile robot based on hybrid multi-objective bare bones particle swarm optimization with differential evolution. IEEE Access, 6, 44542–44555. https://doi.org/10.1109/ACCESS.2018.2864188
33. Zhong, X., Tian, J., Hu, H., & Peng, X. (2020). Hybrid Path Planning Based on Safe A* Algorithm and Adaptive Window Approach for Mobile Robot in Large-Scale Dynamic Environment. Journal of Intelligent and Robotic Systems: Theory and Applications, 99(1), 65–77. https://doi.org/10.1007/s10846-019-01112-z