Multi-Area Path Planning for Multiple Unmanned Surface Vessels

To conduct marine surveys, multiple unmanned surface vessels (Multi-USV) with different capabilities perform collaborative mapping in multiple designated areas. This paper proposes a task allocation algorithm based on integer linear programming (ILP) with flow balance constraints, ensuring the fair and efficient distribution of sub-areas among USVs and maintaining strong connectivity of assigned regions. In the established grid map, a search-based path planning algorithm is performed on the sub-areas according to the allocation scheme. It uses the greedy algorithm and the A* algorithm to achieve complete coverage of the barrier-free area and obtain an efficient trajectory of each USV. The greedy algorithm enables fast local traversal of unvisited grids, while the A* algorithm ensures navigation to escape from deadlock areas and maintains global path continuity. The comparison of task allocation results proves that the task allocation algorithm based on ILP improves the mapping efficiency and task distribution fairness. The proposed allocation method and result analysis provide a certain reference for the practical application of Multi-USV to perform survey tasks collaboratively.