You are here

FAU Collections » FAU Research Repository » FAU Theses and Dissertations

SPACE-TIME GRAPH PATH PLANNING FOR UAS TRAFFIC MANAGEMENT SYSTEMS

Download pdf | Full Screen View

Date Issued:
2021
Abstract/Description:
The unmanned aerial vehicle (UAV) technology has evolved considerably in recent years and the global demand for package delivery is expected to grow even more during COVID-19 and the social distance era. The low cost of acquisition, payload capacity, maneuverability, and the ability to y at low-altitude with a very low cost of operation, make UAVs a perfect fit to revolutionize the payload transportation of small items. The large-scale adoption of drone package delivery in high-density urban areas can be challenging and the Unmanned Aircraft Systems (UAS) operators must ensure safety, security, efficiency and equity of the airspace system. In order to address some of these challenges, FAA and NASA have developed a new architecture that will support a set of services to enable cooperative management of low-altitude operations between UAS operators. The architecture is still in its conceptual stage and designing a mechanism that ensures the fair distribution of the available airspace to commercial applications has become increasingly important. Considering that, the path planning is one of the most important problems to be explored. The objective is not only to find an optimal and shortest path but also to provide a collision-free environment to the UAVs. Taking into consideration all these important aspects and others such as serving on-demand requests, flight duration limitation due to energy constraints, maintaining the safety distance to avoid collisions, and using warehouses as starting and ending points in parcel delivery, this dissertation proposes: (i) an energy-constrained scheduling mechanism using a multi-source A* algorithm variant, and (ii) a generalized path planning mechanism using a space-time graph with multi-source multi-destination BFS generalization to ensure pre-flight UAV collision-free trajectories. This dissertation also uses the generalized path planning mechanism to solve the energy-constrained drone delivery problem. The experimental results show that the proposed algorithms are computationally efficient and scalable with the number of requests and graph size.
Title: SPACE-TIME GRAPH PATH PLANNING FOR UAS TRAFFIC MANAGEMENT SYSTEMS.
58 views
15 downloads
Name(s): Papa, Rafael, author
Cardei, Mihaela, Thesis advisor
Cardei, Ionut , Thesis advisor
Florida Atlantic University, Degree grantor
Department of Computer and Electrical Engineering and Computer Science
College of Engineering and Computer Science
Type of Resource: text
Genre: Electronic Thesis Or Dissertation
Date Created: 2021
Date Issued: 2021
Publisher: Florida Atlantic University
Place of Publication: Boca Raton, Fla.
Physical Form: application/pdf
Extent: 135 p.
Language(s): English
Abstract/Description: The unmanned aerial vehicle (UAV) technology has evolved considerably in recent years and the global demand for package delivery is expected to grow even more during COVID-19 and the social distance era. The low cost of acquisition, payload capacity, maneuverability, and the ability to y at low-altitude with a very low cost of operation, make UAVs a perfect fit to revolutionize the payload transportation of small items. The large-scale adoption of drone package delivery in high-density urban areas can be challenging and the Unmanned Aircraft Systems (UAS) operators must ensure safety, security, efficiency and equity of the airspace system. In order to address some of these challenges, FAA and NASA have developed a new architecture that will support a set of services to enable cooperative management of low-altitude operations between UAS operators. The architecture is still in its conceptual stage and designing a mechanism that ensures the fair distribution of the available airspace to commercial applications has become increasingly important. Considering that, the path planning is one of the most important problems to be explored. The objective is not only to find an optimal and shortest path but also to provide a collision-free environment to the UAVs. Taking into consideration all these important aspects and others such as serving on-demand requests, flight duration limitation due to energy constraints, maintaining the safety distance to avoid collisions, and using warehouses as starting and ending points in parcel delivery, this dissertation proposes: (i) an energy-constrained scheduling mechanism using a multi-source A* algorithm variant, and (ii) a generalized path planning mechanism using a space-time graph with multi-source multi-destination BFS generalization to ensure pre-flight UAV collision-free trajectories. This dissertation also uses the generalized path planning mechanism to solve the energy-constrained drone delivery problem. The experimental results show that the proposed algorithms are computationally efficient and scalable with the number of requests and graph size.
Identifier: FA00013861 (IID)
Degree granted: Dissertation (Ph.D.)--Florida Atlantic University, 2021.
Collection: FAU Electronic Theses and Dissertations Collection
Note(s): Includes bibliography.
Subject(s): Unmanned aerial vehicles
Drone aircraft
Space and time
Persistent Link to This Record: http://purl.flvc.org/fau/fd/FA00013861
Use and Reproduction: Copyright © is held by the author with permission granted to Florida Atlantic University to digitize, archive and distribute this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.
Use and Reproduction: http://rightsstatements.org/vocab/InC/1.0/
Host Institution: FAU
Is Part of Series: Florida Atlantic University Digital Library Collections.