Evolving flocking in embodied agents based on local and global application of Reynolds’ rules
Autoři:
Rita Parada Ramos aff001; Sancho Moura Oliveira aff002; Susana Margarida Vieira aff001; Anders Lyhne Christensen aff002
Působiště autorů:
Instituto Superior Técnico (IST), Lisbon, Portugal
aff001; Instituto Universitário de Lisboa (ISCTE-IUL), Lisbon, Portugal
aff002; Instituto de Telecomunicações, Lisbon, Portugal
aff003; Embodied Systems for Robotics and Learning at the Mærsk Mc-Kinney Møller Institute, University of Southern Denmark (SDU), Odense, Denmark
aff004
Vyšlo v časopise:
PLoS ONE 14(10)
Kategorie:
Research Article
prolekare.web.journal.doi_sk:
https://doi.org/10.1371/journal.pone.0224376
Souhrn
In large scale systems of embodied agents, such as robot swarms, the ability to flock is essential in many tasks. However, the conditions necessary to artificially evolve self-organised flocking behaviours remain unknown. In this paper, we study and demonstrate how evolutionary techniques can be used to synthesise flocking behaviours, in particular, how fitness functions should be designed to evolve high-performing controllers. We start by considering Reynolds’ seminal work on flocking, the boids model, and design three components of a fitness function that are directly based on his three local rules to enforce local separation, cohesion and alignment. Results show that embedding Reynolds’ rules in the fitness function can lead to the successful evolution of flocking behaviours. However, only local, fragmented flocking behaviours tend to evolve when fitness scores are based on the individuals’ conformity to Reynolds’ rules. We therefore modify the components of the fitness function so that they consider the entire group of agents simultaneously, and find that the resulting behaviours lead to global flocking. Furthermore, the results show that alignment need not be explicitly rewarded to successfully evolve flocking. Our study thus represents a significant step towards the use of evolutionary techniques to synthesise collective behaviours for tasks in which embodied agents need to move as a single, cohesive group.
Klíčová slova:
Predation – Foraging – Inertia – Collective animal behavior – Artificial neural networks – Robots – Robotics – Robotic behavior
Zdroje
1. Feare C. The starling. Oxford University Press; 1984.
2. Partridge B. The effect of school size on the structure and dynamics of minnow schools. Animal Behaviour. 1980;28(1):68–IN3. doi: 10.1016/S0003-3472(80)80009-1
3. Buhl J, Sumpter DJ, Couzin ID, Hale JJ, Despland E, Miller ER, et al. From disorder to order in marching locusts. Science. 2006;312(5778):1402–1406. doi: 10.1126/science.1125142 16741126
4. Pitcher TJ. Functions of shoaling behaviour in teleosts. In: The behaviour of teleost fishes. Springer; 1986. p. 294–337.
5. Landeau L, Terborgh J. Oddity and the ‘confusion effect’ in predation. Animal Behaviour. 1986;34(5):1372–1380. doi: 10.1016/S0003-3472(86)80208-1
6. Pulliam HR. On the advantages of flocking. Journal of theoretical Biology. 1973;38(2):419–422. doi: 10.1016/0022-5193(73)90184-7 4734745
7. Elgar MA. Predator vigilance and group size in mammals and birds: a critical review of the empirical evidence. Biological Reviews. 1989;64(1):13–33. doi: 10.1111/j.1469-185X.1989.tb00636.x 2655726
8. Partridge BL. The structure and function of fish schools. Scientific american. 1982;246(6):114–123. doi: 10.1038/scientificamerican0682-114 7201674
9. Krebs JR, MacRoberts MH, Cullen J. Flocking and feeding in the great tit Parus major—an experimental study. IBIS. 1972;114(4):507–530. doi: 10.1111/j.1474-919X.1972.tb00852.x
10. Pitcher T, Magurran A, Winfield I. Fish in larger shoals find food faster. Behavioral Ecology and Sociobiology. 1982;10(2):149–151. doi: 10.1007/BF00300175
11. Ryer CH, Olla BL. Social mechanisms facilitating exploitation of spatially variable ephemeral food patches in a pelagic marine fish. Animal Behaviour. 1992;44(1):69–74. doi: 10.1016/S0003-3472(05)80756-0
12. Brown C, Laland KN. Social learning in fishes: a review. Fish and fisheries. 2003;4(3):280–288. doi: 10.1046/j.1467-2979.2003.00122.x
13. Werner GM, Dyer MG. Evolution of herding behavior in artificial animals. In: From Animals to Animats 2: Proceedings of the Second International Conference on Simulation of Adaptive Behavior. vol. 2. MIT Press; 1993. p. 393–399.
14. Ballerini M, Cabibbo N, Candelier R, Cavagna A, Cisbani E, Giardina I, et al. Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study. Proceedings of the National Academy of Sciences. 2008;105(4):1232–1237. doi: 10.1073/pnas.0711437105
15. Reynolds CW. Flocks, herds and schools: A distributed behavioral model. ACM SIGGRAPH Computer Graphics. 1987;21(4):25–34. doi: 10.1145/37402.37406
16. Vicsek T, Zafeiris A. Collective motion. Physics Reports. 2012;517(3):71–140. doi: 10.1016/j.physrep.2012.03.004
17. Toner J, Tu Y. Flocks, herds, and schools: A quantitative theory of flocking. Physical review E. 1998;58(4):4828. doi: 10.1103/PhysRevE.58.4828
18. Olfati-Saber R. Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Transactions on Automatic Control. 2006;51(3):401–420. doi: 10.1109/TAC.2005.864190
19. Turgut AE, Çelikkanat H, Gökçe F, Şahin E. Self-organized flocking in mobile robot swarms. Swarm Intelligence. 2008;2(2-4):97–120. doi: 10.1007/s11721-008-0016-2
20. Ferrante E. Information transfer in a flocking robot swarm. Ph.D. thesis, Université Libre de Bruxelles, Brussels, Belgium; 2013.
21. Dorigo M, Birattari M, Brambilla M. Swarm robotics. Scholarpedia. 2014;9(1):1463. doi: 10.4249/scholarpedia.1463
22. Brambilla M, Ferrante E, Birattari M, Dorigo M. Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence. 2013;7(1):1–41. doi: 10.1007/s11721-012-0075-2
23. Silva F, Correia L, Christensen AL. Evolutionary Robotics. Scholarpedia. 2016;11(7):33333. doi: 10.4249/scholarpedia.33333
24. Trianni V, Groß R, Labella TH, Şahin E, Dorigo M. Evolving aggregation behaviors in a swarm of robots. In: European Conference on Artificial Life. Springer; 2003. p. 865–874.
25. Sperati V, Trianni V, Nolfi S. Evolving coordinated group behaviours through maximisation of mean mutual information. Swarm Intelligence. 2008;2(2):73–95. doi: 10.1007/s11721-008-0017-1
26. Duarte M, Costa V, Gomes J, Rodrigues T, Silva F, Oliveira SM, et al. Evolution of collective behaviors for a real swarm of aquatic surface robots. PLoS ONE. 2016;11(3):e0151834. doi: 10.1371/journal.pone.0151834 26999614
27. Baldassarre G, Nolfi S, Parisi D. Evolving mobile robots able to display collective behaviors. Artificial Life. 2003;9(3):255–267. doi: 10.1162/106454603322392460 14556687
28. Groß R, Dorigo M. Evolution of solitary and group transport behaviors for autonomous robots capable of self-assembling. Adaptive Behavior. 2008;16(5):285–305. doi: 10.1177/1059712308090537
29. Zaera N, Cliff D, Bruten J. (Not) evolving collective behaviours in synthetic fish. In: In Proceedings of International Conference on the Simulation of Adaptive Behavior. MIT Press, Cambridge, MA; 1996. p. 635–642.
30. Ferrante E, Turgut AE, Huepe C, Stranieri A, Pinciroli C, Dorigo M. Self-organized flocking with a mobile robot swarm: a novel motion control method. Adaptive Behavior. 2012;20(6):460–477. doi: 10.1177/1059712312462248
31. Nembrini J. Minimalist coherent swarming of wireless networked autonomous mobile robots. University of the West of England; 2005.
32. Hauert S, Leven S, Varga M, Ruini F, Cangelosi A, Zufferey JC, et al. Reynolds flocking in reality with fixed-wing robots: communication range vs. maximum turning rate. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. IEEE; 2011. p. 5015–5020.
33. Ward CR, Gobet F, Kendall G. Evolving collective behavior in an artificial ecology. Artificial Life. 2001;7(2):191–209. doi: 10.1162/106454601753139005 11580880
34. Witkowski O, Ikegami T. Emergence of swarming behavior: foraging agents evolve collective motion based on signaling. PLoS ONE. 2016;11(4):e0152756. doi: 10.1371/journal.pone.0152756 27119340
35. Kwasnicka H, Markowska-Kaczmar U, Mikosik M. Flocking behaviour in simple ecosystems as a result of artificial evolution. Applied Soft Computing. 2011;11(1):982–990. doi: 10.1016/j.asoc.2010.01.018
36. Olson RS, Hintze A, Dyer FC, Knoester DB, Adami C. Predator confusion is sufficient to evolve swarming behaviour. Journal of The Royal Society Interface. 2013;10(85):20130305. doi: 10.1098/rsif.2013.0305
37. Olson RS, Knoester DB, Adami C. Evolution of swarming behavior is shaped by how predators attack. Artificial Life. 2016;22(3):299–318. doi: 10.1162/ARTL_a_00206 27139941
38. Demšar J, Bajec IL. Evolution of Collective Behaviour in an Artificial World Using Linguistic Fuzzy Rule-Based Systems. PLoS ONE. 2017;12(1):1–20.
39. Vásárhelyi G, Virágh C, Somorjai G, Nepusz T, Eiben AE, Vicsek T. Optimized flocking of autonomous drones in confined environments. Science Robotics. 2018;3(20):eaat3536. doi: 10.1126/scirobotics.aat3536
40. Duarte M, Silva F, Rodrigues T, Oliveira SM, Christensen AL. JBotEvolver: A versatile simulation platform for evolutionary robotics. In: Proceedings of the 14th International Conference on the Synthesis & Simulation of Living Systems. MIT Press, Cambridge, MA; 2014. p. 210–211.
41. Ramos RP, Oliveira S, Christensen AL. Code, configuration files and results; 2019. Available from: https://github.com/RitaRamo/flocking-evolver/tree/rita/JBotRita/experiments.
42. Nelson AL, Barlow GJ, Doitsidis L. Fitness functions in evolutionary robotics: A survey and analysis. Robotics and Autonomous Systems. 2009;57(4):345–370. doi: 10.1016/j.robot.2008.09.009
43. Beer RD, Gallagher JC. Evolving dynamical neural networks for adaptive behavior. Adaptive behavior. 1992;1(1):91–122. doi: 10.1177/105971239200100105
44. Reynolds C. Webpage of Craig Reynolds. Boids: Background and Update; 2001. http://www.red3d.com/cwr/boids/, visited 2019-03-13.
45. Vicsek T, Czirók A, Ben-Jacob E, Cohen I, Shochet O. Novel type of phase transition in a system of self-driven particles. Physical Review Letters. 1995;75(6):1226–1229. doi: 10.1103/PhysRevLett.75.1226 10060237
46. Waibel M, Keller L, Floreano D. Genetic team composition and level of selection in the evolution of cooperation. IEEE Transactions on Evolutionary Computation. 2009;13(3):648–660. doi: 10.1109/TEVC.2008.2011741
47. Hauert S, Mitri S, Keller L, Floreano D. Evolving cooperation: From biology to engineering. MIT press; 2014.
48. Cavagna A, Cimarelli A, Giardina I, Parisi G, Santagati R, Stefanini F, et al. Scale-free correlations in starling flocks. Proceedings of the National Academy of Sciences. 2010;107(26):11865–11870. doi: 10.1073/pnas.1005766107
49. Huepe C, Ferrante E, Wenseleers T, Turgut AE. Scale-free correlations in flocking systems with position-based interactions. Journal of Statistical Physics. 2015;158(3):549–562. doi: 10.1007/s10955-014-1114-8
50. Fine BT, Shell DA. Unifying microscopic flocking motion models for virtual, robotic, and biological flock members. Autonomous Robots. 2013;35(2-3):195–219. doi: 10.1007/s10514-013-9338-z
51. Lee D, Spong MW. Stable flocking of multiple inertial agents on balanced graphs. IEEE Transactions on Automatic Control. 2007;52(8):1469–1475. doi: 10.1109/TAC.2007.902752
52. Attanasi A, Cavagna A, Del Castello L, Giardina I, Grigera TS, Jelić A, et al. Information transfer and behavioural inertia in starling flocks. Nature Physics. 2014;10(9):691. doi: 10.1038/nphys3035
Článok vyšiel v časopise
PLOS One
2019 Číslo 10
- Metamizol jako analgetikum první volby: kdy, pro koho, jak a proč?
- Parazitičtí červi v terapii Crohnovy choroby a dalších zánětlivých autoimunitních onemocnění
- Nejasný stín na plicích – kazuistika
- Masturbační chování žen v ČR − dotazníková studie
- Eliquis (apixaban) nově hrazen ze zdravotního pojištění
Najčítanejšie v tomto čísle
- Correction: Low dose naltrexone: Effects on medication in rheumatoid and seropositive arthritis. A nationwide register-based controlled quasi-experimental before-after study
- Combining CDK4/6 inhibitors ribociclib and palbociclib with cytotoxic agents does not enhance cytotoxicity
- Risk factors associated with IgA vasculitis with nephritis (Henoch–Schönlein purpura nephritis) progressing to unfavorable outcomes: A meta-analysis
- Prevalence of pectus excavatum (PE), pectus carinatum (PC), tracheal hypoplasia, thoracic spine deformities and lateral heart displacement in thoracic radiographs of screw-tailed brachycephalic dogs