Abstract
Creatures in the real world constantly encounter new and diverse challenges they have never seen before. They will often need to adapt to some of these tasks and solve them in order to survive. This almost endless world of novel challenges is not as common in virtual environments, where artificially evolving agents often have a limited set of tasks to solve. An exception to this is the field of open-endedness where the goal is to create unbounded exploration of interesting artefacts. We want to move one step closer to creating simulated environments similar to the diverse real world, where agents can both find solvable tasks, and adapt to them. Through the use of MAP-Elites we create a structured repertoire, a map, of terrains and virtual creatures that locomote through them. By using novelty as a dimension in the grid, the map can continuously develop to encourage exploration of new environments. The agents must adapt to the environments found, but can also search for environments within each cell of the grid to find the one that best fits their set of skills. Our approach combines the structure of MAP-Elites, which can allow the virtual creatures to use adjacent cells as stepping stones to solve increasingly difficult environments, with open-ended innovation. This leads to a search that is unbounded, but still has a clear structure. We find that while handcrafted bounded dimensions for the map lead to quicker exploration of a large set of environments, both the bounded and unbounded approach manage to solve a diverse set of terrains.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Source code is available at https://github.com/EmmaStensby/environment-map.
- 2.
References
Auerbach, J.E., Bongard, J.C.: Environmental influence on the evolution of morphological complexity in machines. PLoS Comput. Biol. 10(1), e1003399 (2014)
Bongard, J.C.: Morphological and environmental scaffolding synergize when evolving robot controllers: artificial life/robotics/evolvable hardware. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. In: GECCO 2011, pp. 179–186. Association for Computing Machinery, Dublin (2011)
Bossens, D.M., Mouret, J.-B., Tarapore, D.: Learning behaviour-performance maps with meta-evolution. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 49–57 (2020)
Brockman, G., et al.: OpenAI Gym (2016)
Catto, E.: Box2D (2019)
Chatzilygeroudis, K., Cully, A., Vassiliades, V., Mouret, J.-B.: Quality-diversity optimization: a novel branch of stochastic optimization. In: Pardalos, P.M., Rasskazova, V., Vrahatis, M.N. (eds.) Black Box Optimization, Machine Learning, and No-Free Lunch Theorems. SOIA, vol. 170, pp. 109–135. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-66515-9_4
Cheney, N., et al.: Scalable co-optimization of morphology and control in embodied machines. J. Roy. Soc. Interface 15(143), 20170937 (2018)
Cully, A.: Autonomous skill discovery with quality-diversity and unsupervised descriptors. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO 2019, pp. 81–89. Association for Computing Machinery, Prague (2019)
Cully, A., et al.: Robots that can adapt like animals. Nature 521(7553), 503–507 (2015)
Gaier, A., Asteroth, A., Mouret, J.-B.: Are quality diversity algorithms better at generating stepping stones than objective-based search?. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion. GECCO 2019, pp. 115–116. Association for Computing Machinery, Prague (2019)
Hinton, G.E., Salakhutdinov, R.R.: Reducing the dimensionality of data with neural networks. In: Science 313(5786), 504–507 (2006)
Lehman, J., Stanley, K.O.: Abandoning objectives: evolution through the search for novelty alone. Evol. Comput. 19(2), 189–223 (2011)
Lehman, J., Stanley, K.O.: Evolving a diversity of virtual creatures through novelty search and local competition. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. GECCO 2011, pp. 211–218. Association for Computing Machinery, Dublin (2011)
Lipson, H., et al.: On the difficulty of co-optimizing morphology and control in evolved virtual creatures. In: Artificial Life Conference Proceedings 13, pp. 226–233. MIT Press (2016)
Miras, K., Ferrante, E., Eiben, A.E.: Environmental influences on evolvable robots. PloS ONE 15(5), e0233848 (2020)
Mouret, J.-B., Clune, J.: Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909 (2015)
Nordmoen, J., et al.: MAP-elites enables powerful stepping stones and diversity for modular robotics. Front. Robot. AI 8, 56 (2021)
Stanley, K.O.: Compositional pattern producing networks: a novel abstraction of development. Genet. Program. Evolv. Mach. 8(2), 131–162 (2007)
Stanley, K.O.: Why open-endedness matters. Artif. Life 25(3), 232–235 (2019)
Taylor, T., et al.: Open-ended evolution: perspectives from the OEE workshop in York. Artif. Life 22(3), 408–423 (2016)
Open Ended Learning Team, et al.: Open-ended learning leads to generally capable agents. arXiv preprint arXiv:2107.12808 (2021)
Veenstra, F., Glette, K.: How different encodings affect performance and diversification when evolving the morphology and control of 2D virtual creatures. In: Artificial Life Conference Proceedings, vol. 32, pp. 592–601 (2020)
Wang, R., et al.: Enhanced POET: open-ended reinforcement learning through unbounded invention of learning challenges and their solutions. In: International Conference on Machine Learning, pp. 9940–9951. PMLR (2020)
Wang, R., et al.: POET: open-ended coevolution of environments and their optimized solutions. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO 2019, pp. 142–151. Association for Computing Machinery, Prague (2019)
Zhao, A., et al.: RoboGrammar: graph grammar for terrain-optimized robot design. ACM Trans. Graph. (TOG) 39(6), 1–16 (2020)
Acknowledgments
This work was partially supported by the Research Council of Norway through its Centres of Excellence scheme, project number 262762. The simulations were performed on resources provided by UNINETT Sigma2 - the National Infrastructure for High Performance Computing and Data Storage in Norway. Thank you to Frank Veenstra for support using the 2D simulator for modular robots.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Norstein, E.S., Ellefsen, K.O., Glette, K. (2022). Open-Ended Search for Environments and Adapted Agents Using MAP-Elites. In: Jiménez Laredo, J.L., Hidalgo, J.I., Babaagba, K.O. (eds) Applications of Evolutionary Computation. EvoApplications 2022. Lecture Notes in Computer Science, vol 13224. Springer, Cham. https://doi.org/10.1007/978-3-031-02462-7_41
Download citation
DOI: https://doi.org/10.1007/978-3-031-02462-7_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-02461-0
Online ISBN: 978-3-031-02462-7
eBook Packages: Computer ScienceComputer Science (R0)