Task Planning and Optimization for Multi-Region Multi-UAV Cooperative Inspection

Highlights: What are the main findings? A new multi-region multi-UAV task and path planning model is proposed: the multiple traveling salesmen with neighborhoods problem (MTSPN) model, which integrates the multiple traveling salesmen problem (MTSP) with the traveling salesmen problem with neighborhoods (TSPN). A novel decoupled multi-region multi-UAV task and path planning framework has been designed: firstly, the KMGA algorithm—combining K-Means++ algorithm with the genetic algorithm—computes the sequence of task regions to be inspected for each UAV. Subsequently, a multi-neighborhood iterative dynamic programming (MNIDP) algorithm is proposed to solve the multi-neighborhood path planning problem for each UAV. What are the implications of the main finding? This work provides a new multi-UAV task and path planning model, which is solved based on the concept of decoupling. The proposed KMGA-MNIDP composite planning strategy could effectively address the multi-region multi-UAV task and path planning problems. To improve the efficiency of multi-region multi-unmanned aerial vehicle (UAV) inspection, this paper proposes a composite task planning strategy integrating the K-Means++ genetic algorithm (KMGA) and the multi-neighborhood iterative dynamic programming (MNIDP) method. Firstly, the multi-region multi-UAV inspection problem is modeled as a multiple traveling salesmen problem with neighborhoods (MTSPN). Then, this problem is decomposed into two interrelated subproblems to mitigate the complexity inherent in the solution process: that is, the multiple traveling salesmen problem (MTSP) and multi-neighborhoods path planning (MNPP) problem. Based on this decomposition, the MTSP is solved by the KMGA by converting it into m spatially non-overlapping traveling salesmen problems (TSPs) and then these TSPs are solved to obtain the approximate optimal visiting sequences for the nodes in each TSP in a short time. Subsequently, the MNPP can be efficiently solved by an MNIDP which plans the paths between the corresponding neighborhood of each node based on the node visiting sequences, thus obtaining the approximate optimal path length of the MTSPN. The simulation results demonstrate that the proposed composite strategy exhibits advantages in computational efficiency and optimal path length. Specifically, compared to the baseline algorithm, the average tour length obtained by the KMGA decreased by 23.24%. Meanwhile, the average path lengths computed by MNIDP in three instances were reduced from 8.00% to 11.41% and from 6.46% to 10.08% compared to two baseline algorithms, respectively. It provides an efficient task and path planning solution for multi-region multi-UAV operations in power transmission line inspections, thereby enhancing inspection efficiency.