Bi-Level Optimization for Multi-UAV Collaborative Coverage Path Planning in Irregular Areas

Source abstract

Multiple Unmanned Aerial Vehicle (UAV) collaborative coverage path planning is widely applied in fields such as regional surveillance. However, optimizing the trade-off between deployment costs and task execution efficiency remains challenging. To balance resource costs and execution efficiency with an uncertain number of UAVs, this paper analyzes the characteristics of irregular mission areas and formulates a bi-level optimization model for multi-UAV collaborative CPP. The model aims to minimize both the number of UAVs and the total path length. First, in the upper level, an improved Best Fit Decreasing algorithm based on binary search is designed. Straight-line scanning paths are generated by determining the minimum span direction of the irregular regions. Task allocation follows a longest-path-first, minimum-residual-range rule to rapidly determine the minimum number of UAVs required for complete coverage. Considering UAV’s turning radius constraints, Dubins curves are employed to plan transition paths between scanning regions, ensuring path feasibility. Second, the lower level transforms the problem into a Multiple Traveling Salesman Problem that considers path continuity, range constraints, and non-overlapping path allocation. This problem is solved using an Improved Biased Random Key Genetic Algorithm. The algorithm employs a variable-length master–slave chromosome encoding structure to adapt to the task allocation of each UAV. By integrating biased crossover operators with 2-opt interval mutation operators, the algorithm accelerates convergence and improves solution quality. Finally, comparative experiments on mission regions of varying scales demonstrate that, compared with single-level optimization and other intelligent algorithms, the proposed method reduces the required number of UAVs and shortens the total path length, while ensuring complete coverage of irregular regions. This method provides an efficient and practical solution for multi-UAV collaborative CPP in complex environments.