journal article Oct 07, 2024

A survey of 3D Space Path-Planning Methods and Algorithms

Abstract
Due to their agility, cost-effectiveness, and high maneuverability, Unmanned Aerial Vehicles (UAVs) have attracted considerable attention from researchers and investors alike. Path planning is one of the practical subsets of motion planning for UAVs. It prevents collisions and ensures complete coverage of an area. This study provides a structured review of applicable algorithms and coverage path planning solutions in Three-Dimensional (3D) space, presenting state-of-the-art technologies related to heuristic decomposition approaches for UAVs and the forefront challenges. Additionally, it introduces a comprehensive and novel classification of practical methods and representational techniques for path-planning algorithms. This depends on environmental characteristics and optimal parameters in the real world. The first category presents a classification of semi-accurate decomposition approaches as the most practical decomposition method, along with the data structure of these practices, categorized by phases. The second category illustrates path-planning processes based on symbolic techniques in 3D space. Additionally, it provides a critical analysis of crucial influential approaches based on their importance in path quality and researchers’ attention, highlighting their limitations and research gaps. Furthermore, it will provide the most pertinent recommendations for future work for researchers. The studies demonstrate an apparent inclination among experimenters toward using the semi-accurate cellular decomposition approach to improve 3D path planning.
Topics

No keywords indexed for this article. Browse by subject →

References
210
[1]
K. Daniel and C. Wietfeld. 2011. Using public network infrastructures for UAV remote sensing in Civilian security operations. In Proceedings of the Homeland Security Affairs Journal.
[5]
E. Santamaria, F. Segor, and I. Tchouchenkov. 2013. Rapid aerial mapping with multiple heterogeneous unmanned vehicles. In Proceedings of the 10th International Conference on Information Systems for Crisis Response and Management. Baden-Baden, Germany, 12–.
[7]
P. Romanowski M. Mazur and J. McMillan. 2018. Global market for commercial applications of drone technology valued at over 127bn PwC.
[12]
A. M.-C. Ye and Y. So. 2005. On solving coverage problems in a wireless sensor network using voronoi diagrams. Proc. WINE, 3828 (2005), 584–593.
[15]
Hugenholtz and C. H. Whitehead. 2014. Remote sensing of the environment with small unmanned aircraft systems, part 1:A review of progress and challenges. Journal of Unmanned Vehicle Systems 2, 3 (2014), 69--85. DOI:10.1139/juvs-2014-0006
[19]
C. Nattero, C. T. Recchiuto, A. Sgorbissa, and F. Wanderlingh. 2014. Coverage algorithms for search and rescue with UAV drones. In Proceedings of the Workshop of the XIII AI*IA Symposium on Artificial Intelligence.
[20]
A. Nourollah and N. Behzadpour. 2018. Robot arm reconfiguration to minimization moving parts. Journal of Electrical and Computer Engineering Innovations 6, 2 (2018), 235–249.
[21]
A survey on coverage path planning for robotics

Enric Galceran, Marc Carreras

Robotics and Autonomous Systems 10.1016/j.robot.2013.09.004
[23]
Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction

Marina Torres, David A. Pelta, José L. Verdegay et al.

Expert Systems with Applications 10.1016/j.eswa.2016.02.007
[26]
S. M. N. Haas and Z. J. Alam. 2006. Coverage and connectivity in three-dimensional networks. In Proceedings of the MOBICOM. 346–357
[30]
J. Giesbrecht. 2004. Global path planning for unmanned ground vehicles. Engineering Computer Science 56 (2004).
[33]
A. Majeed and S. Oun Hwang. 2022. Recent developments in path planning for unmanned aerial vehicles. Intech Open. DOI:10.5772/intechopen.99576 10.5772/intechopen.99576
[40]
H. Choset, E. Acar, A. A. Rizzi, and J. Luntz. 2000. Exactcellular decompositions interms of critical points of morse functions. In Proceedings of the IEEE Int. Conf. Robotics and AutomationI CRA. 2270–2277.
[42]
Y. Li, H. Chen, M. J. Er, and X. Wang. 2011. Coverage path planning for UAVs based on enhanced exact cellular decomposition method. Mechatron. Spec. Issue Dev. Auton. Unmanned Aer. Veh. Das, A. Ghosh and S. K. 21, 5 (2011), 876–885.
[44]
W. H. Huang. 2001. Optimal line-sweep-based decompositions for coverage algorithms. In Proceedings of the IEEE International Conference on Robotics and Automation. Seoul, Korea, 27–32.
[47]
Gabriely E. Rimon. 2002. Spiral-stc: An on-line coverage algorithm of grid environments by a mobile robot. In Proc. IEEE Int. Conf. Robotics and Automation 1 (2002), 954–960.

Showing 50 of 210 references

Cited By
23
Metrics
23
Citations
210
References
Details
Published
Oct 07, 2024
Vol/Issue
57(1)
Pages
1-32
License
View
Cite This Article
Hakimeh Mazaheri, Salman Goli, Ali Nourollah (2024). A survey of 3D Space Path-Planning Methods and Algorithms. ACM Computing Surveys, 57(1), 1-32. https://doi.org/10.1145/3673896
Related

You May Also Like

Data clustering

A. K. Jain, M. N. Murty · 1999

9,568 citations

Anomaly detection

Varun Chandola, Arindam Banerjee · 2009

8,799 citations

Machine learning in automated text categorization

Fabrizio Sebastiani · 2002

5,027 citations

Object tracking

Alper Yilmaz, Omar Javed · 2006

3,632 citations

A Survey on Bias and Fairness in Machine Learning

Ninareh Mehrabi, Fred Morstatter · 2021

3,466 citations