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

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

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,

PDF

___

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