The DOI matches its Crossref record; 66 of the 66 references it cites were found in a registry or an index.
Survey of Robot 3D Path Planning Algorithms
Open accessAbstract
Robot 3D (three-dimension) path planning targets for finding an optimal and collision-free path in a 3D workspace while taking into account kinematic constraints (including geometric, physical, and temporal constraints). The purpose of path planning, unlike motion planning which must be taken into consideration of dynamics, is to find a kinematically optimal path with the least time as well as model the environment completely. We discuss the fundamentals of these most successful robot 3D path planning algorithms which have been developed in recent years and concentrate on universally applicable algorithms which can be implemented in aerial robots, ground robots, and underwater robots. This paper classifies all the methods into five categories based on their exploring mechanisms and proposes a category, called multifusion based algorithms. For all these algorithms, they are analyzed from a time efficiency and implementable area perspective. Furthermore a comprehensive applicable analysis for each kind of method is presented after considering their merits and weaknesses.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Holland, J. H. (1992) · The MIT Press eBooks · doi:10.7551/mitpress/1090.001.0001 · Cited by 47,002
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 24,043
Particle swarm optimization: An overview
Poli, R., Kennedy, J., & Blackwell, T. (2007) · Swarm Intelligence · doi:10.1007/s11721-007-0002-0 · Cited by 21,101
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
Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Sturm, J. F. (1999) · Optimization Methods and Software · doi:10.1080/10556789908805766 · Cited by 7,377
Latombe, J.-C. (1991) · Springer eBooks · doi:10.1007/978-1-4615-4022-9 · Cited by 6,396
Probabilistic roadmaps for path planning in high-dimensional configuration spaces
Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.508439 · Cited by 6,343 · cited 2×
“…graph [18] which works by connecting visible vertexes of polyhedron, random-exploring algorithms such as rapidly exploring random tree [19], Probabilistic Road Map [20], optimal search algorithms (such as Dijkstra’s algorithm [21], A ∗ [22], and D ∗ [23]), and bioinspired planning algorithms.”
BackgroundMethodSampling-based algorithms for optimal motion planning
Karaman, S., & Frazzoli, E. (2011) · The International Journal of Robotics Research · doi:10.1177/0278364911406761 · Cited by 5,275
LaValle, S. M. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546877 · Cited by 5,211
Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory
Olfati-Saber, R. (2006) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.864190 · Cited by 5,037
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
Particle Swarm Optimization: Basic Concepts, Variants and Applications in Power Systems
del Valle, Y., Venayagamoorthy, G. K., Mohagheghi, S., Hernandez, J.-C., & Harley, R. G. (2008) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2007.896686 · Cited by 2,277
Principles of Robot Motion: Theory, Algorithms, and Implementations
Choset, H., & Latombe, J. (2005) · Medical Entomology and Zoology · Cited by 2,149
Exact robot navigation using artificial potential functions
Rimon, E., & Koditschek, D. E. (1992) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.163777 · Cited by 1,835
A survey on coverage path planning for robotics
Galceran, E., & Carreras, M. (2013) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2013.09.004 · Cited by 1,575
Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm
Eusuff, M. M., & Lansey, K. E. (2003) · Journal of Water Resources Planning and Management · doi:10.1061/(asce)0733-9496(2003)129:3(210 · Cited by 1,390
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
Shamos, M. I., & Hoey, D. (1975) · 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) · doi:10.1109/sfcs.1975.8 · Cited by 1,057
New potential functions for mobile robot path planning
Ge, S. S., & Cui, Y. (2000) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.880813 · Cited by 868
The focussed D* algorithm for real-time replanning
Stentz, A. (1995) · Cited by 865
Randomized Kinodynamic Motion Planning with Moving Obstacles
Hsu, D., Kindel, R., Latombe, J.-C., & Rock, S. (2002) · The International Journal of Robotics Research · doi:10.1177/027836402320556421 · Cited by 771
Fast replanning for navigation in unknown terrain
Koenig, S., & Likhachev, M. (2005) · IEEE Transactions on Robotics · doi:10.1109/tro.2004.838026 · Cited by 697
A potential field approach to path planning
Hwang, Y. K., & Ahuja, N. (1992) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.127236 · Cited by 684
Shortest Path Algorithms: An Evaluation Using Real Road Networks
Zhan, F. B., & Noon, C. E. (1998) · Transportation Science · doi:10.1287/trsc.32.1.65 · Cited by 570
Planning Long Dynamically Feasible Maneuvers for Autonomous Vehicles
Likhachev, M., & Ferguson, D. (2009) · The International Journal of Robotics Research · doi:10.1177/0278364909340445 · Cited by 512
Path planning using Laplace's equation
Connolly, C. I., Burns, J. B., & Weiss, R. (2002) · Proceedings., IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1990.126315 · Cited by 483
Chitta, S., Sucan, I., & Cousins, S. (2012) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2011.2181749 · Cited by 466
Optimal kinodynamic motion planning using incremental sampling-based methods
Karaman, S., & Frazzoli, E. (2010) · 49th IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2010.5717430 · Cited by 416
OBPRM: an obstacle-based PRM for 3D workspaces
Amato, N. M., Bayazıt, O. B., Dale, L. K., Jones, C. A., & Vallejo, D. (1998) · Cited by 414
Randomized preprocessing of configuration for fast path planning
Kavraki, L., & Latombe, J.-C. (2002) · Proceedings of the 1994 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1994.350966 · Cited by 412
A review of pseudospectral optimal control: From theory to flight
Ross, I. M., & Karpenko, M. (2012) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2012.09.002 · Cited by 371
Pehlivanoglu, Y. V. (2012) · Aerospace Science and Technology · doi:10.1016/j.ast.2011.02.006 · Cited by 304
Dorigo, M., & Birattari, M. (2017) · Encyclopedia of Machine Learning and Data Mining · doi:10.1007/978-1-4899-7687-1_22 · Cited by 298
Improved fast replanning for robot navigation in unknown terrain
Koenig, S., & Likhachev, M. (2003) · Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292) · doi:10.1109/robot.2002.1013481 · Cited by 294
Neural Network Dynamics for Path Planning and Obstacle Avoidance
Glasius, R., Komoda, A., & Gielen, S. C. A. M. (1995) · Neural Networks · doi:10.1016/0893-6080(94)e0045-m · Cited by 289
Footstep planning on uneven terrain with mixed-integer convex optimization
Deits, R., & Tedrake, R. (2014) · 2014 IEEE-RAS International Conference on Humanoid Robots · doi:10.1109/humanoids.2014.7041373 · Cited by 280
Autonomous UAV path planning and estimation
Tisdale, J., Kim, Z., & Hedrick, J. (2009) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2009.932529 · Cited by 275
Theta*: any-angle path planning on grids
Nash, A., Daniel, K., Koenig, S., & Feiner, A. (2007) · Cited by 268
Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain
Yershova, A., Jaillet, L., Simeon, T., & LaValle, S. M. (2006) · Proceedings of the 2005 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2005.1570709 · Cited by 258
Anderson, S. J., Peters, S. C., Pilutti, T. E., & Iagnemma, K. (2010) · International Journal of Vehicle Autonomous Systems · doi:10.1504/ijvas.2010.035796 · Cited by 255
Yilmaz, N. K., Evangelinos, C., Lermusiaux, P., & Patrikalakis, N. M. (2008) · IEEE Journal of Oceanic Engineering · doi:10.1109/joe.2008.2002105 · Cited by 232
Multi-Task Allocation and Path Planning for Cooperating UAVs
Bellingham, J., Tillerson, M., Richards, A., & How, J. P. (2003) · Cooperative Systems · doi:10.1007/978-1-4757-3758-5_2 · Cited by 216
Path Planning Strategies for UAVS in 3D Environments
De Filippis, L., Guglieri, G., & Quagliotti, F. (2012) · Journal of Intelligent & Robotic Systems · doi:10.1007/s10846-011-9568-2 · Cited by 212
On the generation of smooth three-dimensional rigid body motions
Zefran, M., Kumar, V., & Croke, C. B. (1998) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.704225 · Cited by 197
A literature review of UAV 3D path planning
Yang, L., Qi, J., Xiao, J., & Yong, X. (2014) · Proceeding of the 11th World Congress on Intelligent Control and Automation · doi:10.1109/wcica.2014.7053093 · Cited by 172
Self-citationRahimi-Vahed, A., & Mirzaei, A. H. (2007) · Computers & Industrial Engineering · doi:10.1016/j.cie.2007.06.007 · Cited by 160
Path Planning in Complex 3D Environments Using a Probabilistic Roadmap Method
Yan, F., Liu, Y.-S., & Xiao, J. (2013) · Machine Intelligence Research · doi:10.1007/s11633-013-0750-9 · Cited by 155
Self-citationThree-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm
Duan, H., Yu, Y., Zhang, X., & Shao, S. (2009) · Simulation Modelling Practice and Theory · doi:10.1016/j.simpat.2009.10.006 · Cited by 155
Conflict-directed A* and its role in model-based embedded systems
Williams, B. C., & Ragno, R. J. (2007) · Discrete Applied Mathematics · doi:10.1016/j.dam.2005.10.022 · Cited by 154
Automatic centerline extraction for virtual colonoscopy
Wan, M., Liang, Z., Ke, Q., et al. (2002) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2002.806409 · Cited by 152
A voronoi diagram‐visibility graph‐potential field compound algorithm for robot path planning
Masehian, E., & Amin‐Naseri, M. R. (2004) · Journal of Robotic Systems · doi:10.1002/rob.20014 · Cited by 147
Planning short paths with clearance using explicit corridors
Gerærts, R. (2010) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2010.5509263 · Cited by 141
Control design along trajectories with sums of squares programming
Majumdar, A., Ahmadi, A. A., & Tedrake, R. (2013) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2013.6631149 · Cited by 140
Optimal obstacle avoidance based on the Hamilton-Jacobi-Bellman equation
Sundar, S., & Shiller, Z. (1997) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.563653 · Cited by 131
Receding horizon control for multi-UAVs close formation control based on differential evolution
Zhang, X., Duan, H., & Yu, Y. (2010) · Science China Information Sciences · doi:10.1007/s11432-010-0036-6 · Cited by 71
Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D
Nash, A., Koenig, S., & Tovey, C. A. (2010) · Proceedings of the International Symposium on Combinatorial Search · doi:10.1609/socs.v1i1.18152 · Cited by 68
Shortest path routing algorithmusing Hopfield neural network
Ahn, C. W., Ramakrishna, R. S., Kang, C. G., & Choi, I. (2001) · Electronics Letters · doi:10.1049/el:20010800 · Cited by 65
A unified approach for robot motion planning with moving polyhedral obstacles
Shih, C., Lee, T., & Gruver, W. A. (1990) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/21.105088 · Cited by 63
Reactive deformation roadmaps: motion planning of multiple robots in dynamic environments
Gayle, R., Sud, A., Lin, M. C., & Manocha, D. (2007) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2007.4399287 · Cited by 60
Region-expansion for the Voronoi diagram of 3D spheres
Kim, D., Kim, D., Kim, D.-S., et al. (2006) · Computer-Aided Design · doi:10.1016/j.cad.2005.11.007 · Cited by 59
Three-Dimensional Path Planning of Unmanned Aerial Vehicles Using Particle Swarm Optimization
Foo, J. L., Knutzon, J. S., Oliver, J. H., & Winer, E. H. (2006) · AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference (MAO) · doi:10.2514/6.2006-6995 · Cited by 48
Rapidly exploring random graphs: motion planning of multiple mobile robots
Kala, R. (2013) · Advanced Robotics · doi:10.1080/01691864.2013.805472 · Cited by 45
Scalable unit commitment by memory-bounded ant colony optimization with local search
Saber, A. Y., & Alshareef, A. M. (2008) · International Journal of Electrical Power & Energy Systems · doi:10.1016/j.ijepes.2008.01.001 · Cited by 34
Relative Coordination 3D Trajectory Generation Based on the Trimmed ACO
Chen, Y., Zhao, X., Zhang, C., & Han, J. (2010) · International Conference on Electrical and Control Engineering · doi:10.1109/icece.2010.378 · Cited by 7
Self-citation
Cited by
A review: On path planning strategies for navigation of mobile robot
Patle, B. K., Babu L, G., Pandey, A., Parhi, D. R. K., & Jagadeesh, A. (2019) · Defence Technology · doi:10.1016/j.dt.2019.04.011 · Cited by 914
Path-Planning for Unmanned Aerial Vehicles with Environment Complexity Considerations: A Survey
Jones, M., Djahel, S., & Welsh, K. (2023) · ACM Computing Surveys · doi:10.1145/3570723 · Cited by 258
A survey on hybrid human-artificial intelligence for autonomous driving
Ning, H., Yin, R., Ullah, A., & Shi, F. (2022) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2021.3074695 · Cited by 84
Metadata
- Authors
- Yang, L., Qi, J., Song, D., Xiao, J., Han, J., & Xia, Y.
- Venue
- Journal of Control Science and Engineering
- Publisher
- Wiley
- Published
- 2016
- Volume
- 2016
- Pages
- 1-22
- ISSN
- 1687-5249 (ISSN-L)
- 1687-5257
- OpenAlex
- W2468618434
- Cited by
- 328
- References
- 66
- FWCI
- 15.97
- 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.