Distributed Knowledge Leader Selection for Multi-Robot Environmental Sampling

Abstract

In many multi-robot applications such as target search, environmental monitoring and reconnaissance, the multi-robot system operates semi-autonomously, but under the supervision of a remote human who monitors task progress. In these applications, each robot collects a large amount of task-specific data that must be sent to the human periodically to keep the human aware of task progress. It is often the case that the human-robot communication links are extremely bandwidth constrained and/or have significantly higher latency than inter-robot communication links, so it is impossible for all robots to send their task-specific data together. Thus, only a subset of robots, which we call the knowledge leaders, can send their data at a time. In this paper, we study the knowledge leader selection problem, where the goal is to select a subset of robots with a given cardinality that transmits the most informative task-specific data for the human. We prove that the knowledge leader selection problem is a submodular optimization problem under some explicit conditions. We also present a novel distributed submodular optimization algorithm that has the same approximation guarantees as the centralized greedy algorithm for submodular function maximization. The effectiveness of our approach is demonstrated using numerical simulations.