nach oben

Swarm Intelligence

07.03.2024

The effect of uneven and obstructed site layouts in best-of-N

verfasst von: Jennifer Leaf, Julie A. Adams

Erschienen in: Swarm Intelligence

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Biologically inspired collective decision-making algorithms show promise for implementing spatially distributed searching tasks with robotic systems. One example is the best-of-N problem in which a collective must search an environment for an unknown number of sites and select the best option. Real-world robotic deployments must achieve acceptable success rates and execution times across a wide variety of environmental conditions, a property known as resilience. Existing experiments for the best-of-N problem have not explicitly examined how the site layout affects a collective’s performance and resilience. Two novel resilience metrics are used to compare algorithmic performance and resilience between evenly distributed, obstructed, or unobstructed uneven site configurations. Obstructing the highest valued site negatively affected selection accuracy for both algorithms, while uneven site distribution had no effect on either algorithm’s resilience. The results also illuminate the distinction between absolute resilience as measured against an objective standard, and relative resilience used to compare an algorithm’s performance across different operating conditions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Allen, C. R., Gunderson, L., & Johnson, A. R. (2005). The use of discontinuities and functional groups to assess relative resilience in complex systems. Ecosystems, 8(8), 958–966. https://doi.org/10.2307/25053891CrossRef

Angeler, D. G., Allen, C. R., Rojo, C., Alvarez-Cobelas, M., Rodrigo, M. A., & Sánchez-Carrillo, S. (2013). Inferring the relative resilience of alternative states. PLoS ONE, 8(10), e77338. https://doi.org/10.1371/journal.pone.0077338ADSCrossRefPubMedCentralPubMed

Bayındır, L. (2016). A review of swarm robotics tasks. Neurocomputing, 172, 292–321. https://doi.org/10.1016/J.NEUCOM.2015.05.116CrossRef

Bruneau, M., Chang, S. E., Eguchi, R. T., Lee, G. C., O’Rourke, T. D., Reinhorn, A. M., Shinozuka, M., Tierney, K., Wallace, W. A., & Von Winterfeldt, D. (2003). A framework to quantitatively assess and enhance the seismic resilience of communities. Earthquake Spectra, 19(4), 733–752. https://doi.org/10.1193/1.1623497CrossRef

Canciani, F., Talamali, M. S., Marshall, J. A. R., Bose, T., & Reina, A. (2019). Keep calm and vote on: Swarm resiliency in collective decision making. In Proceedings of workshop resilient robot teams of the IEEE international conference on robotics and automation.

Codling, E. A., Plank, M. J., & Benhamou, S. (2008). Random walk models in biology. Journal of The Royal Society Interface, 5(25), 813–834. https://doi.org/10.1098/rsif.2008.0014CrossRefPubMedCentralPubMed

Cody, J. R. (2018). Discrete Consensus Decisions in Human-Collective Teams. PhD thesis, Vanderbilt University.

Cody, J. R., & Adams, J. A. (2017). An evaluation of quorum sensing mechanisms in collective value-sensitive site selection. In International symposium on multi-robot and multi-agent systems (pp. 40–47). https://doi.org/10.1109/MRS.2017.8250929

Cody, J. R., Roundtree, K. A., & Adams, J. A. (2021). Human-collective collaborative target selection. ACM Transactions on Human-Robot Interaction, 10(2), 1–29. https://doi.org/10.1145/3442679CrossRef

Franks, N. R., Hardcastle, K. A., Collins, S., Smith, F. D., Sullivan, K. M., Robinson, E. J., & Sendova-Franks, A. B. (2008). Can ant colonies choose a far-and-away better nest over an in-the-way poor one? Animal Behaviour, 76(2), 323–334. https://doi.org/10.1016/j.anbehav.2008.02.009CrossRef

Gordon, D. M. (2014). The ecology of collective behavior. PLoS Biology, 12(3), e1001805. https://doi.org/10.1371/journal.pbio.1001805CrossRefPubMedCentralPubMed

Gordon, D. M. (2016). The evolution of the algorithms for collective behavior. Cell Systems, 3(6), 514–520. https://doi.org/10.1016/j.cels.2016.10.013ADSCrossRefPubMed

Hamann, H., & Wörn, H. (2008). A framework of space-time continuous models for algorithm design in swarm robotics. Swarm Intelligence, 2, 209–239. https://doi.org/10.1007/s11721-008-0015-3CrossRef

Henry, D., & Emmanuel Ramirez-Marquez, J. (2012). Generic metrics and quantitative approaches for system resilience as a function of time. Reliability Engineering & System Safety, 99, 114–122. https://doi.org/10.1016/J.RESS.2011.09.002CrossRef

