PaperlayerView exact revision on arXiv

Source-linked AI summary

Entropy-Regularized Optimal Transport for Time-Varying Multi-Agent Coverage Control

Italo Napolitano, Mario di Bernardo

arXiv:2609.09829v1eess.SYcs.SYmath.OC

TL;DR

The paper addresses how to steer a finite set of agents toward a possibly time-varying target density without prescribing individual target positions. It uses entropy-regularized semi-discrete optimal transport to derive smooth density-tracking control, with exponential tracking and numerical performance comparable to the unregularized approach at moderate regularization while outperforming Voronoi-based coverage.

  • Problem

    Coverage specified by a collective target density avoids prescribing individual agent positions, but unregularized semi-discrete transport uses moving Laguerre-cell boundaries that complicate sensitivities and nonsmooth closed-loop analysis.

    Source: §I · p. 1

  • Method

    The paper formulates time-varying density tracking for finite-agent systems as entropy-regularized semi-discrete optimal transport, replacing hard partitions with smooth transport weights.

    Source: §I · p. 1

  • Results

    For moderate regularization, the approach has comparable performance to the unregularized method [13] and outperforms Voronoi-based coverage, while tracking the evolving optimality conditions exponentially and making the collapsed configuration locally optimal above a threshold.

    Source: §IV · p. 4, §VI · p. 6

  • Takeaways & Limitations

    Positive soft assignments make masses, barycenters, and sensitivities continuously differentiable, removing the need for Laguerre-cell construction and geometric regularity assumptions.

    Source: §IV · p. 4

    The paper focuses on the centralized setting.

    Source: §I · p. 1

Abstract

from arXiv · show

This paper addresses time-varying coverage control for multi-agent systems, formulated as the tracking of an evolving target density via entropy-regularized semi-discrete optimal transport. Unlike the hard Laguerre partition of the unregularized formulation, entropic regularization assigns fractions of the mass at each point to all agents, simplifying the design and numerical implementation of the control law. We derive a feedback-feedforward controller that tracks the evolving first-order optimality conditions with exponential convergence, and we investigate the role of the regularization parameter, which, above a critical threshold, renders the fully collapsed configuration locally optimal. Numerical experiments validate the theory: for moderate regularization, the proposed approach has performance comparable to the unregularized formulation and outperforms the corresponding Voronoi-based coverage baseline.

I. INTRODUCTION

The paper frames time-varying coverage as tracking a target density rather than assigning each agent an individual target position. It uses entropic regularization to smooth semi-discrete transport assignments and support continuous-time control design.

I. INTRODUCTION

  • The proposed formulation steers the agents’ empirical measure toward a possibly time-varying target density without prescribing individual target positions.The target is specified at a collective or probabilistic level,.Source: §I · p. 1
  • Wasserstein distance incorporates domain geometry and compares discrete agent distributions directly with continuous target densities.The paper retains finite-dimensional agent dynamics and formulates the problem through semi-discrete optimal transport.Source: §I · p. 1
  • The earlier unregularized formulation [13] uses moving Laguerre-cell boundaries, which complicate sensitivities and nonsmooth closed-loop analysis.It also requires geometric regularity assumptions.Source: §I · p. 1
  • Entropic regularization replaces hard Laguerre assignments with smooth transport weights, facilitating smooth continuous-time feedback laws for density tracking.The regularization parameter trades fidelity to the original Wasserstein problem against smoothness of the induced allocation.Source: §I · p. 1

II. MATHEMATICAL PRELIMINARIES

The preliminaries establish notation for vectors, matrices, probability measures, and Wasserstein distances. They also specify the transport value associated with the half-squared Euclidean cost.

