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

Abstract

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.

Keywords

• Mobil robot
• LiDAR
• ROS
• Gazebo
• Yol planlama

Project Number

1139B412302608

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

Abstract

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.

Keywords

• Mobile robot
• LiDAR
• ROS
• Gazebo
• Path planning

Supporting Institution

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

Project Number

1139B412302608

Ethical Statement

The Authors declare that there is no conflict of interest.

Thanks

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

References

1. 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
2. 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
3. Dijkstra EW (1959) A note on two problems in connexion with graphs. Numerische Mathematik 1:269–271. https://doi.org/10.1007/BF01386390
4. 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
5. LaValle SM (1998) Rapidly-exploring random trees: A new tool for path planning. Technical Report Computer Science Department, Iowa State University.
6. 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
7. 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.
8. 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

9. 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
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
17. 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
18. 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
19. 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.
20. 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
21. 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
22. 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
23. 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
24. 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
25. 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
26. Javaid A (2013) Understanding Dijkstra's algorithm. SSRN 2340905. https://doi.org/10.2139/ssrn.2340905
27. 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
28. 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
29. 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
30. 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
31. 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
32. 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
33. 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
34. 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