Evaluation of Popular Path Planning Algorithms
Abstract
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.
References
E. Oztemel and S. Gursev, “Literature review of industry 4.0 and related
technologies,” Journal of Intelligent Manufacturing, vol. 31, pp. 127–
, 1 2020.
B. Siciliano and O. Khatib, “Springer handbook of robotics,” Springer
Handbook of Robotics, pp. 1–2227, 1 2016.
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.
Y. Rasekhipour, “A potential field-based model predictive path-planning
controller for autonomous road vehicles,” IEEE Transactions on Intelli-
gent Transportation Systems, vol. 18, pp. 1255–1267, 2017.
Y. Zhao, Z. Zheng, and Y. Liu, “Survey on computational-intelligence-
based uav path planning,” Knowledge-Based Systems, vol. 158, pp. 54–
, 10 2018.
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.
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.
M. Korkmaz and A. Durdu, “Comparison of optimal path planning
algorithms,” 14th International Conference on Advanced Trends in Ra-
dioelectronics, Telecommunications and Computer Engineering, TCSET
- Proceedings, vol. 2018-April, pp. 255–258, 4 2018.
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.
–99, 10 2019.
P. G. Luan, “Real-time hybrid navigation system-based path planning
and obstacle avoidance for mobile robots,” Applied Sciences, 2020.
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.
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.
F. Kiani, “Adapted-rrt: novel hybrid method to solve three-dimensional
path planning problem using sampling and metaheuristic-based algo-
rithms,” Neural Computing and Applications, vol. 33, pp. 15 569 –
599, 2021.
B. Cherkassky, “Shortest paths algorithms: Theory and experimental
evaluation,” Mathematical Programming, vol. 73, pp. 129–174, 1994.
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.
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.
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.
–712, 2021.
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.
L. A. Zadeh, “Fuzzy sets,” Information and Control, vol. 8, no. 3, pp.
–353, 1965, cited By :62358.
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.
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.
S. Aggarwal and N. Kumar, “Path planning techniques for unmanned
aerial vehicles: A review, solutions, and challenges,” Computer Commu-
nications, vol. 149, pp. 270–299, 1 2020.
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.
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.
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.
M. Nazarahari, E. Khanmirza, and S. Doostie, “Multi-objective multi-
robot path planning in continuous environment using an enhanced
genetic algorithm,” Expert Systems with Applications, vol. 115, pp. 106–
, 1 2019.
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.
U. Orozco-Rosas, O. Montiel, and R. Sep ́ulveda, “Mobile robot path
planning using membrane evolutionary artificial potential field,” Applied
Soft Computing, vol. 77, pp. 236–251, 4 2019.
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.
J. R. S ́anchez-Ib ́a ̃nez, C. J. P ́erez-Del-pulgar, and A. Garc ́ıa-Cerezo,
“Path planning for autonomous mobile robots: A review,” Sensors,
vol. 21, 12 2021.
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.
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–
, 9 2018.
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.
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.
743–221 766, 2020.
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 Man-
ufacturing Automation, IEEE-ROMA2014, pp. 52–56, 10 2015.
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.
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.
Z. Tahir, A. H. Qureshi, Y. Ayaz, and R. Nawaz, “Potentially guided
bidirectionalized rrt* for fast optimal path planning in cluttered envi-
ronments,” Robotics and Autonomous Systems, vol. 108, pp. 13–27, 10
Downloads
Published
Issue
Section
License
Copyright (c) 2024 International Journal of Electronics and Telecommunications
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
1. License
The non-commercial use of the article will be governed by the Creative Commons Attribution license as currently displayed on https://creativecommons.org/licenses/by/4.0/.
2. Author’s Warranties
The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. The undersigned also warrants that the manuscript (or its essential substance) has not been published other than as an abstract or doctorate thesis and has not been submitted for consideration elsewhere, for print, electronic or digital publication.
3. User Rights
Under the Creative Commons Attribution license, the author(s) and users are free to share (copy, distribute and transmit the contribution) under the following conditions: 1. they must attribute the contribution in the manner specified by the author or licensor, 2. they may alter, transform, or build upon this work, 3. they may use this contribution for commercial purposes.
4. Rights of Authors
Authors retain the following rights:
- copyright, and other proprietary rights relating to the article, such as patent rights,
- the right to use the substance of the article in own future works, including lectures and books,
- the right to reproduce the article for own purposes, provided the copies are not offered for sale,
- the right to self-archive the article
- the right to supervision over the integrity of the content of the work and its fair use.
5. Co-Authorship
If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.
6. Termination
This agreement can be terminated by the author or the Journal Owner upon two months’ notice where the other party has materially breached this agreement and failed to remedy such breach within a month of being given the terminating party’s notice requesting such breach to be remedied. No breach or violation of this agreement will cause this agreement or any license granted in it to terminate automatically or affect the definition of the Journal Owner. The author and the Journal Owner may agree to terminate this agreement at any time. This agreement or any license granted in it cannot be terminated otherwise than in accordance with this section 6. This License shall remain in effect throughout the term of copyright in the Work and may not be revoked without the express written consent of both parties.
7. Royalties
This agreement entitles the author to no royalties or other fees. To such extent as legally permissible, the author waives his or her right to collect royalties relative to the article in respect of any use of the article by the Journal Owner or its sublicensee.
8. Miscellaneous
The Journal Owner will publish the article (or have it published) in the Journal if the article’s editorial process is successfully completed and the Journal Owner or its sublicensee has become obligated to have the article published. Where such obligation depends on the payment of a fee, it shall not be deemed to exist until such time as that fee is paid. The Journal Owner may conform the article to a style of punctuation, spelling, capitalization and usage that it deems appropriate. The Journal Owner will be allowed to sublicense the rights that are licensed to it under this agreement. This agreement will be governed by the laws of Poland.
By signing this License, Author(s) warrant(s) that they have the full power to enter into this agreement. This License shall remain in effect throughout the term of copyright in the Work and may not be revoked without the express written consent of both parties.
