Rapid MRTA in Large UAV Swarms Based on Topological Graph Construction in Obstacle Environments

Highlights: What are the main findings? A regional partitioning method for obstacle environments is proposed based on Topological Graph Construction (TGC). A heuristic two-stage MRTA approach for UAV swarms is developed using the constructed topological graph. What is the implication of the main finding? The proposed method constructs a topological graph of the obstacle environment to achieve a more reasonable partition, maintaining solution quality and yielding computation speeds over 60 times faster than the baseline. By considering path planning in obstacle environments, the method is better suited for real-world physical scenarios and is well-equipped for further generation of UAV flight paths. In large-scale Unmanned Aerial Vehicle (UAV) and task environments—particularly those involving obstacles—dimensional explosion remains a significant challenge in Multi-Robot Task Allocation (MRTA). To this end, a novel heuristic MRTA framework based on Topological Graph Construction (TGC) is proposed. First, the physical map is transformed into a pixel map, from which a Generalized Voronoi Graph (GVG) is generated by extracting clearance points, which is then used to construct the topological graph of the obstacle environment. Next, the affiliations of UAVs and tasks within the topological graph are determined to partition different topological regions, and the task value of each topological node is calculated, followed by the first-phase Task Allocation (TA) on these topological nodes. Finally, UAVs within the same topological region with their allocated tasks perform a local second-phase TA and generate the final TA result. The simulation experiments analyze the influence of different pixel resolutions on the performance of the proposed method. Subsequently, robustness experiments under localization noise, path cost noise, and communication delays demonstrate that the total benefit achieved by the proposed method remains relatively stable, while the computational time is moderately affected. Moreover, comparative experiments and statistical analyses were conducted against k-means clustering-based MRTA methods in different UAV, task, and obstacle scale environments. The results show that the proposed method improves computational speed while maintaining solution quality, with the PI-based method achieving speedups of over 60 times and the CBBA-based method over 10 times compared with the baseline method.