We study the problem of planning a tour for an energy-limited Unmanned Aerial Vehicle (UAV) to visit a set of sites in the least amount of time. We envision scenarios where the UAV can be recharged along the way either by landing on stationary recharging stations or on Unmanned Ground Vehicles (UGVs) acting as mobile recharging stations. This leads to a new variant of the Traveling Salesperson Problem (TSP) with mobile recharging stations. We present an algorithm that finds not only the order in which to visit the sites but also when and where to land on the charging stations to recharge. Our algorithm plans tours for the UGVs as well as determines the best locations to place stationary charging stations. While the problems we study are NP-Hard, we present a practical solution using Generalized TSP that finds the optimal solution. If the UGVs are slower, the algorithm also finds the minimum number of UGVs required to support the UAV mission such that the UAV is not required to wait for the UGV. We present a calibration routine to identify parameters that are needed for our algorithm as well as simulation results that show the running time is acceptable for reasonably sized instances in practice. We evaluate the performance of our algorithm through simulations and proof-of-concept experiments with a fully autonomous system of one UAV and UGV. / Master of Science / Commercially available Unmanned Aerial Vehicles (UAVs), especially multi-rotor aircrafts, have a flight time of less than 30 minutes. However many UAV applications, such as surveillance, package delivery, and infrastructure monitoring, require much longer flight times. To address this problem, we present a system in which an Unmanned Ground Vehicle (UGV) can recharge the UAV during deployments. This thesis studies the problem of finding when, where, and how much to recharge the battery. We also allow for the UGV to recharge while moving from one site to another. We present an algorithm that finds the paths for the UAV and UGV to visit a set of points of interest in the least time possible. We also present algorithms for cases when the UGV is slower than the UAV, and more than one UGV may be required. We evaluate our algorithms through simulations and proof-of-concept experiments.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/83493 |
| Date | January 2018 |
| Creators | Yu, Kevin L. |
| Contributors | Electrical and Computer Engineering, Tokekar, Pratap, Williams, Ryan, Abbott, A. Lynn |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
| Format | ETD, application/pdf |
| Rights | Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International, http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Page generated in 0.003 seconds