Policy methods improve safety guarantees for finite agent groups
Policy Synthesis for Finite Populations of MDP Agents under Aggregate Reach-Avoid Chance Constraints
Multiagent Systems
Summary
When controlling many agents like robots or electric vehicles working together, it’s important to make sure enough of them reach their goals while keeping unsafe situations rare. The authors find that typical methods, which work well when there are infinitely many agents, don’t handle randomness well in smaller groups. They develop a method that tracks not only the average behavior but also how much the group’s behavior can vary. This lets them create safer control policies that better guarantee outcomes for finite numbers of agents.
What this means in practice
- •For power grid operators: Manage aggregated electric vehicle charging to ensure safety and performance constraints reliably hold with finite fleets.
- •For robotics fleet managers: Design feedback control policies that probabilistically guarantee a high fraction of robots safely reach goals in uncertain environments.
Authors
Jie Fu, Anamika Dubey
Abstract
Consider a finite population of agents with decoupled Markov transition dynamics and empirical-density feedback, subject to the following constraints: with probability at least $1-δ_r$, at least a fraction $α_r$ of agents must reach a target region at some time $t^*$, while, at each time up to $t^*$, the unsafe population fraction must remain below $β_u$ with probability at least $1-δ_u$. However, standard mean-field methods enforce these constraints only in expectation, which fails to account for stochastic fluctuations at finite fleet size $N$. To address this control problem, we propagate the second-order moment (variance) of the empirical density alongside the mean-field trajectory via a discrete-time Lyapunov recursion, and apply the Cantelli inequality to convert chance constraints into tractable deterministic conditions on the moments of the empirical density. We then incorporate these moment-based surrogate constraints into a gradient-based sequential convex approximation procedure for density-feedback policy synthesis. We further introduce additional moment-error bounds to construct a rigorous finite-$N$ certificate. The method is evaluated on a gridworld environment and a power-system EV-charging aggregation problem and compared with a standard deterministic population-level LP baseline.