Efficient collective search by BRT algorithm using fast rising threshold agent
133 viewsDOI:
https://doi.org/10.54939/1859-1043.j.mst.CSCE5.2021.102-108Keywords:
Best-of-n problem, BRT algorithm, Swarm robotics, Collective decision-making.Abstract
The BRT algorithm is a method for the best-of-n problem that allows a group of distributed robots to find out the most appropriate collective option among many alternatives. Computer experiments show that the time required for finding out the best option is proportional to the number of options. In this paper, we aim to shorten this search time by introducing a few agents whose threshold increases faster than the normal one to achieve higher scalability of the BRT algorithm. The results show that the search time is reduced, and the variance is improved, especially under challenging problems where robots are required to make decisions out of a large number of options.
References
[1]. G. Valentini, E. Ferrante and M. Dorigo, “The Best-of-n Problem in Robot Swarms: Formalization, State of the Art, and Novel Perspectives”, Frontiers in Robotics and AI, Vol. 9, no. 9, pp. 1-18, 2017.
[2]. J. Wessnitzer and C. Melhuish, “Collective Decision-Making and Behaviour Transitions in Distributed Ad Hoc Wireless Networks of Mobile Robots: Target-Hunting”, in Advances in Artificial Life. ECAL 2003, Lecture Notes in Computer Science (W. Banzhaf, J. Ziegler, T. Christaller, P. Dittrich, and J. T. Kim, eds.), Vol. 2801, pp. 893–902, 2003.
[3]. S. Garnier, F. Tache, M. Combe, A. Grimal, and G. Theraulaz, “Alice in pheromone land: an experimental setup for the study of ant-like robots”, Proceeding of 2007 IEEE Swarm Intelligence Symposium, pp. 37-44, 2007.
[4]. A. Scheidler, A. Brutschy, E. Ferrante, and M. Dorigo, “The k- Unanimity Rule for Self-Organized Decision Making in Swarms of Robots”, IEEE Transactions on Cybernetics, Vol. 46, no. 4, pp. 1175-1188, 2016.
[5]. S. Garnier, J. Gautrais, M. Asadpour, C. Jost, and G. Theraulaz, “Selforganized aggregation triggers collective decision making in a group of cockroach- like robots,” Adapt. Behav, Vol. 17, pp. 109–133, 2009.
[6]. H. Hamann, T. Schmickl, H. Wörn, and K. Crailsheim, “Analysis of emergent symmetry breaking in collective decision making”, Neural Comput. Appl, vol. 21, pp. 207–218, 2012.
[7]. A. Okubo, “Dynamical aspects of animal grouping: swarms, schools, flocks, and herds”, Adv. Biophys. Vol. 22, pp. 1–94, 1986.
[8]. D. J. T. Sumpter, “Collective Animal Behavior. Princeton”, NJ: Princeton University Press, 2010.
[9]. A. Reina, G. Valentini, C. Fernandez-Oto, M. Dorigo, V. Trianni, “A design pattern for decentralised decision-making”, PloS One 10 (10), 2015.
[10]. A. Reina, J. A. R. Marshall, V. Trianni, T. Bose, “Model of the best-of-N nest-site selection process in honeybees”, Physical Review E, Vol. 95, 2017.
[11]. E. Hasegawa, N. Mizumoto, K. Kobayashi, S. Dobata, J. Yoshimura, S. Watanabe, Y. Murakami, K Matsuura, “Nature of collective decision-making by simple yes/no decision units”, Scientific Reports, Vol. 7, no. 14436, 2017.
[12]. N. H. Phung, M. Kubo, and H. Sato, “Agreement algorithm with trial and error method at macro level”, Artificial life and robotics, Vol. 23, no. 4, pp. 564–570, 2018.
[13]. S. Iwanaga and A. Namatame, “The complexity of collective decision”, Nonlinear Dynamics, Psychology and Life Sciences, Vol. 6, no. 2, pp. 137–158, 2002.
[14]. D. Charbonneau, C. Poff, H. Nguyen, M. C. Shin, K. Kiestead and A. Dornhaus, “Who Are the “Lazy” Ants? The Function of Inactivity in Social Insects and a Possible Role of Constraint: Inactive Ants Are Corpulent and May Be Young and/or Selfish”, Vol. 57, no. 3, pp. 649-667, 2017
[15]. E. Bonabeau, G. Theraulaz and J. Deneubourg, “Fixed response thresholds and the regulation of division of labor in insect societies”, Vol. 60, pp. 753-807, 1998.
[16]. N. H. Phung, M. Kubo, and H. Sato, “Efficient searching by bias and raising threshold algorithm using multiple voting in the best-of-n problem”, Vol. 11, no. 3, pp. 39-45, 2019.
