Finding Consensus Without Computation

Abstract

A canonical problem for swarms of agents is to collectively choose one of multiple options in their environment. We present a novel control strategy for solving this problem—the first to be free of arithmetic computation. The agents do not communicate with each other nor do they store run-time information. They have a line-of-sight sensor that extracts one ternary digit of information from the environment. At every time step, they directly map this information onto constant-value motor commands. We evaluate the control strategy with both simulated and physical e-puck robots. By default, the robots are expected to choose, and move to, one of two options of equal value. The simulation studies show that the strategy is robust against sensory noise, scalable to large swarm sizes, and generalizes to the problems of choosing between more than two options or between unequal options. The experiments— <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\text{50}$</tex-math></inline-formula> trials conducted with a group of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathbf{20}$</tex-math></inline-formula> e-puck robots—show that the group achieves consensus in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\text{96}\%$ </tex-math></inline-formula> of the trials. Given the extremely low hardware requirements of the strategy, it opens up new possibilities for the design of swarms of robots that are small in size ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf{\ll\text{10}^{-3}}$</tex-math></inline-formula> m) and large in numbers ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathbf{\gg \text{10}^3}$</tex-math></inline-formula> ).