Distributed Safety Verification for Multi-Agent Systems

The control barrier function (CBF) framework is a powerful tool for safe controller design and safety analysis. Given a dynamical system and a CBF, the system is safe if the CBF-induced constraints are satisfied for every state inside an invariant set, which is a subset of the safe set. In this paper we propose a safety verification algorithm for networked nonlinear multi-agent systems. In our proposed algorithm, we independently sample scenarios from the invariant set, and subsequently quantify safety for the multi-agent system by solving a scenario program in a distributed manner. Both the scenario sampling and safety verification algorithms are fully distributed. The efficacy of our algorithm is demonstrated by an example on multi-robot collision avoidance.