Randomized Algorithms and Neural Networks for Communication-Free Multiagent Singleton Set Cover

Abstract

This paper considers how a system designer can program a team of autonomous agents to coordinate with one another such that each agent selects (or covers) an individual resource with the goal that all agents collectively cover the maximum number of resources. Specifically, we study how agents can formulate strategies without information about other agents’ actions so that system-level performance remains robust in the presence of communication failures. First, we use an algorithmic approach to study the scenario in which all agents lose the ability to communicate with one another, have a symmetric set of resources to choose from, and select actions independently according to a probability distribution over the resources. We show that the distribution that maximizes the expected system-level objective under this approach can be computed by solving a convex optimization problem, and we introduce a novel polynomial-time heuristic based on subset selection. Further, both of the methods are guaranteed to be within 1−1/e of the system’s optimal in expectation. Second, we use a learning-based approach to study how a system designer can employ neural networks to approximate optimal agent strategies in the presence of communication failures. The neural network, trained on system-level optimal outcomes obtained through brute-force enumeration, generates utility functions that enable agents to make decisions in a distributed manner. Empirical results indicate the neural network often outperforms greedy and randomized baseline algorithms. Collectively, these findings provide a broad study of optimal agent behavior and its impact on system-level performance when the information available to agents is extremely limited.