II. MATHEMATICAL PRELIMINARIES

  • Scalars use lowercase, vectors bold lowercase, and matrices bold uppercase; λmax(A) denotes the maximum eigenvalue.The notation also defines vec(·), the identity matrix, zero and one matrices, the Kronecker product, and δij.Source: §II · p. 2
  • P2(Rd) denotes Borel probability measures on Rd with finite second moment, and Wp(·, ·) denotes the p-Wasserstein distance..Source: §II · p. 2
  • W2^2 is the transport value associated with the half-squared Euclidean cost..Source: §II · p. 2

A. Semi-Discrete Optimal Transport

Semi-discrete optimal transport compares a discrete agent measure with an absolutely continuous target measure. Its dual formulation is associated with Laguerre cells, which generalize Voronoi cells through additive weights.

A. Semi-Discrete Optimal Transport

B. Entropic Regularization

Entropic regularization smooths the semi-discrete transport problem by replacing hard Laguerre assignments with fractional assignments. As the regularization vanishes, the hard partition is recovered under stated uniqueness and positive-mass conditions.

B. Entropic Regularization

  • Entropic regularization smooths the transport problem and typically reduces the computational burden of classical optimal transport..Source: B. Entropic Regularization · p. 2
  • The regularized coupling is induced by the soft Laguerre assignments Πi(x)ρ̄(x)dx.Π is the vector of soft Laguerre assignments.Source: B. Entropic Regularization · p. 2
  • Each point x is fractionally assigned to all discrete atoms through a softmax distribution, rather than belonging to a single Laguerre cell.The discrete atom cost is ci = 1/2∥x−pi∥2².Source: B. Entropic Regularization · p. 2
  • As ε → 0, the hard Laguerre partition is recovered when the limiting assignment is unique almost everywhere and its cells have positive mass..Source: B. Entropic Regularization · p. 2

C. Coverage Control

Coverage control places agents according to a target density; this section contrasts Voronoi and Laguerre partitions and explains the added analytical complexity of the earlier unregularized approach.

C. Coverage Control

  • Laguerre partitions use dual variables ϕ to enforce equal-mass constraints, unlike Voronoi partitions, and reduce finite-agent approximation error.They also concentrate agents in high-density areas.Source: C. Coverage Control · p. 2
  • The prior unregularized method tracked first-order conditions pi = bi and ai = 1/N for a time-varying target density.It minimized the semi-discrete squared 2-Wasserstein distance.Source: C. Coverage Control · p. 2
  • Its moving Laguerre-cell integral sensitivities involve facet integrals and change with adjacency, requiring nondegenerate cells, moving-boundary formulas, and a nonsmooth solution concept.The proposed entropic framework avoids these requirements.Source: C. Coverage Control · p. 2

III. MODELING AND PROBLEM STATEMENT

The problem is to control a finite ensemble of agents to approximate a possibly time-varying target distribution. The objective is to minimize instantaneous entropic semi-discrete transport cost between the target and empirical measures.

III. MODELING AND PROBLEM STATEMENT

  • The stated aim is to approximate a continuous, possibly time-varying distribution by minimizing instantaneous entropic semi-discrete transport cost.The control objective builds on the authors’ earlier formulation.Source: §III · p. 2
  • The target density is positive, has unit mass, and is defined on a convex compact domain; it may vary over time.The density is C1 and Lipschitz in time, ensuring that its time derivative exists.Source: §III · pp. 2–3
  • The ensemble contains N agents whose positions evolve according to the control inputs ui(t).The agent measure is the normalized sum of Dirac delta measures centered at their positions.Source: §III · p. 3
  • The control objective is to minimize the mismatch between the target measure and the agents’ empirical measure at each time.The controller assumes access to the target density and its time derivative.Source: §III · p. 3
  • The instantaneous Wasserstein minimization with entropy regularization is distinct from dynamic OT in the Benamou-Brenier formulation.The cost uses regularization parameter ε > 0 and F ε given by (3).Source: §III · p. 3

IV. ENTROPIC COVERAGE CONTROL

The proposed primal-dual dynamics exponentially track the evolving first-order optimality conditions. Entropic regularization smooths the coverage formulation, but introduces a parameter-dependent approximation bias and can make collapse locally optimal.

