ARAMA ALGORİTMALARININ YOL PLANLAMASI PERFORMANSLARININ KARŞILAŞTIRMALI ANALİZİ

Mehmet Gök; Öznur Şifa Akçam; Mehmet Tekerek

doi:10.17780/ksujes.1171461

TR

ARAMA ALGORİTMALARININ YOL PLANLAMASI PERFORMANSLARININ KARŞILAŞTIRMALI ANALİZİ

Öz

Haritası bilinen ya da bilinmeyen herhangi bir ortamda, otonom mobil robotların başlangıç noktasından hedef noktasına en az maliyetle ve en hızlı ulaşımı yol planlaması ile gerçekleştirilir. Yol planlamasında alternatif yollar arasından optimum yolun seçimi önemlidir. Bu çalışmada, yol planlama görevini yerine getirmek amacıyla farklı arama yaklaşımlarına sahip algoritmaların Robot İşletim Sistemine (ROS) entegrasyonu ve performanslarının karşılaştırılması yapılmıştır. Bu amaçla, tasarımı görüntü işleme yazılımı kullanılarak yapılan ve RViz arayüzünde yayınlanan örnek haritalar üzerinde BFS, DFS, Dijkstra, Bellman-Ford, A* ve RRT algoritmaları kullanılarak yol planlaması gerçekleştirilmiştir. Yol planlama işleminin değerlendirilmesi için en kısa yol ve en kısa süre ölçütleri dikkate alınmıştır. Elde edilen bulgular, en kısa yolun planlanmasında A*; en kısa sürede planlama işleminin gerçekleştirilmesinde ise DFS algoritmasının ön plana çıktığını göstermektedir. Ayrıca, çalışmada literatüre katkı olarak, ROS ortamında farklı senaryolar için kullanılabilecek algoritmaların performans ölçümü için bir test ortamı da sunulmuştur.

Anahtar Kelimeler

Kaynakça

