nach oben

Swarm Intelligence

Erschienen in:

01.09.2013

Towards swarm calculus: urn models of collective decisions and universal properties of swarm performance

verfasst von: Heiko Hamann

Erschienen in: Swarm Intelligence | Ausgabe 2-3/2013

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Methods of general applicability are searched for in swarm intelligence with the aim of gaining new insights about natural swarms and to develop design methodologies for artificial swarms. An ideal solution could be a ‘swarm calculus’ that allows to calculate key features of swarms such as expected swarm performance and robustness based on only a few parameters. To work towards this ideal, one needs to find methods and models with high degrees of generality. In this paper, we report two models that might be examples of exceptional generality. First, an abstract model is presented that describes swarm performance depending on swarm density based on the dichotomy between cooperation and interference. Typical swarm experiments are given as examples to show how the model fits to several different results. Second, we give an abstract model of collective decision making that is inspired by urn models. The effects of positive-feedback probability, that is increasing over time in a decision making system, are understood by the help of a parameter that controls the feedback based on the swarm’s current consensus. Several applicable methods, such as the description as Markov process, calculation of splitting probabilities, mean first passage times, and measurements of positive feedback, are discussed and applications to artificial and natural swarms are reported.

Vorheriger Artikel Evolution of swarm robotics systems with novelty search

Nächster Artikel Task partitioning in a robot swarm: a study on the effect of communication

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

This paper is an extended version of Hamann (2012). The main extensions are the method of deriving the probability of positive feedback based on observed decision revisions (Sect. 4.1), a discussion of additional methodology such as Markov chains, splitting probabilities, and mean first passage times (Sect. 4.3), and a comprehensive introduction of the Ehrenfest and the Eigen urn models.

See http://www.gnuplot.info/.

Arkin, R. C., Balch, T., & Nitz, E. (1993). Communication of behavioral state in multi-agent retrieval tasks. In W. Book & J. Luh (Eds.), IEEE conference on robotics and automation (Vol. 3, pp. 588–594). Los Alamitos: IEEE Press. CrossRef

Berman, S., Kumar, V., & Nagpal, R. (2011). Design of control policies for spatially inhomogeneous robot swarms with application to commercial pollination. In S. LaValle, H. Arai, O. Brock, H. Ding, C. Laugier, A. M. Okamura, S. S. Reveliotis, G. S. Sukhatme, & Y. Yagi (Eds.), IEEE international conference on robotics and automation (ICRA’11) (pp. 378–385). Los Alamitos: IEEE Press. CrossRef

Bjerknes, J. D., & Winfield, A. (2013). On fault-tolerance and scalability of swarm robotic systems. In A. Martinoli, F. Mondada, N. Correll, G. Mermoud, M. Egerstedt, M. A. Hsieh, L. E. Parker, & K. Støy (Eds.), Springer tracts in advanced robotics: Vol. 83. Distributed autonomous robotic systems (DARS 2010) (pp. 431–444). Berlin: Springer. CrossRef

Bjerknes, J. D., Winfield, A., & Melhuish, C. (2007). An analysis of emergent taxis in a wireless connected swarm of mobile robots. In Y. Shi & M. Dorigo (Eds.), IEEE swarm intelligence symposium (pp. 45–52). Los Alamitos: IEEE Press.

Breder, C. M. (1954). Equations descriptive of fish schools and other animal aggregations. Ecology, 35(3), 361–370. CrossRef

Camazine, S., Deneubourg, J.-L., Franks, N. R., Sneyd, J., Theraulaz, G., & Bonabeau, E. (2001). Self-organizing biological systems. Princeton: Princeton University Press.

Deneubourg, J.-L., Aron, S., Goss, S., & Pasteels, J. M. (1990). The self-organizing exploratory pattern of the Argentine ant. Journal of Insect Behavior, 3(2), 159–168. CrossRef

Dussutour, A., Fourcassié, V., Helbing, D., & Deneubourg, J.-L. (2004). Optimal traffic organization in ants under crowded conditions. Nature, 428, 70–73. CrossRef

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, Series B, 276, 4353–4361. CrossRef

Edelstein-Keshet, L. (2006). Mathematical models of swarming and social aggregation. Robotica, 24(3), 315–324. CrossRef

Ehrenfest, P., & Ehrenfest, T. (1907). Über zwei bekannte Einwände gegen das Boltzmannsche H-Theorem. Physikalische Zeitschrift, 8, 311–314. MATH

Eigen, M., & Winkler, R. (1993). Laws of the game: how the principles of nature govern chance. Princeton: Princeton University Press.

Galam, S. (2004). Contrarian deterministic effect on opinion dynamics: the “hung elections scenario”. Physica A, 333(1), 453–460. MathSciNetCrossRef

Gardiner, C. W. (1985). Handbook of stochastic methods for physics, chemistry and the natural sciences. Berlin: Springer.

