An Analysis of Random Peer-to-Peer Communication for System-Level Coordination in Decentralized Multiple-Robot Systems

Inter-robot communication is essential if general purpose intelligent decentralized multiple-robot systems are to become a reality. Traditionally, explicit communication amongst the robots of a MRS has been broadcasted or eliminated altogether. The limits of these two approaches prevent the widespread deployment of useful decentralized MRS. In this paper, we present and analyze, both analytically and empirically, a communication protocol that we call random peer-to-peer or RP2P. Using RP2P, a decentralized MRS can share state in logarithmic time with respect to system population. Additionally, the load placed upon the individual robots by RP2P is independent of system population size. Potential applications of random peer-to-peer communication also are provided, including state sharing, decision-making and task allocation