Download pdf
The evolution and current frontiers of path planning algorithms for mobile robots: A comprehensive review
- 1 The University of Sheffield
* Author to whom correspondence should be addressed.
Abstract
The success of robotics heavily relies on path planning, which is a crucial link between computational processes and actual robot actions. This review deeply explores the evolution of path-planning algorithms tracing their development from strategies to advanced and adaptable methodologies powered by artificial intelligence. Moreover, this paper examines techniques like grid-based methods and potential fields, discussing their strengths and inherent limitations. Moving forward, this review delves into the game-changing potential of methods highlighting advancements such as Probabilistic Roadmaps (PRM) and Rapidly-exploring Random Trees (RRT). Furthermore, this paper dissects the impact of intelligence on path planning emphasizing the synergy between machine learning—particularly deep reinforcement learning—and robotic navigation. This review also sheds light on the challenges faced by these algorithms, including real-world implementation hurdles and potential risks associated with reliance on AI-centric approaches. Lastly, this study offers insights into trends. Speculate how emerging technologies like quantum computing may shape next-generation path planning. With its overview, this review aims to be a resource for researchers, academics, and practitioners interested, in exploring the vast realm of robotic path planning.
Keywords
Mobile Robotics, Path Planning, Artificial Intelligence, Traditional Algorithms, Quantum Computing
[1]. LaValle S M 2006 Planning Algorithms: Cambridge University Press, 2006.
[2]. Choset H, Lynch K, Hutchinson S, Kantor G, Burgard W, Kavraki L and Thrun S 2007 Principles of Robot Motion: Theory, Algorithms, and Implementation ERRATA!!!!.
[3]. Latombe J C 2012 Robot motion planning (Vol. 124). Springer Science & Business Media.
[4]. Brooks R 1986 A robust layered control system for a mobile robot. IEEE journal on robotics and automation, 2(1), 14-23.
[5]. Granda C P N 2021 Robust Distributed Multi-Robot Information Based Exploration and Sampling. University of California, San Diego.
[6]. Alagić E, Velagić J and Osmanović A 2019 Design of Mobile Robot Motion Framework based on Modified Vector Field Histogram. In 2019 International Symposium ELMAR (pp. 135-138). IEEE.
[7]. Lin H C, Liu C, Fan Y and Tomizuka M 2017 Real-time collision avoidance algorithm on industrial manipulators. In 2017 IEEE Conference on Control Technology and Applications (CCTA) (pp. 1294-99). IEEE.
[8]. Montiel O, Sepúlveda R and Orozco-Rosas U 2015 Optimal path planning generation for mobile robots using parallel evolutionary artificial potential field. Journal of Intelligent & Robotic Systems, 79, 237-257.
[9]. Elfes A 2013 Occupancy grids: A stochastic spatial representation for active robot perception. arXiv preprint arXiv:1304.1098.
[10]. Zhong X, Tian J, Hu H and Peng X 2020 Hybrid path planning based on safe A* algorithm and adaptive window approach for mobile robot in large-scale dynamic environment. Journal of Intelligent & Robotic Systems, 99, 65-77.
[11]. Liang J H and Lee C H 2015 Efficient collision-free path-planning of multiple mobile robots system using efficient artificial bee colony algorithm. Advances in Engineering Software, 79, 47-56.
[12]. Ayawli B B K, Appiah A Y, Nti I K, Kyeremeh F and Ayawli E I 2021 Path planning for mobile robots using Morphological Dilation Voronoi Diagram Roadmap algorithm. Scientific African, 12, e00745.
[13]. Rostami S M H, Sangaiah A K, Wang J and Liu X 2019 Obstacle avoidance of mobile robots using modified artificial potential field algorithm. EURASIP Journal on Wireless Communications and Networking, 2019(1), 1-19.
[14]. Thrun S 2002 Probabilistic robotics. Communications of the ACM, 45(3), 52-57.
[15]. Wang Z and Cai J 2018 Probabilistic roadmap method for path-planning in radioactive environment of nuclear facilities. Progress in Nuclear Energy, 109, 113-120.
[16]. Rybus T and Seweryn K 2015 Application of rapidly-exploring random trees (RRT) algorithm for trajectory planning of free-floating space manipulator. In 2015 10th International Workshop on Robot Motion and Control (RoMoCo) (pp. 91-96). IEEE.
[17]. Peng J H, Li I H, Chien Y H, Hsu C C and Wang W Y 2015 Multi-robot path planning based on improved D* lite algorithm. In 2015 IEEE 12th International Conference on Networking, Sensing and Control (pp. 350-353). IEEE.
[18]. Aradi S 2020 Survey of deep reinforcement learning for motion planning of autonomous vehicles. IEEE Transactions on Intelligent Transportation Systems, 23(2), 740-759.
[19]. Tai L and Liu M 2016 Deep-learning in mobile robotics-from perception to control systems: A survey on why and why not. arXiv preprint arXiv:1612.07139, 1.
[20]. Buhet T, Wirbel E, Bursuc A and Perrotton X 2020 Plop: Probabilistic polynomial objects trajectory planning for autonomous driving. arXiv preprint arXiv:2003.08744.
[21]. Qu C, Gai W, Zhong M and Zhang J 2020 A novel reinforcement learning based grey wolf optimizer algorithm for unmanned aerial vehicles (UAVs) path planning. Applied soft computing, 89, 106099.
[22]. Liu G, Deng W, Xie X, Huang L and Tang H 2022 Human-Level Control Through Directly Trained Deep Spiking $ Q $-Networks. IEEE Transactions on Cybernetics.
[23]. Schulman J, Wolski F, Dhariwal P, Radford A and Klimov O 2017 Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347.
[24]. Kalyanmoy D 2002 A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation, 6(2), 182-197.
[25]. Deb K and Jain H 2013 An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE transactions on evolutionary computation, 18(4), 577-601.
[26]. van Den Berg J, Snoeyink J, Lin M C and Manocha D 2009 Centralized path planning for multiple robots: Optimal decoupling into sequential plans. In Robotics: Science and systems (Vol. 2, No. 2.5, pp. 2-3).
[27]. Henkel C, Bubeck A and Xu W 2016 Energy efficient dynamic window approach for local path planning in mobile service robotics. IFAC-papersonline, 49(15), 32-37.
[28]. Zhang L, Lin Z, Wang J and He B 2020 Rapidly-exploring Random Trees multi-robot map exploration under optimization framework. Robotics and Autonomous Systems, 131, 103565.
[29]. Chen Y F, Everett M, Liu M and How J P 2017 Socially aware motion planning with deep reinforcement learning. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 1343-1350). IEEE.
[30]. Doshi-Velez F and Kim B 2017 Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv:1702.0860
Cite this article
Yang,W. (2024). The evolution and current frontiers of path planning algorithms for mobile robots: A comprehensive review. Applied and Computational Engineering,50,80-88.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of the 4th International Conference on Signal Processing and Machine Learning
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).