A Bilevel Optimization Framework For fuel-constrained UAV-UGV Cooperative Routing: Planning and Experimental Validation

Fast moving unmanned aerial vehicles (UAVs) are well suited for aerial surveillance, but are limited by their battery capacity. To increase their endurance UAVs can be refueled on slow moving unmanned ground vehicles (UGVs). The cooperative routing of UAV-UGV to survey vast regions within their speed and fuel constraints is a computationally challenging problem, but can be simplified with heuristics. Here we present multiple heuristics to enable feasible and sufficiently optimal solutions to the problem. Using the UAV fuel limits and the minimum set cover algorithm, the UGV refueling stops are determined. These refueling stops enable the allocation of mission points to the UAV and UGV. A standard traveling salesman formulation and a vehicle routing formulation with time windows, dropped visits, and capacity constraints is used to solve for the UGV and UAV route, respectively. Experimental validation of the approach on a small-scale testbed shows the efficacy of the approach.