Evaluation of popular path planning algorithms

• Autorzy: Kara Mehmet

Identyfikatory

DOI

10.24425/ijet.2023.147699

• Języki publikacji: EN

Abstrakty

EN

The navigation of mobile robots is a key element of autonomous systems, which allows robots to move effectively and securely in changing environments with greater autonomy and precision. This study aims to provide researchers with a comprehensive guide for selecting the best path-planning methods for their particular projects. We evaluate some popular algorithms that are regularly used in mobile robot navigation, in order to demonstrate their specifications and determine where they are most effective. For example, one algorithm is used to model the problem as a standard graph, and another algorithm is found to be the most suitable for highly dynamic and highly dimensional environments, due to its robust path-planning capabilities and efficient route construction. We also filter high-performance algorithms in terms of computational complexity, accuracy, and robustness. In conclusion, this study provides valuable information on its individual strengths and weaknesses, helping robotics and engineers make informed decisions when selecting the most appropriate algorithm for their specific applications.

Słowa kluczowe

EN

mobile robots; navigation; algorithms; evaluation; robotics

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2024
• Tom: Vol. 70, No. 1
• Strony: 13--22
• Opis fizyczny: Bibliogr. 38 poz., rys., tab.

Twórcy

autor

Kara Mehmet

• AGH University of Science and Technology, Krakow, Poland

• https://orcid.org/0000-0001-9045-2614

Bibliografia

