Handling state uncertainty in distributed information leader selection for robotic swarms

In many scenarios involving human interaction with a remote swarm, the human operator needs to be periodically updated with state information from the robotic swarm. A complete representation of swarm state is high dimensional and perceptually inaccessible to the human. Thus, a summary representation is often required. In addition, it is often the case that the human-swarm communication channel is extremely bandwidth constrained and may have high latency. This motivates the need for the swarm itself to compute a summary representation of its own state for transmission to the human operator. The summary representation may be generated by selecting a subset of robots, known as the information leaders, whose own states suffice to give a bounded approximation of the entire swarm, even in the presence of uncertainty. In this paper, we propose two fully distributed asynchronous algorithms for information leader selection that only rely on inter-robot local communication. In particular, by representing noisy robot states as error ellipsoids with tunable confidence level, the information leaders are selected such that the Minimum-Volume Covering Ellipsoid (MVCE) summarizes the noisy swarm state boundary. We provide bounded optimality analysis and proof of convergence for the algorithms. We present simulation results demonstrating the performance and effectiveness of the proposed algorithms.