Exact and heuristic algorithms for multi-robot system routing, oriented to underwater monitoring. ​

The exploration of the underwater environment has always been a relevant field for science and technology, to enlarge our knowledge of this mainly unexplored environment. In this work, we apply a vehicle routing optimization method for underwater exploration and monitoring based on a fleet of small autonomous underwater vehicles (AUVs). We assume a coarse-grained map is already available from satellite measurements and the set of robots is used to get detailed information on sea bottom features. We provide exact and heuristic linear programming methods for finding both the optimal starting position and path planning for a fleet of drones. To obtain a realistic model useful in real applications, we enhance our formulation by imposing connectivity constraints among the AUVs. Lastly, we present a use case application for coral reef monitoring with real data taken by Abu Dhabi environmental authorities.