Probabilistic Resilience of Dynamic Multi-Robot Systems

Abstract

In this letter, we aim to calculate the probability that a dynamic multi-robot system (MRS) satisfies the conditions of (r,s)-robustness, given that robot communication is subject to random failures that can be modeled using a probability distribution. The property of (r,s)-robustness is a topological property used to quantify the resilience of a multi-robot system against misbehaving robots. In the presence of random communication failures, which are typical of real-world deployments, we argue it is important to calculate the probability that an MRS will be resilient at a given time instance. To this end, we begin by enumerating edge sets that represent the conditions of (r,s)-robustness. Then, we use a tree structure known as a binary decision diagram (BDD) to efficiently encode the (r,s)-robustness conditions into a graphical form. This approach allows us to calculate the exact probability of resilience, as well as to derive bounds which are less computationally expensive to compute. To demonstrate the validity of our results, we track the probability of resilience of an MRS performing a collaborative task.