Abstract
In decentralised autonomous systems it is the interactions between individual agents which govern the collective behaviours of the system. These local-level interactions are themselves often governed by an underlying network structure. These networks are particularly important for collective learning and decision-making whereby agents must gather evidence from their environment and propagate this information to other agents in the system. Models for collective behaviours may often rely upon the assumption of total connectivity between agents to provide effective information sharing within the system, but this assumption may be ill-advised. In this paper we investigate the impact that the underlying network has on performance in the context of collective learning. Through simulations we study small-world networks with varying levels of connectivity and randomness and conclude that totally-connected networks result in higher average error when compared to networks with less connectivity. Furthermore, we show that networks of high regularity outperform networks with increasing levels of random connectivity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Balenzuela, P., Pinasco, J.P., Semeshenko, V.: The undecided have the key: interaction-driven opinion dynamics in a three state model. PLoS ONE 10(10), 1–21 (2015)
Baronchelli, A.: The emergence of consenus: a primer. R. Soc. Open Sci. 5(2), 172,189 (2018)
Brambilla, M., Ferrante, E., Birattari, M., Dorigo, M.: Swarm robotics: a review from the swarm engineering perspective. Swarm Intell. 7(1), 1–41 (2013)
Crosscombe, M., Lawry, J.: A model of multi-agent consensus for vague and uncertain beliefs. Adapt. Behav. 24(4), 249–260 (2016)
Crosscombe, M., Lawry, J., Hauert, S., Homer, M.: Robust distributed decision-making in robot swarms: exploiting a third truth state. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4326–4332 (2017)
Dabarera, R., Wickramarathne, T.L., Premaratne, K., Murthi, M.N.: Achieving consensus under bounded confidence in multi-agent distributed decision-making. In: 2019 22th International Conference on Information Fusion (FUSION), pp. 1–8 (2019)
DeGroot, M.H.: Reaching a consensus. J. Am. Stat. Assoc. 69(345), 118–121 (1974)
Douven, I.: Optimizing group learning: an evolutionary computing approach. Artif. Intell. 275, 235–251 (2019)
Douven, I., Kelp, C.: Truth approximation, social epistemology, and opinion dynamics. Erkenntnis 75(2), 271 (2011)
Erdös, P., Rényi, A.: On random graphs. Publ. Math. (Debrecen) 6, 290–297 (1959)
Franks, N., Pratt, S., Mallon, E., Britton, N., Sumpter, D.: Information flow, opinion-polling and collective intelligence in house-hunting social insects. Philos. Trans. B Biol. Sci. 357(1427), 1567–1583 (2002)
Hamann, H.: Superlinear scalability in parallel computing and multi-robot systems: shared resources, collaboration, and network topology. In: Berekovic, M., Buchty, R., Hamann, H., Koch, D., Pionteck, T. (eds.) ARCS 2018. LNCS, vol. 10793, pp. 31–42. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-77610-1_3
Hegselmann, R., Krause, U.: Opinion dynamics driven by various ways of averaging. Comput. Econ. 25(4), 381–405 (2005)
Hegselmann, R., Krause, U., et al.: Opinion dynamics and bounded confidence models, analysis, and simulation. J. Artif. Soc. Soc. Simul. 5(3) (2002)
Lawry, J., Crosscombe, M., Harvey, D.: Epistemic sets applied to best-of-n problems. In: Kern-Isberner, G., Ognjanović, Z. (eds.) ECSQARU 2019. LNCS (LNAI), vol. 11726, pp. 301–312. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-29765-7_25
Lee, C., Lawry, J., Winfield, A.: Negative updating combined with opinion pooling in the best-of-n problem in swarm robotics. In: Dorigo, M., Birattari, M., Blum, C., Christensen, A.L., Reina, A., Trianni, V. (eds.) ANTS 2018. LNCS, vol. 11172, pp. 97–108. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00533-7_8
Masuda, N., Aihara, K.: Global and local synchrony of coupled neurons in small-world networks. Biol. Cybern. 90, 302–9 (2004)
Newman, M.E.J., Watts, D.J., Strogatz, S.H.: Random graph models of social networks. Proc. Natl. Acad. Sci. 99(suppl 1), 2566–2572 (2002)
Olfati-Saber, R., Fax, J.A., Murray, R.M.: Consensus and cooperation in networked multi-agent systems. Proc. IEEE 95(1), 215–233 (2007)
Parker, C.A.C., Zhang, H.: Cooperative decision-making in decentralized multiple-robot systems: the best-of-n problem. IEEE/ASME Trans. Mechatron. 14(2), 240–251 (2009)
Parker, C.A.C., Zhang, H.: Biologically inspired collective comparisons by robotic swarms. Int. J. Robot. Res. 30(5), 524–535 (2011)
Perron, E., Vasudevan, D., Vojnović, M.: Using three states for binary consensus on complete graphs. In: Proceedings - IEEE INFOCOM, pp. 2527–2535 (2009)
Rubenstein, M., Ahler, C., Nagpal, R.: Kilobot: a low cost scalable robot system for collective behaviors. In: 2012 IEEE International Conference on Robotics and Automation, pp. 3293–3298 (2012)
Schranz, M., Umlauft, M., Sende, M., Elmenreich, W.: Swarm robotic behaviors and current applications. Front. Robot. AI 7, 36 (2020)
Stone, M.: The opinion pool. Ann. Math. Stat. 32(4), 1339–1342 (1961)
Valentini, G., Ferrante, E., Dorigo, M.: The best-of-n problem in robot swarms: formalization, state of the art, and novel perspectives. Front. Robot. AI 4, 9 (2017)
Valentini, G., Hamann, H., Dorigo, M.: Efficient decision-making in a self-organizing robot swarm: on the speed versus accuracy trade-off. In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, pp. 1305–1314. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2015)
Watts, D.J.: Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton University Press, USA (2003)
Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393(June), 440–442 (1998)
Acknowledgements
This work was funded and delivered in partnership between Thales Group, University of Bristol and with the support of the UK Engineering and Physical Sciences Research Council, ref. EP/R004757/1 entitled “Thales-Bristol Partnership in Hybrid Autonomous Systems Engineering (T-B PHASE).”
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Crosscombe, M., Lawry, J. (2022). The Impact of Network Connectivity on Collective Learning. In: Matsuno, F., Azuma, Si., Yamamoto, M. (eds) Distributed Autonomous Robotic Systems. DARS 2021. Springer Proceedings in Advanced Robotics, vol 22. Springer, Cham. https://doi.org/10.1007/978-3-030-92790-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-92790-5_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-92789-9
Online ISBN: 978-3-030-92790-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)