Optimizing Topologies for Probabilistically Secure Multi-Robot Systems

Abstract

In this paper, we optimize the interaction graph of a multi-robot system (MRS) by maximizing its probability of security while requiring the MRS to have the fewest edges possible. Edges that represent robot interactions exist according to a probability distribution and security is defined using the control theoretic notion of left invertibility. To compute an optimal solution to our problem, we first start by reducing our problem to a variation of the rooted k-connections problem using three graph transformations. Then, we apply a weighted matroid intersection algorithm (WMIA) on matroids defined on the edge set of the interaction graph. Although the optimal solution can be found in polynomial time, MRSs are dynamic and their topologies may change faster than the rate at which the optimal security solution can be found. To cope with dynamic behavior, we present two heuristics that relax optimality but execute with much lower time complexity. Finally, we validate our results through Monte Carlo simulations.