Coherent collective behaviour emerging from decentralised balancing of social feedback and noise
Tóm tắt
Decentralised systems composed of a large number of locally interacting agents often rely on coherent behaviour to execute coordinated tasks. Agents cooperate to reach a coherent collective behaviour by aligning their individual behaviour to the one of their neighbours. However, system noise, determined by factors such as individual exploration or errors, hampers and reduces collective coherence. The possibility to overcome noise and reach collective coherence is determined by the strength of social feedback, i.e. the number of communication links. On the one hand, scarce social feedback may lead to a noise-driven system and consequently incoherent behaviour within the group. On the other hand, excessively strong social feedback may require unnecessary computing by individual agents and/or may nullify the possible benefits of noise. In this study, we investigate the delicate balance between social feedback and noise, and its relationship with collective coherence. We perform our analysis through a locust-inspired case study of coherently marching agents, modelling the binary collective decision-making problem of symmetry breaking. For this case study, we analytically approximate the minimal number of communication links necessary to attain maximum collective coherence. To validate our findings, we simulate a 500-robot swarm and obtain good agreement between theoretical results and physics-based simulations. We illustrate through simulation experiments how the robot swarm, using a decentralised algorithm, can adaptively reach coherence for various noise levels by regulating the number of communication links. Moreover, we show that when the system is disrupted by increasing and decreasing the robot density, the robot swarm adaptively responds to these changes in real time. This decentralised adaptive behaviour indicates that the derived relationship between social feedback, noise and coherence is robust and swarm size independent.
Tài liệu tham khảo
Ariel, G., & Ayali, A. (2015). Locust collective motion and its modeling. PLoS Computational Biology, 11(12), e1004522.
Baronchelli, A. (2018). The emergence of consensus: A primer. Royal Society Open Science, 5(2), 172189.
Bayındır, L. (2016). A review of swarm robotics tasks. Neurocomputing, 172(C), 292–321.
Berman, S., Halász, Á., Hsieh, M. A., & Kumar, V. (2009). Optimized stochastic policies for task allocation in swarms of robots. IEEE Transactions on Robotics, 25(4), 927–937.
Böhme, G. A., & Gross, T. (2012). Fragmentation transitions in multistate voter models. Physical Review E, 85, 066117.
Bonabeau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm intelligence: From natural to artificial systems. New York: Oxford University Press.
Bonani, M., Longchamp, V., Magnenat, S., Rétornaz, P., Burnier, D., Roulet, G., Vaussard, F., Bleuler, H., & Mondada, F. (2010). The marXbot, a miniature mobile robot opening new perspectives for the collective-robotic research. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (IROS 2010) (pp. 4187–4193). IEEE Press.
Bose, T., Reina, A., & Marshall, J. A. R. (2017). Collective decision-making. Current Opinion in Behavioral Sciences, 6, 30–34.
Brambilla, M., Ferrante, E., Birattari, M., & Dorigo, M. (2013). Swarm robotics: A review from the swarm engineering perspective. Swarm Intelligence, 7(1), 1–41.
Buhl, J., Sumpter, D. J., Couzin, I. D., Hale, J. J., Despland, E., Miller, E. R., et al. (2006). From disorder to order in marching locusts. Science, 312(5778), 1402–1406.
Camazine, S., Deneubourg, J.-L., Franks, N. R., Sneyd, J., Bonabeau, E., & Theraulaz, G. (2003). Self-organization in biological systems (Vol. 7). Princeton: Princeton University Press.
Castellano, C., Fortunato, S., & Loreto, V. (2009). Statistical physics of social dynamics. Reviews of Modern Physics, 81(2), 591–646.
Chen, L., Huepe, C., & Gross, T. (2016). Adaptive network models of collective decision making in swarming systems. Physical Review E, 94(2), 022415.
Czirók, A., Barabási, A.-L., & Vicsek, T. (1999). Collective motion of self-propelled particles: Kinetic phase transition in one dimension. Physical Review Letters, 82, 209–212.
Danon, L., Ford, A. P., House, T., Jewell, C. P., Keeling, M. J., Roberts, G. O., et al. (2011). Networks and the epidemiology of infectious disease. Interdisciplinary Perspectives on Infectious Diseases, 2011, 284909.
Dussutour, A., Beekman, M., Nicolis, S. C., & Meyer, B. (2009). Noise improves collective decision-making by ants in dynamic environments. Proceedings of the Royal Society of London B: Biological Sciences, 276(1677), 4353–4361.
Gross, T., D’Lima, C. J. D., & Blasius, B. (2006). Epidemic dynamics on an adaptive network. Physical Review Letters, 96, 208701.
Hamann, H. (2018). The role of largest connected components in collective motion. In M. Dorigo, M. Birattari, C. Blum, A. L. Christensen, A. Reina, & V. Trianni (Eds.), Swarm intelligence: 11th International conference, ANTS 2018, volume 11172 of LNCS (pp. 290–301). Cham: Springer.
Hamann, H., Valentini, G., Khaluf, Y., & Dorigo, M. (2014). Derivation of a micro-macro link for collective decision-making systems. In T. Bartz-Beielstein, J. Branke, B. Filipič, & J. Smith (Eds.), International conference on parallel problem solving from nature—PPSN XIII, PPSN 2014, volume 8672 of LNCS (pp. 181–190). Cham: Springer.
Hamann, H., & Wörn, H. (2008). A framework of space–time continuous models for algorithm design in swarm robotics. Swarm Intelligence, 2(2), 209–239.
House, T., Davies, G., Danon, L., & Keeling, M. J. (2009). A motif-based approach to network epidemics. Bulletin of Mathematical Biology, 71(7), 1693–1706.
Huepe, C., Zschaler, G., Do, A.-L., & Gross, T. (2011). Adaptive-network models of swarm dynamics. New Journal of Physics, 13(7), 073022.
Keeling, M. J., & Eames, K. T. (2005). Networks and epidemic models. Journal of The Royal Society Interface, 2(4), 295–307.
Keeling, M. J., House, T., Cooper, A. J., & Pellis, L. (2016). Systematic approximations to susceptible-infectious-susceptible dynamics on networks. PLoS Computational Biology, 12(12), e1005296.
Khaluf, Y., Birattari, M., & Rammig, F. (2016). Analysis of long-term swarm performance based on short-term experiments. Soft Computing, 20(1), 37–48.
Khaluf, Y., Ferrante, E., Simoens, P., & Huepe, C. (2017a). Scale invariance in natural and artificial collective systems: A review. Journal of The Royal Society Interface, 14(136), 20170662.
Khaluf, Y., & Hamann, H. (2016). On the definition of self-organizing systems: Relevance of positive/negative feedback and fluctuations. In M. Dorigo, M. Birattari, X. Li, M. López-Ibáñez, K. Ohkura, C. Pinciroli, & T. Stützle (Eds.), Swarm intelligence: 10th International conference, ANTS 2016, volume 9882 of LNCS (p. 298). Cham: Springer. (extended abstract).
Khaluf, Y., Pinciroli, C., Valentini, G., & Hamann, H. (2017b). The impact of agent density on scalability in collective systems: Noise-induced versus majority-based bistability. Swarm Intelligence, 11(2), 155–179.
Khaluf, Y., Rausch, I., & Simoens, P. (2018). The impact of interaction models on the coherence of collective decision-making: A case study with simulated locusts. In M. Dorigo, M. Birattari, C. Blum, A. L. Christensen, A. Reina, & V. Trianni (Eds.), Swarm intelligence: 11th International conference, ANTS 2018, volume 11172 of LNCS (pp. 252–263). Cham: Springer.
Kimura, D., & Hayakawa, Y. (2008). Coevolutionary networks with homophily and heterophily. Physical Review E, 78, 016103.
Lerman, K., Martinoli, A., & Galstyan, A. (2004). A review of probabilistic macroscopic models for swarm robotic systems. In E. Şahin & W. M. Spears (Eds.), International workshop on swarm robotics (pp. 143–152). Berlin, Heidelberg: Springer.
Liang, Y., An, K. N., Yang, G., & Huang, J. P. (2013). Contrarian behavior in a complex adaptive system. Physical Review E, 87, 012809.
Mateo, D., Horsevad, N., Hassani, V., Chamanbaz, M., & Bouffanais, R. (2019). Optimal network topology for responsive collective behavior. Science Advances, 5(4), eaau0999.
Mateo, D., Kuan, Y. K., & Bouffanais, R. (2017). Effect of correlations in swarms on collective response. Scientific Reports, 7(1), 10388.
Mayya, S., Pierpaoli, P., & Egerstedt, M. (2019). Voluntary retreat for decentralized interference reduction in robot swarms. In ICRA 2019. IEEE Press. (in press).
Pagliara, R., Gordon, D. M., & Leonard, N. E. (2018). Regulation of harvester ant foraging as a closed-loop excitable system. PLoS Computational Biology, 14(12), e1006200.
Pinciroli, C., Trianni, V., O’Grady, R., Pini, G., Brutschy, A., Brambilla, M., et al. (2012). ARGoS: A modular, parallel, multi-engine simulator for multi-robot systems. Swarm Intelligence, 6(4), 271–295.
Pinero, J., & Sole, R. (2019). Statistical physics of liquid brains. Philosophical Transactions of the Royal Society B, 374(1774), 20180376.
Pitonakova, L., Crowder, R., & Bullock, S. (2018). The Information-Cost-Reward framework for understanding robot swarm foraging. Swarm Intelligence, 12(1), 71–96.
Rausch, I., Khaluf, Y., & Simoens, P. (2019). Scale-free features in collective robot foraging. Applied Sciences, 9(13), 2667.
Reina, A., Miletitch, R., Dorigo, M., & Trianni, V. (2015a). A quantitative micro-macro link for collective decisions: The shortest path discovery/selection example. Swarm Intelligence, 9(2–3), 75–102.
Reina, A., Valentini, G., Fernández-Oto, C., Dorigo, M., & Trianni, V. (2015b). A design pattern for decentralised decision making. PLoS ONE, 10(10), e0140950.
Roberts, J. F., Stirling, T. S., Zufferey, J.-C., & Floreano, D. (2009). 2.5D infrared range and bearing system for collective robotics. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (IROS 2009) (pp. 3659–3664). IEEE Press.
Saldaña, D., Prorok, A., Sundaram, S., Campos, M. F., & Kumar, V. (2017). Resilient consensus for time-varying networks of dynamic agents. In 2017 American control conference (ACC) (pp. 252–258).
Saulnier, K., Saldaña, D., Prorok, A., Pappas, G. J., & Kumar, V. (2017). Resilient flocking for mobile robot teams. IEEE Robotics and Automation Letters, 2(2), 1039–1046.
Shang, Y., & Bouffanais, R. (2014). Influence of the number of topologically interacting neighbors on swarm dynamics. Scientific Reports, 4, 4184.
Shklarsh, A., Ariel, G., Schneidman, E., & Ben-Jacob, E. (2011). Smart swarms of bacteria-inspired agents with performance adaptable interactions. PLoS Computational Biology, 7(9), e1002177.
Talamali, M. S., Bose, T., Haire, M., Xu, X., Marshall, J. A. R., & Reina, A. (2019a). Sophisticated collective foraging with minimalist agents: A swarm robotics test. Swarm Intelligence. (in press).
Talamali, M. S., Bose, T., James, M. A., & Reina, A. (2019b). Improving collective decision accuracy via time-varying cross-inhibition. In ICRA 2019. IEEE Press. (in press).
Torney, C. J., Neufeld, Z., & Couzin, I. D. (2009). Context-dependent interaction leads to emergent search behavior in social aggregates. Proceedings of the National Academy of Sciences, 106(52), 22055–22060.
Tsimring, L. S. (2014). Noise in biology. Reports on Progress in Physics, 77(2), 026601.
Valentini, G., & Hamann, H. (2015). Time-variant feedback processes in collective decision-making systems: Influence and effect of dynamic neighborhood sizes. Swarm Intelligence, 9(2–3), 153–176.
Vicsek, T., Czirók, A., Ben-Jacob, E., Cohen, I., & Shochet, O. (1995). Novel type of phase transition in a system of self-driven particles. Physical Review Letters, 75, 1226–1229.
Wahby, M., Petzold, J., Eschke, C., Schmickl, T., & Hamann, H. (2019). Collective change detection: Adaptivity to dynamic swarm densities and light conditions in robot swarms. In The 2018 conference on artificial life: A hybrid of the European conference on artificial life (ECAL) and the international conference on the synthesis and simulation of living systems (ALIFE) (pp. 642–649). MIT Press.
Yates, C. A., Erban, R., Escudero, C., Couzin, I. D., Buhl, J., Kevrekidis, I. G., et al. (2009). Inherent noise can facilitate coherence in collective swarm motion. Proceedings of the National Academy of Sciences, 106(14), 5464–5469.
Zhong, L.-X., Zheng, D.-F., Zheng, B., & Hui, P. M. (2005). Effects of contrarians in the minority game. Physical Review E, 72, 026134.