Open Access

ARTICLE

Multi-Area Path Planning for Multiple Unmanned Surface Vessels

Jianing Wu¹, Yufeng Chen^1,*, Li Yin¹, Huajun He², Panshuan Jin²

1 Institute of Systems Engineering, Macau University of Science and Technology, Macau, 999078, China
2 Guangzhou Jiafan Computer Co., Ltd., Room 601, Building A8, No. 11 Kaiyuan Avenue, Huangpu District, Guangzhou, 510000, China

* Corresponding Author: Yufeng Chen. Email:

(This article belongs to the Special Issue: Intelligent Perception, Decision-making and Security Control for Unmanned Systems in Complex Environments)

Computers, Materials & Continua 2026, 87(1), 44 https://doi.org/10.32604/cmc.2025.072937

Received 07 September 2025; Accepted 24 November 2025; Issue published 10 February 2026

Abstract

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.

---

Keywords

---