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

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

Yıl 2025, Cilt: 5 Sayı: 2, 589 - 606

Dilara Galeli , Bilge Kartal Cetın , Kamil Çetin

Öz

Effective path planning is crucial for mobile robots to navigate safely and efficiently in various environments. The main purpose of this study is to compare and investigate the performances of three important path planning algorithms, namely A*, Dijkstra and Rapidly exploring Random Trees (RRT), for a mobile autonomous robot with LiDAR sensors and mechanical wheels. The mobile robot can move in multiple directions with its mecanum wheels and can precisely avoid obstacles with the help of LiDAR sensors and decision-making mechanisms (path planning algorithms). Various scenarios with cluttered and open areas were used in a simulated ROS Gazebo environment to evaluate the effectiveness of each algorithm. The performance metrics among the algorithms were analyzed with respect to path length, time to reach the target, velocity command frequency and CPU utilization. In terms of travel time performance criterion, A* performed approximately 35% better than Dijkstra and 85% better than RRT. In terms of the path length traveled, A* reached the target in approximately 11% shorter path length than Dijkstra and 17% shorter path length than RRT. In terms of the number of velocity commands processed, A* outperformed Dijkstra by approximately 36% and RRT by 38%. In terms of CPU utilization performance criterion, RRT performed approximately 10% better than A* and 74% better than Dijkstra. As a result, significant information was obtained about the strengths and weaknesses of each algorithm in selecting the most appropriate path planning strategies for mobile autonomous robots.

Anahtar Kelimeler

Mobile robot LiDAR ROS Gazebo Path planning

Etik Beyan

The Authors declare that there is no conflict of interest.

Destekleyen Kurum

This study is supported by TÜBİTAK with project No. 1139B412302608, 2023.

Proje Numarası

1139B412302608

Teşekkür

This study was supported by the İzmir Katip Çelebi University Scientific Research Projects Coordination Unit with the project number 2022-GAP-MÜMF-0055.

