Min-Punishment Sweep Coverage based Path Plan Algorithm for USV
Jun Wei, Dong Ding, Xianggen Meng · 2021 IEEE International Conference on Unmanned Systems (ICUS) · 2021
Scanning coverage problem of unmanned surface vehicles (USVs) is hot problem. Considering the cost of USVs, this paper proposes the minimum penalty scanning coverage problem and assigns a time penalty factor to each target point under limited number of sensors. The paper gives the resolution based on equal allocation strategy, branch-and-bound strategy and greedy strategy, respectively. As the branch-and-bound strategy has high time complexity and is not applicable to the case of large-scale target points, experiments of different scales are set up in this paper to compare the branch-and-bound algorithm, the greedy algorithm and the basic algorithm – equal allocation strategy, respectively. In the experiments, the penalty value of the greedy algorithm is only 3.26%, which is better than that of the branch-and-bound algorithm. The proposed method outperforms the equal allocation strategy on both small and large scale data.