Developing Computationally Efficient Optimization Framework for Online Routing of UAV-UGV Systems

Unmanned Aerial Vehicles (UAVs) are increasingly popular for autonomous tasks such as surveillance, package delivery, and disaster relief. However, as these applications expand, so do the challenges of enabling UAVs to perform these tasks over extended durations or on a larger scale. One solution is to pair UAVs with Unmanned Ground Vehicles (UGVs), which can serve as carriers to transport UAVs or as mobile recharging stations to extend their operational range. To achieve effective performance and coordination between UAVs and UGVs, optimal route planning is essential. The UAV-UGV routing problem, being an NP-Hard combinatorial optimization challenge, is further complicated by the heterogeneity of these vehicles. Traditional optimization approaches, including exact methods like Branch and Bound with MILP formulations, as well as standard heuristics and metaheuristics, are often too time-consuming to be practical due to the dynamic nature of the environment and the autonomous vehicles involved. Thus, a faster, more adaptive planning method is crucial to address these challenges effectively. This thesis focuses on solving this collaborative UAV-UGV routing problem in a computationally efficient manner such that the solutions are obtained quick enough to be feasibly applied on to the actual UAV-UGV system in a realistic environment. The core concept of solving such a collaborative routing problem is by formulating them as bi-level optimization problem, where the outer-level handles the UGV optimization and for each UGV candidate route, the inner-level handles the UAV optimization. The computational efficiency aspect is made possible by developing a multi-agent optimization framework, where the agents consist of different optimization algorithms integrated into it. Those algorithms are complementary to each other such that the optimization happens to the best of its ability by picking the best performance out of the algorithms used. Initial studies concentrated on leveraging the existing multi-agent optimization framework known as A-Teams, incorporating Nelder-Mead and Genetic Algorithms with complementary features for outer-level UGV optimization. The framework was tested across various instances to evaluate its performance compared to using only Genetic Algorithm at the outer level. Each of these approaches employs local search heuristics at the inner level for UAV optimization. Subsequently, the existing A-Teams framework is developed to be more smarter by integrating a newer 'Predictor agent' into the framework, which imparts slightly better computational efficiency compared to the original A-Teams framework. This A-Teams variant is novel in the sense of adding the Predictor agent into the framework. Finally, an end-to-end autonomous approach is developed to enhance computational efficiency by enabling decision-making during the optimization process. This approach involves creating a learning-based hyper-heuristic method using Reinforcement Learning (RL) within the multi-agent framework to deliver computationally efficient, real-time UAV-UGV routing solutions. This approach increases the autonomy of the framework, requiring minimal user input.