Efficient Path Planning for Autonomous Underwater Vehicles: Solver Comparison for Multi-Cluster Coverage Missions

Abstract

Autonomous underwater vehicles are increasingly employed for seafloor survey missions, requiring fully autonomous decision-making under strict energy and communication constraints. In operations targeting seafloor hazards, vehicles typically conduct a two-stage survey: an initial broad scan identifies potential sites, followed by detailed inspections of spatially separated clusters. Planning these inspections requires optimising the visitation sequence and scan orientations while navigating ocean currents and physical obstacles. Because the number of possible routes grows exponentially with cluster count, onboard planning must rely on approximation algorithms. Selecting an appropriate solver under tight computational limits, however, remains an open question. Here we show that, across a range of operationally relevant mission sizes, a regret-based constructive heuristic with local search refinement improves route quality for multi-cluster coverage missions compared to greedy and population-based alternatives. Across a benchmark of missions with six to twenty clusters with a two-minute time-budget on a reference system, this method matches the best route found by any solver on the majority of instances (excluding all-tied instances), with its advantage growing as cluster numbers increase. On the smaller instances where a near-exact dynamic-programming reference can be computed, its routes remain close to that reference. Although it shows occasional degradation on the largest instances, this limitation can be mitigated during deployment by falling back to an alternative solver, and the solver continues to improve well into the planning budget rather than converging early, which is well suited to on-device deployment. These results establish a practical hierarchy of planning algorithms, positioning the regret-based approach as a reliable default for resource-constrained underwater missions. The benchmarking framework further provides a template for evaluating optimisation strategies in other autonomous systems, where balancing solution quality against computational limits is essential. (Deep Sea Monitoring Reports ; DSMR-0005)