A Comprehensive Overview of Classical and Modern Route Planning Algorithms for Self-Driving Mobile Robots
Abstract
Mobile robots are increasingly being applied in a variety of sectors, including agricultural, firefighting, and search and rescue operations. Robotics and autonomous technology research and development have played a major role in making this possible. Before a robot can reliably and effectively navigate a space without human aid, there are still several challenges to be addressed. When planning a path to its destination, the robot should be able to gather information from its surroundings and take the appropriate actions to avoid colliding with obstacles along the way. The following review analyses and compares 200 articles from two databases, Scopus and IEEE Xplore, and selects 60 articles as references from those articles. This evaluation focuses mostly on the accuracy of the different path-planning algorithms. Common collision-free path planning methodologies are examined in this paper, including classical or traditional and modern intelligence techniques, as well as both global and local approaches, in static and dynamic environments. Classical or traditional methods, such as Roadmaps (Visibility Graph and Voronoi Diagram), Potential Fields, and Cell Decomposition, and modern methodologies such as heuristic-based (Dijkstra Method, A* Algorithms, and D* Algorithms), metaheuristics algorithms (such as PSO, Bat Algorithm, ACO, and Genetic Algorithm), and neural systems such as fuzzy neural networks or fuzzy logic (FL) and Artificial Neural Networks (ANN) are described in this report. In this study, we outline the ideas, benefits, and downsides of modeling and path-searching technologies for a mobile robot.
Keywords
Full Text:
PDFReferences
C. S. Tan, R. Mohd-Mokhtar, and M. R. Arshad, "A Comprehensive Review of Coverage Path Planning in Robotics Using Classical and Heuristic Algorithms," in IEEE Access, vol. 9, pp. 119310-119342, 2021, doi: 10.1109/ACCESS.2021.3108177.
S. Campbell, N. O’Mahony, A. Carvalho, L. Krpalkova, D. Riordan, and J. Walsh, “Path Planning Techniques for Mobile Robots A Review,” 2020 6th Int. Conf. Mechatronics Robot. Eng. ICMRE 2020, pp. 12–16, 2020, doi: 10.1109/ICMRE49073.2020.9065187.
J. Maldonado-romo and M. Aldape-pérez, “Path Planning Generator with Metadata through a Domain Change by GAN between Physical and Virtual Environments,” Sensors (Basel, Switzerland) vol. 21,22 7667. 18 Nov. 2021, doi:10.3390/s21227667
T. Shen and J. Zhai, “Reactive Obstacle Avoidance Strategy Based on Fuzzy Neural Network and Arc Trajectory,” Proc. - 2019 Chinese Autom. Congr. CAC 2019, pp. 4792–4796, 2019, doi: 10.1109/CAC48633.2019.8996374.
E. A. Oyekanlu et. Al., “A review of recent advances in automated guided vehicle technologies: Integration challenges and research areas for 5G-based smart manufacturing applications,” IEEE Access, vol. 8, pp. 202312–202353, 2020.
U. Agwogie, “Mobile Robot Path Planning in an Obstacle-free Static Environment using Multiple Optimization Algorithms,” Niger. J. Technol. Dev., vol. 17, pp. 165 – 173, 2020.
T.-W. Kang, J.-G. Kang, and J.-W. Jung, “A Bidirectional Interpolation Method for Post-Processing in Sampling-Based Robot Path Planning,” Sensors, vol. 21, no. 21, p. 7425, Nov. 2021, doi: 10.3390/s21217425
H. Ren, S. Chen, L. Yang, and Y. Zhao, “Optimal Path Planning and Speed Control Integration Strategy for UGVs in Static and Dynamic Environments,” IEEE Transactions on Vehicular Technology, vol. 69, no. 10, pp. 10619–10629, 2020.
R. Pina, H. Tibebu, J. Hook, D. De Silva, and A. Kondoz, “Overcoming Challenges of Applying Reinforcement Learning for Intelligent Vehicle Control,” Sensors, vol. 21, no. 23, p. 7829, 2021, doi: 10.3390/s21237829.
C. Wang and J. Mao, "Summary of AGV Path Planning," 2019 3rd International Conference on Electronic Information Technology and Computer Engineering (EITCE), 2019, pp. 332-335, doi: 10.1109/EITCE47263.2019.9094825.
H. Shin and J. Chae, “A Performance Review of Collision-Free Path Planning Algorithms,” Electronics, vol. 9, no. 2, p. 316, Feb. 2020, doi: 10.3390/electronics9020316.
F. H. Ajeil, I. K. Ibraheem, A. T. Azar, and A. J. Humaidi, “Grid-Based Mobile Robot Path Planning Using Aging-Based Ant Colony Optimization Algorithm in Static and Dynamic Environments,” Sensors, vol. 20, no. 7, p. 1880, Mar. 2020, doi: 10.3390/s20071880
D. Li, P. Wang, and L. Du, “Path planning technologies for autonomous underwater vehicles-a review,” IEEE Access, vol. 7, pp. 9745–9768, 2019, doi: 10.1109/ACCESS.2018.2888617.
H. Wang and Z. Zhou, “A heuristic elastic particle swarm optimization algorithm for robot path planning,” Inf., vol. 10, no. 3, pp. 1–18, 2019, doi: 10.3390/info10030099.
J. Huerta-Chua et al., “Exploring a Novel Multiple-Query Resistive Grid-Based Planning Method Applied to High-DOF Robotic Manipulators,” Sensors, vol. 21, no. 9, p. 3274, May 2021, doi: 10.3390/s21093274.
G. Karalekas, S. Vologiannidis, and J. Kalomiros, ‘‘EUROPA: A case study for teaching sensors, data acquisition and robotics via a ROS-based educational robot,’’ Sensors, vol. 20, no. 9, p. 2469, Apr. 2020.
X. Liu, Q. Gu, and C. Yang, “Path planning of multi-cruise missile based on particle swarm optimization,” Proc. - 2019 Int. Conf. Sensing, Diagnostics, Progn. Control. SDPC 2019, pp. 910–912, 2019, doi: 10.1109/SDPC.2019.00173.
C. Zhang, L. Zhou, Y. Li, and Y. Fan, “A dynamic path planning method for social robots in the home environment,” Electron., vol. 9, no. 7, pp. 1–18, 2020, doi: 10.3390/electronics9071173.
A. A. Nasr, N. A. El-Bahnasawy, and A. El-Sayed, “Straight-line: A new global path planning algorithm for Mobile Robot,” ICEEM 2021 - 2nd IEEE Int. Conf. Electron. Eng., no. July, pp. 3–4, 2021, doi: 10.1109/ICEEM52022.2021.9480376.
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," in IEEE Access, vol. 9, pp. 59196-59210, 2021, doi: 10.1109/ACCESS.2021.3070054.
J. W. Jung, B. C. So, J. G. Kang, D. W. Lim, and Y. Son, “Expanded Douglas-Peucker polygonal approximation and opposite angle-based exact cell decomposition for path planning with curvilinear obstacles,” Appl. Sci., vol. 9, no. 4, 2019, doi: 10.3390/app9040638.
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," in IEEE Access, vol. 8, pp. 221743-221766, 2020, doi: 10.1109/ACCESS.2020.3043333.
G. Y. Jeon and J. W. Jung, “Water Sink Model for Robot Motion Planning,” Sensors, vol. 19, no. 6, 2019, doi: 10.3390/s19061269.
R. Szczepanski, A. Bereit, and T. Tarczewski, “Efficient Local Path Planning Algorithm Using Artificial Potential Field Supported by Augmented Reality,” Energies, vol. 14, no. 20, p. 6642, 2021, doi: 10.3390/en14206642.
J. Feng, J. Zhang, G. Zhang, S. Xie, Y. Ding and Z. Liu, "UAV Dynamic Path Planning Based on Obstacle Position Prediction in an Unknown Environment," in IEEE Access, vol. 9, pp. 154679-154691, 2021, doi: 10.1109/ACCESS.2021.3128295.
L. Yujie, P. Yu, S. Yixin, Z. Huajun, Z. Danhong, and S. Yong, “Ship Path Planning Based on Improved Particle Swarm Optimization,” Proc. 2018 Chinese Autom. Congr. CAC 2018, no. 2017, pp. 226–230, 2019, doi: 10.1109/CAC.2018.8623037.
B. Ge, S. Hu, and P. Zheng, “Research on full traversal path planning based on improved reciprocating algorithm,” vol. 2020, pp. 922–926, 2020, doi: 10.1109/ITAIC49862.2020.9338939.
J. Zhao, X. Zhu and T. Song, "Serial Manipulator Time-Jerk Optimal Trajectory Planning Based on Hybrid IWOA-PSO Algorithm," in IEEE Access, vol. 10, pp. 6592-6604, 2022, doi: 10.1109/ACCESS.2022.3141448.
T. F. Abaas and A. H. Shabeeb, “Autonomous mobile robot navigation based on PSO algorithm with inertia weight variants for optimal path planning,” IOP Conf. Ser. Mater. Sci. Eng., vol. 928, no. 2, 2020, doi: 10.1088/1757-899X/928/2/022005.
H. Ali, D. Gong, M. Wang, and X. Dai, “Path Planning of Mobile Robot with Improved Ant Colony Algorithm and MDP to Produce Smooth Trajectory in Grid-Based Environment,” Frontiers in neurorobotics, vol. 14, p. 44, Jul. 2020, doi: 10.3389/fnbot.2020.00044
S. Hameed, Q. -A. Minhas, S. Ahmed, Z. Najam, A. Nawaz and D. Khan, "BAT-COOP: Cooperative Diversity in FANETs using BAT Algorithm with two relay mechanism," 2020 IEEE 23rd International Multitopic Conference (INMIC), 2020, pp. 1-6, doi: 10.1109/INMIC50486.2020.9318208.
X. Zhou, F. Gao, X. Fang and Z. Lan, "Improved Bat Algorithm for UAV Path Planning in Three-Dimensional Space," in IEEE Access, vol. 9, pp. 20100-20116, 2021, doi: 10.1109/ACCESS.2021.3054179.
L. X. Wei, S. K. Wu, H. Sun, and J. Zheng, “Mobile robot path planning based on multi-behaviours,” Kongzhi yu Juece/Control Decis., vol. 34, no. 12, pp. 2721–2726, 2019, doi: 10.13195/j.kzyjc.2018.0278.
M. Wang, J. Chen, Z. Deng and Y. Xiang, "Velocity Planning Method Base on Fuzzy Neural Network for Autonomous Vehicle," in IEEE Access, vol. 9, pp. 19111-19126, 2021, doi: 10.1109/ACCESS.2021.3054124.
M. A. K. Niloy et al., “Critical Design and Control Issues of Indoor Autonomous Mobile Robots: A Review,” IEEE Access, vol. 9, pp. 35338–35370, 2021, doi: 10.1109/ACCESS.2021.3062557.
O. A. A. Salama, M. E. H. Eltaib, H. A. Mohamed and O. Salah, "RCD: Radial Cell Decomposition Algorithm for Mobile Robot Path Planning," in IEEE Access, vol. 9, pp. 149982-149992, 2021, doi: 10.1109/ACCESS.2021.3125105.
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,” Def. Technol., vol. 15, no. 4, pp. 582–606, 2019, doi: 10.1016/j.dt.2019.04.011.
W. Chi, Z. Ding, J. Wang, G. Chen and L. Sun, "A Generalized Voronoi Diagram-Based Efficient Heuristic Path Planning Method for RRTs in Mobile Robots," in IEEE Transactions on Industrial Electronics, vol. 69, no. 5, pp. 4926-4937, May 2022, doi: 10.1109/TIE.2021.3078390.
J. Qi, H. Yang and H. Sun, "MOD-RRT*: A Sampling-Based Algorithm for Robot Path Planning in Dynamic Environment," in IEEE Transactions on Industrial Electronics, vol. 68, no. 8, pp. 7244-7251, Aug. 2021, doi: 10.1109/TIE.2020.2998740.
R. Szczepanski, T. Tarczewski and K. Erwinski, "Energy Efficient Local Path Planning Algorithm Based on Predictive Artificial Potential Field," in IEEE Access, vol. 10, pp. 39729-39742, 2022, doi: 10.1109/ACCESS.2022.3166632.
Q. Yao et al., "Path Planning Method With Improved Artificial Potential Field—A Reinforcement Learning Perspective," in IEEE Access, vol. 8, pp. 135513-135523, 2020, doi: 10.1109/ACCESS.2020.3011211.
J. Batista et al., "Trajectory Planning Using Artificial Potential Fields with Metaheuristics," in IEEE Latin America Transactions, vol. 18, no. 5, pp. 914-922, May 2020, doi: 10.1109/TLA.2020.9082920.
W. Sheng, B. Li and X. Zhong, "Autonomous Parking Trajectory Planning With Tiny Passages: A Combination of Multistage Hybrid A-Star Algorithm and Numerical Optimal Control," in IEEE Access, vol. 9, pp. 102801-102810, 2021, doi: 10.1109/ACCESS.2021.3098676.
R. J. Wai and A. S. Prasetia, “Adaptive Neural Network Control and Optimal Path Planning of UAV Surveillance System with Energy Consumption Prediction,” IEEE Access, vol. 7, pp. 126137–126153, 2019, doi: 10.1109/ACCESS.2019.2938273.
M. Alireza, D. Vincent and W. Tony, "Experimental study of path planning problem using EMCOA for a holonomic mobile robot," in Journal of Systems Engineering and Electronics, vol. 32, no. 6, pp. 1450-1462, Dec. 2021, doi: 10.23919/JSEE.2021.000123.
M. Gulzar, Y. Muhammad, and N. Muhammad, “A Survey on Motion Prediction of Pedestrians and Vehicles for Autonomous Driving,” IEEE Access, vol. 9, pp. 137957–137969, 2021, doi: 10.1109/ACCESS.2021.3118224.
R. Vieira, E. Argento and T. Revoredo, "Trajectory Planning For Car-like Robots Through Curve Parametrization And Genetic Algorithm Optimization With Applications To Autonomous Parking," in IEEE Latin America Transactions, vol. 20, no. 2, pp. 309-316, Feb. 2022, doi: 10.1109/TLA.2022.9661471.
L. Li, Q. Gu, and L. Liu, “Research on path planning algorithm for multi-uav maritime targets search based on genetic Algorithm,” Proc. 2020 IEEE Int. Conf. Inf. Technol. Big Data Artif. Intell. ICIBA 2020, no. Iciba, pp. 840–843, 2020, doi: 10.1109/ICIBA50161.2020.9277470.
M. Asim, W. K. Mashwani, S. B. Belhaouari and S. Hassan, "A Novel Genetic Trajectory Planning Algorithm With Variable Population Size for Multi-UAV-Assisted Mobile Edge Computing System," in IEEE Access, vol. 9, pp. 125569-125579, 2021, doi: 10.1109/ACCESS.2021.3111318.
S. Shao, W. Shi, Y. Zhao and Y. Du, "A New Method of Solving UAV Trajectory Planning Under Obstacles and Multi-Constraint," in IEEE Access, vol. 9, pp. 161161-161180, 2021, doi: 10.1109/ACCESS.2021.3132650.
E. M. Hassib, A. I. El-Desouky, E. S. M. El-Kenawy, and S. M. El-Ghamrawy, “An imbalanced big data mining framework for improving optimization algorithms performance,” IEEE Access, vol. 7, pp. 170774–170795, 2019, doi: 10.1109/ACCESS.2019.2955983.
X. Zhou, F. Gao, X. Fang, and Z. Lan, “Improved Bat Algorithm for UAV Path Planning in Three-Dimensional Space,” IEEE Access, vol. 9, pp. 20100–20116, 2021, doi: 10.1109/ACCESS.2021.3054179.
Z. Zhang, J. Wu, J. Dai and C. He, "A Novel Real-Time Penetration Path Planning Algorithm for Stealth UAV in 3D Complex Dynamic Environment," in IEEE Access, vol. 8, pp. 122757-122771, 2020, doi: 10.1109/ACCESS.2020.3007496.
N. Faruk et al., “Path Loss Predictions in the VHF and UHF Bands within Urban Environments: Experimental Investigation of Empirical, Heuristics and Geospatial Models,” IEEE Access, vol. 7, pp. 77293–77307, 2019, doi: 10.1109/ACCESS.2019.2921411
Q. Liu, Y. Zhang, M. Li, Z. Zhang, N. Cao and J. Shang, "Multi-UAV Path Planning Based on Fusion of Sparrow Search Algorithm and Improved Bioinspired Neural Network," in IEEE Access, vol. 9, pp. 124670-124681, 2021, doi: 10.1109/ACCESS.2021.3109879.
Y. Xu and C. Che, “A brief review of the intelligent algorithm for traveling salesman problem in UAV route planning,” ICEIEC 2019 - Proc. 2019 IEEE 9th Int. Conf. Electron. Inf. Emerg. Commun., pp. 705–711, 2019, doi: 10.1109/ICEIEC.2019.8784651.
D. Liu and X. Chen, "An ANN-Based Data Fusion Algorithm for INS/CNS Integrated Navigation System," in IEEE Sensors Journal, vol. 22, no. 8, pp. 7846-7854, April, 2022, doi: 10.1109/JSEN.2022.3159662.
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," in IEEE Access, vol. 8, pp. 62107-62115, 2020, doi: 10.1109/ACCESS.2020.2984695.
J. Guo, C. Li and S. Guo, "A Novel Step Optimal Path Planning Algorithm for the Spherical Mobile Robot Based on Fuzzy Control," in IEEE Access, vol. 8, pp. 1394-1405, 2020, doi: 10.1109/ACCESS.2019.2962074.
Y. -C. Chang et al., "Interpretable Fuzzy Logic Control for Multirobot Coordination in a Cluttered Environment," in IEEE Transactions on Fuzzy Systems, vol. 29, no. 12, pp. 3676-3685, Dec. 2021, doi: 10.1109/TFUZZ.2021.3111446.
DOI: https://doi.org/10.18196/jrc.v3i5.14683
Refbacks
- There are currently no refbacks.
Copyright (c) 2022 NUR SYUHADAH BINTI ABU
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Journal of Robotics and Control (JRC)
P-ISSN: 2715-5056 || E-ISSN: 2715-5072
Organized by Peneliti Teknologi Teknik Indonesia
Published by Universitas Muhammadiyah Yogyakarta in collaboration with Peneliti Teknologi Teknik Indonesia, Indonesia and the Department of Electrical Engineering
Website: http://journal.umy.ac.id/index.php/jrc
Email: jrcofumy@gmail.com