A Blob Method for Mean Field Control With Terminal Constraints

Katy Craig, Karthik Elamvazhuthi, Harlin Lee

Abstract

In the present work, we develop a novel particle method for a general class of mean field control problems, with source and terminal constraints. Specific examples of the problems we consider include the dynamic formulation of the p-Wasserstein metric, optimal transport around an obstacle, and measure transport subject to acceleration controls. Unlike existing numerical approaches, our particle method is meshfree and does not require global knowledge of an underlying cost function or of the terminal constraint. A key feature of our approach is a novel way of enforcing the terminal constraint via a soft, nonlocal approximation, inspired by recent work on blob methods for diffusion equations. We prove convergence of our particle approximation to solutions of the continuum mean-field control problem in the sense of Gamma-convergence. A byproduct of our result is an extension of existing discrete-to-continuum convergence results for mean field control problems to more general state and measure costs, as arise when modeling transport around obstacles, and more general constraint sets, including controllable linear time invariant systems. Finally, we conclude by implementing our method numerically and using it to compute solutions the example problems discussed above. We conduct a detailed numerical investigation of the convergence properties of our method, as well as its behavior in sampling applications and for approximation of optimal transport maps.

Introduction

Mean Field Control (MFC) provides a mathematical framework for managing the collective behavior of large populations, such as swarms of drones, crowds of pedestrians, or clouds of data points. The objective is to transition a distribution of agents from an initial state to a target state while minimizing a cost functional, typically representing energy or time.

Traditionally, MFC problems are solved using Eulerian methods, which rely on fixed grids. However, these methods suffer from the "curse of dimensionality": as the number of dimensions increases, the computational requirements grow exponentially. Lagrangian, or particle-based, methods offer a meshfree alternative that avoids this scaling issue. However, Lagrangian methods often struggle with "terminal constraints"—the requirement that the final population distribution must exactly match a specific target. Enforcing these hard constraints in a discrete system is computationally expensive and often requires global knowledge of the target distribution.

The Blob Method Approach

This paper introduces a novel particle method that replaces "hard" terminal constraints with a "soft" nonlocal "blob" approximation. This approach allows for a scalable algorithm capable of navigating obstacles and handling complex dynamics like acceleration control.

Softening the Constraint

Instead of requiring the final particle distribution to exactly equal the target measure, the authors employ a penalty function. This function penalizes the $L^2$ distance between the final state and the target, transforming a constrained optimization problem into an unconstrained one that is easier to solve numerically.

Blob Regularization

To apply this penalty to discrete particles—which are mathematically represented as "spiky" Dirac masses—the method convolves the distributions with a smoothing kernel, or "mollifier." This turns each discrete particle into a "blob." This regularization allows the algorithm to calculate smooth gradients even when particles are far from their targets, facilitating the use of gradient-based optimization.

Discretization and Optimization

The continuous MFC problem is transformed into a system of $N$ particles governed by Ordinary Differential Equations (ODEs). The optimal trajectories for these particles are then found using gradient descent, implemented via modern auto-differentiation frameworks like PyTorch.

Theoretical Contributions and Convergence

A significant contribution of this work is the rigorous proof of $\Gamma$-convergence. The authors demonstrate that as the number of particles ($N$) increases and the blob size ($\delta$) decreases, the solution to the discrete particle problem converges to the true solution of the original continuous mean-field problem.

Furthermore, the theory is extended to handle "unbounded costs." This is particularly useful for modeling obstacles; by assigning an infinite cost to specific regions, the particles are forced to find optimal paths around them. The method is also flexible enough to accommodate Linear Time-Invariant (LTI) systems, allowing for the control of agents with momentum or other physical constraints.

Numerical Results

The method was validated through several synthetic numerical experiments, including transport between uniform squares, Gaussian distributions, and empirical measures.

  • Comparison with Standard Solvers: When compared against the Python Optimal Transport (POT) library, the Blob Method achieved nearly identical objective values. While POT solves the hard matching problem, the Blob Method provides the added benefit of smooth, continuous trajectories.
  • Obstacle Avoidance: In 2D simulations featuring circular obstacles, the particles successfully adjusted their trajectories to flow around the obstructions and converged efficiently to the target distribution.
  • Structured Sampling: An interesting emergent property was observed when moving particles toward a continuous Gaussian target: the particles "self-organized" into a highly regular structure. This suggests the method may be superior to standard i.i.d. sampling for certain numerical integration tasks.
  • Convergence Rates: Numerical tests confirmed that the error decreases as the particle count increases, following a rate consistent with theoretical expectations for particle-based methods (slightly slower than $O(1/N)$).

Limitations and Future Work

Despite its advantages, the method faces challenges related to the non-convexity of the loss landscape. Gradient descent can occasionally become trapped in local minima depending on particle initialization. Additionally, the performance of the algorithm is sensitive to the balancing of three hyperparameters: the number of particles ($N$), the penalty weight ($\epsilon$), and the blob size ($\delta$).

While the method is theoretically robust for high-dimensional spaces, current numerical validations have been focused on 1D and 2D scenarios. Future research will explore the limits of this approach in higher-dimensional settings (e.g., 10D or 100D) and seek more automated ways to tune the regularization parameters.

Summary updated

Abstract

In the present work, we develop a novel particle method for a general class of mean field control problems, with source and terminal constraints. Specific examples of the problems we consider include the dynamic formulation of the p-Wasserstein metric, optimal transport around an obstacle, and measure transport subject to acceleration controls. Unlike existing numerical approaches, our particle method is meshfree and does not require global knowledge of an underlying cost function or of the terminal constraint. A key feature of our approach is a novel way of enforcing the terminal constraint via a soft, nonlocal approximation, inspired by recent work on blob methods for diffusion equations. We prove convergence of our particle approximation to solutions of the continuum mean-field control problem in the sense of Gamma-convergence. A byproduct of our result is an extension of existing discrete-to-continuum convergence results for mean field control problems to more general state and measure costs, as arise when modeling transport around obstacles, and more general constraint sets, including controllable linear time invariant systems. Finally, we conclude by implementing our method numerically and using it to compute solutions the example problems discussed above. We conduct a detailed numerical investigation of the convergence properties of our method, as well as its behavior in sampling applications and for approximation of optimal transport maps.
BibTeX
@inproceedings{craig2025blob,
  author = {Katy Craig and Karthik Elamvazhuthi and Harlin Lee},
  title = {{A Blob Method for Mean Field Control With Terminal Constraints}},
  booktitle = {ESAIM},
  year = {2025},
  doi = {10.1051/cocv/2025010},
}
Figure