Hodgson, D., McDonald, J. L., & Hosken, D. J. (2015). What do you mean, ‘resilient’? Trends in Ecology & Evolution, 30(9), 503–506. https://doi.org/10.1016/J.TREE.2015.06.010CrossRef

Hosseini, S., Barker, K., & Ramirez-Marquez, J. E. (2016). A review of definitions and measures of system resilience. Reliability Engineering and System Safety, 145, 47–61. https://doi.org/10.1016/j.ress.2015.08.006CrossRef

Ingrisch, J., & Bahn, M. (2018). Towards a comparable quantification of resilience. Trends in Ecology & Evolution, 33(4), 251–259. https://doi.org/10.1016/J.TREE.2018.01.013CrossRef

Jain, P., & Goodrich, M. A. (2022). Processes for a colony solving the best-of-N problem using a bipartite graph representation. In M. Yamamoto, F. Matsuno, & S. Azuma (Eds.), Distributed autonomous robotic (pp. 376–388). Systems, Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-92790-5_29CrossRef

Janson, S., Middendorf, M., & Beekman, M. (2007). Searching for a new home—Scouting behavior of honeybee swarms. Behavioral Ecology, 18(2), 384–392. https://doi.org/10.1093/beheco/arl095CrossRef

Krotkov, E., Hackett, D., Jackel, L., Perschbacher, M., Pippine, J., Strauss, J., Pratt, G., & Orlowski, C. (2017). The DARPA robotics challenge finals: Results and perspectives. Journal of Field Robotics, 34(2), 229–240. https://doi.org/10.1002/rob.21683CrossRef

Laomettachit, T., Termsaithong, T., Sae-Tang, A., & Duangphakdee, O. (2015). Decision-making in honeybee swarms based on quality and distance information of candidate nest sites. Journal of Theoretical Biology, 364, 21–30. https://doi.org/10.1016/j.jtbi.2014.09.005ADSMathSciNetCrossRefPubMed

Leaf, J., & Adams, J. A. (2022). Measuring resilience in collective robotic algorithms. In: Proceedings of the international conference on autonomous agents and multiagent systems (pp. 1666–1668).

Lerman, K., & Galstyan, A. (2002). Mathematical model of foraging in a group of robots: Effect of interference. Autonomous Robots, 13, 127–141.CrossRef

Lu, Q., Hecker, J. P., & Moses, M. E. (2016). The MPFA: A multiple-place foraging algorithm for biologically-inspired robot swarms. In: IEEE/RSJ international conference on intelligent robots and systems (pp. 3815–3821). https://doi.org/10.1109/IROS.2016.7759561

Pais, D., Hogan, P. M., Schlegel, T., Franks, N. R., Leonard, N. E., & Marshall, J. A. (2013). A mechanism for value-sensitive decision-making. PLoS ONE, 8(9), e73216. https://doi.org/10.1371/journal.pone.0073216ADSCrossRefPubMedCentralPubMed

Parker, C., & Zhang, Hong. (2009). Cooperative decision-making in decentralized multiple-robot systems: The best-of-N problem. IEEE/ASME Transactions on Mechatronics, 14(2), 240–251. https://doi.org/10.1109/TMECH.2009.2014370CrossRef

Prasetyo, J., De Masi, G., Ranjan, P., & Ferrante, E., et al. (2018). The best-of-n problem with dynamic site qualities: Achieving adaptability with stubborn individuals. In M. Dorigo, M. Birattari, & C. Blum (Eds.), Swarm intelligence (pp. 239–251). Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-00533-7_19CrossRef

Prasetyo, J., De Masi, G., & Ferrante, E. (2019). Collective decision making in dynamic environments. Swarm Intelligence, 13(3–4), 217–243. https://doi.org/10.1007/s11721-019-00169-8CrossRef

Prasetyo, J., De Masi. G., Tuci. E., & Ferrante, E. (2020). The effect of differential quality and differential zealotry in the best-of-n problem. In Proceedings of the genetic and evolutionary computation conference companion (pp. 65–66). https://doi.org/10.1145/3377929.3390053

Pratt, S. C., Sumpter, D. J., Mallon, E. B., & Franks, N. R. (2005). An agent-based model of collective nest choice by the ant Temnothorax albipennis. Animal Behaviour, 70(5), 1023–1036. https://doi.org/10.1016/j.anbehav.2005.01.022CrossRef

Reina, A., Miletitch, R., Dorigo, M., & Trianni, V. (2015). A quantitative micro-macro link for collective decisions: The shortest path discovery/selection example. Swarm Intelligence, 9(2–3), 75–102. https://doi.org/10.1007/s11721-015-0105-yCrossRef

Reina, A., Valentini, G., Fernández-Oto, C., Dorigo, M., & Trianni, V. (2015). A design pattern for decentralised decision making. PLOS ONE, 10(10), e0140950. https://doi.org/10.1371/journal.pone.0140950CrossRefPubMedCentralPubMed

