Combining Meta-heuristics and K-Means++ for Solving Unmanned Surface Vessels Task Assignment and Path Planning Problems

This study addresses Unmanned Surface Vessels (USVs) task assignment and path planning problems with minimizing the maximum completion time of USVs. First, a mathematical model is developed for the concerned problems. Second, an unsupervised learning algorithm, K-Means++, is employed to assign multi-tasks to USVs. According to the assignment results, five meta-heuristics are used to solve path planning problems for USVs. Finally, experiments are executed to solve 10 cases with different scales. The effectiveness of K-Means++ for task assignment is verified. The results of five meta-heuristics for path planning are reported and analyzed. The harmony search algorithm has the strongest competitiveness among all compared algorithms for solving the concerned problems.