Collaborative Coverage Path Planning for AUV Formations: Dual-Layer PSO-Voronoi Partitioning for Time-Based Load Balancing Combined with BINN

In multi-AUV collaborative underwater coverage operations, the fundamental principle of load balancing is temporally rather than spatially defined. Traditional partition schemes that equalize area or grid counts suffer from a critical fallacy: they assume a linear mapping from geometry to working time, which collapses in the presence of irregular obstacles. This paper demonstrates that temporal load imbalance causes some AUVs to finish prematurely and remain idle—consuming power and fighting currents while their counterparts struggle with topologically complex sub-regions. To address this, we propose a dual-layer nested Particle Swarm Optimization (PSO) framework for Voronoi partitioning, where the outer layer coarsely initializes grid counts, while the inner layer directly minimizes the makespan and time variance derived from actual BINN-simulated coverage paths. This two-stage PSO architecture effectively resolves the nonlinear mismatch between geometric partitioning and real operation time, redefining load balancing from a geometrical abstraction to a temporally grounded, operationally relevant metric. Furthermore, we rigorously distinguish the intrinsic nature of coverage path planning (CPP) from Traveling Salesman Problem (TSP)-based point routing—the latter generates discontinuous, sharp-turning trajectories that violate the kinematic constraints of side-scan sonar payloads and cause critical data gaps. The proposed architecture yields a standard deviation of mission times that is an order of magnitude lower than area-based heuristics, while maintaining kinematically feasible continuous sweeps. Crucially, we explicitly delineate the operational boundary of this framework: it is purpose-built for static, pre-surveyed environments where offline computational overhead (approximately 8 min) is a justifiable investment against a 3 h optimal field execution.