A Comprehensive Study on Coverage Path Planning Strategies for Autonomous Underwater Vehicles with Nadir Gap

Abstract

Autonomous Underwater Vehicles (AUVs) play a vital role in exploring and mapping underwater environments. However, the presence of nadir gaps, or blind zones, in commercial AUVs can lead to unexplored areas during mission execution, limiting their effectiveness. We refer to the area under inspection not sensed by the AUV as nadir gap. We study the problem of underwater exploration of a rectangular region focusing on single and multiple AUVs with nadir gaps. Complete exploration of a given area using such a AUV requires careful planning such that no area is left uncovered due to nadir gaps. Initially unexplored areas can be covered later using extra trips, but that may cause some areas to be covered multiple times leading to redundant overlap and ineffective resource usage. Hence, we devise strategies that not only cover the entire input area but also aim to minimize mission completion time and the total number of turns taken by the AUV(s). There has been extensive work on developing strategies which explore the entire area of interest but all of them are limited to exploration with a single AUV when nadir gap is a constraint. When multiple AUVs are available for deployment, the challenge is how to facilitate efficient collaboration among them while effectively compensating for the nadir gap and avoiding collision. A comprehensive study on efficient exploration of the entire region using an arbitrary number of AUVs each with nadir gaps is lacking in the literature. Our thesis aims to fill this gap by proposing scalable path planning strategies that offer complete coverage while minimizing either the mission completion time or the total number of turns performed. Another challenge with the availability of multiple AUVs can be their unexpected failures. We take the first step towards addressing this challenge with two AUVs specifically and develop robust strategies which can handle the failure of a single AUV by effectively re-planning the path for the other (alive) AUV to obtain complete coverage. On the empirical front, we consider diverse input configurations based on real-world instances and provide extensive simulation results to validate the key properties of our strategies developed for single AUV, two AUV and multiple AUV scenarios. Further, we also show the maximal number of AUVs required that can be utilized fruitfully to achieve complete coverage for a given input (increasing the number of AUVs after this threshold doesn’t decrease the overall completion time) and how to compute it efficiently. We end with a discussion of our most effective strategies from which a practitioner can select the best strategy based on the use case.