Coverage path planning for multiple unmanned aerial vehicles in maritime search and rescue operations

The number of casualties in the maritime sector is increasing consistently. To reduce the scope of search area extensions in the event of a maritime accident, maritime authorities and operation centers are currently trying to develop a quick search for survivors at sea using unmanned aerial vehicles (UAVs) in maritime search and rescue (SAR) operations. Here, we propose a two-phase method for solving the coverage path planning (CPP) problem of multiple-UAV areas in maritime SAR. In phase 1, we propose a grid-based area decomposition method that minimizes the decomposed search area to transform the search area into a graph made up of vertices and edges. In phase 2, we formulate a mixed-integer linear programming (MILP) model to derive an optimal coverage path that minimizes the completion time. To solve the model for large-scale instances, a randomized search heuristic (RSH) algorithm is developed. We conducted extensive numerical experiments to validate the performance of the algorithm. Experimental results show that the RSH yields a better solution with an approximately 0.7% optimality gap within a much shorter computation time than that of a commercial solver. In addition, our grid-based CPP algorithm outperforms those used in previous research with respect to the solution quality. Furthermore, we showed the results of real flight experiments in the marine field using the proposed algorithm.