Objective Programming Partitions and Rule-Based Spanning Tree for UAV Swarm Regional Coverage Path Planning
Bangrong Ruan, Jing Tian, Meigen Huang, Xi Ning, Jiarui Wang, Boquan Zhang, Fengyao Zhi · Drones · 2026
To address the problem of regional coverage path planning for unmanned aerial vehicle swarms (UAVs), this study proposes an algorithm based on objective programming partitions (OPP) and rule-based spanning tree coverage (RSTC). Aiming at the shortcomings of the traditional Divide Areas based on Robots Initial Positions combined with Spanning Tree Coverage (DARP-STC) algorithm in two core stages, that is, region partitions and spanning tree generation, the proposed algorithm conducts a targeted design and optimization, respectively. In the region partition stage, an objective programming and 0–1 integer programming model are adopted to realize the balanced allocation of UAVs’ task regions. In the spanning tree generation stage, a rule is designed to construct a spanning tree of coverage paths and is proven to achieve the minimum number of turns for the UAV under certain conditions. Both simulations and physical experiments demonstrate that the proposed algorithm can not only significantly reduce the number of turns of UAVs but also enhance the efficiency and coverage degree of tasks for UAV swarms.