IV. ENTROPIC COVERAGE CONTROL

  • Fixing the dual gauge with ϕN = 0, the primal-dual dynamics track time-varying conditions; because the outer minimization is nonconvex, the design targets stationary points.The soft assignment gives every agent positive mass at every point, yielding regularized masses and barycenters.Source: §IV · p. 3
  • When (Mε)^−1 is well defined, the control dynamics exponentially track the first-order optimality conditions (10), with position and mass errors converging to zero at rates Kx and Kϕ, respectively.The closed loop is forward complete: its solutions exist for all t ≥ 0 without finite escape.Source: §IV · p. 4
  • Positive soft assignments keep masses, barycenters, and sensitivities smooth at every configuration, simplifying implementation but making Mε generally dense.Smooth integral sensitivities can be evaluated with vectorizable quadrature and softmax operations, without constructing Laguerre cells or evaluating facet integrals.Source: §IV · pp. 3–4
  • 0 ≤ W^2_{2,ε}(p,t) − W^2_2(p,t) ≤ ε log N uniformly in p and t.The bound quantifies the regularized transport-cost gap relative to the unregularized cost.Source: §IV · p. 4
  • The collapsed configuration is a strict local minimum when ε > λmax(Σ), and a saddle point when ε < λmax(Σ).The proposition classifies full collapse at the target distribution’s global barycenter.Source: §IV · p. 4
  • Choosing ε below λmax(Σ(t)) for all t rules out neither partial clustering nor agent collisions.Collision-free trajectories are not guaranteed, and characterizing partial collapses or enforcing collision constraints is left for future work.Source: §IV · pp. 4–5

V. NUMERICAL VALIDATION

Numerical experiments validate time-varying density tracking and show how regularization controls agent spread and approximation error. For tested ε ≤ 3, the entropic controller is more accurate than the Voronoi-based approach.

V. NUMERICAL VALIDATION

  • In the two-dimensional advection-diffusion experiment, agents redistribute with the drifting density and spread as it diffuses.Mass and position errors decay exponentially; W2 first decreases rapidly, then grows linearly as target variance and finite-agent quantization error increase.Source: §V · p. 5
  • At ε = 0.1, agents remain distinct; at ε = 6, three central agents coincide; at ε = 10 > 9, all coincide at the target barycenter.As ε increases, normalized ensemble spread falls to zero near the critical threshold, while normalized W2 rises to approximately 3 after full collapse.Source: §V · p. 5, Figure 2 · p. 6
  • For tested ε ≤ 3, the entropic controller remains more accurate than the Voronoi-based approach.The table compares Voronoi, unregularized OT, and proposed solutions for representative ε values.Source: §V · p. 6, Table I · p. 6
  • Across the experiments, the suboptimality gap W2^2,ε − W2^2 stays below the ε log N upper bound.At a collapsed configuration, the regularized optimal coupling has zero KL divergence.Source: §V · p. 6

VI. CONCLUSION

The paper introduces entropy-regularized OT for time-varying multi-agent coverage and derives a controller that tracks evolving first-order optimality conditions exponentially. Experiments show comparable performance to unregularized OT for moderate regularization and better performance than Voronoi-based coverage.

VI. CONCLUSION

  • The framework applies entropy-regularized optimal transport to time-varying coverage control and multi-agent density tracking.The smooth assignment supports a control law that exponentially tracks evolving first-order optimality conditions.Source: §VI · p. 6
  • For moderate regularization, experiments show performance comparable to unregularized OT [13] and better than Voronoi-based coverage.An explicit threshold is identified above which the collapsed configuration becomes locally optimal.Source: §VI · p. 6
  • Future work includes distributed implementations, adaptive ε selection, constrained dynamics, collision avoidance, and conditions ensuring Mε invertibility.Source: §VI · p. 6
Loading 2609.09829v1…