Gautrais, J., Theraulaz, G., Deneubourg, J.-L., & Anderson, C. (2002). Emergent polyethism as a consequence of increased colony size in insect societies. Journal of Theoretical Biology, 215(3), 363–373. CrossRef

Goldberg, D., & Matarić, M. J. (1997). Interference as a tool for designing and evaluating multi-robot controllers. In B. J. Kuipers & B. Webber (Eds.), Proc. of the fourteenth national conference on artificial intelligence (AAAI’97) (pp. 637–642). Cambridge: MIT Press.

Graham, R., Knuth, D., & Patashnik, O. (1998). Concrete mathematics: a foundation for computer science. Reading: Addison–Wesley.

Grinstead, C. M., & Snell, J. L. (1997). Introduction to probability. Providence: American Mathematical Society. MATH

Hamann, H. (2006). Modeling and investigation of robot swarms. Master’s thesis, University of Stuttgart, Germany.

Hamann, H. (2010). Space-time continuous models of swarm robotics systems: supporting global-to-local programming. Berlin: Springer. CrossRef

Hamann, H. (2012). Towards swarm calculus: universal properties of swarm performance and collective decisions. In M. Dorigo, M. Birattari, C. Blum, A. L. Christensen, A. P. Engelbrecht, R. Groß, & T. Stützle (Eds.), Lecture notes in computer science: Vol. 7461. Swarm intelligence: 8th international conference, ANTS 2012 (pp. 168–179). Berlin: Springer.

Hamann, H., & Wörn, H. (2007). Embodied computation. Parallel Processing Letters, 17(3), 287–298. MathSciNetCrossRef

Hamann, H., & Wörn, H. (2008). Aggregating robots compute: an adaptive heuristic for the Euclidean Steiner tree problem. In M. Asada, J. C. Hallam, J.-A. Meyer, & J. Tani (Eds.), Lecture notes in artificial intelligence: Vol. 5040. The tenth international conference on simulation of adaptive behavior (SAB’08) (pp. 447–456). Berlin: Springer.

Hamann, H., Meyer, B., Schmickl, T., & Crailsheim, K. (2010). A model of symmetry breaking in collective decision-making. In S. Doncieux, B. Girard, A. Guillot, J. Hallam, J.-A. Meyer, & J.-B. Mouret (Eds.), Lecture notes in artificial intelligence: Vol. 6226. From animals to animats 11 (pp. 639–648). Berlin: Springer. CrossRef

Hamann, H., Schmickl, T., Wörn, H., & Crailsheim, K. (2012). Analysis of emergent symmetry breaking in collective decision making. Neural Computing & Applications, 21(2), 207–218. CrossRef

Ingham, A. G., Levinger, G., Graves, J., & Peckham, V. (1974). The Ringelmann effect: studies of group size and group performance. Journal of Experimental Social Psychology, 10(4), 371–384. CrossRef

Jeanne, R. L., & Nordheim, E. V. (1996). Productivity in a social wasp: per capita output increases with swarm size. Behavioral Ecology, 7(1), 43–48. CrossRef

Jeanson, R., Fewell, J. H., Gorelick, R., & Bertram, S. M. (2007). Emergence of increased division of labor as a function of group size. Behavioral Ecology and Sociobiology, 62, 289–298. CrossRef

Karsai, I., & Wenzel, J. W. (1998). Productivity, individual-level and colony-level flexibility, and organization of work as consequences of colony size. Proceedings of the National Academy of Sciences of the United States of America, 95, 8665–8669. CrossRef

Kennedy, J., & Eberhart, R. C. (2001). Swarm intelligence. San Mateo: Morgan Kaufmann.

Klein, M. J. (1956). Generalization of the Ehrenfest urn model. Physical Review, 103(1), 17–20. MATHCrossRef

Krafft, O., & Schaefer, M. (1993). Mean passage times for triangular transition matrices and a two parameter Ehrenfest urn model. Journal of Applied Probability, 30(4), 964–970. MathSciNetMATHCrossRef

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

Lerman, K., Martinoli, A., & Galstyan, A. (2005). A review of probabilistic macroscopic models for swarm robotic systems. In E. Şahin & W. M. Spears (Eds.), Lecture notes in computer science: Vol. 3342. Swarm robotics—SAB 2004 international workshop (pp. 143–152). Berlin: Springer.

Levenberg, K. (1944). A method for the solution of certain non-linear problems in least squares. Quarterly of Applied Mathematics, 2, 164–168. MathSciNetMATH

Lighthill, M. J., & Whitham, G. B. (1955). On kinematic waves. II. A theory of traffic flow on long crowded roads. Proceedings of the Royal Society of London, Series A, 229(1178), 317–345. MathSciNetMATHCrossRef

Mahmassani, H. S., Dong, J., Kim, J., Chen, R. B., & Park, B. (2009). Incorporating weather impacts in traffic estimation and prediction systems. Technical Report FHWA-JPO-09-065, U.S. Department of Transportation.

Mallon, E. B., Pratt, S. C., & Franks, N. R. (2001). Individual and collective decision-making during nest site selection by the ant leptothorax albipennis. Behavioral Ecology and Sociobiology, 50, 352–359. CrossRef

