Embodied evolutionary robotics is a sub-field of evolutionary robotics that employs evolutionary algorithms on the robotic hardware itself, during the operational period, i.e., in an on-line fashion. This enables robotic systems that continuously adapt, and are therefore capable of (re-)adjusting themselves to previously unknown or dynamically changing conditions autonomously, without human oversight. This paper addresses one of the major challenges that such systems face, viz. that the robots must satisfy two sets of requirements. Firstly, they must continue to operate reliably in their environment (viability), and secondly they must competently perform user-specified tasks (usefulness). The solution we propose exploits the fact that evolutionary methods have two basic selection mechanisms–survivor selection and parent selection. This allows evolution to tackle the two sets of requirements separately: survivor selection is driven by the environment and parent selection is based on task-performance. This idea is elaborated in the Multi-Objective aNd open-Ended Evolution (monee) framework, which we experimentally validate. Experiments with robotic swarms of 100 simulated e-pucks show that monee does indeed promote task-driven behaviour without compromising environmental adaptation. We also investigate an extension of the parent selection process with a ‘market mechanism’ that can ensure equitable distribution of effort over multiple tasks, a particularly pressing issue if the environment promotes specialisation in single tasks.
References
[1]
Nolfi S, Floreano D (2000) Evolutionary Robotics: The Biology, Intelligence, and Technology of Self-Organizing Machines. Cambridge, MA: MIT Press/Bradford Books.
[2]
Watson RA, Ficici SG, Pollack JB (2002) Embodied evolution: Distributing an evolutionary algorithm in a population of robots. Robotics and Autonomous Systems 39: 1–18. doi: 10.1016/s0921-8890(02)00170-7
[3]
Usui Y, Arita T (2003) Situated and Embodied Evolution in Collective Evolutionary Robotics. In: Proceedings of the 8th International Symposium on Artificial Life and Robotics. c, 1–4.
[4]
Bianco R, Nolfi S (2004) Toward open-ended evolutionary robotics: evolving elementary robotic units able to self-assemble and self-reproduce. Connection Science 16: 227–248. doi: 10.1080/09540090412331314759
[5]
Schwarzer C, Schlachter F, Michiels NK (2011) Online evolution in dynamic environments using neural networks in autonomous robots. International Journal On Advances in Intelligent Systems 4: 288–298.
[6]
Wischmann S, Stamm K, Florentin W (2007) Embodied Evolution and Learning: The Neglected Timing of Maturation. Advances in Artificial Life: 9th European Conference on Artificial Life, LNAI: 284–293.
[7]
Elfwing S, Uchibe E, Doya K, Christensen HI (2011) Darwinian embodied evolution of the learning ability for survival. Adaptive Behavior 19: 101–120. doi: 10.1177/1059712310397633
[8]
Darwin C (1859) On the Origin of Species. John Murray.
[9]
Eiben AE, Smith JE (2007) Introduction to Evolutionary Computing. Springer.
[10]
Prieto A, Becerra J, Bellas F, Duro R (2010) Open-ended evolution as a means to self-organize heterogeneous multi-robot systems in real time. Robotics and Autonomous Systems 58: 1282–1291. doi: 10.1016/j.robot.2010.08.004
[11]
Weel B, Hoogendoorn M, Eiben A (2012) On-line evolution of controllers for aggregating swarm robots in changing environments. In: Coello CAC, Cutello V, Deb K, Forrest S, Nicosia G, et al., editors, PPSN. Springer, volume 7491–7492, 245–254.
[12]
Eiben AE, Smith JE (2003) Introduction to Evolutionary Computing. Springer.
[13]
Bedau MA, McCaskill JS, Packard NH, Rasmussen S, Adami C, et al. (2000) Open problems in artificial life. Artificial Life 6: 363–376. doi: 10.1162/106454600300103683
[14]
Ray TS (1992) Synthetic life: Evolution and optimization of digital organisms. In: Billingsley KR, Iii BHU, Derohanes E, editors, Scientific Excellence in Supercomputing: The 1990 IBM Contest Prize Papers. 489–531.
[15]
Rasmussen S, Carsten K, Feldberg P, Hindsholm M (1990) Is it alive, or is it ga? Physica D 42: 111–134. doi: 10.1016/0167-2789(90)90070-6
[16]
Adami C, Brown TC (1994) Evolutionary learning in the 2d artificial life system avida. In: Proceedings of Artificial Life IV: 377–381.
[17]
Yaeger L (1994) polyworld: life in a new context. In: Artificial Life III. 1, 1–25.
[18]
Lenski RE, Ofria C, Collier TC, Adami C (1999) Genome complexity, robustness and genetic interactions in digital organisms. Nature 400: 661–4. doi: 10.1038/23245
[19]
Spector L, Klein J, Feinstein M (2007) Division blocks and the open-ended evolution of development, form, and behavior. In: Proceedings of the 9th annual conference on Genetic and evolutionary computation. ACM, 316–323.
[20]
Yaeger LS, Griffith V, Sporns O (2008) Passive and driven trends in the evolution of complexity. In: Proceedings of Artificial Life XI: 725–732.
[21]
Bredeche N, Montanier JM, Wenguo L, Winfield AF (2012) Environment-driven Distributed Evolutionary Adaptation in a Population of Autonomous Robotic Agents. Mathematical and Computer Modelling of Dynamical Systems 18.
[22]
Jones C, Mataric M (2003) Adaptive division of labor in large-scale minimalist multi-robot systems. In: Intelligent Robots and Systems, 2003. (IROS 2003). Proceedings. 2003 IEEE/RSJ International Conference on. volume 2, 1969–1974. doi:10.1109/IROS.2003.1248936.
[23]
Walsh W, Wellman M (1998) A market protocol for decentralized task allocation. In: Multi Agent Systems, 1998. Proceedings. International Conference on. 325–332. doi:10.1109/ICMAS.1998.699077.
[24]
Tang F, Parker L (2007) A complete methodology for generating multi-robot task solutions using asymtre-d and market-based task allocation. In: Robotics and Automation, 2007 IEEE International Conference on. 3351–3358. doi:10.1109/ROBOT.2007.363990.
[25]
Bredeche N, Montanier JM, Liu W, Winfield AF (2012) Environment-driven distributed evolutionary adaptation in a population of autonomous robotic agents. Mathematical and Computer Modelling of Dynamical Systems 18: 101–129. doi: 10.1080/13873954.2011.601425
[26]
Mascaro S, Korb K, Nicholson A (2005) An alife investigation on the origins of dimorphic parental investments. In: Abbass HA, Bossomaier T, Wiles J, editors, Advances in Natural Computation, Proceedings of the Australian Conference on Artificial Life (ACAL 2005). volume 3, 171–185.
[27]
Ventrella J (2005) Genepool: Exploring the interaction between natural selection and sexual selection. Artificial Life Models in Software: 81–96.
[28]
Schwarzer C, H？sler C, Michiels N (2010) Artificial sexuality and reproduction of robot organisms. In: Levi P, Kernbach S, editors, Symbiotic Multi-Robot Organisms: Reliability, Adaptability, Evolution, Berlin–Heidelberg–New York: Springer–Verlag. 384–403. URL http://www.springer.com/engineering/math？ematical/book/978-3-642-11691-9.
[29]
Menczer F, Belew R (1996) Latent energy environments. In: Santa Fe Institute Studies In The Sciences Of Complexity-Proceedings Volume-. volume 26, 191–210.
[30]
Menczer F, Willuhn W, Belew R (1994) An endogenous fitness paradigm for adaptive information agents. In: CIKM Workshop on Intelligent Information Agents. Citeseer.
[31]
Burtsev M, Red’ko V, Gusarev R (2001) Model of evolutionary emergence of purposeful adaptive behavior. the role of motivation. In: Kelemen J, Sosík P, editors, ECAL. Springer, volume 2159 of Lecture Notes in Computer Science, 413–416.
[32]
Scheutz M, Schermerhorn P (2005) Predicting population dynamics and evolutionary trajectories based on performance evaluations in alife simulations. In: Beyer HG, O’Reilly UM, editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2005). ACM, ACM, 35–42.
[33]
Nguyen Q, Nguyen X, O’Neill M, Agapitos A (2012) An investigation of fitness sharing with semantic and syntactic distance metrics. In: Moraglio A, Silva S, Krawiec K, Machado P, Cotta C, editors, Genetic Programming, Springer Berlin Heidelberg, volume 7244 of Lecture Notes in Computer Science. 109–120.
[34]
Bredeche N, Montanier JM, Weel B, Haasdijk E (2013) Roborobo! a fast robot simulator for swarm and collective robotics. CoRR abs/1304.2888.
[35]
Beyer HG, Schwefel HP (2002) Evolution strategies – A comprehensive introduction. Natural Computing 1: 3–52.
[36]
Fisher RA (1925) Theory of statistical estimation. Mathematical Proceedings of the Cambridge Philosophical Society 22: 700–725. doi: 10.1017/s0305004100009580
