The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
A Survey of Path Planning Algorithms for Mobile Robots
Open accessAbstract
Path planning algorithms are used by mobile robots, unmanned aerial vehicles, and autonomous cars in order to identify safe, efficient, collision-free, and least-cost travel paths from an origin to a destination. Choosing an appropriate path planning algorithm helps to ensure safe and effective point-to-point navigation, and the optimal algorithm depends on the robot geometry as well as the computing constraints, including static/holonomic and dynamic/non-holonomically-constrained systems, and requires a comprehensive understanding of contemporary solutions. The goal of this paper is to help novice practitioners gain an awareness of the classes of path planning algorithms used today and to understand their potential use cases—particularly within automated or unmanned systems. To that end, we provide broad, rather than deep, coverage of key and foundational algorithms, with popular algorithms and variants considered in the context of different robotic systems. The definitions, summaries, and comparisons are relevant to novice robotics engineers and embedded system developers seeking a primer of available algorithms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 29,065
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
Ant system: optimization by a colony of cooperating agents
Dorigo, M., Maniezzo, V., & Colorni, A. (1996) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/3477.484436 · Cited by 12,067
LaValle, S. M. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546877 · Cited by 5,211
LaValle, S. M. (2006) · Cited by 4,177
Rapidly-exploring random trees : a new tool for path planning
LaValle, S. M. (1998) · Cited by 3,704
RRT-connect: An efficient approach to single-query path planning
Kuffner, J. J., & LaValle, S. M. (2000) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844730 · Cited by 3,555
Randomized Kinodynamic Planning
LaValle, S. M., & Kuffner, J. J. (2001) · The International Journal of Robotics Research · doi:10.1177/02783640122067453 · Cited by 3,254
Computational Geometry: Algorithms and Applications
de Berg, M., van Kreveld, M., Overmars, M., & Schwarzkopf, O. C. (2000) · Springer eBooks · doi:10.1007/978-3-662-04245-8 · Cited by 1,473
A comprehensive review of firefly algorithms
Fister, I., Fister, I., Yang, X.-S., & Brest, J. (2013) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2013.06.001 · Cited by 1,308
Optimal and Efficient Path Planning for Partially Known Environments
Stentz, A. (1997) · Intelligent Unmanned Ground Vehicles · doi:10.1007/978-1-4615-6325-9_11 · Cited by 1,233
Rules for Biologically Inspired Adaptive Network Design
Tero, A., Takagi, S., Saigusa, T., Ito, K., Bebber, D. P., Fricker, M. D., Yumiki, K., Kobayashi, R., & Nakagaki, T. (2010) · Science · doi:10.1126/science.1177894 · Cited by 778
Koenig, S., Likhachev, M. A., & Furcy, D. (2004) · Artificial Intelligence · doi:10.1016/j.artint.2003.12.001 · Cited by 662
Heuristic approaches in robot path planning: A survey
Mac, T. T., Copot, C., Tran, D. T., & De Keyser, R. (2016) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2016.08.001 · Cited by 641
Multi-robot exploration controlled by a market economy
Zlot, R., Stentz, A., Dias, M. B., & Thayer, S. (2003) · Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292) · doi:10.1109/robot.2002.1013690 · Cited by 489
A Guide to Heuristic-based Path Planning
Ferguson, D., Likhachev, M. A., & Stentz, A. (2005) · Cited by 299
A knowledge based genetic algorithm for path planning of a mobile robot
Hu, Y., & Yang, S. X. (2004) · IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004 · doi:10.1109/robot.2004.1302402 · Cited by 296
A*-based Pathfinding in Modern Computer Games
Cui, X., & Shi, H. (2011) · Victoria University Research Repository (Victoria University) · Cited by 251
Field D*: An Interpolation-Based Path Planner and Replanner
Ferguson, D., & Stentz, A. (2007) · Springer Tracts in Advanced Robotics · doi:10.1007/978-3-540-48113-3_22 · Cited by 250
Recent progress in local and global traversability for planetary rovers
Singh, S., Simmons, R., Smith, T., Stentz, A., Verma, V., Yahja, A., & Schwehr, K. (2002) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844761 · Cited by 248
A review of chaos-based firefly algorithms: Perspectives and research challenges
Fister, I., Perc, M., Kamal, S. M., & Fister, I. (2015) · Applied Mathematics and Computation · doi:10.1016/j.amc.2014.12.006 · Cited by 220
An Overview of Autonomous Mobile Robot Path Planning Algorithms
Sariff, N., & Buniyamin, N. (2006) · 2006 4th Student Conference on Research and Development · doi:10.1109/scored.2006.4339335 · Cited by 219
Guided Hybrid A-star Path Planning Algorithm for Valet Parking Applications
Sedighi, S., Nguyen, D.-V., & Kuhnert, K.-D. (2019) · International Conference on Control, Automation and Robotics (ICCAR) · doi:10.1109/iccar.2019.8813752 · Cited by 186
Path-planning of automated guided vehicle based on improved Dijkstra algorithm
Guo, Q., Zhang, Z., & Xu, Y. (2017) · Chinese Control and Decision Conference (CCDC) · doi:10.1109/ccdc.2017.7978471 · Cited by 170
Ammar, A., Bennaceur, H., Châari, I., Koubâa, A., & Alajlan, M. (2015) · Soft Computing · doi:10.1007/s00500-015-1750-1 · Cited by 166
A survey of dynamic programming computational procedures
Larson, R. E. (1967) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1967.1098755 · Cited by 103
The SRT method: randomized strategies for exploration
Oriolo, G., Vendittelli, M., Freda, L., & Troso, G. (2004) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2004.1302457 · Cited by 95
Active Balancing of Lithium-Ion Batteries Using Graph Theory and A-Star Search Algorithm
Dong, G., Yang, F., Tsui, K., & Zou, C. (2020) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2020.2997828 · Cited by 86
Autonomous agents for real-time animation
Latombe, J., & Kuffner, J. (1999) · Cited by 70
Implementation of Path Planning using Genetic Algorithms on Mobile Robots
Burchardt, H., & Salomon, R. (2006) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2006.1688529 · Cited by 61
Global Path Planning for Autonomous Mobile Robot Using Genetic Algorithm
Samadi, M., & Othman, M. F. (2013) · International Conference on Signal-Image Technology & Internet-Based Systems (SITIS) · doi:10.1109/sitis.2013.118 · Cited by 60
The D* Algorithm for Real-Time Planning of Optimal Traverses
Stentz, A. (1994) · Cited by 59
On the heuristics of A* or A algorithm in ITS and robot path-planning
Goto, T., Kosaka, T., & Noborio, H. (2004) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2003.1248802 · Cited by 47
High-dimensional planning on the GPU
Kider, J. T., Henderson, M., Likhachev, M. A., & Safonova, A. (2010) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2010.5509470 · Cited by 43
Ant colony system for robot path planning in global static environment
Sariff, N. B., & Buniyamin, N. (2010) · International Conference on System Science and Simulation in Engineering · Cited by 26
NP-Hard Problems of Learning from Examples
Chen, B., & Quan, G. (2008) · International Conference on Fuzzy Systems and Knowledge Discovery (FSKD) · doi:10.1109/fskd.2008.406 · Cited by 25
Local Path Planning of Autonomous Vehicles Based on A* Algorithm with Equal-Step Sampling
Wang, Y., Liu, Z., Zhiqiang, Z., & Zheng, L. (2018) · Chinese Control Conference (CCC) · doi:10.23919/chicc.2018.8482915 · Cited by 19
Majeed, A., & Hwang, S. O. (2021) · Applied Sciences · doi:10.3390/app11125340 · Cited by 17
A SRT-based path planning algorithm in unknown complex environment
Yiping, Z., Guo, J. C., Ruilei, Z., & Qingwei, C. (2014) · Chinese Control and Decision Conference (CCDC) · doi:10.1109/ccdc.2014.6852853 · Cited by 10
A Multi-agent System for Dynamic Path Planning
Silva, M. C., García, A. C. B., & Conci, A. (2010) · Brazilian Workshop on Social Simulation (BWSS) · doi:10.1109/bwss.2010.20 · Cited by 5
Metadata
- Authors
- Karur, K., Sharma, N., Dharmatti, C., & Siegel, J. E.
- Venue
- Vehicles
- Publisher
- MDPI AG
- Published
- 2021-08-04
- Volume
- 3
- Issue
- 3
- Pages
- 448-468
- ISSN
- 2624-8921 (ISSN-L)
- OpenAlex
- W3187511524
- Cited by
- 401
- References
- 40
- FWCI
- 21.08
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.