Complete Coverage Path Planning of UUV for Marine Mine Countermeasure Using Grid Division and Spanning Tree

In recent years, with the continuous improvement of the Unmanned Underwater Vehicle (UUV) systems, naval mine detection missions carried out by UUVs have proliferated and made significant progress. During the process of mine detection, the completeness and efficiency of path planning are critical to the effectiveness of the mission. This paper addresses an off-line and on-line path planning algorithm for UUV in a marine area with obstacles based on the rectangular grid division and spanning tree circumnavigation. In this algorithm, area to detect is equally divided into (2*M)*(2*N) rectangular cell and the UUV circumnavigates the spanning tree of the graph induced from the 2*2 mega cell division while visiting every 1*1 grid with minor backtracking. Simulation results show that the path generated by the algorithm is complete and efficient.