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

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.