Path planning algorithm to minimize an overlapped path and turning number for an underwater mining robot

This paper considers the problem of minimizing an overlapped path and turning number to cover an uneven terrain ocean floor for an underwater mining robot. The purpose of this algorithm is to generate the shortest path to travel through the entire given bathymetric map with minimum overlapping path and minimum turning number based on binary map, cell decomposition, minimal sum of altitude method and depth-first search algorithm. To do this task, the following tasks are performed. Firstly, a binary map is obtained by applying threshold to the high slope regions of the ocean floor. Secondly, Morse cell decomposition method is applied to divide the whole area of work space into cells in the vertical and horizontal directions. To minimize the turning number, a minimal sum of altitude method is applied to the combination of vertical and horizontal cell decompositions. Finally, the coverage order is calculated by depth-first search algorithm. The simulation result shows that the proposed method generates the short coverage path with minimum overlapping, minimum turning number and fast coverage time compared to vertical and horizontal cell decomposition methods.