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

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.