Collective Decision with 100 Kilobots

Speed vs Accuracy in Binary Discrimination Problems

Gabriele Valentini,¹ Eliseo Ferrante,² Heiko Hamann,³ and Marco Dorigo¹ (2015)

¹IRIDIA, Université Libre de Bruxelles, Belgium
²Laboratory of Socioecology and Social Evolution, KU Leuven, Leuven, Belgium
³Department of Computer Science, University of Paderborn, Paderborn, Germany

Abstract

Achieving fast and accurate collective decisions with a large number of simple agents without relying on a central planning unit or on global communication is essential for developing complex collective behaviors. In this paper, we investigate the speed versus accuracy trade-off in collective decision-making in the context of a binary discrimination problem—i.e., how a swarm can collectively determine the best of two options. We describe a novel, fully distributed collective decision-making strategy that only requires agents with minimal capabilities and is faster than previous approaches. We evaluate our strategy experimentally, using a swarm of 100 Kilobots, and we study it theoretically, using both continuum and finite-size models. We find that the main factor affecting the speed versus accuracy trade-off of our strategy is the agents neighborhood size—i.e., the number of agents with whom the current opinion of each agent is shared. The proposed strategy and the associated theoretical framework can be used to design swarms that take collective decisions at a given level of speed and/or accuracy.

Keywords: collective decision-making; swarm robotics; majority rule; voter model; self-organization; ordinary differential equations; chemical reaction network; Gillespie algorithm; Kilobot;

Introductory video

The following video provides an explanatory introduction to the robot experiments performed in the main paper. This video, titled Self-organized collective decisions in a robot swarm, has been previously published as part of the video proceedings of the 29th AAAI Conference on Artificial Intelligence.

HD video recording of a robot experiment

The following video is a high definition version of one experimental run performed with 100 Kilobots. In this experiment, an individual robot applies the majority rule over a maximum number of 24 neighbors (i.e., maximum group size of 25). The speed of the video is 30x faster than real time.

Video recordings of all robot experiments

Video recordings of all the robot experiments performed for the main paper. Video recordings are organized by maximum group size. The speed of all videos is 30x faster than real time.

First setting: maximum group size 5

Second setting: maximum group size 25

Stability analysis

This pdf contains the results of the stability analysis performed for the ODE model. The Mathematica notebook can be downloaded here.