Marquardt, D. (1963). An algorithm for least-squares estimation of nonlinear parameters. SIAM Journal on Applied Mathematics, 11(2), 431–441. MathSciNetMATHCrossRef

Milutinovic, D., & Lima, P. (2007). Cells and robots: modeling and control of large-size agent populations. Berlin: Springer.

Miramontes, O. (1995). Order-disorder transitions in the behavior of ant societies. Complexity, 1(1), 56–60. CrossRef

Mondada, F., Bonani, M., Guignard, A., Magnenat, S., Studer, C., & Floreano, D. (2005). Superlinear physical performances in a SWARM-BOT. In M. S. Capcarrere (Ed.), Lecture notes in computer science: Vol. 3630. Proc. of the 8th European conference on artificial life (ECAL) (pp. 282–291). Berlin: Springer.

Nembrini, J., Winfield, A. F. T., & Melhuish, C. (2002). Minimalist coherent swarming of wireless networked autonomous mobile robots. In B. Hallam, D. Floreano, J. Hallam, G. Hayes, & J.-A. Meyer (Eds.), Proceedings of the seventh international conference on simulation of adaptive behavior on from animals to animats (pp. 373–382). Cambridge: MIT Press.

Nicolis, S. C., Zabzina, N., Latty, T., & Sumpter, D. J. T. (2011). Collective irrationality and positive feedback. PLoS ONE, 6, e18901. CrossRef

Okubo, A. (1986). Dynamical aspects of animal grouping: swarms, schools, flocks, and herds. Advances in Biophysics, 22, 1–94. CrossRef

Okubo, A., & Levin, S. A. (2001). Diffusion and ecological problems: modern perspectives. Berlin: Springer. CrossRef

Østergaard, E. H., Sukhatme, G. S., & Matarić, M. J. (2001). Emergent bucket brigading: a simple mechanisms for improving performance in multi-robot constrained-space foraging tasks. In E. André, S. Sen, C. Frasson, & J. P. Müller (Eds.), Proceedings of the fifth international conference on autonomous agents (AGENTS’01) (pp. 29–35). New York: ACM. CrossRef

Prorok, A., Correll, N., & Martinoli, A. (2011). Multi-level spatial models for swarm-robotic systems. The International Journal of Robotics Research, 30(5), 574–589. CrossRef

Saffre, F., Furey, R., Krafft, B., & Deneubourg, J.-L. (1999). Collective decision-making in social spiders: dragline-mediated amplification process acts as a recruitment mechanism. Journal of Theoretical Biology, 198, 507–517. CrossRef

Schmickl, T., & Hamann, H. (2011). BEECLUST: a swarm algorithm derived from honeybees. In Y. Xiao (Ed.), Bio-inspired computing and communication networks. Boca Raton: CRC Press.

Schneider-Fontán, M., & Matarić, M. J. (1996). A study of territoriality: the role of critical mass in adaptive task division. In P. Maes, S. W. Wilson, & M. J. Matarić (Eds.), From animals to animats IV (pp. 553–561). Cambridge: MIT Press.

Seeley, T. D., Camazine, S., & Sneyd, J. (1991). Collective decision-making in honey bees: how colonies choose among nectar sources. Behavioral Ecology and Sociobiology, 28(4), 277–290. CrossRef

Strogatz, S. H. (2001). Exploring complex networks. Nature, 410(6825), 268–276. CrossRef

Vicsek, T., & Zafeiris, A. (2012). Collective motion. Physics Reports, 517(3–4), 71–140. CrossRef

Wong, G., & Wong, S. (2002). A multi-class traffic flow model—an extension of LWR model with heterogeneous drivers. Transportation Research. Part A, Policy and Practice, 36(9), 827–841. CrossRef

Yates, C. A., Erban, R., Escudero, C., Couzin, I. D., Buhl, J., Kevrekidis, I. G., Maini, P. K., & Sumpter, D. J. T. (2009). Inherent noise can facilitate coherence in collective swarm motion. Proceedings of the National Academy of Sciences of the United States of America, 106(14), 5464–5469. CrossRef

Titel: Towards swarm calculus: urn models of collective decisions and universal properties of swarm performance
verfasst von: Heiko Hamann
Publikationsdatum: 01.09.2013
Verlag: Springer US
Erschienen in: Swarm Intelligence / Ausgabe 2-3/2013
Print ISSN: 1935-3812
Elektronische ISSN: 1935-3820
DOI: https://doi.org/10.1007/s11721-013-0080-0

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"

Weitere Artikel der Ausgabe 2-3/2013

ANTS 2012 special issue

Learning Bayesian network classifiers using ant colony optimization

Modular self-assembling and self-reconfiguring e-pucks

On the use of Bio-PEPA for modelling and analysing collective behaviours in swarm robotics

Evolution of swarm robotics systems with novelty search

Task partitioning in a robot swarm: a study on the effect of communication