2022

Augmentative Topology Agents For Open-Ended Learning

Nasir, Muhammad Umair, Beukman, Michael, James, Steven et al.

Understand

In this work, we tackle the problem of open-ended learning by introducing a method that simultaneously evolves agents and increasingly challenging environments.

Unlike previous open-ended approaches that optimize agents using a fixed neural network topology, we hypothesize that generalization can be improved by allowing agents' controllers to become more complex as they encounter more difficult environments.
Our method, Augmentative Topology EPOET (ATEP), extends the Enhanced Paired Open-Ended Trailblazer (EPOET) algorithm by allowing agents to evolve their own neural network structures over time, adding complexity and capacity as necessary.
Empirical results demonstrate that ATEP results in general agents capable of solving more environments than a fixed-topology baseline.

Built on

M. J. Kusner, B. Paige, and J. M. Hernández-Lobato, “Grammar variational autoencoder,” in International Conference on Machine Learning , 2017, pp. 1945–1954
1954
Earlier work this paper cites.
D. J. Montana, L. Davis et al. , “Training feedforward neural networks using genetic algorithms.” in International Joint Conference on Artificial Intelligence , vol. 89, 1989, pp. 762–767
1989
Earlier work this paper cites.
T. S. Ray, “An approach to the synthesis of life,” Artificial life II , pp. 371–408, 1991
1991
Earlier work this paper cites.
N. J. Radcliffe, “Genetic set recombination and its application to neural network topology optimisation,” Neural Computing & Applications , vol. 1, no. 1, pp. 67–90, 1993
1993
Earlier work this paper cites.
S. W. Mahfoud, “Niching methods for genetic algorithms,” Ph.D. dissertation, University of Illinois at Urbana-Champaign, 1995
1995
Earlier work this paper cites.
K. O. Stanley and R. Miikkulainen, “Evolving neural networks through augmenting topologies,” Evolutionary computation , vol. 10, no. 2, pp. 99–127, 2002
2002
Earlier work this paper cites.
C. Ofria and C. O. Wilke, “Avida: A software platform for research in computational evolutionary biology,” Artificial life , vol. 10, no. 2, pp. 191–229, 2004
2004
Earlier work this paper cites.
L. S. Yaeger and O. Sporns, “Evolution of neural structure and complexity in a computational ecology,” in Artificial Life X: Proceedings of the Tenth International Conference on the Simulation and Synthesis of Living Systems , 2006, pp. 330–336
2006
Earlier work this paper cites.
L. Spector, J. Klein, and M. Feinstein, “Division blocks and the open-ended evolution of development, form, and behavior,” in Proceedings of the Genetic and Evolutionary Computation Conference , 2007, pp. 316–323
2007
Earlier work this paper cites.
K. O. Stanley, “Compositional pattern producing networks: A novel abstraction of development,” Genetic programming and evolvable machines , vol. 8, no. 2, pp. 131–162, 2007
2007
Earlier work this paper cites.
J. Lehman, K. O. Stanley et al. , “Exploiting open-endedness to solve problems through the search for novelty.” in ALIFE , 2008, pp. 329–336
2008
Earlier work this paper cites.
K. O. Stanley, D. B. D’Ambrosio, and J. Gauci, “A hypercube-based encoding for evolving large-scale neural networks,” Artificial life , vol. 15, no. 2, pp. 185–212, 2009
2009
Earlier work this paper cites.
J. Lehman and K. O. Stanley, “Evolving a diversity of virtual creatures through novelty search and local competition,” in Proceedings of the Genetic and Evolutionary Computation Conference , 2011, pp. 211–218
2011
Earlier work this paper cites.
S. C. Duncan, “Minecraft, beyond construction and survival,” 2011
2011
Earlier work this paper cites.
A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional neural networks,” in Advances in Neural Information Processing Systems , 2012, pp. 1106–1114
2012
Earlier work this paper cites.
K. Khetarpal, M. Riemer, I. Rish, and D. Precup, “Towards continual reinforcement learning: A review and perspectives,” CoRR , vol. abs/2012.13490, 2020. [Online]. Available: https://arxiv.org/abs/2012.13490
Original
2012
Earlier work this paper cites.
L. Soros and K. Stanley, “Identifying necessary conditions for open-ended evolution through the artificial life world of chromaria,” in ALIFE 14: The Fourteenth International Conference on the Synthesis and Simulation of Living Systems , 2014, pp. 793–800
2014
Earlier work this paper cites.
M. Cipollone, C. C. Schifter, and R. A. Moffat, “Minecraft as a creative tool: A case study,” International Journal of Game-Based Learning (IJGBL) , vol. 4, no. 2, pp. 1–14, 2014
2014
Earlier work this paper cites.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski et al. , “Human-level control through deep reinforcement learning,” nature , vol. 518, no. 7540, pp. 529–533, 2015
2015
Earlier work this paper cites.
J.-B. Mouret and J. Clune, “Illuminating search spaces by mapping elites,” arXiv preprint arXiv:1504.04909 , 2015
Original
2015
Earlier work this paper cites.
A. Cully, J. Clune, D. Tarapore, and J.-B. Mouret, “Robots that can adapt like animals,” Nature , vol. 521, no. 7553, pp. 503–507, 2015
2015
Earlier work this paper cites.
D. Tarapore, J. Clune, A. Cully, and J.-B. Mouret, “How do different encodings influence the performance of the map-elites algorithm?” in Proceedings of the Genetic and Evolutionary Computation Conference , 2016, pp. 173–180
2016
Earlier work this paper cites.
F. Sadeghi and S. Levine, “Cad2rl: Real single-image flight without a single real image,” arXiv preprint arXiv:1611.04201 , 2016
Original
2016
Earlier work this paper cites.
X. Chen, D. P. Kingma, T. Salimans, Y. Duan, P. Dhariwal, J. Schulman, I. Sutskever, and P. Abbeel, “Variational lossy autoencoder,” arXiv preprint arXiv:1611.02731 , 2016
Original
2016
Earlier work this paper cites.
A. A. Rusu, N. C. Rabinowitz, G. Desjardins, H. Soyer, J. Kirkpatrick, K. Kavukcuoglu, R. Pascanu, and R. Hadsell, “Progressive neural networks,” CoRR , vol. abs/1606.04671, 2016. [Online]. Available: http://arxiv.org/abs/1606.04671
Original
2016
Earlier work this paper cites.

