Safe Metropolis–Hastings algorithm and its application to swarm control ☆

Abstract This paper presents a new method to synthesize safe reversible Markov chains via extending the classical Metropolis–Hastings (M–H) algorithm. The classical M–H algorithm does not impose safety upper bound constraints on the probability vector, discrete probability density function, that evolves with the resulting Markov chain. This paper presents a new M–H algorithm for Markov chain synthesis that ensures such safety constraints together with reversibility and convergence to a desired stationary (steady-state) distribution. Specifically, we provide a convex synthesis method that incorporates the safety constraints via designing the proposal matrix for the M–H algorithm. It is shown that the M–H algorithm with this proposal matrix, safe M–H algorithm, ensures safety for a well-characterized convex set of stationary probability distributions, i.e., it is robustly safe with respect to this set of stationary distributions. The size of the safe set is then incorporated in the design problem to further enhance the robustness of the synthesized M–H proposal matrix. Numerical simulations are provided to demonstrate that multi-agent systems, swarms, can utilize the safe M–H algorithm to control the swarm density distribution. The controlled swarm density tracks time-varying desired distributions, while satisfying the safety constraints. Numerical simulations suggest that there is insignificant trade-off between the speed of convergence and the robustness.