Sea Area Clearance

Many dangers still lurk in the waters of this world. We consider a (rectangular) open sea area which is filled with sea mines. While the density of the mines can be estimated, their exact locations are unknown. The goal is to evacuate the area by identifying and clearing all mines in the shortest possible time. The main tool for this task is a platform for mine hunting (mine counter-measure vessel, MCMV) which is supported by a number of identical AUVs (autonomous underwater vehicles) operating from this platform (i. e., they are deployed, recovered, recharged and data is analyzed).

We formulated this problem as a mixed-integer linear optimization problem with time discretization. In our model, the sea area is divided into several rectangular subareas which are assigned to the systems (MCMV and AUVs) on the time axis. The timing of certain actions (especially searching and clearing an area) must be taken into account - for example, the MCMV cannot enter uncleared territory at any time to protect the workers on board. An important decision is the fineness of the time discretization. Lots of small details (such as deploying and recovering AUVs or regular shift changes) must be taken into account. However, if the length of a time step is chosen too small, instances of the model become so large that they are practically not treatable even with modern hard- and software.

Industry Partner

Atlas Elektronik GmbH, Bremen