Similar

Z. Li and D. Hoiem, “Learning without forgetting,” vol. 9908, pp. 614–629, 2016. [Online]. Available: https://doi.org/10.1007/978-3-319-46493-0_37
2016
Cited alongside, same era.
G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, “OpenAI gym,” arXiv preprint arXiv:1606.01540 , 2016
Original
2016
Cited alongside, same era.
D. Gravina, A. Liapis, and G. Yannakakis, “Surprise search: Beyond objectives and novelty,” in Proceedings of the Genetic and Evolutionary Computation Conference 2016 , 2016, pp. 677–684
2016
Cited alongside, same era.
K. O. Stanley, J. Lehman, and L. Soros, “Open-endedness: The last grand challenge you’ve never heard of,” O’Reilly Online , 2017. [Online]. Available: https://www.oreilly.com/ideas/open-endedness-the-last-grand-challenge-youve-never-heard-of
2017
Cited alongside, same era.
J. C. Brant and K. O. Stanley, “Minimal criterion coevolution: a new approach to open-ended search,” in Proceedings of the Genetic and Evolutionary Computation Conference , 2017, pp. 67–74
2017
Cited alongside, same era.
T. Salimans, J. Ho, X. Chen, S. Sidor, and I. Sutskever, “Evolution strategies as a scalable alternative to reinforcement learning,” arXiv preprint arXiv:1703.03864 , 2017
Original
2017
Cited alongside, same era.
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” arXiv preprint arXiv:1707.06347 , 2017
Original
2017
Cited alongside, same era.
T. J. Draelos, N. E. Miner, C. C. Lamb, J. A. Cox, C. M. Vineyard, K. D. Carlson, W. M. Severa, C. D. James, and J. B. Aimone, “Neurogenesis deep learning: Extending deep networks to accommodate new classes,” in 2017 International Joint Conference on Neural Networks (IJCNN) . IEEE, 2017, pp. 526–533
2017
Cited alongside, same era.
D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel et al. , “A general reinforcement learning algorithm that masters chess, shogi, and go through self-play,” Science , vol. 362, no. 6419, pp. 1140–1144, 2018
2018
Cited alongside, same era.
A. Khalifa, S. Lee, A. Nealen, and J. Togelius, “Talakat: Bullet hell generation through constrained map-elites,” in Proceedings of The Genetic and Evolutionary Computation Conference , 2018, pp. 1047–1054
2018
Cited alongside, same era.
A. Abdolmaleki, J. T. Springenberg, J. Degrave, S. Bohez, Y. Tassa, D. Belov, N. Heess, and M. Riedmiller, “Relative entropy regularized policy iteration,” arXiv preprint arXiv:1812.02256 , 2018
Original
2018
Cited alongside, same era.
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever et al. , “Language models are unsupervised multitask learners,” OpenAI blog , vol. 1, no. 8, p. 9, 2019
2019
Cited alongside, same era.

Then