AbuSalim, S. W., Ibrahim, R., Saringat, M. Z., Jamel, S., & Wahab, J. A. (2020, September). Comparative analysis between dijkstra and bellman-ford algorithms in shortest path optimization. In IOP Conference Series: Materials Science and Engineering, 917(1), 012077. doi: 10.1088/1757-899X/917/1/012077
Akka, K., & Khaber, F. (2018). Mobile robot path planning using an improved ant colony optimization. International Journal of Advanced Robotic Systems, 15(3), 1729881418774673. doi: 10.1177/1729881418774673
Aqel, M. O., Issa, A., Khdair, M., ElHabbash, M., AbuBaker, M., & Massoud, M. (2017, October). Intelligent maze solving robot based on image processing and graph theory algorithms. In 2017 International Conference on Promising Electronic Technologies (ICPET) (pp. 48-53). IEEE. doi: 10.1109/ICPET.2017.15
Barnouti, N. H., Al-Dabbagh, S. S. M., & Naser, M. A. S. (2016). Pathfinding in strategy games and maze solving using A* search algorithm. Journal of Computer and Communications, 4(11), 15. doi: 10.4236/jcc.2016.411002
Campbell, S., O'Mahony, N., Carvalho, A., Krpalkova, L., Riordan, D., & Walsh, J. (2020, February). Path planning techniques for mobile robots a review. In 2020 6th International Conference on Mechatronics and Robotics Engineering (ICMRE) (pp. 12-16). IEEE. doi: 10.1109/ICMRE49073.2020.9065187.
Chan, S. Y. M., Adnan, N. A., Sukri, S. S., & Wan Zainon, W. M. N. (2016). An experiment on the performance of shortest path algorithm. Knowledge Management International Conference (KMICe) (pp. 7-12). Chiang Mai, Thailand. Erişim adresi: https://repo.uum.edu.my/id/eprint/20010/
Debnath, S. K., Omar, R., Latip, N. B. A., Shelyna, S., Nadira, E., Melor, C. K. N. C. K., & Natarajan, E. (2019). A review on graph search algorithms for optimal energy efficient path planning for an unmanned air vehicle. Indonesian Journal of Electrical Engineering and Computer Science, 15(2), 743-749. doi: 10.11591/ijeecs.v15.i2.pp743-749
Dewang, H. S., Mohanty, P. K., & Kundu, S. (2018). A robust path planning for mobile robot using smart particle swarm optimization. Procedia computer science, 133, 290-297. doi: 10.1016/j.procs.2018.07.036

Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization. IEEE computational intelligence magazine, 1(4), 28-39. doi: 10.1109/MCI.2006.329691.
Edelkamp, S., & Schrodl, S. (2011). Basic Search Algorithms. In R. Roumeliotis, & D. Bevans (Eds.), Heuristic search: theory and applications, (pp. 47-86). Waltham, USA: Elsevier.
Elbanhawi, M., & Simic, M. (2014). Sampling-based robot motion planning: a review. IEEE Access, 2, 56-77. doi: 10.1109/ACCESS.2014.2302442
GIMP, www.gimp.org, Erişim tarihi: 25.06.2022.
He, Y., Wang, P., & Zhang, J. (2021, September). A Comparison Between A* & RRT in maze solving problem. In 2021 3rd International Symposium on Robotics & Intelligent Manufacturing Technology (ISRIMT) (pp. 333-338). IEEE. doi: 10.1109/ISRIMT53730.2021.9596830
Iloh, P. C. (2022). A Comprehensive and comparative study of DFS, BFS, and A* search algorithms in a solving the maze transversal problem. International Journal of Social Sciences and Scientific Studies, 2(2), 482-490. Erişim adresi: https://www.ijssass.com/index.php/ijssass/article/view/54
Indriyono, B. V. (2021). Optimization of breadth-first search algorithm for path solutions in mazyin games. International Journal of Artificial Intelligence & Robotics (IJAIR), 3(2), 58-66. doi: 10.25139/ijair.v3i2.4256
Injarapu, A. S. H. H. V., & Gawre, S. K. (2017, October). A survey of autonomous mobile robot path planning approaches. In 2017 International conference on recent innovations in signal processing and embedded systems (RISE) (pp. 624-628). IEEE. doi: 10.1109/RISE.2017.8378228.
Kaur, N. K. S. (2019). A review of various maze solving algorithms based on graph theory. International Journal for Scientific Research & Development (IJSRD), 6(12), 431-434. Erişim adresi: https://www.researchgate.net/publication/331481380
Korf, R. E. (1996). Artificial intelligence search algorithms. In M. J. Atallah, & M. Blanton (Eds.), Algorithms and theory of computation handbook: special topics and techniques (pp. 582-604). Boca Raton, Florida: Chapman & Hall/CRC.
Koubâa, A., Bennaceur, H., Chaari, I., Trigui, S., Ammar, A., Sriti, M. F., & Javed, Y. (2018). Robot path planning and cooperation (1st ed.). Cham, Swiss: Springer International Publishing, (Chapter 1-2).
Mac, T. T., Copot, C., Tran, D. T., & De Keyser, R. (2016). Heuristic approaches in robot path planning: a survey. Robotics and Autonomous Systems, 86, 13-28. doi: 10.1016/j.robot.2016.08.001
Mohanty, P. K., Kundu, S., Srivastava, S., & Dash, R. N. (2020, December). A new TS model based fuzzy logic approach for mobile robots path planning. In 2020 IEEE International Women in Engineering (WIE) Conference on Electrical and Computer Engineering (WIECON-ECE) (pp. 476-480). IEEE. doi: 10.1109/WIECON-ECE52138.2020.9397986
Mukhlif, F., & Saif, A. (2020, February). Comparative study on Bellman-Ford and Dijkstra algorithms, International Conference on Communication, Electrical and Computer Networks (ICCECN). Kuala Lumpur, Malaysia. Erişim adresi: https://www.researchgate.net/publication/340790429
Niu, C., Li, A., Huang, X., & Xu, C. (2021, October). Research on intelligent vehicle path planning method based on improved RRT algorithm. In 2021 Global Reliability and Prognostics and Health Management (PHM-Nanjing) (pp. 1-7). IEEE. doi: 10.1109/PHM-Nanjing52125.2021.9613000.
Pathak, M. J., Patel, R. L., & Rami, S. P. (2018). Comparative analysis of search algorithms. International Journal of Computer Applications, 179(50), 40-43. doi: 10.5120/IJCA2018917358
Patle, B. K., Pandey, A., Parhi, D. R. K., & Jagadeesh, A. (2019). A review: On path planning strategies for navigation of mobile robot. Defence Technology, 15(4), 582-606. doi: 10.1016/j.dt.2019.04.011
Paulino, L., Hannum, C., Varde, A. S., & Conti, C. J. (2021, September). Search methods in motion planning for mobile robots. In K. Arai (Eds.), Intelligent Systems and Applications. Proceedings of the 2021 Intelligent Systems Conference, (pp. 802-822). Cham: Springer. doi: 10.1007/978-3-030-82199-9_54
Permana, S. H., Bintoro, K. Y., Arifitama, B., & Syahputra, A. (2018). Comparative analysis of pathfinding algorithms A*, Dijkstra, and BFS on maze runner game. International Journal Of Information System & Technology, 1(2), 1-8. doi: 10.30645/IJISTECH.V1I2.7
Pradhan, S. K., Parhi, D. R., & Panda, A. K. (2009). Fuzzy logic techniques for navigation of several mobile robots. Applied soft computing, 9(1), 290-304. doi: 10.1016/j.asoc.2008.04.008
Samadi, M., & Othman, M. F. (2013, December). Global path planning for autonomous mobile robot using genetic algorithm. In 2013 International Conference on Signal-Image Technology & Internet-Based Systems (pp. 726-730). IEEE. doi: 10.1109/SITIS.2013.118.
Shamsfakhr, F., & Bigham, B. S. (2017). A neural network approach to navigation of a mobile robot and obstacle avoidance in dynamic and unknown environments. Turkish Journal of Electrical Engineering and Computer Sciences, 25(3), 1629-1642. doi: 1629-1642. 10.3906/elk-1603-75
Siegwart, R., Nourbakhsh, I. R., & Scaramuzza, D. (2011). Planning and Navigation. In R. C. Arkin (Eds.), Introduction to autonomous mobile robots, (pp. 369-423). London, England: The MIT Press.
Sung, I., Choi, B., & Nielsen, P. (2021). On the training of a neural network for online path planning with offline path planning algorithms. International Journal of Information Management, 57, 102142. doi: 10.1016/j.ijinfomgt.2020.102142
Tan, C. S., Mohd-Mokhtar, R., & Arshad, M. R. (2021). A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms. IEEE Access, 9, 119310-119342. doi: 10.1109/ACCESS.2021.3108177
Tuncer, A., & Yildirim, M. (2012). Dynamic path planning of mobile robots with improved genetic algorithm. Computers & Electrical Engineering, 38(6), 1564-1572. doi: 10.1016/j.compeleceng.2012.06.016
Wang, D., Tan, D., & Liu, L. (2018). Particle swarm optimization algorithm: an overview. Soft computing, 22(2), 387-408. doi:10.1007/s00500-016-2474-6
Wang, J., Wu, S., Li, H., & Zou, J. (2018, May). Path planning combining improved rapidly-exploring random trees with dynamic window approach in ROS. In 2018 13th IEEE Conference on Industrial Electronics and Applications (ICIEA) (pp. 1296-1301). IEEE. doi: 10.1109/ICIEA.2018.8397909
Zhang, H. Y., Lin, W. M., & Chen, A. X. (2018). Path planning for the mobile robot: a review. Symmetry, 10 (10), 450. doi:10.3390/sym10100450
Zhang, L., Zhang, Y., & Li, Y. (2020). Mobile robot path planning based on improved localized particle swarm optimization. IEEE Sensors Journal, 21(5), 6962-6972. doi: 10.1109/JSEN.2020.3039275

