Evaluation of Popular Path Planning Algorithms

Mehmet Kara

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.


Full Text:

PDF

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


Refbacks

  • There are currently no refbacks.


International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933