Kaynakça

  • Levine S, Shah D (2022) Learning robotic navigation from experience: principles, methods and recent results. Phil Trans R Soc B 378:20210447. https://doi.org/10.1098/rstb.2021.0447
  • Sahoo SK, Choudhury BB (2023) A review of methodologies for path planning and optimization of mobile robots. Journal of process management and new technologies 11(1-2):122-140. https://doi.org/10.5937/jpmnt11-45039
  • Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1:269–271. https://doi.org/10.1007/BF01386390
  • Hart PE, Nilsson NJ, Raphael B (1968) A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics 4(2):100–7. https://doi: 10.1109/TSSC.1968.300136
  • LaValle SM (1998) Rapidly-exploring random trees: A new tool for path planning. Technical Report Computer Science Department, Iowa State University.
  • Al-Ansarry, Suhaib, Al-Darraji S (2021) Hybrid RRT-A*: An Improved Path Planning Method for an Autonomous Mobile Robots. Iraqi Journal for Electrical & Electronic Engineering 17(1):1-10. https://doi.org/10.37917/ijeee.17.1.13
  • Dirik M, Kocamaz F (2020) Rrt-dijkstra: An improved path planning algorithm for mobile robots. Journal of Soft Computing and Artificial Intelligence 1(2):69-77.
  • Chen R, Hu J, Xu W (2022) An RRT-Dijkstra-Based Path Planning Strategy for Autonomous Vehicles. Applied Sciences 12(23):11982. https://doi.org/10.3390/app122311982
  • Zammit C, Van Kampen EJ (2022) Comparison between A* and RRT algorithms for 3D UAV path planning. Unmanned Systems 10(02):129-146. https://doi.org/10.1142/S2301385022500078
  • Cai Q (2024) A Comparison Between A* and RRT Algorithm in Path Planning for Mobile Robot. Highlights in Science, Engineering and Technology 97:282-287. https://doi.org/10.54097/2stv5y97
  • Aydemir H, Tekerek M, Gök M (2021) Examining of the Effect of Geometric Objects on SLAM Performance Using ROS and Gazebo. El-Cezeri 8(3):1441-1454. https://doi.org/10.31202/ecjse.943364
  • Zhou L, Zhu C, Su X (2022) Slam algorithm and navigation for indoor mobile robot based on ros. IEEE International Conference on Software Engineering and Artificial Intelligence pp. 230-236. Xiamen, China, June 10-12. https://doi.org/10.1109/SEAI55746.2022.9832313
  • Karur K, Sharma N, Dharmatti C, Siegel JE (2021) A survey of path planning algorithms for mobile robots. Vehicles 3(3):448-468. https://doi.org/10.3390/vehicles3030027
  • Gök M, Akçam ÖŞ, Tekerek M (2022) Performance Analysis of Search Algorithms for Path Planning, KSU Journal of Engineering Sciences 26(2):379-394. https://doi.org/10.17780/ksujes.1171461
  • Yao J (2023) Path planning algorithm of indoor mobile robot based on ROS system. IEEE International Conference on Image Processing and Computer Applications pp. 523-529. Changchun, China, August 11-13. https://doi.org/10.1109/ICIPCA59209.2023.10257966
  • Tamang MT, Maheriya D, Sharif MS, Sutharssan T (2024) Autonomous Navigation for TurtleBot3 Robots in Gazebo Simulation Environment. International Conference on Innovation and Intelligence for Informatics, Computing, and Technologies pp. 568-574. Sakhir, Bahrain, November 17-19. https://doi.org/10.1109/3ict64318.2024.10824668
  • Megalingam RK, Rajendraprasad A, Manoharan SK (2020) Comparison of planned path and travelled path using ROS navigation stack. International Conference for Emerging Technology pp. 1-6. Belgaum, India, June 5-7. https://doi.org/10.1109/INCET49848.2020.9154132
  • Breiling B, Dieber B, Schartner P (2017) Secure communication for the robot operating system. IEEE international systems conference pp. 1-6. Montreal, QC, Canada, April 24-27. https://doi.org/10.1109/SYSCON.2017.7934755
  • Quigley M, Conley K, Gerkey B et al (2009) ROS: an open-source Robot Operating System. 3-3.2, p. 5. ICRA workshop on open source software, Kobe, Japan, May 12-17.
  • Rivera ZB, De Simone MC, Guida D (2019). Unmanned ground vehicle modelling in Gazebo/ROS-based environments. Machines, 7(2), 42. https://doi.org/10.3390/machines7020042
  • Qiao J, Guo J, Li Y (2024) Simultaneous localization and mapping (SLAM)-based robot localization and navigation algorithm. Appl Water Sci 14, 151. https://doi.org/10.1007/s13201-024-02183-6
  • Duchoň F, Babinec A, Kajan M, Beňo P, Florek M, Fico T, Jurišica L (2014) Path planning with modified a star algorithm for a mobile robot. Procedia engineering, 96:59-69. https://doi.org/10.1016/j.proeng.2014.12.098
  • Zhang L, Li Y (2021) Mobile robot path planning algorithm based on improved a star. Journal of Physics: Conference Series 1848-1, p.012013, Sanya, China, Jan. 29-31. https://doi.org/10.1088/1742-6596/1848/1/012013
  • Nayak S, Bhat, M, Reddy NS, Rao BA (2022) Study of distance metrics on k-nearest neighbor algorithm for star categorization. Journal of Physics: Conference Series v.2161-1, pp.012004, Manipal, India, Oct. 28-30. https://doi.org/10.1088/1742-6596/2161/1/012004
  • Bernardo GT, Vogás LM, Rodrigues SD, Lopes TG et al (2022) A-star based algorithm applied to target search and rescue by a uav swarm. Latin American Robotics Symposium, Brazilian Symposium on Robotics, and Workshop on Robotics in Education, pp.49-54. São Bernardo do Campo, Brazil, Oct. 18-21. https://doi.org/10.1109/LARS/SBR/WRE56824.2022.9996054
  • Javaid A (2013) Understanding Dijkstra's algorithm. SSRN 2340905. https://doi.org/10.2139/ssrn.2340905
  • Candra A, Budiman MA, Hartanto K (2020) Dijkstra's and a-star in finding the shortest path: A tutorial. International Conference on Data Science, Artificial Intelligence, and Business Analytics pp.28-32, Medan, Indonesia, July 16-17. https://doi.org/10.1109/DATABIA50434.2020.9190342
  • Rachmawati D, Gustin L (2020) Analysis of Dijkstra’s algorithm and A* algorithm in shortest path problem. Journal of Physics: Conference Series, Medan 1566-1, pp.012061, Indonesia, Nov. 26-27, 2019. https://doi.org/10.1088/1742-6596/1566/1/012061
  • Karaman S, Walter MR, Perez A, Frazzoli E, Teller S (2011) Anytime motion planning using the RRT. IEEE international conference on robotics and automation pp.1478-1483, Shanghai, China, May 9-13. https://doi.org/10.1109/ICRA.2011.5980479
  • Duchoň F, Hažík J, Rodina J et al (2019) Verification of slam methods implemented in ros. Journal of Multidisciplinary Engineering Science and Technology, 6(9):2458-9403. https://doi.org/10.22223/tr.2016-1/2011
  • Rojas-Fernández M, Mújica-Vargas D, Matuz-Cruz M, López-Borreguero D (2018) Performance comparison of 2D SLAM techniques available in ROS using a differential drive robot. International Conference on Electronics, Communications and Computers pp.50-58, Cholula, Mexico, Feb. 21-23. https://doi.org/10.1109/CONIELECOMP.2018.8327175
  • Walenta R, Schellekens T, Ferrein A, Schiffer S (2017) A decentralised system approach for controlling AGVs with ROS. IEEE AFRICON pp.1436-1441, Cape Town, South Africa, Sept. 18-20. https://doi.org/10.1109/AFRCON.2017.8095693
  • Thale SP, Prabhu MM, Thakur PV, Kadam P (2020) ROS based SLAM implementation for Autonomous navigation using Turtlebot. ITM Web of conferences v.32 p.01011, Navi Mumbai, India, June 27-28. https://doi.org/10.1051/itmconf/20203201011
  • Chen SP, Peng CY, Huang GS, Lai CC, Chen CC, Yen MH (2023). Comparison of 2D and 3D LiDARs Trajectories and AMCL Positioning in ROS-Based move_base Navigation. IEEE International Conference on Omni-layer Intelligent Systems pp. 1-6, Berlin, Germany, July 23-25. https://doi.org/10.1109/COINS57856.2023.10189271

