An Approximation Algorithm for Distributed Resilient Submodular Maximization: Extended Abstract

摘要

We study a distributed coordination problem in which a group of robots collaborates to maximize a submodular objective function. We consider an adversarial scenario where a subset of the robots can be attacked and cannot contribute to the objective function. We do not know which robots will be attacked, but know an upper bound of how many can be attacked. We study the distributed version of the problem, where each robot must choose its own actions only by communicating with its neighbors. We present a distributed resilient submodular maximization algorithm that guarantees performance within a constant factor of the optimal. Our analysis uses the curvature of submodular set functions. We show that the algorithm is scalable, runs in polynomial time, and is faster than its centralized version. We demonstrate the efficacy of our algorithm through simulations of a multi-robot target tracking scenario.