A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments

This paper presents a multi-objective coverage flight path planning algorithm that finds minimum length, collision-free, and flyable paths for unmanned aerial vehicles (UAV) in three-dimensional (3D) urban environments inhabiting multiple obstacles for covering spatially distributed regions. In many...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Abdul Majeed, Seong Oun Hwang
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	coverage path planning unmanned aerial vehicle sparse waypoint graphs urban environments obstacles area of interest Motor vehicles. Aeronautics. Astronautics TL1-4050
Acceso en línea:	https://doaj.org/article/f45d0e8df92b4527bb32ff1c782a2187
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:f45d0e8df92b4527bb32ff1c782a2187
record_format	dspace
spelling	oai:doaj.org-article:f45d0e8df92b4527bb32ff1c782a21872021-11-25T15:57:44ZA Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments10.3390/aerospace81103432226-4310https://doaj.org/article/f45d0e8df92b4527bb32ff1c782a21872021-11-01T00:00:00Zhttps://www.mdpi.com/2226-4310/8/11/343https://doaj.org/toc/2226-4310This paper presents a multi-objective coverage flight path planning algorithm that finds minimum length, collision-free, and flyable paths for unmanned aerial vehicles (UAV) in three-dimensional (3D) urban environments inhabiting multiple obstacles for covering spatially distributed regions. In many practical applications, UAVs are often required to fully cover multiple spatially distributed regions located in the 3D urban environments while avoiding obstacles. This problem is relatively complex since it requires the optimization of both inter (e.g., traveling from one region/city to another) and intra-regional (e.g., within a region/city) paths. To solve this complex problem, we find the traversal order of each area of interest (AOI) in the form of a coarse tour (i.e., graph) with the help of an ant colony optimization (ACO) algorithm by formulating it as a traveling salesman problem (TSP) from the center of each AOI, which is subsequently optimized. The intra-regional path finding problem is solved with the integration of fitting sensors’ footprints sweeps (SFS) and sparse waypoint graphs (SWG) in the AOI. To find a path that covers all accessible points of an AOI, we fit fewer, longest, and smooth SFSs in such a way that most parts of an AOI can be covered with fewer sweeps. Furthermore, the low-cost traversal order of each SFS is computed, and SWG is constructed by connecting the SFSs while respecting the global and local constraints. It finds a global solution (i.e., inter + intra-regional path) without sacrificing the guarantees on computing time, number of turning maneuvers, perfect coverage, path overlapping, and path length. The results obtained from various representative scenarios show that proposed algorithm is able to compute low-cost coverage paths for UAV navigation in urban environments.Abdul MajeedSeong Oun HwangMDPI AGarticlecoverage path planningunmanned aerial vehiclesparse waypoint graphsurban environmentsobstaclesarea of interestMotor vehicles. Aeronautics. AstronauticsTL1-4050ENAerospace, Vol 8, Iss 343, p 343 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	coverage path planning unmanned aerial vehicle sparse waypoint graphs urban environments obstacles area of interest Motor vehicles. Aeronautics. Astronautics TL1-4050
spellingShingle	coverage path planning unmanned aerial vehicle sparse waypoint graphs urban environments obstacles area of interest Motor vehicles. Aeronautics. Astronautics TL1-4050 Abdul Majeed Seong Oun Hwang A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments
description	This paper presents a multi-objective coverage flight path planning algorithm that finds minimum length, collision-free, and flyable paths for unmanned aerial vehicles (UAV) in three-dimensional (3D) urban environments inhabiting multiple obstacles for covering spatially distributed regions. In many practical applications, UAVs are often required to fully cover multiple spatially distributed regions located in the 3D urban environments while avoiding obstacles. This problem is relatively complex since it requires the optimization of both inter (e.g., traveling from one region/city to another) and intra-regional (e.g., within a region/city) paths. To solve this complex problem, we find the traversal order of each area of interest (AOI) in the form of a coarse tour (i.e., graph) with the help of an ant colony optimization (ACO) algorithm by formulating it as a traveling salesman problem (TSP) from the center of each AOI, which is subsequently optimized. The intra-regional path finding problem is solved with the integration of fitting sensors’ footprints sweeps (SFS) and sparse waypoint graphs (SWG) in the AOI. To find a path that covers all accessible points of an AOI, we fit fewer, longest, and smooth SFSs in such a way that most parts of an AOI can be covered with fewer sweeps. Furthermore, the low-cost traversal order of each SFS is computed, and SWG is constructed by connecting the SFSs while respecting the global and local constraints. It finds a global solution (i.e., inter + intra-regional path) without sacrificing the guarantees on computing time, number of turning maneuvers, perfect coverage, path overlapping, and path length. The results obtained from various representative scenarios show that proposed algorithm is able to compute low-cost coverage paths for UAV navigation in urban environments.
format	article
author	Abdul Majeed Seong Oun Hwang
author_facet	Abdul Majeed Seong Oun Hwang
author_sort	Abdul Majeed
title	A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments
title_short	A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments
title_full	A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments
title_fullStr	A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments
title_full_unstemmed	A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments
title_sort	multi-objective coverage path planning algorithm for uavs to cover spatially distributed regions in urban environments
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/f45d0e8df92b4527bb32ff1c782a2187
work_keys_str_mv	AT abdulmajeed amultiobjectivecoveragepathplanningalgorithmforuavstocoverspatiallydistributedregionsinurbanenvironments AT seongounhwang amultiobjectivecoveragepathplanningalgorithmforuavstocoverspatiallydistributedregionsinurbanenvironments AT abdulmajeed multiobjectivecoveragepathplanningalgorithmforuavstocoverspatiallydistributedregionsinurbanenvironments AT seongounhwang multiobjectivecoveragepathplanningalgorithmforuavstocoverspatiallydistributedregionsinurbanenvironments
_version_	1718413415062437888

A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments

Ejemplares similares