Reina, A., Bose, T., Trianni, V., & Marshall, J. A. (2018). Effects of spatiality on value-sensitive decisions made by robot swarms. In R. Groß, A. Kolling, & S. Berman (Eds.), Distributed autonomous robotic systems (pp. 461–473). Springer International Publishing. https://doi.org/10.1007/978-3-319-73008-0_32CrossRef

Rothman, K. J., Greenland, S., & Lash, T. L. (2008). Modern epidemiology (3rd ed.). Wolters Kluwer Health.

Şahin, E. (2004). Swarm robotics: From sources of inspiration to domains of application. In: International workshop on swarm robotics (pp 10–20). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-540-30552-1_2

Schaerf, T. M., Makinson, J. C., Myerscough, M. R., & Beekman, M. (2013). Do small swarms have an advantage when house hunting? The effect of swarm size on nest-site selection by Apis mellifera. Journal of the Royal Society Interface, 10(20130), 533. https://doi.org/10.1098/rsif.2013.0533CrossRef

Seeley, T. D. (1995). The wisdom of the hive: The social physiology of honey bee colonies. Harvard University Press.

Seeley, T. D. (2010). Honeybee democracy. Princeton University Press.

Seeley, T. D., & Buhrman, S. C. (2001). Nest-site selection in honey bees: How well do swarms implement the “best-of-N’’ decision rule? Behavioral Ecology and Sociobiology, 49(5), 416–427. https://doi.org/10.1007/s002650000299CrossRef

Seeley, T. D., Visscher, P. K., Schlegel, Thomas, et al. (2012). Stop signals provide cross inhibition in collective decision-making by honeybee swarms. Science, 335, 108–111. https://doi.org/10.1177/002204260603600304ADSCrossRefPubMed

Sumpter, D. J. T. (2010). Collective animal behavior. Princeton University Press.

Talamali, M. S., Marshall, J. A., Bose, T., & Reina, A., (2019). Improving collective decision accuracy via time-varying cross-inhibition. In: International conference on robotics and automation (pp. 9652–9659). https://doi.org/10.1109/ICRA.2019.8794284

Talamali, M. S., Bose, T., Haire, M., Xu, X., Marshall, J. A., & Reina, A. (2020). Sophisticated collective foraging with minimalist agents: A swarm robotics test. Swarm Intelligence, 14(1), 25–56. https://doi.org/10.1007/s11721-019-00176-9CrossRef

Valentini, G., Ferrante, E., Hamann, H., & Dorigo, M. (2016). Collective decision with 100 Kilobots: Speed versus accuracy in binary discrimination problems. Autonomous Agents and Multi-Agent Systems, 30(3), 553–580. https://doi.org/10.1007/s10458-015-9323-3CrossRef

Valentini, G., Ferrante, E., & Dorigo, M. (2017). The best-of-n problem in robot swarms: Formalization, state of the art, and novel perspectives. Frontiers in Robotics and AI, 4, 9. https://doi.org/10.3389/frobt.2017.00009CrossRef

Valentini, G., Moore D. G., Hanson, J. R., Pavlic, T. P., Pratt, S. C., & Walker, S. I. (2020). Transfer of information in collective decisions by artificial agents. In Conference on Artificial Life (pp. 641–648). https://doi.org/10.1162/isal_a_00117

Van Riemsdijk, M. B., Dastani, M., & Winikoff, M. (2008). Goals in agent systems: a unifying framework. In Proceedings of the international joint conference on autonomous agents and multiagent systems (pp 702–709)

Woods, D. D., & Branlat. M. (2011). Basic patterns in how adaptive systems fail. In Resilience engineering in practice (pp. 127–144). Farnham, UK, Ashgate. https://doi.org/10.1201/9781317065265-10

Yang, G. Z., Bellingham, J., Dupont, P. E., Fischer, P., Floridi, L., Full, R., Jacobstein, N., Kumar, V., McNutt, M., Merrifield, R., & Nelson, B. J. (2018). The grand challenges of Science Robotics. Science Robotics. https://doi.org/10.1126/scirobotics.aar7650CrossRefPubMed

Zobel, C. W. (2010). Representing perceived tradeoffs in defining disaster resilience. Decision Support Systems, 50, 394–403. https://doi.org/10.1016/j.dss.2010.10.001CrossRef

Titel: The effect of uneven and obstructed site layouts in best-of-N
verfasst von: Jennifer Leaf
Julie A. Adams
Publikationsdatum: 07.03.2024
Verlag: Springer US
Erschienen in: Swarm Intelligence
Print ISSN: 1935-3812
Elektronische ISSN: 1935-3820
DOI: https://doi.org/10.1007/s11721-024-00236-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Premium Partner