Replanning paths in emergencies is essential for the successful completion of coverage tasks. In this context, this study specifically focuses on centralized path replanning for multiple autonomous underwater vehicles (AUVs) equipped with side-scan sonar, aiming to efficiently allocate uncovered regions and plan optimal paths for covering these assigned areas. The issue is formulated as a customized multi-robot multi-regional coverage path planning (M \( ^{2} \) CPP) problem. Taking account of the limited AUV energies, vulnerable imaging quality and paths’ structure, this study proposes a novel lawn-mower and cooperative co-evolution (LMCC) method. First, the lawnmower method is adopted to determine the intra-region paths as well as the entrance and exit locations of each region. Then, a customized cooperative co-evolution method is proposed to solve optimal region assignment, visiting order, and entrance positions. Additionally, a novel and simple population division strategy is designed for coding the area assignment results efficiently. According to simulation results, the LMCC method can balance AUV workloads and generate optimal paths based on positions and energies. In addition, fewer paths connect different regions to ensure that there is an adequate supply of energy to cover them which is an innovation abstracted from real task scenarios.
