Robust coordinated path planning for unmanned aerial vehicles and unmanned surface vehicles in maritime monitoring with travel time uncertainty

Abstract

This study examines the routing and scheduling of an integrated system of unmanned aerial vehicles (UAVs) and unmanned surface vehicles (USVs) for maritime surveillance. The uncertainties in air and maritime conditions can cause delays in the movements of UAVs and USVs. We introduce a robust coordinated path planning approach for the UAV-USV system, optimizing operational efficiency while accounting for UAV/USV travel time unreliability. Specifically, we propose a novel robust compact formulation for the coordinated path planning problem using the budgeted uncertainty sets. To solve this complex problem, we decompose it into a master problem, i.e., a set partitioning problem, and a subproblem that deals with the robust resource-constrained elementary shortest paths. Furthermore, we propose a customized branch-and-price-and-cut solution algorithm to efficiently solve the robust path planning problem. Numerical studies illustrate that our approach can produce solutions that are significantly more robust than those that ignore uncertainty.