A New Coverage Flight Path Planning Algorithm Based on Footprint Sweep Fitting for Unmanned Aerial Vehicle Navigation in Urban Environments
Source abstract
Abstract
This paper presents a new coverage flight path planning algorithm that finds collision-free, minimum length and flyable paths for unmanned aerial vehicle (UAV) navigation in three-dimensional (3D) urban environments with fixed obstacles for coverage missions. The proposed algorithm significantly reduces computational time, number of turns, and path overlapping while finding a path that passes over all reachable points of an area or volume of interest by using sensor footprints’ sweeps fitting and a sparse waypoint graph in the pathfinding process. We devise a novel footprints’ sweep fitting method considering UAV sensor footprint as coverage unit in the free spaces to achieve maximal coverage with fewer and longer footprints’ sweeps. After footprints’ sweeps fitting, the proposed algorithm determines the visiting sequence of footprints’ sweeps by formulating it as travelling salesman problem (TSP), and ant colony optimization (ACO) algorithm is employed to solve the TSP. Furthermore, we generate a sparse waypoint graph by connecting footprints’ sweeps’ endpoints to obtain a complete coverage flight path. The simulation results obtained from various scenarios fortify the effectiveness of the proposed algorithm and verify the aforementioned claims.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Robotic Path Planning Algorithms · UAV Applications and Optimization · Robotics and Sensor-Based Localization
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Information and Electronics Engineering, Korea Aerospace University, Deogyang-gu, Goyang-si, Gyeonggi-do 412-791, Korea
Funding
Institute for Information and communications Technology Promotion
References (55)
Show source-provided references
1. Drones: Augmenting Our Quality of Life10.1109/MPOT.2018.2850386 ↗
2. Autonomous robots for harsh environments: A holistic overview of current solutions and ongoing challenges10.1080/21642583.2018.1477634 ↗
3. Pinto, M.F., Marcato, A.L., Melo, A.G., Honório, L.M., and Urdiales, C. (2019). A Framework for Analyzing Fog-Cloud Computing Cooperation Applied to Information Processing of UAVs. Wirel. Commun. Mob. Comput.10.1155/2019/7497924 ↗
4. Karaduman, M., Çınar, A., and Eren, H. (2019). UAV Traffic Patrolling via Road Detection and Tracking in Anonymous Aerial Video Frames. J. Intell. Robot. Syst., 1–16.10.1007/s10846-018-0954-x ↗
5. Wang, Y.C. (2019). Mobile Solutions to Air Quality Monitoring. Mobile Solutions and Their Usefulness in Everyday Life, Springer.10.1007/978-3-319-93491-4_12 ↗
6. Luo, C., Miao, W., Ullah, H., McClean, S., Parr, G., and Min, G. (2019). Unmanned Aerial Vehicles for Disaster Management. Geological Disaster Monitoring Based on Sensor Networks, Springer.10.1007/978-981-13-0992-2_7 ↗
7. UAV-enabled healthcare architecture: Issues and challenges10.1016/j.future.2019.01.028 ↗
8. Benefits and challenges of using unmanned aerial systems in the monitoring of electrical distribution systems10.1016/j.tej.2018.02.004 ↗
9. Coverage for robotics—A survey of recent results10.1023/A:1016639210559 ↗
10. Quality-aware UAV coverage and path planning in geometrically complex environments10.1016/j.adhoc.2018.02.008 ↗
11. Time-optimal trajectory generation for aerial coverage of urban building10.1016/j.ast.2018.10.011 ↗
12. Remote proximity monitoring between mobile construction resources using camera-mounted UAVs10.1016/j.autcon.2018.12.014 ↗
13. Generating a hyperspectral digital surface model using a hyperspectral 2D frame camera10.1016/j.isprsjprs.2018.11.025 ↗
14. Díaz-Delgado, R., Ónodi, G., Kröel-Dulay, G., and Kertész, M. (2019). Enhancement of Ecological Field Experimental Research by Means of UAV Multispectral Sensing. Drones, 3.10.3390/drones3010007 ↗
15. Lingelbach, F. (May, January 26). Path planning using probabilistic cell decomposition. Proceedings of the 2004 IEEE International Conference on Robotics and Automation, ICRA’04, New Orleans, LA, USA.10.1109/ROBOT.2004.1307193 ↗
16. Morse decompositions for coverage tasks10.1177/027836402320556359 ↗
17. Wong, S. (2006). Qualitative Topological Coverage of Unknown Environments by Mobile Robots. [Doctoral Dissertation, The University of Auckland].
18. Shivashankar, V., Jain, R., Kuter, U., and Nau, D.S. (2011, January 18–20). Real-Time Planning for Covering an Initially-Unknown Spatial Environment. Proceedings of the Twenty-Fourth International Florida Artificial Intelligence Research Society Conference, Palm Beach, FL, USA.
19. Butler, Z.J., Rizzi, A.A., and Hollis, R.L. (1999, January 17). Contact sensor-based coverage of rectilinear environments. Proceedings of the 1999 IEEE International Symposium on Intelligent Control/Intelligent Systems and Semiotics, Cambridge, MA, USA.10.1109/ISIC.1999.796666 ↗
20. Xu, L. (2011). Graph Planning for Environmental Coverage. [Ph.D. Thesis, Robotics Institute, Carnegie Mellon University].
21. Coverage path planning for UAVs based on enhanced exact cellular decomposition method10.1016/j.mechatronics.2010.10.009 ↗
22. A multi-scroll chaotic system for a higher coverage path planning of a mobile robot using flatness controller10.1016/j.chaos.2018.12.002 ↗
23. Framework for automated UAS-based structural condition assessment of bridges10.1016/j.autcon.2018.10.006 ↗
24. Agricultural operations planning in fields with multiple obstacle areas10.1016/j.compag.2014.08.013 ↗
25. Coombes, M., Fletcher, T., Chen, W.H., and Liu, C. (2018). Optimal polygon decomposition for UAV survey coverage path planning in wind. Sensors, 18.10.3390/s18072132 ↗
26. Montanari, A., Kringberg, F., Valentini, A., Mascolo, C., and Prorok, A. (2018, January 10–15). Surveying Areas in Developing Regions Through Context Aware Drone Mobility. Proceedings of the 4th ACM Workshop on Micro Aerial Vehicle Networks, Systems, and Applications, Munich, Germany.10.1145/3213526.3213532 ↗
27. Aerial coverage optimization in precision agriculture management: A musical harmony inspired approach10.1016/j.compag.2013.09.008 ↗
28. Cabreira, T., Brisolara, L., and Ferreira, P.R. (2019). Survey on Coverage Path Planning with Unmanned Aerial Vehicles. Drones, 3.10.3390/drones3010004 ↗
29. Region filling operations with random obstacle avoidance for mobile robots10.1002/rob.4620050202 ↗
30. A survey on coverage path planning for robotics10.1016/j.robot.2013.09.004 ↗
31. Smooth coverage path planning and control of mobile robots based on high-resolution grid map representation10.1016/j.robot.2011.06.002 ↗
32. Hierarchical heuristic search using a Gaussian Mixture Model for UAV coverage planning10.1109/TCYB.2014.2309898 ↗
33. Coverage of known spaces: The boustrophedon cellular decomposition10.1023/A:1008958800904 ↗
34. Choset, H.M., Hutchinson, S., Lynch, K.M., Kantor, G., Burgard, W., Kavraki, L.E., and Thrun, S. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementation, MIT Press.
35. Milnor, J.W., Spivak, M., Wells, R., and Wells, R. (1963). Morse Theory, Princeton University Press.
36. Nam, L.H., Huang, L., Li, X.J., and Xu, J.F. (2016, January 22–24). An approach for coverage path planning for UAVs. Proceedings of the 2016 IEEE 14th International Workshop on Advanced Motion Control (AMC), Auckland, New Zealand.10.1109/AMC.2016.7496385 ↗
37. Bochkarev, S., and Smith, S.L. (2016, January 21–25). On minimizing turns in robot coverage path planning. Proceedings of the 2016 IEEE International Conference on Automation Science and Engineering (CASE), Fort Worth, TX, USA.10.1109/COASE.2016.7743548 ↗
38. Andersen, H.L. (2014). Path Planning for Search and Rescue Mission Using Multicopters. [Master’s Thesis, Institutt for Teknisk Kybernetikk].
39. Jiao, Y.S., Wang, X.M., Chen, H., and Li, Y. (2010, January 15–17). Research on the coverage path planning of uavs for polygon areas. Proceedings of the 2010 5th IEEE Conference on Industrial Electronics and Applications (ICIEA), Taichung, Taiwan.
40. Levcopoulos, C., and Krznaric, D. (1996, January 28–30). Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation. Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, GA, USA.
41. Xu, A., Viriyasuthee, C., and Rekleitis, I. (2011, January 9–13). Optimal complete terrain coverage using an unmanned aerial vehicle. Proceedings of the 2011 IEEE International Conference On Robotics and automation (ICRA), Shanghai, China.10.1109/ICRA.2011.5979707 ↗
42. Öst, G. (2012). Search Path Generation With UAV Applications Using Approximate Convex Decomposition. [Master Thesis, Linkoping University].
43. Sadat, S.A., Wawerla, J., and Vaughan, R.T. (2014, January 14–18). Recursive non-uniform coverage of unknown terrains for uavs. Proceedings of the 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2014), Chicago, IL, USA.10.1109/IROS.2014.6942790 ↗
44. Sadat, S.A., Wawerla, J., and Vaughan, R. (2015, January 26–30). Fractal trajectories for online non-uniform aerial coverage. Proceedings of the 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA.10.1109/ICRA.2015.7139606 ↗
45. Aerial remote sensing in agriculture: A practical approach to area coverage and path planning for fleets of mini aerial robots10.1002/rob.20403 ↗
46. LaValle, S.M. (2006). Planning Algorithms, Cambridge University Press.10.1017/CBO9780511546877 ↗
47. Ant system: Optimization by a colony of cooperating agents10.1109/3477.484436 ↗
48. Genetic algorithms for the travelling salesman problem: A review of representations and operators10.1023/A:1006529012972 ↗
49. Zelinsky, A., Jarvis, R.A., Byrne, J.C., and Yuta, S. (1993, January 8–9). Planning paths of complete coverage of an unstructured environment by a mobile robot. Proceedings of the International Conference on Advanced Robotics, Tsukuba, Japan.
50. A formal basis for the heuristic determination of minimum cost paths10.1109/TSSC.1968.300136 ↗
51. Nash, A., Daniel, K., Koenig, S., and Felner, A. (2007, January 22–26). Theta*: Any-Angle Path Planning on Grids. Proceedings of the AAAI Conference on Artificial Intelligence, Vancouver, BC, Canada.
52. Route planning for unmanned aerial vehicle (UAV) on the sea using hybrid differential evolution and quantum-behaved particle swarm optimization10.1109/TSMC.2013.2248146 ↗
53. Efficient complete coverage of a known arbitrary environment with applications to aerial operations10.1007/s10514-013-9364-x ↗
54. Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction10.1016/j.eswa.2016.02.007 ↗
55. Majeed, A., and Lee, S. (2018). A Fast Global Flight Path Planning Algorithm Based on Space Circumscription and Sparse Visibility Graph for Unmanned Aerial Vehicle. Electronics, 7.10.3390/electronics7120375 ↗