The Best-of-n Problem in Robot Swarms: Formalization, State of the Art, and Novel Perspectives
Open accessThe DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Consensus and Cooperation in Networked Multi-Agent Systems
Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2006.887293 · Cited by 10,522 · cited 2×
“For example, the selection of a common direction of motion by a swarm of agents flocking in a two-or three-dimensional space (Reynolds, 1987; Olfati-Saber et al., 2007) is a continuous problem.”
BackgroundFlocks, herds and schools: A distributed behavioral model
Reynolds, C. W. (1987) · ACM SIGGRAPH Computer Graphics · doi:10.1145/37402.37406 · Cited by 5,148
Statistical physics of social dynamics
Castellano, C., Fortunato, S., & Loreto, V. (2009) · Reviews of Modern Physics · doi:10.1103/revmodphys.81.591 · Cited by 4,119
Self-Organization in Biological Systems
Sneyd, J., Theraula, G., Bonabeau, E., Deneubourg, J.-L., & Franks, N. R. (2001) · doi:10.1515/9780691212920 · Cited by 2,949
Vicsek, T., & Zafeiris, A. (2012) · Physics Reports · doi:10.1016/j.physrep.2012.03.004 · Cited by 2,923
Graph Theoretic Methods in Multiagent Networks
Mesbahi, M., & Egerstedt, M. (2010) · Princeton University Press eBooks · doi:10.1515/9781400835355 · Cited by 2,897 · cited 1×
“The community of control theory has intensively studied the problem of consensus achievement (Mesbahi and Egerstedt, 2010) with the objective of deriving optimal control strategies and proves their stability.”
BackgroundDistributed Consensus in Multi-vehicle Cooperative Control
Ren, W., & Beard, R. W. (2008) · Communications and Control Engineering · doi:10.1007/978-1-84800-015-5 · Cited by 2,826
The Complexity of Decentralized Control of Markov Decision Processes
Bernstein, D. S., Givan, R., Immerman, N., & Zilberstein, S. (2002) · Mathematics of Operations Research · doi:10.1287/moor.27.4.819.297 · Cited by 1,192
The group as a polarizer of attitudes.
Moscovici, S., & Zavalloni, M. (1969) · Journal of Personality and Social Psychology · doi:10.1037/h0027568 · Cited by 1,038 · cited 1×
“This phenomenon is widespread across natural and artificial systems and is studied in a number of different disciplines including psychology (Moscovici and Zavalloni, 1969; Hirokawa and Poole, 1996), biology (Camazine et al., 2001; Conradt and List, 2009; Couzin et al., 2011), and physics (Galam,…”
BackgroundSumpter, D. J. T. (2010) · doi:10.1515/9781400837106 · Cited by 914
Cited by
Swarm Robotics: Past, Present, and Future [Point of View]
Dorigo, M., Theraulaz, G., & Trianni, V. (2021) · Proceedings of the IEEE · doi:10.1109/jproc.2021.3072740 · Cited by 431
“literature is beyond the scope of this perspective (but see [42]–[46]).”
BackgroundSelf-citationStrobel, V., Castelló Ferrer, E., & Dorigo, M. (2018) · International Joint Conference on Autonomous Agents and Multiagent Systems · doi:10.65109/nlel1871 · Cited by 149
Self-citationStrobel, V., Castelló Ferrer, E., & Dorigo, M. (2020) · Frontiers in Robotics and AI · doi:10.3389/frobt.2020.00054 · Cited by 127
“Consensus Achievement Consensus achievement problems in robot swarms can be divided into discrete and continuous problems (Valentini et al., 2017).”
BackgroundSelf-citationMean-field models in swarm robotics: a survey
Elamvazhuthi, K., & Berman, S. (2019) · Bioinspiration & Biomimetics · doi:10.1088/1748-3190/ab49a4 · Cited by 110
Kilogrid: a novel experimental environment for the Kilobot robot
Valentini, G., Antoun, A., Trabattoni, M., Wiandt, B., Tamura, Y., Hocquard, E., Trianni, V., & Dorigo, M. (2018) · Swarm Intelligence · doi:10.1007/s11721-018-0155-z · Cited by 52
Self-citationAutomatic Design of Collective Behaviors for Robots that Can Display and Perceive Colors
Garzón Ramos, D., & Birattari, M. (2020) · Applied Sciences · doi:10.3390/app10134654 · Cited by 26
“FORAGING is an abstraction of a foraging task, in a best-of-n fashion [63]—similar to the experiment of Valentini et al.”
ResultFormation Control of UAVs and Mobile Robots Using Self-organized Communication Topologies
Zhu, W., Allwright, M., Heinrich, M. K., Oğuz, S., Christensen, A. L., & Dorigo, M. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-60376-2_25 · Cited by 25
Self-citationFinding Consensus Without Computation
Ozdemir, A., Gauci, M., Bonnet, S., & Gros, R. (2018) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2018.2795640 · Cited by 22
Metadata
- Authors
- Valentini, G., Ferrante, E., & Dorigo, M.
- Venue
- Frontiers in Robotics and AI
- Publisher
- Frontiers Media SA
- Published
- 2017-03-13
- Volume
- 4
- ISSN
- 2296-9144 (ISSN-L)
- OpenAlex
- W2590885566
- Cited by
- 194
- References
- 18
- FWCI
- 13.29
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.