LiDAR tabanlı mekanum tekerlekli mobil otonom robot için ROS tabanlı Gazebo üzerinde A*, Dijkstra ve RRT yol planlama algoritmalarının performans analizi

Yıl 2025, Cilt: 5 Sayı: 2, 589 - 606

Dilara Galeli , Bilge Kartal Cetın , Kamil Çetin

Öz

Mobil robotların çeşitli ortamlarda güvenli ve verimli bir şekilde gezinmesi için etkili yol planlaması yapmak çok önemlidir. Bu çalışmada, LiDAR sensörlü ve mecanum tekerleklerli bir mobil robot için üç önemli yol planlama algoritmasının (A*, Dijkstra ve Rapidly-exploring Random Trees (RRT)) performans karşılaştırmaları yapılmıştır. Mobil robot sahip olduğu mecanum tekerleklerle çok yönlü hareket yapabilir ve LiDAR sensörü ve karar alma mekanizması (yol planlama algoritmaları) sayesinde hassas şekilde engellerden kaçınabilir. Her algoritmanın etkinliğini değerlendirmek için simüle edilmiş bir ROS Gazebo ortamında dağınık ve açık alanlara sahip çeşitli senaryolar kullanılmıştır. Algoritmalar arasındaki performans ölçütleri, yol uzunluğu, hedefe ulaşma süresi, hız komut sıklığı ve işlemci kullanım miktarına göre analiz edilmiştir. Sonuç olarak, mobil otonom robotlar için en uygun yol planlama stratejilerinin seçiminde her algoritmanın güçlü ve zayıf yönleri hakkında önemli bilgiler elde edilmiştir.

Anahtar Kelimeler

Mobil robot LiDAR ROS Gazebo Yol planlama

Proje Numarası

1139B412302608

