Collective decision-making algorithm for the best-of-n problem in multiple options
The best-of-n problem [Valentini G, Ferrante E, Dorigo M. The best-of-n problem in robot swarms: formalization, state of the art, and novel perspectives. Frontiers in Robotics and AI. 2017;4(9):1–18.] is a collective decision-making problem in which many robots (agents) select the best option among...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2022-06-01
|
| Series: | SICE Journal of Control, Measurement, and System Integration |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1080/18824889.2022.2077588 |
| _version_ | 1797661060352704512 |
|---|---|
| author | Masao Kubo Hiroshi Sato Nhuhai Phung Akihiro Yamaguchi |
| author_facet | Masao Kubo Hiroshi Sato Nhuhai Phung Akihiro Yamaguchi |
| author_sort | Masao Kubo |
| collection | DOAJ |
| description | The best-of-n problem [Valentini G, Ferrante E, Dorigo M. The best-of-n problem in robot swarms: formalization, state of the art, and novel perspectives. Frontiers in Robotics and AI. 2017;4(9):1–18.] is a collective decision-making problem in which many robots (agents) select the best option among a set of n alternatives and is focused on the field of distributed autonomous robotic systems and swarm robotics. It is desirable to develop a collective decision-making algorithm that can work even when there are a lot of social–behavioural alternatives (n>2) to realize an intelligent system that can solve more complicated problems. However, previous studies mainly focused on binary collective decision-making scenarios (n = 2). In this paper, we propose a collective decision-making algorithm for the best-of-n problem with a large number of options by using short-term experience memory with a trial and error approach at the group level. After proposing this decision-making process, we show typical behaviour. Next, we show the convergence of this algorithm when a quadratic function is used for the bias corresponding to the individual characteristic. Next, the bias distribution proposed shows that an equilibrium point where all candidates have the same number of supports is unstable, and consensus states are a stable fixed point. Therefore, dynamics is expected to converge towards a consensus. Simulation results and mathematical analysis show that the average time required to find the best option is nearly proportional to the number of options and does not depend on the number of robots. |
| first_indexed | 2024-03-11T18:39:50Z |
| format | Article |
| id | doaj.art-6e7f7e0d8f4a4b8d88ba5906b73883bd |
| institution | Directory Open Access Journal |
| issn | 1884-9970 |
| language | English |
| last_indexed | 2024-03-11T18:39:50Z |
| publishDate | 2022-06-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | SICE Journal of Control, Measurement, and System Integration |
| spelling | doaj.art-6e7f7e0d8f4a4b8d88ba5906b73883bd2023-10-12T13:43:52ZengTaylor & Francis GroupSICE Journal of Control, Measurement, and System Integration1884-99702022-06-01152718810.1080/18824889.2022.20775882077588Collective decision-making algorithm for the best-of-n problem in multiple optionsMasao Kubo0Hiroshi Sato1Nhuhai Phung2Akihiro Yamaguchi3National Defense Academy of JapanNational Defense Academy of JapanMilitary Institute of Information TechnologyFukuoka Institute of TechnologyThe best-of-n problem [Valentini G, Ferrante E, Dorigo M. The best-of-n problem in robot swarms: formalization, state of the art, and novel perspectives. Frontiers in Robotics and AI. 2017;4(9):1–18.] is a collective decision-making problem in which many robots (agents) select the best option among a set of n alternatives and is focused on the field of distributed autonomous robotic systems and swarm robotics. It is desirable to develop a collective decision-making algorithm that can work even when there are a lot of social–behavioural alternatives (n>2) to realize an intelligent system that can solve more complicated problems. However, previous studies mainly focused on binary collective decision-making scenarios (n = 2). In this paper, we propose a collective decision-making algorithm for the best-of-n problem with a large number of options by using short-term experience memory with a trial and error approach at the group level. After proposing this decision-making process, we show typical behaviour. Next, we show the convergence of this algorithm when a quadratic function is used for the bias corresponding to the individual characteristic. Next, the bias distribution proposed shows that an equilibrium point where all candidates have the same number of supports is unstable, and consensus states are a stable fixed point. Therefore, dynamics is expected to converge towards a consensus. Simulation results and mathematical analysis show that the average time required to find the best option is nearly proportional to the number of options and does not depend on the number of robots.http://dx.doi.org/10.1080/18824889.2022.2077588collective intelligencemulti-agent systemsthe best-of-n problem |
| spellingShingle | Masao Kubo Hiroshi Sato Nhuhai Phung Akihiro Yamaguchi Collective decision-making algorithm for the best-of-n problem in multiple options SICE Journal of Control, Measurement, and System Integration collective intelligence multi-agent systems the best-of-n problem |
| title | Collective decision-making algorithm for the best-of-n problem in multiple options |
| title_full | Collective decision-making algorithm for the best-of-n problem in multiple options |
| title_fullStr | Collective decision-making algorithm for the best-of-n problem in multiple options |
| title_full_unstemmed | Collective decision-making algorithm for the best-of-n problem in multiple options |
| title_short | Collective decision-making algorithm for the best-of-n problem in multiple options |
| title_sort | collective decision making algorithm for the best of n problem in multiple options |
| topic | collective intelligence multi-agent systems the best-of-n problem |
| url | http://dx.doi.org/10.1080/18824889.2022.2077588 |
| work_keys_str_mv | AT masaokubo collectivedecisionmakingalgorithmforthebestofnprobleminmultipleoptions AT hiroshisato collectivedecisionmakingalgorithmforthebestofnprobleminmultipleoptions AT nhuhaiphung collectivedecisionmakingalgorithmforthebestofnprobleminmultipleoptions AT akihiroyamaguchi collectivedecisionmakingalgorithmforthebestofnprobleminmultipleoptions |