Critical Evaluations of Path Planning Algorithms: A Comprehensive Review
Keywords:
path planning, Mobile robots, Review, Static environment, Sampling methods, Graph methodsAbstract
Over the past few years, there has been a significant amount of interest in the research of path planning strategies, particularly in situations that remained static. This is because it is pertinent to the operations of mobile robots that are successful and autonomous. The reason for this is that it is relevant. The purpose of this study is to investigate and evaluate the algorithms and methodologies that are currently being utilized for the purpose of path planning in static settings. This study was specifically constructed for the purpose of achieving this goal. Graph-based algorithms and sampling-based algorithms are the two kinds that will be the focus of our subsequent discussion in this section. Both of these categories are subjected to a comprehensive investigation, with a particular emphasis placed on the underlying ideas, problems, and opportunities that lay beneath them. A special emphasis is being placed on the specific factors that need to be taken into consideration when applying graph-based and sampling-based tactics in static settings. In addition, various trajectories for future study are being evaluated.
References
1. L. Liu, X. Wang, X. Yang, H. Liu, J. Li, and P. Wang, “Path planning techniques for mobile robots: Review and prospect,” Oct. 01, 2023, Elsevier Ltd. doi: 10.1016/j.eswa.2023.120254.
2. R. Raj and A. Kos, “A Comprehensive Study of Mobile Robot: History, Developments, Applications, and Future Research Perspectives,” Jul. 01, 2022, MDPI. doi: 10.3390/app12146951.
3. J. R. Sánchez-Ibáñez, C. J. Pérez-Del-pulgar, and A. García-Cerezo, “Path planning for autonomous mobile robots: A review,” Dec. 01, 2021, MDPI. doi: 10.3390/s21237898.
4. B. K. Patle, G. Babu L, A. Pandey, D. R. K. Parhi, and A. Jagadeesh, “A review: On path planning strategies for navigation of mobile robot,” Aug. 01, 2019, China Ordnance Society. doi: 10.1016/j.dt.2019.04.011.
5. L. Yang et al., “Path Planning Technique for Mobile Robots: A Review,” Oct. 01, 2023, Multidisciplinary Digital Publishing Institute (MDPI). doi: 10.3390/machines11100980.
6. C. Zhou, B. Huang, and P. Fränti, “A review of motion planning algorithms for intelligent robots,” Feb. 01, 2022, Springer. doi: 10.1007/s10845-021-01867-z.
7. B. K. Jogeshwar and K. Lochan, “Algorithms for Path Planning on Mobile Robots,” in IFAC-PapersOnLine, Elsevier B.V., 2022, pp. 94–100. doi: 10.1016/j.ifacol.2022.04.016.
8. J. R. Sánchez-Ibáñez, C. J. Pérez-Del-pulgar, and A. García-Cerezo, “Path planning for autonomous mobile robots: A review,” Dec. 01, 2021, MDPI. doi: 10.3390/s21237898.
9. S. Lin, A. Liu, J. Wang, and X. Kong, “A Review of Path-Planning Approaches for Multiple Mobile Robots,” Sep. 01, 2022, MDPI. doi: 10.3390/machines10090773.
10. F. Gul, W. Rahiman, and S. S. Nazli Alhady, “A comprehensive study for robot navigation techniques,” Jan. 01, 2019, Cogent OA. doi: 10.1080/23311916.2019.1632046.
11. K. Karur, N. Sharma, C. Dharmatti, and J. E. Siegel, “A Survey of Path Planning Algorithms for Mobile Robots,” Vehicles, vol. 3, no. 3, pp. 448–468, Sep. 2021, doi: 10.3390/vehicles3030027.
12. B. K. Patle, G. Babu L, A. Pandey, D. R. K. Parhi, and A. Jagadeesh, “A review: On path planning strategies for navigation of mobile robot,” Aug. 01, 2019, China Ordnance Society. doi: 10.1016/j.dt.2019.04.011.
13. X. Zhou, J. Yan, M. Yan, K. Mao, R. Yang, and W. Liu, “Path Planning of Rail-Mounted Logistics Robots Based on the Improved Dijkstra Algorithm,” Applied Sciences (Switzerland), vol. 13, no. 17, Sep. 2023, doi: 10.3390/app13179955.
14. L. S. Liu et al., “Path Planning for Smart Car Based on Dijkstra Algorithm and Dynamic Window Approach,” Wirel Commun Mob Comput, vol. 2021, 2021, doi: 10.1155/2021/8881684.
15. X. Li, “Path planning of intelligent mobile robot based on Dijkstra algorithm,” in Journal of Physics: Conference Series, IOP Publishing Ltd, Dec. 2021. doi: 10.1088/1742-6596/2083/4/042034.
16. R. Szczepanski and T. Tarczewski, “Global path planning for mobile robot based on Artificial Bee Colony and Dijkstra’s algorithms,” in Proceedings - 2021 IEEE 19th International Power Electronics and Motion Control Conference, PEMC 2021, Institute of Electrical and Electronics Engineers Inc., Apr. 2021, pp. 724–730. doi: 10.1109/PEMC48073.2021.9432570.
17. A. Alyasin, E. I. Abbas, and S. D. Hasan, “An Efficient Optimal Path Finding for Mobile Robot Based on Dijkstra Method,” in 4th Scientific International Conference Najaf, SICN 2019, Institute of Electrical and Electronics Engineers Inc., Apr. 2019, pp. 11–14. doi: 10.1109/SICN47020.2019.9019345.
18. R. S. Wijaya, A. Mahendra, S. Prayoga, and A. Wibisana, “Path Planning Application using Dijkstra Algorithm on Service Robot,” 2024, pp. 262–271. doi: 10.2991/978-94-6463-620-8_20.
19. D. Rachmawati and L. Gustin, “Analysis of Dijkstra’s Algorithm and A∗ Algorithm in Shortest Path Problem,” in Journal of Physics: Conference Series, Institute of Physics Publishing, Jul. 2020. doi: 10.1088/1742-6596/1566/1/012061.
20. M. Luo, X. Hou, and J. Yang, “Surface Optimal Path Planning Using an Extended Dijkstra Algorithm,” IEEE Access, vol. 8, pp. 147827–147838, 2020, doi: 10.1109/ACCESS.2020.3015976.
21. O. M. ÇELİK and M. KÖSEOĞLU, “A Modified Dijkstra Algorithm for ROS Based Autonomous Mobile Robots,” Journal of Advanced Research in Natural and Applied Sciences, vol. 9, no. 1, pp. 205–217, Mar. 2023, doi: 10.28979/jarnas.1119957.
22. J. Pak, J. Kim, Y. Park, and H. Il Son, “Field Evaluation of Path-Planning Algorithms for Autonomous Mobile Robot in Smart Farms,” IEEE Access, vol. 10, pp. 60253–60266, 2022, doi: 10.1109/ACCESS.2022.3181131.
23. S. Alshammrei, S. Boubaker, and L. Kolsi, “Improved Dijkstra Algorithm for Mobile Robot Path Planning and Obstacle Avoidance,” Computers, Materials and Continua, vol. 72, no. 3, pp. 5939–5954, 2022, doi: 10.32604/cmc.2022.028165.
24. L. Zhang and Y. Li, “Mobile Robot Path Planning Algorithm Based on Improved A Star,” in Journal of Physics: Conference Series, IOP Publishing Ltd, Apr. 2021. doi: 10.1088/1742-6596/1848/1/012013.
25. G. Tang, C. Tang, C. Claramunt, X. Hu, and P. Zhou, “Geometric A-Star Algorithm: An Improved A-Star Algorithm for AGV Path Planning in a Port Environment,” IEEE Access, vol. 9, pp. 59196–59210, 2021, doi: 10.1109/ACCESS.2021.3070054.
26. H. Liu and Y. Zhang, “ASL-DWA: An Improved A-Star Algorithm for Indoor Cleaning Robots,” IEEE Access, vol. 10, pp. 99498–99515, 2022, doi: 10.1109/ACCESS.2022.3206356.
27. W. Xin, L. Wanlin, F. Chao, and H. Likai, “Path Planning Research Based on An Improved A∗ Algorithmfor Mobile Robot,” in IOP Conference Series: Materials Science and Engineering, Institute of Physics Publishing, Aug. 2019. doi: 10.1088/1757-899X/569/5/052044.
28. F. Duchon et al., “Path planning with modified A star algorithm for a mobile robot,” in Procedia Engineering, Elsevier Ltd, 2014, pp. 59–69. doi: 10.1016/j.proeng.2014.12.098.
29. D. Xiang, H. Lin, J. Ouyang, and D. Huang, “Combined improved A* and greedy algorithm for path planning of multi-objective mobile robot,” Sci Rep, vol. 12, no. 1, Dec. 2022, doi: 10.1038/s41598-022-17684-0.
30. X. Dai, S. Long, Z. Zhang, and D. Gong, “Mobile robot path planning based on ant colony algorithm with a∗ heuristic method,” Front Neurorobot, vol. 13, Apr. 2019, doi: 10.3389/fnbot.2019.00015.
31. O. O. Martins, A. A. Adekunle, O. M. Olaniyan, and B. O. Bolaji, “An Improved multi-objective a-star algorithm for path planning in a large workspace: Design, Implementation, and Evaluation,” Sci Afr, vol. 15, Mar. 2022, doi: 10.1016/j.sciaf.2021.e01068.
32. T. XiangRong, Z. Yukun, and J. XinXin, “Improved a-star algorithm for robot path planning in static environment,” in Journal of Physics: Conference Series, IOP Publishing Ltd, Feb. 2021. doi: 10.1088/1742-6596/1792/1/012067.
33. J. Jermyn, “A Comparison of the Effectiveness of the RRT, PRM, and Novel Hybrid RRT-PRM Path Planners,” Int J Res Appl Sci Eng Technol, vol. 9, no. 12, pp. 600–611, Dec. 2021, doi: 10.22214/ijraset.2021.39297.
34. S. Alarabi, C. Luo, and M. Santora, “A PRM Approach to Path Planning with Obstacle Avoidance of an Autonomous Robot,” in 2022 8th International Conference on Automation, Robotics and Applications, ICARA 2022, Institute of Electrical and Electronics Engineers Inc., 2022, pp. 76–80. doi: 10.1109/ICARA55094.2022.9738559.
35. G. Song, S. Thomas, and N. M. Amato, “A general framework for PRM motion planning,” in 2003 IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422), 2003, pp. 4445–4450.
36. Q. Li, Y. Xu, S. Bu, and J. Yang, “Smart Vehicle Path Planning Based on Modified PRM Algorithm,” Sensors, vol. 22, no. 17, Sep. 2022, doi: 10.3390/s22176581.
37. L. Changan, C. Jingang, and L. Chunyang, “Path Planning for Mobile Robot Based on an Improved Probabilistic Roadmap Method *,” 2009.
38. L. Qiao, X. Luo, and Q. Luo, “An Optimized Probabilistic Roadmap Algorithm for Path Planning of Mobile Robots in Complex Environments with Narrow Channels,” Sensors, vol. 22, no. 22, Nov. 2022, doi: 10.3390/s22228983.
39. L. Jaillet and T. Siméon, “A PRM-based motion planner for dynamically changing environments,” in 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2004, pp. 1606–1611. doi: 10.1109/iros.2004.1389625.
40. A. MSaeed, K. Shaaban Rijab, A. M. Saeed, and K. S. Rijab, “Enhancing Performance of Path Planning PRM Algorithm for Automated Boat Using PID Controller,” Journal of Global Scientific Research in Electrical and Electronic Engineering, vol. 9, pp. 3678–3689, 2024, doi: 10.5281/jgsr.2024.14039138.
41. R. Bohlin and L. E. Kavraki, “Path planning using Lazy PRM,” Proceedings-IEEE International Conference on Robotics and Automation, vol. 1, pp. 521–528, 2000, doi: 10.1109/ROBOT.2000.844107.
42. X. Ma, R. Gong, Y. Tan, H. Mei, and C. Li, “Path Planning of Mobile Robot Based on Improved PRM Based on Cubic Spline,” Wirel Commun Mob Comput, vol. 2022, 2022, doi: 10.1155/2022/1632698.
43. L. Garrote, C. Premebida, M. Silva, and U. Nunes, “An RRT-based navigation approach for mobile robots and automated vehicles,” in Proceedings - 2014 12th IEEE International Conference on Industrial Informatics, INDIN 2014, Institute of Electrical and Electronics Engineers Inc., Nov. 2014, pp. 326–331. doi: 10.1109/INDIN.2014.6945533.
44. J. G. Kang, D. W. Lim, Y. S. Choi, W. J. Jang, and J. W. Jung, “Improved RRT-connect algorithm based on triangular inequality for robot path planning,” Sensors (Switzerland), vol. 21, no. 2, pp. 1–34, Jan. 2021, doi: 10.3390/s21020333.
45. I. Noreen, A. Khan, and Z. Habib, “A Comparison of RRT, RRT* and RRT*-Smart Path Planning Algorithms,” 2016.
46. Z. Wu, Z. Meng, W. Zhao, and Z. Wu, “Fast-RRT: A RRT-based optimal path finding method,” Applied Sciences (Switzerland), vol. 11, no. 24, Dec. 2021, doi: 10.3390/app112411777.
47. B. Liu and C. Liu, “Path planning of mobile robots based on improved RRT algorithm,” in Journal of Physics: Conference Series, IOP Publishing Ltd, Apr. 2022. doi: 10.1088/1742-6596/2216/1/012020.
48. R. Mashayekhi, M. Y. I. Idris, M. H. Anisi, I. Ahmedy, and I. Ali, “Informed RRT∗-Connect: An Asymptotically Optimal Single-Query Path Planning Method,” IEEE Access, vol. 8, pp. 19842–19852, 2020, doi: 10.1109/ACCESS.2020.2969316.
49. P. Xin, X. Wang, X. Liu, Y. Wang, Z. Zhai, and X. Ma, “Improved Bidirectional RRT* Algorithm for Robot Path Planning,” Sensors, vol. 23, no. 2, Jan. 2023, doi: 10.3390/s23021041.
50. K. Hao, Y. Yang, Z. Li, Y. Liu, and X. Zhao, “CERRT: A Mobile Robot Path Planning Algorithm Based on RRT in Complex Environments,” Applied Sciences (Switzerland), vol. 13, no. 17, Sep. 2023, doi: 10.3390/app13179666.
51. Feraco, S. ; Luciani, S. ; Bonfitto, and A. ; Amati, “A local trajectory planning and control method for autonomous vehicles based on the RRT algorithm,” 2021.
52. J. Chen, Y. Zhao, and X. Xu, “Improved RRT-Connect Based Path Planning Algorithm for Mobile Robots,” IEEE Access, vol. 9, pp. 145988–145999, 2021, doi: 10.1109/ACCESS.2021.3123622.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Abbas Nadhim Kadhim, Muhammed Sabri Salim
This work is licensed under a Creative Commons Attribution 4.0 International License.