Kaynakça

  • Levine S, Shah D (2022) Learning robotic navigation from experience: principles, methods and recent results. Phil Trans R Soc B 378:20210447. https://doi.org/10.1098/rstb.2021.0447
  • Sahoo SK, Choudhury BB (2023) A review of methodologies for path planning and optimization of mobile robots. Journal of process management and new technologies 11(1-2):122-140. https://doi.org/10.5937/jpmnt11-45039
  • Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1:269–271. https://doi.org/10.1007/BF01386390
  • Hart PE, Nilsson NJ, Raphael B (1968) A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics 4(2):100–7. https://doi: 10.1109/TSSC.1968.300136
  • LaValle SM (1998) Rapidly-exploring random trees: A new tool for path planning. Technical Report Computer Science Department, Iowa State University.
  • Al-Ansarry, Suhaib, Al-Darraji S (2021) Hybrid RRT-A*: An Improved Path Planning Method for an Autonomous Mobile Robots. Iraqi Journal for Electrical & Electronic Engineering 17(1):1-10. https://doi.org/10.37917/ijeee.17.1.13
  • Dirik M, Kocamaz F (2020) Rrt-dijkstra: An improved path planning algorithm for mobile robots. Journal of Soft Computing and Artificial Intelligence 1(2):69-77.
  • Chen R, Hu J, Xu W (2022) An RRT-Dijkstra-Based Path Planning Strategy for Autonomous Vehicles. Applied Sciences 12(23):11982. https://doi.org/10.3390/app122311982
  • Zammit C, Van Kampen EJ (2022) Comparison between A* and RRT algorithms for 3D UAV path planning. Unmanned Systems 10(02):129-146. https://doi.org/10.1142/S2301385022500078
  • Cai Q (2024) A Comparison Between A* and RRT Algorithm in Path Planning for Mobile Robot. Highlights in Science, Engineering and Technology 97:282-287. https://doi.org/10.54097/2stv5y97
  • Aydemir H, Tekerek M, Gök M (2021) Examining of the Effect of Geometric Objects on SLAM Performance Using ROS and Gazebo. El-Cezeri 8(3):1441-1454. https://doi.org/10.31202/ecjse.943364
  • Zhou L, Zhu C, Su X (2022) Slam algorithm and navigation for indoor mobile robot based on ros. IEEE International Conference on Software Engineering and Artificial Intelligence pp. 230-236. Xiamen, China, June 10-12. https://doi.org/10.1109/SEAI55746.2022.9832313
  • Karur K, Sharma N, Dharmatti C, Siegel JE (2021) A survey of path planning algorithms for mobile robots. Vehicles 3(3):448-468. https://doi.org/10.3390/vehicles3030027
  • Gök M, Akçam ÖŞ, Tekerek M (2022) Performance Analysis of Search Algorithms for Path Planning, KSU Journal of Engineering Sciences 26(2):379-394. https://doi.org/10.17780/ksujes.1171461
  • Yao J (2023) Path planning algorithm of indoor mobile robot based on ROS system. IEEE International Conference on Image Processing and Computer Applications pp. 523-529. Changchun, China, August 11-13. https://doi.org/10.1109/ICIPCA59209.2023.10257966
  • Tamang MT, Maheriya D, Sharif MS, Sutharssan T (2024) Autonomous Navigation for TurtleBot3 Robots in Gazebo Simulation Environment. International Conference on Innovation and Intelligence for Informatics, Computing, and Technologies pp. 568-574. Sakhir, Bahrain, November 17-19. https://doi.org/10.1109/3ict64318.2024.10824668
  • Megalingam RK, Rajendraprasad A, Manoharan SK (2020) Comparison of planned path and travelled path using ROS navigation stack. International Conference for Emerging Technology pp. 1-6. Belgaum, India, June 5-7. https://doi.org/10.1109/INCET49848.2020.9154132
  • Breiling B, Dieber B, Schartner P (2017) Secure communication for the robot operating system. IEEE international systems conference pp. 1-6. Montreal, QC, Canada, April 24-27. https://doi.org/10.1109/SYSCON.2017.7934755
  • Quigley M, Conley K, Gerkey B et al (2009) ROS: an open-source Robot Operating System. 3-3.2, p. 5. ICRA workshop on open source software, Kobe, Japan, May 12-17.
  • Rivera ZB, De Simone MC, Guida D (2019). Unmanned ground vehicle modelling in Gazebo/ROS-based environments. Machines, 7(2), 42. https://doi.org/10.3390/machines7020042
  • Qiao J, Guo J, Li Y (2024) Simultaneous localization and mapping (SLAM)-based robot localization and navigation algorithm. Appl Water Sci 14, 151. https://doi.org/10.1007/s13201-024-02183-6
  • Duchoň F, Babinec A, Kajan M, Beňo P, Florek M, Fico T, Jurišica L (2014) Path planning with modified a star algorithm for a mobile robot. Procedia engineering, 96:59-69. https://doi.org/10.1016/j.proeng.2014.12.098
  • Zhang L, Li Y (2021) Mobile robot path planning algorithm based on improved a star. Journal of Physics: Conference Series 1848-1, p.012013, Sanya, China, Jan. 29-31. https://doi.org/10.1088/1742-6596/1848/1/012013
  • Nayak S, Bhat, M, Reddy NS, Rao BA (2022) Study of distance metrics on k-nearest neighbor algorithm for star categorization. Journal of Physics: Conference Series v.2161-1, pp.012004, Manipal, India, Oct. 28-30. https://doi.org/10.1088/1742-6596/2161/1/012004
  • Bernardo GT, Vogás LM, Rodrigues SD, Lopes TG et al (2022) A-star based algorithm applied to target search and rescue by a uav swarm. Latin American Robotics Symposium, Brazilian Symposium on Robotics, and Workshop on Robotics in Education, pp.49-54. São Bernardo do Campo, Brazil, Oct. 18-21. https://doi.org/10.1109/LARS/SBR/WRE56824.2022.9996054
  • Javaid A (2013) Understanding Dijkstra's algorithm. SSRN 2340905. https://doi.org/10.2139/ssrn.2340905
  • Candra A, Budiman MA, Hartanto K (2020) Dijkstra's and a-star in finding the shortest path: A tutorial. International Conference on Data Science, Artificial Intelligence, and Business Analytics pp.28-32, Medan, Indonesia, July 16-17. https://doi.org/10.1109/DATABIA50434.2020.9190342
  • Rachmawati D, Gustin L (2020) Analysis of Dijkstra’s algorithm and A* algorithm in shortest path problem. Journal of Physics: Conference Series, Medan 1566-1, pp.012061, Indonesia, Nov. 26-27, 2019. https://doi.org/10.1088/1742-6596/1566/1/012061
  • Karaman S, Walter MR, Perez A, Frazzoli E, Teller S (2011) Anytime motion planning using the RRT. IEEE international conference on robotics and automation pp.1478-1483, Shanghai, China, May 9-13. https://doi.org/10.1109/ICRA.2011.5980479
  • Duchoň F, Hažík J, Rodina J et al (2019) Verification of slam methods implemented in ros. Journal of Multidisciplinary Engineering Science and Technology, 6(9):2458-9403. https://doi.org/10.22223/tr.2016-1/2011
  • Rojas-Fernández M, Mújica-Vargas D, Matuz-Cruz M, López-Borreguero D (2018) Performance comparison of 2D SLAM techniques available in ROS using a differential drive robot. International Conference on Electronics, Communications and Computers pp.50-58, Cholula, Mexico, Feb. 21-23. https://doi.org/10.1109/CONIELECOMP.2018.8327175
  • Walenta R, Schellekens T, Ferrein A, Schiffer S (2017) A decentralised system approach for controlling AGVs with ROS. IEEE AFRICON pp.1436-1441, Cape Town, South Africa, Sept. 18-20. https://doi.org/10.1109/AFRCON.2017.8095693
  • Thale SP, Prabhu MM, Thakur PV, Kadam P (2020) ROS based SLAM implementation for Autonomous navigation using Turtlebot. ITM Web of conferences v.32 p.01011, Navi Mumbai, India, June 27-28. https://doi.org/10.1051/itmconf/20203201011
  • Chen SP, Peng CY, Huang GS, Lai CC, Chen CC, Yen MH (2023). Comparison of 2D and 3D LiDARs Trajectories and AMCL Positioning in ROS-Based move_base Navigation. IEEE International Conference on Omni-layer Intelligent Systems pp. 1-6, Berlin, Germany, July 23-25. https://doi.org/10.1109/COINS57856.2023.10189271
Toplam 34 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Mekatronik Sistemlerin Simülasyonu, Modellenmesi ve Programlanması, Otonom Araç Sistemleri
Bölüm Araştırma Makaleleri
Yazarlar

Dilara Galeli 0009-0002-4970-9865

Bilge Kartal Cetın 0000-0002-3338-1538

Kamil Çetin 0000-0003-1029-5626

Proje Numarası 1139B412302608
Yayımlanma Tarihi
Gönderilme Tarihi 12 Ocak 2025
Kabul Tarihi 27 Mart 2025
Yayımlandığı Sayı Yıl 2025 Cilt: 5 Sayı: 2

Kaynak Göster

APA Galeli, D., Kartal Cetın, B., & Çetin, K. (t.y.). 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, 5(2), 589-606.
 Kapak Resmi İndir


by.png
Journal of Innovative Engineering and Natural Science by İdris Karagöz is licensed under CC BY 4.0