A Global Coverage Path Planning Method for Multi-UAV Maritime Surveillance in Complex Obstacle Environments

The study of unmanned aerial vehicle (UAV) coverage path planning is of great significance for ensuring maritime situational awareness and monitoring. In response to the problem of maritime multi-region coverage surveillance in complex obstacle environments, this paper proposes a global path planning method capable of simultaneously addressing the multiple traveling salesman problem, coverage path planning problem, and obstacle avoidance problem. Firstly, a multiple traveling salesmen problem–coverage path planning (MTSP-CPP) model with the objective of minimizing the maximum task completion time is constructed. Secondly, a method for calculating obstacle-avoidance path costs based on the Voronoi diagram is proposed, laying the foundation for obtaining the optimal access order. Thirdly, an improved discrete grey wolf optimizer (IDGWO) algorithm integrated with variable neighborhood search (VNS) operations is proposed to perform task assignment for multiple UAVs and achieve workload balancing. Finally, based on dynamic programming, the coverage path points of the area are solved precisely to generate the globally coverage path. Through simulation experiments with scenarios of varying scales, the effectiveness and superiority of the proposed method are validated. The experimental results demonstrate that this method can effectively solve MTSP-CPP in complex obstacle environments.