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
doi: 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:

Artificial neural networks – Collective animal behavior – Foraging – Inertia – Predation – Robotic behavior – Robotics – Robots


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ánek vyšel v časopise

PLOS One


2019 Číslo 10