Research Article
BibTex RIS Cite

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

Year 2023, , 379 - 394, 03.06.2023

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

https://doi.org/10.17780/ksujes.1171461
Cited By: 1

Abstract

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.

Keywords

Yol planlama arama algoritmaları GIMP ROS RViz

References

  • 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

Year 2023, , 379 - 394, 03.06.2023

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

https://doi.org/10.17780/ksujes.1171461
Cited By: 1

Abstract

References

  • 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
There are 38 citations in total.

Details

Primary Language Turkish
Subjects Computer Software
Journal Section Computer Engineering
Authors

Mehmet Gök 0000-0003-1656-5770

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

Mehmet Tekerek 0000-0001-6112-3651

Publication Date June 3, 2023
Submission Date September 6, 2022
Published in Issue Year 2023

Cite

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