Cooperative Decision-Making in Decentralized Multiple-Robot Systems: The Best-of-N Problem

Multiple-robot systems (MRS) that are decentrally organized have many benefits over centralized systems. Decentralized systems are less affected by computational and communicative bottlenecks, and they are more robust to the loss of individual member robots. System-level cognitive operations, though, are much more difficult to implement in decentralized systems. One example is the best-of-N decision-making problem, in which a team attempts to unanimously select a single alternative from a list that maximizes a given metric. This is a valuable operation, since many system-level operations can be expressed in this form. Optimal best-of-N decision-making, however, is intractable in large decentralized systems. The contribution of this paper is a biologically inspired algorithm that enables a decentralized MRS composed of very simple robots to make good, unanimous decisions. In a series of physical experiments using real robots, the best decision was made at least 80% of the time. In all, 100% of the decisions achieved perfect consensus, which prevented the MRS from becoming fragmented. The decisions are made using anonymous, local communication, with no direct comparisons of the available alternatives by the individual robots.