Probabilistic Graph Security for Networked Multi-Robot Systems

Abstract

In this paper, we develop a method for determining the probability of a multi-robot system (MRS) being secure when robot interactions are modeled as a probabilistic graph. To define the security of an MRS, we apply an existing control-theoretic notion of network attacks based on the left invertibility of a dynamical system. We then extend previous work by assuming probabilistic robot communication and sensing, modeling the effects of noise, failure, or adversarial influence on interactions in the network. The probabilistic graph security problem can then be seen as a variant of problems solved in the field of system reliability. This interpretation motivates the application of an efficient graphical representation of boolean functions known as binary decision diagrams (BDDs). Specifically, we use the canonical properties of a special type of BDD, the Reduced Order BDD, to generate a tree that can be efficiently traversed to compute the probability that a networked MRS is left invertible, and thus, secure. We then show how our adopted approach can be applied to systems that have interactions that change over time, e.g., for mobile multi-robot teams. Finally, we demonstrate the validity of our method by simulating a mobile MRS performing a rendezvous objective, while tracking its probability of security over time.