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

Hakimeh Mazaheri; Salman Goli; Ali Nourollah

doi:10.1145/3673896

journal article Oct 07, 2024

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

Hakimeh Mazaheri

Salman Goli

Ali Nourollah

ACM Computing Surveys Vol. 57 No. 1 pp. 1-32 · Association for Computing Machinery (ACM)

View at Publisher Save 10.1145/3673896

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.

[2]

10.3182/20080706-5-kr-1001.00867

[3]

10.1109/itng.2015.83

[4]

10.1109/taes.2012.6237608

[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–.

[6]

10.1109/glocomw.2010.5700245

[7]

P. Romanowski M. Mazur and J. McMillan. 2018. Global market for commercial applications of drone technology valued at over 127bn PwC.

[8]

10.1016/j.jsg.2016.02.012

[9]

10.3390/machines10050375

[10]

10.12720/jcm.9.9.687-692

[11]

10.1109/comst.2015.2495297

[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.

[13]

10.1109/sahcn.2004.1381939

[14]

10.1109/access.2020.3016118

[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

[16]

10.1109/jiot.2020.3030240

[17]

10.3390/s17020336

[18]

10.1109/icc.2017.7997403

[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

[22]

10.1145/3631530

[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

[24]

10.1109/icecet55527.2022.9872904

[25]

10.1145/1287853.1287860

[26]

S. M. N. Haas and Z. J. Alam. 2006. Coverage and connectivity in three-dimensional networks. In Proceedings of the MOBICOM. 346–357

[27]

10.1109/lcn.2004.53

[28]

10.1007/11502593_26

[29]

10.1109/tmc.2006.80

[30]

J. Giesbrecht. 2004. Global path planning for unmanned ground vehicles. Engineering Computer Science 56 (2004).

[31]

10.1109/ihmsc.2017.123

[32]

10.1007/978-1-4471-1273-0_32

[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

[34]

10.1186/s13677-022-00298-2

[35]

10.1109/tie.2004.825197

[36]

10.1145/225294.225297

[37]

10.1109/caidcd.2006.329429

[38]

10.1109/isccsp.2004.1296443

[39]

10.1002/rob.4620070404

[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.

[41]

10.1109/iciea.2010.5514816

[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.

[43]

10.1006/jagm.1997.0918

[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.

[45]

10.1007/978-4-431-35873-2_22

[46]

10.1109/icuas.2016.7502602

[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.

[48]

10.3390/s17040808

[49]

10.1145/967900.967919

[50]

10.1007/s10846-012-9716-3

Showing 50 of 210 references

Cited By

23

Mid‐Infrared nW‐level 2D Van der Waals Photodetector for Centimeter‐Precision Distance Sensing

Ximing Sun, Zhicheng Lin · 2025

Advanced Functional Materials

Metrics

23

Citations

210

References

Details

Published: Oct 07, 2024
Vol/Issue: 57(1)
Pages: 1-32
License: View

Authors

H

Hakimeh Mazaheri

School of Electrical and Computer Engineering, University of Kashan, Kashan, Iran (the Islamic Republic of)

S

Salman Goli

School of Electrical and Computer Engineering, University of Kashan, Kashan, Iran (the Islamic Republic of)

A

Ali Nourollah

School of Computer Engineering, Shahid Rajaee Teacher Training University, Tehran, Iran (the Islamic Republic of)

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

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

You May Also Like