This paper develops a new approach to direct a set of heterogeneous agents, varying in mobility and sensing capabilities, to quickly cover a large region, say for example in the search for victims after a large-scale disaster. Given that time is of the essence, we seek to mitigate computational complexity, which normally grows exponentially as the number of agents increases. We create a new framework which reduces the planning complexity through simultaneously decomposing a target domain into sub-regions, and assigning a team of agents to each sub-region in the target domain, as a way to decompose a large-scale problem into a set of smaller problems. The teams are formed to optimize the coverage of each sub-regions. Doing so requires both the utilization of individual agents’ strengths as well as their collaborative capabilities. We determine the ideal team by introducing a novel evolution-guided generative model based on generative adversarial networks (GANs) that creates allocation plans from the sub-region features in a computationally efficient manner. We validate our framework on a real-world satellite images dataset, and demonstrate that through decomposition and generative allocation, our method has significantly better efficiency and efficacy compared to current centralized multi-robot coverage methods, and is therefore better suited for large-scale time-critical deployment.