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

Year 2021, , 521 - 530, 31.12.2021

Mustafa Yusuf Yıldırım , Rüştü Akay

https://doi.org/10.31590/ejosat.1039899

Abstract

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.

Keywords

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

References

• 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
• Abualigah, L. (2021). The Arithmetic Optimization Algorithm (AOA). MATLAB Central File Exchange. https://www.mathworks.com/matlabcentral/fileexchange/84742-the-arithmetic-optimization-algorithm-aoa
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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.
• 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
• 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
• 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
• 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
• 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
• Mirjalili, S. (2021). SCA: A Sine Cosine Algorithm. MATLAB Central File Exchange. https://www.mathworks.com/matlabcentral/fileexchange/54948-sca-a-sine-cosine-algorithm
• 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.
• 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
• 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
• Salimi, H. (2021). Stochastic Fractal Search (SFS). MATLAB Central File Exchange. https://www.mathworks.com/matlabcentral/fileexchange/47565-stochastic-fractal-search-sfs
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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