A Coverage Path Planning Algorithm for Maritime Search and Rescue (SAR) Operations of Multiple Unmanned Aerial Vehicles (UAVs)

This study addresses a coverage path planning (CPP) problem for maritime search and rescue (SAR) operations of multiple unmanned aerial vehicles (UAVs). For a given search area, the problem is to determine the path of each UAV while visiting all the search regions for the objective of minimizing the longest UAV search time, i,e, maximum among the UAV search times. Due to the problem complexity, a heuristic algorithm is proposed that consists of two phases: (a) grid decomposition of search area; and (b) path determination. In the first phase, the search area is represented as a graph after decomposed into the squared grids with the same size in such a way that the one with the minimum number of grids is selected among those obtained by border lines and their perpendicular vectors. Then, using the graph, the second phase determines the UAV paths by two steps: (b.1) obtaining an initial path of each UAV using a greedy algorithm; and (b.2) balancing the allocations of the search regions to UAVs and improving the current paths by dynamic reallocations of search regions and path modifications using the ant colony optimization (ACO) algorithm. Computational experiments were done on real data, and the test results show that the two-phase algorithm proposed in this study gives more balanced allocations of search regions to UAVs and hence improves the previous algorithm significantly.