A Low-Complexity Path-Planning Algorithm for Multiple USVs in Task Planning Based on the Visibility Graph Method

Path planning for multiple unmanned surface vehicles (USVs) in task planning is a high-complexity problem. When the number of USVs is n, the computational complexity is usually as high as On2, as paths need to be planned from different start points to different target points. In this paper, we propose a low-complexity path-planning algorithm (LCPP) for multiple USVs based on the visibility graph method. First, all paths between the start points, target points, and obstacle vertices are separately planned with the low-complexity On. After that, the Dijkstra algorithm is employed to find the shortest path from each start point to all target points, also with the low-complexity On. To enhance the safety of each USV traveling along the edge of obstacles, the parameters of the adaptive line-of-sight (ALOS) guidance algorithm are optimized using the simulated annealing algorithm. The simulation results show that this algorithm outperforms others in calculation time when dealing with a large number of USVs.