A Robust Min-Max Algorithm for Bi-Objective USV Task Assignment Using Interval Time Costs under Wind-Wave-Current Uncertainty

The practical deployment of unmanned surface vehicle (USV) formations is critically hindered by environmental uncertainties, particularly the combined dynamic effects of wind, waves, and currents, which make accurate mission time prediction infeasible. This compels a shift from deterministic to robust optimization for task assignment. However, prevailing research focuses either on deterministic time costs or on dynamic online reallocation, largely overlooking the optimization of the initial task allocation plan under environmental uncertainty. To bridge this gap, we introduce a robust min-max framework for bi-objective task assignment. First, a novel Fast Perfect-Matching Detection (FPMD) algorithm for bipartite graphs is proposed. Building on this, an exact Fast Min-Max (FMM) algorithm is developed to rapidly identify schemes that minimize the maximum time cost. Finally, to explicitly model the impact of wind-wave-current conditions, travel time is represented as an interval matrix, upon which our Bi-Objective FMM (BOFMM) algorithm computes assignment schemes that respectively address the best-case and worst-case scenarios, thereby effectively balancing the expected task time and its variability. Extensive simulations demonstrate that our method significantly outperforms other approaches, delivering superior and guaranteed performance in uncertain marine environments.