Araştırma Makalesi
BibTex RIS Kaynak Göster

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

Yıl 2023, Cilt: 26 Sayı: 2, 379 - 394, 03.06.2023

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

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

Ö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

Yol planlama arama algoritmaları GIMP ROS RViz

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

Yıl 2023, Cilt: 26 Sayı: 2, 379 - 394, 03.06.2023

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

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

Öz

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
Toplam 38 adet kaynakça vardır.

Ayrıntılar

Birincil Dil Türkçe
Konular Bilgisayar Yazılımı
Bölüm Bilgisayar Mühendisliği
Yazarlar

Mehmet Gök 0000-0003-1656-5770

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

Mehmet Tekerek 0000-0001-6112-3651

Yayımlanma Tarihi 3 Haziran 2023
Gönderilme Tarihi 6 Eylül 2022
Yayımlandığı Sayı Yıl 2023Cilt: 26 Sayı: 2

Kaynak Göster

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
 Kapak Resmi İndir