Energy-Budgeted UAV Swarm Coverage of Time-Varying Densities: Instantaneous Guarantees, Runtime Certificates, and What Downwash Costs Them

Persistent aerial monitoring asks a swarm of endurance-limited UAVs to keep its sensing where a moving importance density puts its mass, at every instant and under a hard battery budget. Existing guarantees fall into two camps: coverage control proves asymptotic convergence to a local optimum, with no approximation ratio and no energy constraint, while distributed submodular maximization gives regret bounds for agents committing one action per round, with no path budget. Neither tells an operator what a battery-feasible plan is worth now.

We present Distributed Budget-and-Locality-aware Greedy (DBLG), a planner in which each UAV commits a battery-feasible set of sorties from its own motion-primitive library using only local information, and we prove an instantaneous per-time-step constant-factor guarantee against the same-budget clairvoyant optimum. Because that worst-case factor is loose, DBLG also emits a distributed runtime certificate that bounds the optimality gap on each instance, averaging 0.96 of that optimum. Our sharpest theoretical result is a predictability dichotomy: for forecastable densities the guarantee holds uniformly in the drift rate, whereas for unpredictable ones we prove a tight, randomization-robust achievable ratio that degrades once the number of reachable configurations exceeds the swarm's covering capacity. The hard axis is predictability, not speed.

We then ask what physics costs these guarantees. The planner scales to 2000 agents while matching centralized greedy to three decimals, but an executed aerial rung with 6-DOF rotorcraft and inter-UAV downwash shows that the "locality is free" property breaks in dense formations, at an interaction range larger for every swarm beyond the smallest we flew, and surviving replacement of both the rigid-body engine and the controller. Extending to densities a swarm must find, an adversarial audit of our own search planner exposes two ways a distance-discounted planner silently stops moving. This is a theory-and-simulation study; the theorems are the contribution.