Cooperative multi-robot routing for AUV–UAV inspection with inter-vehicle synchronization

Abstract

This paper addresses an extension of the classical heterogeneous Vehicle Routing Problem (VRP) tailored to cooperative missions involving Autonomous Underwater Vehicles (AUVs) and Unmanned Aerial Vehicles (UAVs) in monitoring scenarios characterized by heterogeneous task requirements and shoreline-avoidance constraints. The proposed formulation considers alternative coverage patterns for area and line inspection tasks, vehicle-type compatibility constraints, and temporal synchronization requirements between UAVs and AUVs. In particular, monitoring time windows are introduced to enable UAV supervision of AUV activities while ensuring coordinated mission execution. To solve this problem, a routing algorithm is developed and evaluated through two realistic case studies of increasing complexity. The approach integrates path-planning techniques to improve travel-time estimation and mission coordination. Its performance is assessed through comparisons with a Greedy Nearest Task baseline, considering mission makespan, task feasibility, workload balance, computational time, and robustness to positioning uncertainty. The results show that the proposed method reduces mission makespan by 21.26%, improves task feasibility, and enhances workload balance compared with the baseline approach. Furthermore, the synchronization mechanism enables effective coordination between heterogeneous vehicles while maintaining feasible mission schedules. High-quality solutions are obtained with computational times of up to 22 s, demonstrating that the proposed framework can address cooperative inspection missions with manageable computational effort.