Ayrıntılar

Birincil Dil

Türkçe

Konular

Bilgisayar Yazılımı

Bölüm

Araştırma Makalesi

Yazarlar

Mehmet Gök ^*
0000-0003-1656-5770
Türkiye

Öznur Şifa Akçam
0000-0003-1458-3342
Türkiye

Mehmet Tekerek
0000-0001-6112-3651
Türkiye

Yayımlanma Tarihi

3 Haziran 2023

Gönderilme Tarihi

6 Eylül 2022

Kabul Tarihi

28 Kasım 2022

Yayımlandığı Sayı

Yıl 1970 Cilt: 26 Sayı: 2

DOI

https://doi.org/10.17780/ksujes.1171461

IZ

https://izlik.org/JA76NR88MZ

Kaynak Göster

RIS / Bibtex

APA

Gök, M., Akçam, Ö. Ş., & Tekerek, M. (2023). ARAMA ALGORİTMALARININ YOL PLANLAMASI PERFORMANSLARININ KARŞILAŞTIRMALI ANALİZİ. Kahramanmaraş Sütçü İmam Üniversitesi Mühendislik Bilimleri Dergisi, 26(2), 379-394. https://doi.org/10.17780/ksujes.1171461

Cited By

Evaluation of the Deep Q-Learning Models for Mobile Robot Path Planning Problem

Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji

https://doi.org/10.29109/gujsc.1455778

Performance analysis of A*, Dijkstra and RRT path planning algorithms on ROS-based Gazebo for LiDAR-based mecanum wheeled mobile autonomous robot

Journal of Innovative Engineering and Natural Science

https://doi.org/10.61112/jiens.1618552

ARAMA ALGORİTMALARININ YOL PLANLAMASI PERFORMANSLARININ KARŞILAŞTIRMALI ANALİZİ

Öz

Anahtar Kelimeler

Abstract

Kaynakça

Ayrıntılar

Birincil Dil

Konular

Bölüm

Yazarlar

Yayımlanma Tarihi

Gönderilme Tarihi

Kabul Tarihi

Yayımlandığı Sayı

DOI

IZ

Kaynak Göster

Cited By

Evaluation of the Deep Q-Learning Models for Mobile Robot Path Planning Problem

Performance analysis of A*, Dijkstra and RRT path planning algorithms on ROS-based Gazebo for LiDAR-based mecanum wheeled mobile autonomous robot