• [1] E. Oztemel and S. Gursev, “Literature review of industry 4.0 and related technologies,” Journal of Intelligent Manufacturing, vol. 31, pp. 127–182, 1 2020. [Online]. Available: doi:10.1007/S10845-018-1433-8
• [2] B. Siciliano and O. Khatib, “Springer handbook of robotics,” Springer Handbook of Robotics, pp. 1-2227, 1 2016. [Online]. Available: doi:10.1007/978-3-319-32552-1
• [3] H. Y. Hsueh, A. I. Toma, H. A. Jaafar, E. Stow, R. Murai, P. H. Kelly, and S. Saeedi, “Systematic comparison of path planning algorithms using pathbench,” Advanced Robotics, vol. 36, pp. 566-581, 2022. [Online]. Available: doi:10.1080/01691864.2022.2062259
• [4] Y. Rasekhipour, “A potential field-based model predictive path-planning controller for autonomous road vehicles,” IEEE Transactions on Intelligent Transportation Systems, vol. 18, pp. 1255-1267, 2017. [Online]. Available: doi:10.1109/TITS.2016.2604240
• [5] Y. Zhao, Z. Zheng, and Y. Liu, “Survey on computational-intelligence-based uav path planning,” Knowledge-Based Systems, vol. 158, pp. 54-64, 10 2018. [Online]. Available: doi:10.1016/J.KNOSYS.2018.05.033
• [6] S. Grigorescu, B. Trasnea, T. Cocias, and G. Macesanu, “A survey of deep learning techniques for autonomous driving,” Journal of Field Robotics, vol. 37, pp. 362-386, 4 2020. [Online]. Available: doi:10.1002/ROB.21918
• [7] B. K. Patle, G. B. L, A. Pandey, D. R. Parhi, and A. Jagadeesh, “A review: On path planning strategies for navigation of mobile robot,” Defence Technology, vol. 15, pp. 582-606, 8 2019. [Online]. Available: doi:10.1016/J.DT.2019.04.011
• [8] M. Korkmaz and A. Durdu, “Comparison of optimal path planning algorithms,” 14th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering, TCSET 2018 - Proceedings, vol. 2018-April, pp. 255-258, 4 2018. [Online]. Available: doi:10.1109/TCSET.2018.8336197
• [9] A. Belfodil, A. Belfodil, A. Bendimerad, P. Lamarre, C. Robardet, M. Kaytoue, and M. Plantevit, “Fssd - a fast and efficient algorithm for subgroup set discovery,” Proceedings - 2019 IEEE International Conference on Data Science and Advanced Analytics, DSAA 2019, pp. 91-99, 10 2019. [Online]. Available: doi:10.1109/DSAA.2019.00023
• [10] P. G. Luan, “Real-time hybrid navigation system-based path planning and obstacle avoidance for mobile robots,” Applied Sciences, 2020. [Online]. Available: doi:10.3390/app10103355
• [11] M. B. Alatise, “A review on challenges of autonomous mobile robot and sensor fusion methods,” IEEE Access, vol. 8, pp. 39 830-39 846, 2020. [Online]. Available: doi:10.1109/ACCESS.2020.2975643
• [12] Q. Song, Q. Zhao, S. Wang, Q. Liu, and X. Chen, “Dynamic path planning for unmanned vehicles based on fuzzy logic and improved ant colony optimization,” IEEE Access, vol. 8, pp. 62 107-62 115, 2020. [Online]. Available: doi:10.1109/ACCESS.2020.2984695
• [13] F. Kiani, “Adapted-rrt: novel hybrid method to solve three-dimensional path planning problem using sampling and metaheuristic-based algorithms,” Neural Computing and Applications, vol. 33, pp. 15 569-15 599, 2021. [Online]. Available: doi:10.1007/s00521-021-06179-0
• [14] B. Cherkassky, “Shortest paths algorithms: Theory and experimental evaluation,” Mathematical Programming, vol. 73, pp. 129-174, 1994. [Online]. Available: doi:10.1007/BF02592101
• [15] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, pp. 100-107, 1968. [Online]. Available: doi:10.1109/TSSC.1968.300136
• [16] 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. 59 196-59 210, 2021. [Online]. Available: doi:10.1109/ACCESS.2021.3070054
• [17] N. S. Yerramilli, N. Johnson, O. S. Y. Reddy, and S. Prajwal, “Navigation systems using a*,” 2021 International Conference on Recent Trends on Electronics, Information, Communication and Technology (RTEICT), pp. 708-712, 2021. [Online]. Available: doi:10.1109/RTEICT52294.2021.9573801
• [18] Y. Li, R. Jin, X. Xu, Y. yuan Qian, H. Wang, S.-S. Xu, and Z. Wang, “A mobile robot path planning algorithm based on improved a* algorithm and dynamic window approach,” IEEE Access, vol. PP, pp. 1-1, 2022. [Online]. Available: doi:10.1109/ACCESS.2022.3179397
• [19] L. A. Zadeh, “Fuzzy sets,” Information and Control, vol. 8, no. 3, pp. 338-353, 1965, cited By :62358. [Online]. Available: doi:10.1016/S0019-9958(65)90241-X
• [20] J. C. Mohanta and A. Keshari, “A knowledge based fuzzy-probabilistic roadmap method for mobile robot navigation,” Applied Soft Computing Journal, vol. 79, pp. 391-409, 6 2019. [Online]. Available: doi:10.1016/J.ASOC.2019.03.055
• [21] C. Punriboon, C. So-In, P. Aimtongkham, and N. Leelathakul, “Fuzzy logic-based path planning for data gathering mobile sinks in wsns,” IEEE Access, vol. 9, pp. 96 002-96 020, 2021. [Online]. Available: doi:10.1109/ACCESS.2021.3094541
• [22] S. Aggarwal and N. Kumar, “Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges,” Computer Communications, vol. 149, pp. 270-299, 1 2020. [Online]. Available: doi:10.1016/J.COMCOM.2019.10.014
• [23] S. Wang, “Mobile robot path planning based on fuzzy logic algorithm in dynamic environment,” 2022 International Conference on Artificial Intelligence in Everything (AIE), pp. 106-110, 2022. [Online]. Available: doi:10.1109/AIE57029.2022.00027
• [24] I. Zubeiri, Y. E. Morabit, and F. Mrabti, “Genetic algorithm for vertical handover (gafvh) in a heterogeneous networks,” International Journal of Electrical and Computer Engineering, vol. 9, pp. 2534-2540, 8 2019. [Online]. Available: doi:10.11591/IJECE.V9I4.PP2534-2540
• [25] S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimedia Tools and Applications, vol. 80, pp. 8091-8126, 2 2021. [Online]. Available: doi:10.1007/S11042-020-10139-6
• [26] M. Nazarahari, E. Khanmirza, and S. Doostie, “Multi-objective multirobot path planning in continuous environment using an enhanced genetic algorithm,” Expert Systems with Applications, vol. 115, pp. 106-120, 1 2019. [Online]. Available: doi:10.1016/J.ESWA.2018.08.008
• [27] A. N. Alfiyatin, W. F. Mahmudy, and Y. P. Anggodo, “K-means clustering and genetic algorithm to solve vehicle routing problem with time windows problem,” Indonesian Journal of Electrical Engineering and Computer Science, vol. 11, pp. 462-468, 8 2018. [Online]. Available: doi:10.11591/IJEECS.V11.I2.PP462-468
• [28] U. Orozco-Rosas, O. Montiel, and R. Sepúlveda, “Mobile robot path planning using membrane evolutionary artificial potential field,” Applied Soft Computing, vol. 77, pp. 236-251, 4 2019. [Online]. Available: doi:10.1016/J.ASOC.2019.01.036
• [29] D. A. V. Veldhuizen and G. B. Lamont, “Multiobjective evolutionary algorithms: analyzing the state-of-the-art.” Evolutionary computation, vol. 8, pp. 125-147, 2000. [Online]. Available: doi:10.1162/106365600568158
• [30] 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,” Sensors, vol. 21, 12 2021. [Online]. Available: doi:10.3390/S21237898
• [31] S. Hacohen, S. Shoval, and N. Shvalb, “Probability navigation function for stochastic static environments,” International Journal of Control, Automation and Systems, vol. 17, pp. 2097-2113, 8 2019. [Online]. Available: doi:10.1007/S12555-018-0563-2
• [32] A. Faust, K. Oslund, O. Ramirez, A. Francis, L. Tapia, M. Fiser, and J. Davidson, “Prm-rl: Long-range robotic navigation tasks by combining reinforcement learning and sampling-based planning,” Proceedings - IEEE International Conference on Robotics and Automation, pp. 5113-5120, 9 2018. [Online]. Available: doi:10.1109/ICRA.2018.8461096
• [33] Z. Wang and J. Cai, “Probabilistic roadmap method for path-planning in radioactive environment of nuclear facilities,” Progress in Nuclear Energy, vol. 109, pp. 113-120, 11 2018. [Online]. Available: doi:10.1016/J.PNUCENE.2018.08.006
• [34] A. A. Ravankar, A. Ravankar, T. Emaru, and Y. Kobayashi, “Hpprm: Hybrid potential based probabilistic roadmap algorithm for improved dynamic path planning of mobile robots,” IEEE Access, vol. 8, pp. 221 743-221 766, 2020. [Online]. Available: doi:10.1109/ACCESS.2020.3043333
• [35] W. Khaksar, K. S. B. M. Sahari, F. B. Ismail, M. Yousefi, and M. A. Ali, “Runtime reduction in optimal multi-query sampling-based motion planning,” 2014 IEEE International Symposium on Robotics and Manufacturing Automation, IEEE-ROMA2014, pp. 52-56, 10 2015. [Online]. Available: doi:10.1109/ROMA.2014.7295861
• [36] L. Chen, Y. Shan, W. Tian, B. Li, and D. Cao, “A fast and efficient double-tree rrt star-like sampling-based planner applying on mobile robotic systems,” IEEE/ASME Transactions on Mechatronics, vol. 23, pp. 2568-2578, 12 2018. [Online]. Available: doi:10.1109/TMECH. 2018.2821767
• [37] J. Denny, R. Sandstr¨om, A. Bregger, and N. M. Amato, “Dynamic region-biased rapidly-exploring random trees,” Springer Proceedings in Advanced Robotics, vol. 13, pp. 640-655, 2020. [Online]. Available: doi:10.1007/978-3-030-43089-4_41
• [38] Z. Tahir, A. H. Qureshi, Y. Ayaz, and R. Nawaz, “Potentially guided bidirectionalized rrt* for fast optimal path planning in cluttered environments,” Robotics and Autonomous Systems, vol. 108, pp. 13-27, 10 2018. [Online]. Available: doi:10.1016/J.ROBOT.2018.06.013

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).