Methods for Solving the Multi-UAV Rendezvous Recharging Problem and Variants

Abstract

Advances in unmanned aerial vehicles (UAVs) have led to greater usage in many interesting applications such as package delivery, surveillance, and inspection. When used as part of a team, multiple UAVs can perform tasks with improved efficiency over a single one. However, UAVs are often energy-limited and must rendezvous with a fixed or mobile charging station to replenish energy. This dissertation is concerned with the study of the Multi-UAV Rendezvous Recharging Problem. Given a set of UAVs and areas of interest, how do we generate feasible trajectories such that the UAVs can cover such areas repeatedly over a long-horizon, while rendezvousing with charging stations? Solving this problem efficiently is challenging for the following reasons: i) The MRRP generalizes vehicle routing problems, which is known to be NP-HARD, so obtaining optimal solutions may be intractable ii) Long-horizon plans may also be invalidated due to changes in the environment; iii) Evaluating algorithms during the developmental phase with field tests is expensive. In this dissertation, we address each of these challenges in a systematic manner, providing four contributions. First, an agent-based modeling and simulation framework that captures the necessary behavior of each vehicle is presented. Then, an algorithm for MRRP is proposed that decouples planning and execution in a hierarchical way. From this algorithm, we study 2 extensions of MRRP called multi-goal path finding in both the discrete and continuous setting, giving rise to two additional and novel frameworks.