Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Master of Science

Program

Computer Science

Supervisor

Haque, Anwar

Abstract

The use of unmanned aerial vehicles (UAV) or drones appears to be a viable, low-cost solution to problems in many applications. However, the limited onboard computing resources and battery capacity make it challenging to deploy drones for long-distance missions.

Path planning capabilities are essential for autonomous control systems. An autonomous drone must be able to rapidly compute feasible, energy-efficient paths to avoid collisions. We first evaluate existing sampling-based algorithms' performance and present a hybrid sampling-based algorithm to generate a solution quicker, using less memory. We then introduce the notion of a layered graph, which accurately and efficiently models the search environment. Simulations show that when applying a modified A* algorithm on the layered graph, paths can be generated at least twice as fast, using significantly less memory than the sampling-based algorithm.

Finally, we propose a novel cell-based model that uses a network of drones to perform long-range tasks such as last-mile deliveries. Drone charging stations are strategically placed to ensure that drones can replenish their batteries. The genetic algorithm was implemented to solve the scheduling problem for multiple drones using this model. We show that this model can be used to deliver many packages within a short amount of time.

Summary for Lay Audience

Unmanned aerial vehicles (UAV), or drones, have gained a lot of popularity over the last decade. The versatility of drones makes them an ideal solution for many applications. But the battery-powered drones often have limited flight time. Moreover, due to drones' weight restrictions, they do not have many computing resources available to them during flight. To deploy drones for commercial purposes, a robust path planner needs to be developed, and the flight range of drones needs to be extended for tasks such as drone deliveries.

In this thesis, we go over the path planning problem for autonomous drones. First, we investigate sampling-based algorithms, which compute a path based on randomly sampled points from the search space. Specifically, we look into Randomly Exploring Random Trees (RRT) and variants of this algorithm and evaluate its performance in environments with many obstacles. We then introduce a hybrid sampling-based algorithm to generate a solution quicker, using less memory. A layered graph is also proposed for path planning. With this approach, information about the obstacles in the search space can be efficiently represented as a graph. Using a graph traversal algorithm (A* search algorithm), we show that the algorithm can generate an energy-efficient path must faster than the sampling-based algorithm using fewer computing resources.

Finally, we propose a novel cell-based model that uses a network of drones to perform long-range tasks such as last-mile deliveries. Drone charging stations are strategically placed to ensure that drones can replenish their batteries. To evaluate the impact of the cell-based model, we assessed the time it would take for a set of drones to deliver packages using this model. The genetic algorithm, which is commonly used for optimization problems, was implemented to optimize a schedule for drone deliveries. We show that this model can be used to deliver many packages within a short amount of time.

Download

Share

COinS