J. Schrum, V. Volz, and S. Risi, “CPPN2GAN: Combining compositional pattern producing networks and gans for large-scale pattern generation,” in Proceedings of the Genetic and Evolutionary Computation Conference , 2020, p. 139–147
2020
Later among the works it cites.
T. Schick and H. Schütze, “It’s not just size that matters: Small language models are also few-shot learners,” in Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies , 2021, pp. 2339–2352
2021
Later among the works it cites.
A. Quessy and T. S. Richardson, “Rewardless open-ended learning (ROEL),” 2021
2021
Later among the works it cites.
L. Gisslén, A. Eakins, C. Gordillo, J. Bergdahl, and K. Tollmar, “Adversarial reinforcement learning for procedural content generation,” in 2021 IEEE Conference on Games . IEEE, 2021, pp. 1–8
2021
Later among the works it cites.
O. E. L. Team, A. Stooke, A. Mahajan, C. Barros, C. Deck, J. Bauer, J. Sygnowski, M. Trebacz, M. Jaderberg, M. Mathieu et al. , “Open-ended learning leads to generally capable agents,” arXiv preprint arXiv:2107.12808 , 2021
Original
2021
Later among the works it cites.
O. Nilsson and A. Cully, “Policy gradient assisted map-elites,” in Proceedings of the Genetic and Evolutionary Computation Conference , 2021, pp. 866–875
2021
Later among the works it cites.
E. H. Stensby, K. O. Ellefsen, and K. Glette, “Co-optimising robot morphology and controller in a simulated open-ended environment,” in International Conference on the Applications of Evolutionary Computation , 2021, pp. 34–49
2021
Later among the works it cites.
M. Jiang, E. Grefenstette, and T. Rocktäschel, “Prioritized level replay,” in International Conference on Machine Learning , 2021, pp. 4940–4950
2021
Later among the works it cites.
C. Gan, A. Bhandwaldar, A. Torralba, J. B. Tenenbaum, and P. Isola, “Open: An open-ended physics environment for learning without a task,” in 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) . IEEE, 2021, pp. 5878–5885
2021
Later among the works it cites.
S. Earle, J. Snider, M. C. Fontaine, S. Nikolaidis, and J. Togelius, “Illuminating diverse neural cellular automata for level generation,” in Proceedings of the Genetic and Evolutionary Computation Conference , 2022, pp. 68–76
2022
Closest in time.
A. Dharna, A. K. Hoover, J. Togelius, and L. Soros, “Transfer dynamics in emergent evolutionary curricula,” IEEE Transactions on Games , 2022
2022
Closest in time.
R. Meier and A. Mujika, “Open-ended reinforcement learning with neural reward functions,” arXiv preprint arXiv:2202.08266 , 2022
Original
2022
Closest in time.
F. Zhou and J. Vanschoren, “Open-ended learning strategies for learning complex locomotion skills,” arXiv preprint arXiv:2206.06796 , 2022
Original
2022
Closest in time.
E. S. Norstein, K. O. Ellefsen, and K. Glette, “Open-ended search for environments and adapted agents using map-elites,” in International Conference on the Applications of Evolutionary Computation (Part of EvoStar) . Springer, 2022, pp. 651–666
2022
Closest in time.
J. Parker-Holder, M. Jiang, M. Dennis, M. Samvelyan, J. Foerster, E. Grefenstette, and T. Rocktäschel, “Evolving curricula with regret-based environment design,” arXiv preprint arXiv:2203.01302 , 2022
Original
2022
Closest in time.
M. Barthet, A. Liapis, and G. N. Yannakakis, “Open-ended evolution for Minecraft building generation,” IEEE Transactions on Games , 2022
2022
Closest in time.
L. Fan, G. Wang, Y. Jiang, A. Mandlekar, Y. Yang, H. Zhu, A. Tang, D.-A. Huang, Y. Zhu, and A. Anandkumar, “Minedojo: Building open-ended embodied agents with internet-scale knowledge,” arXiv preprint arXiv:2206.08853 , 2022
Original
2022
Closest in time.
M. L. Clei and P. Bellec, “Neuroevolution of recurrent architectures on control tasks,” in Genetic and Evolutionary Computation Conference, Companion Volume , J. E. Fieldsend and M. Wagner, Eds., 2022, pp. 651–654
2022
Closest in time.
V. Bhatt, B. Tjanaka, M. C. Fontaine, and S. Nikolaidis, “Deep surrogate assisted generation of environments,” CoRR , vol. abs/2206.04199, 2022. [Online]. Available: https://doi.org/10.48550/arXiv.2206.04199
Original
2022
Closest in time.
K. Maile, E. Rachelson, H. Luga, and D. G. Wilson, “When, where, and how to add new neurons to ANNs,” arXiv preprint arXiv:2202.08539 , 2022
Original
2022
Closest in time.
M. U. Nasir, S. Earle, J. Togelius, S. James, and C. Cleghorn, “Llmatic: Neural architecture search via large language models and quality-diversity optimization,” arXiv preprint arXiv:2306.01102 , 2023
Original
2023
Closest in time.
G. Todd, S. Earle, M. U. Nasir, M. C. Green, and J. Togelius, “Level generation through large language models,” in Proceedings of the 18th International Conference on the Foundations of Digital Games , 2023, pp. 1–8
2023
Closest in time.
M. U. Nasir and J. Togelius, “Practical pcg through large language models,” arXiv preprint arXiv:2305.18243 , 2023
Original
2023
Closest in time.
M. Beukman, M. Fokam, M. Kruger, G. Axelrod, M. Nasir, B. Ingram, B. Rosman, and S. James, “Hierarchically composing level generators for the creation of complex structures,” arXiv preprint arXiv:2302.01561 , 2023
Original
2023
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…