Semi-discrete Optimal Transport for Time-Varying Multi-Agent Coverage Control

Abstract

Coverage control algorithms have traditionally focused on static target densities, where agents optimally cover a fixed spatial distribution. However, many applications, such as environmental monitoring, surveillance, and adaptive sensing, involve time-varying densities. While time-varying coverage has been studied in Voronoi-based frameworks, extending recent optimal transport formulations of static coverage control to time-varying target densities remains an open problem. This paper presents a semi-discrete optimal transport framework for time-varying coverage control, in which agents track the first-order optimality conditions associated with minimizing the instantaneous Wasserstein distance from an evolving target density. The proposed approach is based on a coupled system of differential equations governing agent positions and the dual variables defining Laguerre regions. The resulting optimality residuals converge exponentially to zero, with global convergence established for one-dimensional domains. We also derive decentralized approximations and numerical simulations demonstrate improved tracking performance over quasi-static and Voronoi-based methods.

Keywords: Optimal Transport; Multi-Agent Systems; Coverage Control; Wasserstein Distance; Time-Varying Density; Autonomous Systems; Distributed Control