The best-of-n problem in robot swarms: Formalization, state of the art, and novel perspectives

Gabriele Valentini; Eliseo Ferrante; Marco Dorigo

doi:10.3389/frobt.2017.00009

The best-of-n problem in robot swarms: Formalization, state of the art, and novel perspectives

Gabriele Valentini^*, Eliseo Ferrante, Marco Dorigo

^*Corresponding author for this work

Research output: Contribution to Journal › Review article › Academic › peer-review

Abstract

The ability to collectively choose the best among a finite set of alternatives is a fundamental cognitive skill for robot swarms. In this paper, we propose a formal definition of the best-of-n problem and a taxonomy that details its possible variants. Based on this taxonomy, we analyze the swarm robotics literature focusing on the decision-making problem dealt with by the swarm. We find that, so far, the literature has primarily focused on certain variants of the best-of-n problem, while other variants have been the subject of only a few isolated studies. Additionally, we consider a second taxonomy about the design methodologies used to develop collective decision-making strategies. Based on this second taxonomy, we provide an in-depth survey of the literature that details the strategies proposed so far and discusses the advantages and disadvantages of current design methodologies.

Original language	English
Article number	9
Journal	Frontiers Robotics AI
Volume	4
Issue number	MAR
DOIs	https://doi.org/10.3389/frobt.2017.00009
Publication status	Published - 1 Mar 2017
Externally published	Yes

Funding

The authors thank S. Garnier, G. Mermoud, and T. Schmickl for giving the permission to reproduce Figures 4B, 5A and 6. This work was partially supported by the European Research Council through the ERC Advanced Grant "E-SWARM: Engineering Swarm Intelligence Systems" (contract 246939) to MD. GV acknowledges support from the National Science Foundation (grant 1505048). EF acknowledges support from the Fund for Scientific Research (FWO) Flanders (grant 12N7515N), the DIVINA Challenge Team framework of the Labex MS2T program, supported by the French Government through the program "Investments for the future" and managed by the National Agency for Research (Reference ANR-11-IDEX-0004-02), and the European Regional Development Fund (ERDF) of the Regional Council of Hauts de France. MD acknowledges support from the Belgian F.R.S.-FNRS, of which he is a Research Director.

Funders	Funder number
Seventh Framework Programme	246939
National Science Foundation	1505048

Keywords

Best-of-n problem
Collective decision-making
Consensus achievement
Self-organization
Swarm robotics

Access to Document

10.3389/frobt.2017.00009

Persistent URL (handle)

Persistent link

Cite this

@article{e08b1b0a74cc4163846d62b8bbc529f0,

title = "The best-of-n problem in robot swarms: Formalization, state of the art, and novel perspectives",

abstract = "The ability to collectively choose the best among a finite set of alternatives is a fundamental cognitive skill for robot swarms. In this paper, we propose a formal definition of the best-of-n problem and a taxonomy that details its possible variants. Based on this taxonomy, we analyze the swarm robotics literature focusing on the decision-making problem dealt with by the swarm. We find that, so far, the literature has primarily focused on certain variants of the best-of-n problem, while other variants have been the subject of only a few isolated studies. Additionally, we consider a second taxonomy about the design methodologies used to develop collective decision-making strategies. Based on this second taxonomy, we provide an in-depth survey of the literature that details the strategies proposed so far and discusses the advantages and disadvantages of current design methodologies.",

keywords = "Best-of-n problem, Collective decision-making, Consensus achievement, Self-organization, Swarm robotics",

author = "Gabriele Valentini and Eliseo Ferrante and Marco Dorigo",

year = "2017",

month = mar,

day = "1",

doi = "10.3389/frobt.2017.00009",

language = "English",

volume = "4",

journal = "Frontiers Robotics AI",

issn = "2296-9144",

publisher = "Frontiers Media SA",

number = "MAR",

}

TY - JOUR

T1 - The best-of-n problem in robot swarms

T2 - Formalization, state of the art, and novel perspectives

AU - Valentini, Gabriele

AU - Ferrante, Eliseo

AU - Dorigo, Marco

PY - 2017/3/1

Y1 - 2017/3/1

N2 - The ability to collectively choose the best among a finite set of alternatives is a fundamental cognitive skill for robot swarms. In this paper, we propose a formal definition of the best-of-n problem and a taxonomy that details its possible variants. Based on this taxonomy, we analyze the swarm robotics literature focusing on the decision-making problem dealt with by the swarm. We find that, so far, the literature has primarily focused on certain variants of the best-of-n problem, while other variants have been the subject of only a few isolated studies. Additionally, we consider a second taxonomy about the design methodologies used to develop collective decision-making strategies. Based on this second taxonomy, we provide an in-depth survey of the literature that details the strategies proposed so far and discusses the advantages and disadvantages of current design methodologies.

AB - The ability to collectively choose the best among a finite set of alternatives is a fundamental cognitive skill for robot swarms. In this paper, we propose a formal definition of the best-of-n problem and a taxonomy that details its possible variants. Based on this taxonomy, we analyze the swarm robotics literature focusing on the decision-making problem dealt with by the swarm. We find that, so far, the literature has primarily focused on certain variants of the best-of-n problem, while other variants have been the subject of only a few isolated studies. Additionally, we consider a second taxonomy about the design methodologies used to develop collective decision-making strategies. Based on this second taxonomy, we provide an in-depth survey of the literature that details the strategies proposed so far and discusses the advantages and disadvantages of current design methodologies.

KW - Best-of-n problem

KW - Collective decision-making

KW - Consensus achievement

KW - Self-organization

KW - Swarm robotics

UR - http://www.scopus.com/inward/record.url?scp=85055332768&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85055332768&partnerID=8YFLogxK

U2 - 10.3389/frobt.2017.00009

DO - 10.3389/frobt.2017.00009

M3 - Review article

AN - SCOPUS:85055332768

SN - 2296-9144

VL - 4

JO - Frontiers Robotics AI

JF - Frontiers Robotics AI

IS - MAR

M1 - 9

ER -

The best-of-n problem in robot swarms: Formalization, state of the art, and novel perspectives

Abstract

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this