List of papers

167 papers are listed.

You can click on each title to display more information, including authors, url to pdf, abstract and bibtex.

2022: 18 Papers

Accelerated Quality-Diversity through Massive Parallelism
Authors:
- Bryan Lim
- Maxime Allard
- Luca Grillotti
- Antoine Cully
Links:
- Paper

Approximating Gradients for Differentiable Quality Diversity in Reinforcement Learning Robotics

Authors:

Bryon Tjanaka

Matthew Fontaine

Julian Togelius

Stefanos Nikolaidis

Abstract:
Consider a walking agent that must adapt to damage. To approach this task, we can train a collection of policies and have the agent select a suitable policy when damaged. Training this collection may be viewed as a quality diversity (QD) optimization problem, where we search for solutions (policies) which maximize an objective (walking forward) while spanning a set of measures (measurable characteristics). Recent work shows that differentiable quality diversity (DQD) algorithms greatly accelerate QD optimization when exact gradients are available for the objective and measures. However, such gradients are typically unavailable in RL settings due to non-differentiable environments. To apply DQD in RL settings, we propose to approximate objective and measure gradients with evolution strategies and actor-critic methods. We develop two variants of the DQD algorithm CMA-MEGA, each with different gradient approximations, and evaluate them on four simulated walking tasks. One variant achieves comparable performance (QD score) with the state-of-the-art PGA-MAP-Elites in two tasks. The other variant performs comparably in all tasks but is less efficient than PGA-MAP-Elites in two tasks. These results provide insight into the limitations of CMA-MEGA in domains that require rigorous optimization of the objective and where exact gradients are unavailable.
Links:

Paper

Webpage

Bibtex:
"@inproceedings{10.1145/3512290.3528705,
  author = {Tjanaka, Bryon and Fontaine, Matthew C. and Togelius, Julian and Nikolaidis, Stefanos},
  title = {Approximating Gradients for Differentiable Quality Diversity in Reinforcement Learning},
  year = {2022},
  isbn = {9781450392372},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/3512290.3528705},
  doi = {10.1145/3512290.3528705},
  abstract = {Consider the problem of training robustly capable agents. One approach is to generate a diverse collection of agent polices. Training can then be viewed as a quality diversity (QD) optimization problem, where we search for a collection of performant policies that are diverse with respect to quantified behavior. Recent work shows that differentiable quality diversity (DQD) algorithms greatly accelerate QD optimization when exact gradients are available. However, agent policies typically assume that the environment is not differentiable. To apply DQD algorithms to training agent policies, we must approximate gradients for performance and behavior. We propose two variants of the current state-of-the-art DQD algorithm that compute gradients via approximation methods common in reinforcement learning (RL). We evaluate our approach on four simulated locomotion tasks. One variant achieves results comparable to the current state-of-the-art in combining QD and RL, while the other performs comparably in two locomotion tasks. These results provide insight into the limitations of current DQD algorithms in domains where gradients must be approximated. Source code is available at https://github.com/icaros-usc/dqd-rl},
  booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
  pages = {1102–1111},
  numpages = {10},
  keywords = {neuroevolution, reinforcement learning, quality diversity},
  location = {Boston, Massachusetts},
  series = {GECCO '22}
}
"

Automatic Acquisition of a Repertoire of Diverse Grasping Trajectories through Behavior Shaping and Novelty Search
Authors:
- Aur{\'e}lien Morel
- Yakumo Kunimoto
- Alex Coninx
- Stephane Doncieux
Abstract:
Grasping a particular object may require a dedicated grasping movement that may also be specific to the robot end-effector. No generic and autonomous method does exist to generate these movements without making hypotheses on the robot or on the object. Learning methods could help to autonomously discover relevant grasping movements, but they face an important issue: grasping movements are so rare that a learning method based on exploration has little chance to ever observe an interesting movement, thus creating a bootstrap issue. We introduce an approach to generate diverse grasping movements in order to solve this problem. The movements are generated in simulation, for particular object positions. We test it on several simulated robots: Baxter, Pepper and a Kuka Iiwa arm. Although we show that generated movements actually work on a real Baxter robot, the aim is to use this method to create a large dataset to bootstrap deep learning methods.
Links:
- Paper
Bibtex:
```
"
@article{morel2022automatic,
title={Automatic Acquisition of a Repertoire of Diverse Grasping Trajectories through Behavior Shaping and Novelty Search},
author={Morel, Aur{\'e}lien and Kunimoto, Yakumo and Coninx, Alex and Doncieux, St{\'e}phane},
journal={arXiv preprint arXiv:2205.08189},
year={2022}
}
"
```
Benchmarking Quality-Diversity Algorithms on Neuroevolution for Reinforcement Learning
Authors:
- Manon Flageat*
- Bryan Lim*
- Luca Grillotti
- Maxime Allard
- Simón C. Smith
- Antoine Cully
Links:
- Paper
Deep Surrogate Assisted Generation of Environments
Authors:
- Varun Bhatt
- Bryon Tjanaka
- Matthew C. Fontaine
- Stefanos Nikolaidis
Abstract:
Recent progress in reinforcement learning (RL) has started producing generally capable agents that can solve a distribution of complex environments. These agents are typically tested on fixed, human-authored environments. On the other hand, quality diversity (QD) optimization has been proven to be an effective component of environment generation algorithms, which can generate collections of high-quality environments that are diverse in the resulting agent behaviors. However, these algorithms require potentially expensive simulations of agents on newly generated environments. We propose Deep Surrogate Assisted Generation of Environments (DSAGE), a sample-efficient QD environment generation algorithm that maintains a deep surrogate model for predicting agent behaviors in new environments. Results in two benchmark domains show that DSAGE significantly outperforms existing QD environment generation algorithms in discovering collections of environments that elicit diverse behaviors of a state-of-the-art RL agent and a planning agent. Our source code and videos are available at https://dsagepaper.github.io/
Links:
- Paper

Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding Games

Authors:

Yulun Zhang

Matthew Fontaine

Amy Hoover

Stefanos Nikolaidis

Abstract:
We study the problem of efficiently generating high-quality and diverse content in games. Previous work on automated deckbuilding in Hearthstone shows that the quality diversity algorithm MAP-Elites can generate a collection of high-performing decks with diverse strategic gameplay. However, MAP-Elites requires a large number of expensive evaluations to discover a diverse collection of decks. We propose assisting MAP-Elites with a deep surrogate model trained online to predict game outcomes with respect to candidate decks. MAP-Elites discovers a diverse dataset to improve the surrogate model accuracy, while the surrogate model helps guide MAP-Elites towards promising new content. In a Hearthstone deckbuilding case study, we show that our approach improves the sample efficiency of MAP-Elites and outperforms a model trained offline with random decks, as well as a linear surrogate model baseline, setting a new state-of-the-art for quality diversity approaches in automated Hearthstone deckbuilding. We include the source code for all the experiments at: https://github.com/icaros-usc/EvoStone2.
Links:

Paper

Bibtex:
"@inproceedings{10.1145/3512290.3528718,
  author = {Zhang, Yulun and Fontaine, Matthew C. and Hoover, Amy K. and Nikolaidis, Stefanos},
  title = {Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding},
  year = {2022},
  isbn = {9781450392372},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/3512290.3528718},
  doi = {10.1145/3512290.3528718},
  abstract = {We study the problem of efficiently generating high-quality and diverse content in games. Previous work on automated deckbuilding in Hearthstone shows that the quality diversity algorithm MAP-Elites can generate a collection of high-performing decks with diverse strategic gameplay. However, MAP-Elites requires a large number of expensive evaluations to discover a diverse collection of decks. We propose assisting MAP-Elites with a deep surrogate model trained online to predict game outcomes with respect to candidate decks. MAP-Elites discovers a diverse dataset to improve the surrogate model accuracy while the surrogate model helps guide MAP-Elites towards promising new content. In a Hearthstone deck-building case study, we show that our approach improves the sample efficiency of MAP-Elites and outperforms a model trained offline with random decks, as well as a linear surrogate model baseline, setting a new state-of-the-art for quality diversity approaches in automated Hearthstone deckbuilding. We include the source code for all the experiments at: https://github.com/icaros-usc/EvoStone2.},
  booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
  pages = {158–167},
  numpages = {10},
  keywords = {deep neural networks, surrogate modeling, MAP-elites},
  location = {Boston, Massachusetts},
  series = {GECCO '22}
}
"

Efficient Learning of Locomotion Skills through the Discovery of Diverse Environmental Trajectory Generator Priors Robotics
Authors:
- Shikha Surana*
- Bryan Lim*
- Antoine Cully
Links:
- Paper
Evolutionary Diversity Optimization with Clustering-based Selection for Reinforcement Learning Robotics
Authors:
- Yutong Wang
- Ke Xue
- Chao Qian
Abstract:
Reinforcement Learning (RL) has achieved significant successes, which aims to obtain a single policy maximizing the expected cumulative rewards for a given task. However, in many real-world scenarios, e.g., navigating in complex environments and controlling robots, one may need to find a set of policies having both high rewards and diverse behaviors, which can bring better exploration and robust few-shot adaptation. Recently, some methods have been developed by using evolutionary techniques, including iterative reproduction and selection of policies. However, due to the inefficient selection mechanisms, these methods cannot fully guarantee both high quality and diversity. In this paper, we propose EDO-CS, a new Evolutionary Diversity Optimization algorithm with Clustering-based Selection. In each iteration, the policies are divided into several clusters based on their behaviors, and a high-quality policy is selected from each cluster for reproduction. EDO-CS also adaptively balances the importance between quality and diversity in the reproduction process. Experiments on various (i.e., deceptive and multi-modal) continuous control tasks, show the superior performance of EDO-CS over previous methods, i.e., EDO-CS can achieve a set of policies with both high quality and diversity efficiently while previous methods cannot.
Links:
- Paper
- Source-code
Bibtex:
```
"
@inproceedings{
wang2022evolutionary,
title={Evolutionary Diversity Optimization with Clustering-based Selection for Reinforcement Learning},
author={Yutong Wang and Ke Xue and Chao Qian},
booktitle={International Conference on Learning Representations},
year={2022},
url={https://openreview.net/forum?id=74x5BXs4bWD}}
"
```
Few-Shot Quality-Diversity Optimization
Authors:
- Achkan Salehi
- Alexandre Coninx
- Stephane Doncieux
Abstract:
In the past few years,a considerable amount of research has been dedicated to the exploitation of previous learning experiences and the design of Few-shot and Meta Learning approaches, in problem domains ranging from Computer Vision to Reinforcement Learning based control. A notable exception, where to the best of our knowledge, little to no effort has been made in this direction is Quality-Diversity (QD) optimization. QD methods have been shown to be effective tools in dealing with deceptive minima and sparse rewards in Reinforcement Learning. However, they remain costly due to their reliance on inherently sample inefficient evolutionary processes. We show that, given examples from a task distribution, information about the paths taken by optimization in parameter space can be leveraged to build a prior population, which when used to initialize QD methods in unseen environments, allows for few-shot adaptation. Our proposed method does not require backpropagation. It is simple to implement and scale, and furthermore, it is agnostic to the underlying models that are being trained. Experiments carried in both sparse and dense reward settings using robotic manipulation and navigation benchmarks show that it considerably reduces the number of generations that are required for QD optimization in these environments.
Links:
- Paper
Bibtex:
```
"
@article{salehi2022few,
title={Few-Shot Quality-Diversity Optimization},
author={Salehi, Achkan and Coninx, Alexandre and Doncieux, Stephane},
journal={IEEE Robotics and Automation Letters},
volume={7},
number={2},
pages={4424--4431},
year={2022},
publisher={IEEE}
}
"
```
Geodesics, Non-linearities and the Archive of Novelty Search
Authors:
- Achkan Salehi
- Alexandre Coninx
- Stephane Doncieux
Abstract:
The Novelty Search (NS) algorithm was proposed more than a decade ago. However, the mechanisms behind its empirical success are still not well formalized/understood. This short note focuses on the effects of the archive on exploration. Experimental evidence from a few application domains suggests that archive-based NS performs in general better than when Novelty is solely computed with respect to the population. An argument that is often encountered in the literature is that the archive prevents exploration from backtracking or cycling, i.e. from revisiting previously encountered areas in the behavior space. We argue that this is not a complete or accurate explanation as backtracking —beside often being desirable —can actually be enabled by the archive. Through low-dimensional/analytical examples, we show that a key effect of the archive is that it counterbalances the exploration biases that result, among other factors, from the use of inadequate behavior metrics and the non-linearities of the behavior mapping. Our observations seem to hint that attributing a more active role to the archive in sampling can be beneficial.
Links:
- Paper
Bibtex:
```
"
@article{salehi2022geodesics,
title={Geodesics, Non-linearities and the Archive of Novelty Search},
author={Salehi, Achkan and Coninx, Alexandre and Doncieux, Stephane},
journal={In Genetic and Evolutionary Computation Conference Companion (GECCO’22 Companion), July 9–13, 2022, Boston, MA, USA. ACM, New York, NY, USA},
year={2022}
}
"
```
Guided Safe Shooting: model based reinforcement learning with safety constraints
Authors:
- Giuseppe Paolo
- Jonas Gonzalez-Billandon
- Albert Thomas
- Bal{\'a}zs K{\'e}gl
Abstract:
In the last decade, reinforcement learning successfully solved complex control tasks and decision-making problems, like the Go board game. Yet, there are few success stories when it comes to deploying those algorithms to real-world scenarios. One of the reasons is the lack of guarantees when dealing with and avoiding unsafe states, a fundamental requirement in critical control engineering systems. In this paper, we introduce Guided Safe Shooting (GuSS), a model-based RL approach that can learn to control systems with minimal violations of the safety constraints. The model is learned on the data collected during the operation of the system in an iterated batch fashion, and is then used to plan for the best action to perform at each time step. We propose three different safe planners, one based on a simple random shooting strategy and two based on MAP-Elites, a more advanced divergent-search algorithm. Experiments show that these planners help the learning agent avoid unsafe situations while maximally exploring the state space, a necessary aspect when learning an accurate model of the system. Furthermore, compared to model-free approaches, learning a model allows GuSS reducing the number of interactions with the real-system while still reaching high rewards, a fundamental requirement when handling engineering systems.
Links:
- Paper
Bibtex:
```
"@article{paolo2022guided,
title={Guided Safe Shooting: model based reinforcement learning with safety constraints},
author={Paolo, Giuseppe and Gonzalez-Billandon, Jonas and Thomas, Albert and K{\'e}gl, Bal{\'a}zs},
journal={arXiv preprint arXiv:2206.09743},
year={2022}
  }
"
```
Heterogeneous Multi-agent Zero-Shot Coordination by Coevolution Games
Authors:
- Ke Xue
- Yutong Wang
- Lei Yuan
- Cong Guan
- Chao Qian
- Yang Yu
Abstract:
Generating agents that can achieve Zero-Shot Coordination (ZSC) with unseen partners is a new challenge in cooperative Multi-Agent Reinforcement Learning (MARL). Recently, some studies have made progress in ZSC by exposing the agents to diverse partners during the training process. They usually involve self-play when training the partners, implicitly assuming that the tasks are homogeneous. However, many real-world tasks are heterogeneous, and hence previous methods may fail. In this paper, we study the heterogeneous ZSC problem for the first time and propose a general method based on coevolution, which coevolves two populations of agents and partners through three sub-processes: pairing, updating and selection. Experimental results on a collaborative cooking task show the necessity of considering the heterogeneous setting and illustrate that our proposed method is a promising solution for heterogeneous cooperative MARL.
Links:
- Paper
Bibtex:
```
"
@article{maze,
  title={Heterogeneous Multi-agent Zero-Shot Coordination by Coevolution},
  author={Ke Xue and Yutong Wang and Lei Yuan and Cong Guan and Chao Qian and Yang Yu},
  journal={arXiv preprint arXiv:2208.04957},
  year={2022}}
"
```

Hierarchical Quality-Diversity for Online Damage Recovery Robotics

Authors:

Maxime Allard

Simón C. Smith

Konstantinos Chatzilygeroudis

Antoine Cully

Abstract:
Adaptation capabilities, like damage recovery, are crucial for the deployment of robots in complex environments. Several works have demonstrated that using repertoires of pre-trained skills can enable robots to adapt to unforeseen mechanical damages in a few minutes. These adaptation capabilities are directly linked to the behavioural diversity in the repertoire. The more alternatives the robot has to execute a skill, the better are the chances that it can adapt to a new situation. However, solving complex tasks, like maze navigation, usually requires multiple different skills. Finding a large behavioural diversity for these multiple skills often leads to an intractable exponential growth of the number of required solutions. In this paper, we introduce the Hierarchical Trial and Error algorithm, which uses a hierarchical behavioural repertoire to learn diverse skills and leverages them to make the robot more adaptive to different situations. We show that the hierarchical decomposition of skills enables the robot to learn more complex behaviours while keeping the learning of the repertoire tractable. The experiments with a hexapod robot show that our method solves maze navigation tasks with 20% less actions in the most challenging scenarios than the best baseline while having 57% less complete failures.
Links:

Paper

Bibtex:
"
@inproceedings{10.1145/3512290.3528751,
author = {Allard, Maxime and Smith, Sim\'{o}n C. and Chatzilygeroudis, Konstantinos and Cully, Antoine},
title = {Hierarchical Quality-Diversity for Online Damage Recovery},
year = {2022},
isbn = {9781450392372},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3512290.3528751},
doi = {10.1145/3512290.3528751},
abstract = {Adaptation capabilities, like damage recovery, are crucial for the deployment of robots in complex environments. Several works have demonstrated that using repertoires of pre-trained skills can enable robots to adapt to unforeseen mechanical damages in a few minutes. These adaptation capabilities are directly linked to the behavioural diversity in the repertoire. The more alternatives the robot has to execute a skill, the better are the chances that it can adapt to a new situation. However, solving complex tasks, like maze navigation, usually requires multiple different skills. Finding a large behavioural diversity for these multiple skills often leads to an intractable exponential growth of the number of required solutions. In this paper, we introduce the Hierarchical Trial and Error algorithm, which uses a hierarchical behavioural repertoire to learn diverse skills and leverages them to make the robot more adaptive to different situations. We show that the hierarchical decomposition of skills enables the robot to learn more complex behaviours while keeping the learning of the repertoire tractable. The experiments with a hexapod robot show that our method solves maze navigation tasks with 20% less actions in the most challenging scenarios than the best baseline while having 57% less complete failures.},
booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
pages = {58–67},
numpages = {10},
keywords = {robotics, hierarchical learning, quality-diversity},
location = {Boston, Massachusetts},
series = {GECCO '22}
}
"

Illuminating Diverse Neural Cellular Automata for Level Generation Games

Authors:

Sam Earle

Justin Snider

Matthew Fontaine

Stefanos Nikolaidis

Julian Togelius

Abstract:
We present a method of generating diverse collections of neural cellular automata (NCA) to design video game levels. While NCAs have so far only been trained via supervised learning, we present a quality diversity (QD) approach to generating a collection of NCA level generators. By framing the problem as a QD problem, our approach can train diverse level generators, whose output levels vary based on aesthetic or functional criteria. To efficiently generate NCAs, we train generators via Covariance Matrix Adaptation MAP-Elites (CMA-ME), a quality diversity algorithm which specializes in continuous search spaces. We apply our new method to generate level generators for several 2D tile-based games: a maze game, Sokoban, and Zelda. Our results show that CMA-ME can generate small NCAs that are diverse yet capable, often satisfying complex solvability criteria for deterministic agents. We compare against a Compositional Pattern-Producing Network (CPPN) baseline trained to produce diverse collections of generators and show that the NCA representation yields a better exploration of level-space.
Links:

Paper

Bibtex:
"@inproceedings{10.1145/3512290.3528754,
  author = {Earle, Sam and Snider, Justin and Fontaine, Matthew C. and Nikolaidis, Stefanos and Togelius, Julian},
  title = {Illuminating Diverse Neural Cellular Automata for Level Generation},
  year = {2022},
  isbn = {9781450392372},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/3512290.3528754},
  doi = {10.1145/3512290.3528754},
  abstract = {We present a method of generating diverse collections of neural cellular automata (NCA) to design video game levels. While NCAs have so far only been trained via supervised learning, we present a quality diversity (QD) approach to generating a collection of NCA level generators. By framing the problem as a QD problem, our approach can train diverse level generators, whose output levels vary based on aesthetic or functional criteria. To efficiently generate NCAs, we train generators via Covariance Matrix Adaptation MAP-Elites (CMA-ME), a quality diversity algorithm which specializes in continuous search spaces. We apply our new method to generate level generators for several 2D tile-based games: a maze game, Sokoban, and Zelda. Our results show that CMA-ME can generate small NCAs that are diverse yet capable, often satisfying complex solvability criteria for deterministic agents. We compare against a Compositional Pattern-Producing Network (CPPN) baseline trained to produce diverse collections of generators and show that the NCA representation yields a better exploration of level-space.},
  booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
  pages = {68–76},
  numpages = {9},
  keywords = {cellular automata, evolutionary strategies, procedural content generation, neural networks},
  location = {Boston, Massachusetts},
  series = {GECCO '22}
}
"

Learning to Walk Autonomously via Reset-Free Quality-Diversity Robotics
Authors:
- Bryan Lim*
- Alexander Reichenbach*
- Antoine Cully
Links:
- Paper
Minimize Surprise MAP-Elites: a Task-Independent MAP-Elites Variant for Swarms Robotics
Authors:
- Tanja Katharina Kaiser
- Heiko Hamann
Abstract:
Swarm robotics controllers are often automatically generated using methods of evolutionary computation with a task-specific fitness function to guide the optimization process. By contrast, our minimize surprise approach uses a task-independent fitness function to generate diverse behaviors over several independent evolutionary runs. Alternatives are divergent search algorithms rewarding behavioral novelty, such as novelty search, and quality-diversity algorithms generating diverse high-quality solutions, such as MAP-Elites. These approaches usually rely on task-dependent measures. We propose Minimize Surprise MAP-Elites, a task-independent MAP-Elites variant that combines MAP-Elites with our minimize surprise approach. Our first experiments result in high-quality solutions that lead to behavioral diversity across tasks and within tasks.
Links:
- Paper
Bibtex:
```
"
@inproceedings{10.1145/3520304.3528773, 
author = {Kaiser, Tanja Katharina and Hamann, Heiko}, 
title = {Minimize Surprise MAP-Elites: A Task-Independent MAP-Elites Variant for Swarms}, 
year = {2022}, 
isbn = {9781450392686}, 
publisher = {Association for Computing Machinery}, 
address = {New York, NY, USA}, 
url = {https://doi.org/10.1145/3520304.3528773}, 
doi = {10.1145/3520304.3528773}, 
series = {GECCO '22}}
"
```

Procedural Content Generation using Neuroevolution and Novelty Search for Diverse Video Game Levels Games

Authors:

Michael Beukman

Christopher Cleghorn

Steven James

Abstract:
Procedurally generated video game content has the potential to drastically reduce the content creation budget of game developers and large studios. However, adoption is hindered by limitations such as slow generation, as well as low quality and diversity of content. We introduce an evolutionary search-based approach for evolving level generators using novelty search to procedurally generate diverse levels in real time, without requiring training data or detailed domain-specific knowledge. We test our method on two domains, and our results show an order of magnitude speedup in generation time compared to existing methods while obtaining comparable metric scores. We further demonstrate the ability to generalise to arbitrary-sized levels without retraining.
Links:

Paper

Bibtex:
"@inproceedings{beukman2022Procedural,
  author = {Beukman, Michael and Cleghorn, Christopher W and James, Steven},
  title = {Procedural Content Generation Using Neuroevolution and Novelty Search for Diverse Video Game Levels},
  year = {2022},
  isbn = {9781450392372},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/3512290.3528701},
  doi = {10.1145/3512290.3528701},
  abstract = {Procedurally generated video game content has the potential to drastically reduce the content creation budget of game developers and large studios. However, adoption is hindered by limitations such as slow generation, as well as low quality and diversity of content. We introduce an evolutionary search-based approach for evolving level generators using novelty search to procedurally generate diverse levels in real time, without requiring training data or detailed domain-specific knowledge. We test our method on two domains, and our results show an order of magnitude speedup in generation time compared to existing methods while obtaining comparable metric scores. We further demonstrate the ability to generalise to arbitrary-sized levels without retraining.},
  booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
  pages = {1028–1037},
  numpages = {10},
  keywords = {neuroevolution, novelty search, procedural content generation},
  location = {Boston, Massachusetts},
  series = {GECCO '22}
  }
"

Towards QD-suite: developing a set of benchmarks for Quality-Diversity algorithms
Authors:
- Achkan Salehi
- Stephane Doncieux
Abstract:
While the field of Quality-Diversity (QD) has grown into a distinct branch of stochastic optimization, a few problems, in particular locomotion and navigation tasks, have become de facto standards. Are such benchmarks sufficient? Are they representative of the key challenges faced by QD algorithms? Do they provide the ability to focus on one particular challenge by properly disentangling it from others? Do they have much predictive power in terms of scalability and generalization? Existing benchmarks are not standardized, and there is currently no MNIST equivalent for QD. Inspired by recent works on Reinforcement Learning benchmarks, we argue that the identification of challenges faced by QD methods and the development of targeted, challenging, scalable but affordable benchmarks is an important step. As an initial effort, we identify three problems that are challenging in sparse reward settings, and propose associated benchmarks: (1) Behavior metric bias, which can result from the use of metrics that do not match the structure of the behavior space. (2) Behavioral Plateaus, with varying characteristics, such that escaping them would require adaptive QD algorithms and (3) Evolvability Traps, where small variations in genotype result in large behavioral changes. The environments that we propose satisfy the properties listed above.
Links:
- Paper
Bibtex:
```
"
@article{salehi2022toward,
title={Towards QD-suite: developing a set of benchmarks for Quality-Diversity algorithms},
author={Salehi, Achkan and Doncieux, Stephane},
journal={arXiv preprint arXiv:2205.03207},
year={2022}
}
"
```

2021: 24 Papers

A Quality Diversity Approach to Automatically Generating Human-Robot Interaction Scenarios in Shared Autonomy Robotics
Authors:
- Matthew Fontaine
- Stefanos Nikolaidis
Abstract:
The growth of scale and complexity of interactions between humans and robots highlights the need for new computational methods to automatically evaluate novel algorithms and applications. Exploring the diverse scenarios of interaction between humans and robots in simulation can improve understanding of the system and avoid potentially costly failures in real-world settings. We formulate this as a quality diversity (QD) problem, where the goal is to discover diverse failure scenarios by simultaneously exploring both environments and human actions. We focus on the shared autonomy domain, where the robot attempts to infer the goal of a human operator, and adopt the QD algorithm MAP-Elites to generate scenarios for two published algorithms in this domain: shared autonomy via hindsight optimization and linear policy blending. Some of the generated scenarios confirm previous theoretical findings, while others are surprising and bring about a new understanding of state-of-the-art implementations. Our experiments show that MAP-Elites outperforms Monte-Carlo simulation and optimization based methods in effectively searching the scenario space, highlighting its promise for automatic evaluation of algorithms in shared autonomy.
Links:
- Paper
Bibtex:
```
"@article{fontaine2020quality,
 title={A Quality Diversity Approach to Automatically Generating Human-Robot Interaction Scenarios in Shared Autonomy},
 author={Fontaine, Matthew and Nikolaidis, Stefanos},
 journal={arXiv preprint arXiv:2012.04283},
 year={2020}
 }
"
```
ARCH-Elites: Quality-Diversity for Urban Design
Authors:
- Theodoros Galanos
- Antonios Liapis
- Georgios N. Yannakakis
- Reinhard Koenig
Abstract:
This paper introduces ARCH-Elites, a MAP-Elites implementation that can reconfigure large-scale urban layouts at real-world locations via a pre-trained surrogate model instead of costly simulations. In a series of experiments, we generate novel urban designs for two real-world locations in Boston, Massachusetts. Combining the exploration of a possibility space with real-time performance evaluation creates a powerful new paradigm for architectural generative design that can extract and articulate design intelligence.
Links:
- Paper
Bibtex:
```
"@article{galanos2021arch,
 title={ARCH-Elites: Quality-Diversity for Urban Design},
 author={Galanos, Theodoros and Liapis, Antonios and Yannakakis, Georgios N and Koenig, Reinhard},
 journal={arXiv preprint arXiv:2104.08774},
 year={2021}
 }
"
```
AutoAlpha: an Efficient Hierarchical Evolutionary Algorithm for Mining Alpha Factors in Quantitative Investment
Authors:
- Tianping Zhang
- Yuanqi Li
- Yifei Jin
- Jian Li
Abstract:
The multi-factor model is a widely used model in quantitative investment. The success of a multi-factor model is largely determined by the effectiveness of the alpha factors used in the model. This paper proposes a new evolutionary algorithm called AutoAlpha to automatically generate effective formulaic alphas from massive stock datasets. Specifically, first we discover an inherent pattern of the formulaic alphas and propose a hierarchical structure to quickly locate the promising part of space for search. Then we propose a new Quality Diversity search based on the Principal Component Analysis (PCA-QD) to guide the search away from the well-explored space for more desirable results. Next, we utilize the warm start method and the replacement method to prevent the premature convergence problem. Based on the formulaic alphas we discover, we propose an ensemble learning-to-rank model for generating the portfolio. The backtests in the Chinese stock market and the comparisons with several baselines further demonstrate the effectiveness of AutoAlpha in mining formulaic alphas for quantitative trading.
Links:
- Paper
Bibtex:
```
"@article{zhang2020autoalpha,
 title={AutoAlpha: an Efficient Hierarchical Evolutionary Algorithm for Mining Alpha Factors in Quantitative Investment},
 author={Zhang, Tianping and Li, Yuanqi and Jin, Yifei and Li, Jian},
 journal={arXiv preprint arXiv:2002.08245},
 year={2020}
 }
"
```
BR-NS: an Archive-less Approach to Novelty Search Robotics
Authors:
- Achkan Salehi
- Alexandre Coninx
- Stephane Doncieux
Abstract:
As open-ended learning based on divergent search algorithms such as Novelty Search (NS) draws more and more attention from the research community, it is natural to expect that its application to increasingly complex real-world problems will require the exploration to operate in higher dimensional Behavior Spaces which will not necessarily be Euclidean. Novelty Search traditionally relies on k-nearest neighbours search and an archive of previously visited behavior descriptors which are assumed to live in a Euclidean space. This is problematic because of a number of issues. On one hand, Euclidean distance and Nearest-neighbour search are known to behave differently and become less meaningful in high dimensional spaces. On the other hand, the archive has to be bounded since, memory considerations aside, the computational complexity of finding nearest neighbours in that archive grows linearithmically with its size. A sub-optimal bound can result in 'cycling' in the behavior space, which inhibits the progress of the exploration. Furthermore, the performance of NS depends on a number of algorithmic choices and hyperparameters, such as the strategies to add or remove elements to the archive and the number of neighbours to use in k-nn search. In this paper, we discuss an alternative approach to novelty estimation, dubbed Behavior Recognition based Novelty Search (BR-NS), which does not require an archive, makes no assumption on the metrics that can be defined in the behavior space and does not rely on nearest neighbours search. We conduct experiments to gain insight into its feasibility and dynamics as well as potential advantages over archive-based NS in terms of time complexity.
Links:
- Paper
Bibtex:
```
"@inproceedings{salehi2021br,
 title={BR-NS: an Archive-less Approach to Novelty Search},
 author={Salehi, Achkan and Coninx, Alexandre and Doncieux, Stephane},
 booktitle={Genetic and Evolutionary Computation Conference},
 year={2021}
 }
"
```
Dynamics-Aware Quality-Diversity for Efficient Learning of Skill Repertoires Robotics
Authors:
- Bryan Lim
- Luca Grillotti
- Lorenzo Bernasconi
- Antoine Cully
Links:
- Paper
Ensemble Feature Extraction for Multi-Container Quality-Diversity Algorithms
Authors:
- Leo Cazenille
Abstract:
Quality-Diversity algorithms search for large collections of diverse and high-performing solutions, rather than just for a single solution like typical optimisation methods. They are specially adapted for multi-modal problems that can be solved in many different ways, such as complex reinforcement learning or robotics tasks. However, these approaches are highly dependent on the choice of feature descriptors (FDs) quantifying the similarity in behaviour of the solutions. While FDs usually needs to be hand-designed, recent studies have proposed ways to define them automatically by using feature extraction techniques, such as PCA or Auto-Encoders, to learn a representation of the problem from previously explored solutions. Here, we extend these approaches to more complex problems which cannot be efficiently explored by relying only on a single representation but require instead a set of diverse and complementary representations. We describe MC-AURORA, a Quality-Diversity approach that optimises simultaneously several collections of solutions, each with a different set of FDs, which are, in turn, defined automatically by an ensemble of modular auto-encoders. We show that this approach produces solutions that are more diverse than those produced by single-representation approaches.
Links:
- Paper
Bibtex:
```
"@inproceedings{cazenille2021ensemble,
 title={Ensemble Feature Extraction for Multi-Container Quality-Diversity Algorithms},
 author={Cazenille, Leo},
 booktitle={Genetic and Evolutionary Computation Conference},
 year={2021}
 }
"
```
Expressivity of Parameterized and Data-driven Representations in Quality Diversity Search
Authors:
- Alexander Hagg
- Sebastian Berns
- Alexander Asteroth
- Simon Colton
- Thomas Bäck
Abstract:
We consider multi-solution optimization and generative models for the generation of diverse artifacts and the discovery of novel solutions. In cases where the domain's factors of variation are unknown or too complex to encode manually, generative models can provide a learned latent space to approximate these factors. When used as a search space, however, the range and diversity of possible outputs are limited to the expressivity and generative capabilities of the learned model. We compare the output diversity of a quality diversity evolutionary search performed in two different search spaces: 1) a predefined parameterized space and 2) the latent space of a variational autoencoder model. We find that the search on an explicit parametric encoding creates more diverse artifact sets than searching the latent space. A learned model is better at interpolating between known data points than at extrapolating or expanding towards unseen examples. We recommend using a generative model's latent space primarily to measure similarity between artifacts rather than for search and generation. Whenever a parametric encoding is obtainable, it should be preferred over a learned representation as it produces a higher diversity of solutions.
Links:
- Paper
Bibtex:
```
"@inproceedings{hagg2021expressivity,
 title={Expressivity of Parameterized and Data-driven Representations in Quality Diversity Search},
 author={Hagg, Alexander and Berns, Sebastian and Asteroth, Alexander and Colton, Simon and B{\"a}ck, Thomas},
 booktitle={Genetic and Evolutionary Computation Conference},
 year={2021}
 }
"
```
Generating Diverse and Competitive Play-Styles for Strategy Games Games
Authors:
- Diego Perez-Liebana
- Cristina Guerrero-Romero
- Alexander Dockhorn
- Dominik Jeurissen
- Linjie Xu
Abstract:
Designing agents that are able to achieve different play-styles while maintaining a competitive level of play is a difficult task, especially for games for which the research community has not found super-human performance yet, like strategy games. These require the AI to deal with large action spaces, long-term planning and partial observability, among other well-known factors that make decision-making a hard problem. On top of this, achieving distinct play-styles using a general algorithm without reducing playing strength is not trivial. In this paper, we propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes) and show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play. Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
Links:
- Paper
Bibtex:
```
"@article{perez2021generating,
 title={Generating Diverse and Competitive Play-Styles for Strategy Games},
 author={Perez-Liebana, Diego and Guerrero-Romero, Cristina and Dockhorn, Alexander and Jeurissen, Dominik and Xu, Linjie},
 journal={arXiv preprint arXiv:2104.08641},
 year={2021}
 }
"
```
Generating and Blending Game Levels via Quality-Diversity in the Latent Space of a Variational Autoencoder Games
Authors:
- Anurag Sarkar
- Seth Cooper
Abstract:
Several recent works have demonstrated the use of variational autoencoders (VAEs) for both generating levels in the style of existing games as well as blending levels across different games. Additionally, quality-diversity (QD) algorithms have also become popular for generating varied game content by using evolution to explore a search space while focusing on both variety and quality. In order to reap the benefits of both these approaches, we present a level generation and game blending approach that combines the use of VAEs and QD algorithms. Specifically, we train VAEs on game levels and then run the MAP-Elites QD algorithm using the learned latent space of the VAE as the search space. The latent space captures the properties of the games whose levels we want to generate and blend, while MAP-Elites searches this latent space to find a diverse set of levels optimizing a given objective such as playability. We test our method using models for 5 different platformer games as well as a blended domain spanning 3 of these games. Our results show that using MAP-Elites in conjunction with VAEs enables the generation of a diverse set of playable levels not just for each individual game but also for the blended domain while illuminating game-specific regions of the blended latent space.
Links:
- Paper
Bibtex:
```
"@article{sarkar2021generating,
 title={Generating and Blending Game Levels via Quality-Diversity in the Latent Space of a Variational Autoencoder},
 author={Sarkar, Anurag and Cooper, Seth},
 journal={arXiv preprint arXiv:2102.12463},
 year={2021}
 }
"
```
Illuminating Mario Scenes in the Latent Space of a Generative Adversarial Network Games
Authors:
- Matthew C. Fontaine
- Ruilin Liu
- Ahmed Khalifa
- Jignesh Modi
- Julian Togelius
- Amy K. Hoover
- Stefanos Nikolaidis
Abstract:
Generative adversarial networks (GANs) are now a ubiquitous approach to procedurally generating video game levels. While GAN generated levels are stylistically similar to human-authored examples, human designers often want to explore the generative design space of GANs to extract interesting levels. However, human designers find latent vectors opaque and would rather explore along dimensions the designer specifies, such as number of enemies or obstacles. We propose using state-of-the-art quality diversity algorithms designed to optimize continuous spaces, i.e. MAP-Elites with a directional variation operator and Covariance Matrix Adaptation MAP-Elites, to efficiently explore the latent space of a GAN to extract levels that vary across a set of specified gameplay measures. In the benchmark domain of Super Mario Bros, we demonstrate how designers may specify gameplay measures to our system and extract high-quality (playable) levels with a diverse range of level mechanics, while still maintaining stylistic similarity to human authored examples. An online user study shows how the different mechanics of the automatically generated levels affect subjective ratings of their perceived difficulty and appearance.
Links:
- Paper
Bibtex:
```
"@inproceedings{fontaine2020illuminating,
 title={Illuminating mario scenes in the latent space of a generative adversarial network},
 author={Fontaine, Matthew C and Liu, Ruilin and Togelius, Julian and Hoover, Amy K and Nikolaidis, Stefanos},
 booktitle={AAAI Conference on Artificial Intelligence},
 year={2021}}
"
```
Illuminating the Space of Beatable Lode Runner Levels Produced By Various Generative Adversarial Networks Games
Authors:
- Kirby Steckel
- Jacob Schrum
Abstract:
Generative Adversarial Networks (GANs) are capable of generating convincing imitations of elements from a training set, but the distribution of elements in the training set affects to difficulty of properly training the GAN and the quality of the outputs it produces. This paper looks at six different GANs trained on different subsets of data from the game Lode Runner. The quality diversity algorithm MAP-Elites was used to explore the set of quality levels that could be produced by each GAN, where quality was defined as being beatable and having the longest solution path possible. Interestingly, a GAN trained on only 20 levels generated the largest set of diverse beatable levels while a GAN trained on 150 levels generated the smallest set of diverse beatable levels, thus challenging the notion that more is always better when training GANs.
Links:
- Paper
Bibtex:
```
"@article{steckel2021illuminating,
 title={Illuminating the Space of Beatable Lode Runner Levels Produced By Various Generative Adversarial Networks},
 author={Steckel, Kirby and Schrum, Jacob},
 journal={arXiv preprint arXiv:2101.07868},
 year={2021}
 }
"
```
MAP-Elites enables Powerful Stepping Stones and Diversity for Modular Robotics Robotics
Authors:
- Jørgen Nordmoen
- Frank Veenstra
- Kai Olav Ellefsen
- Kyrre Glette
Abstract:
In modular robotics, modules can be reconfigured to change the morphology of the robot, making it able to adapt for specific tasks. However, optimizing both the body and control is a difficult challenge due to the intricate relationship between fine-tuning control and morphological changes that can invalidate such optimizations. To solve this challenge we compare three different Evolutionary Algorithms on their capacity to optimize morphologies in modular robotics. We compare two objective-based search algorithms, with MAP-Elites. To understand the benefit of diversity we transition the evolved populations into two difficult environments to see if diversity can have an impact on solving complex environments. In addition, we analyse the genealogical ancestry to shed light on the notion of stepping stones as key to enable high performance. The results show that MAP-Elites is capable of evolving the highest performing solutions in addition to generating the largest morphological diversity. For the transition between environments the results show that MAP-Elites is better at regaining performance by promoting morphological diversity. With the analysis of genealogical ancestry we show that MAP-Elites produces more diverse and higher performing stepping stones than the other objective-based search algorithms. Transitioning the populations to more difficult environments show the utility of morphological diversity, while the analysis of stepping stones show a strong correlation between diversity of ancestry and maximum performance on the locomotion task. The paper shows the advantage of promoting diversity for solving a locomotion task in different environments for modular robotics. By showing that the quality and diversity of stepping stones in Evolutionary Algorithms is an important factor for overall performance we have opened up a new area of analysis and results.
Links:
- Paper
Bibtex:
```
"@article{nordmoen2021map,
 title={MAP-Elites enables Powerful Stepping Stones and Diversity for Modular Robotics},
 author={Nordmoen, J{\o}rgen and Veenstra, Frank and Ellefsen, Kai Olav and Glette, Kyrre},
 journal={Frontiers in Robotics and AI},
 volume={8},
 year={2021},
 publisher={Frontiers Media SA}
 }
"
```
MAP-Elites for Constrained Optimization
Authors:
- Stefano Fioravanzo
- Giovanni Iacca
Abstract:
Constrained optimization problems are often characterized by multiple constraints that, in the practice, must be satisfied with different tolerance levels. While some constraints are hard and as such must be satisfied with zero-tolerance, others may be soft, such that non-zero violations are acceptable. Here, we evaluate the applicability of MAP-Elites to “illuminate” constrained search spaces by mapping them into feature spaces where each feature corresponds to a different constraint. On the one hand, MAP-Elites implicitly preserves diversity, thus allowing a good exploration of the search space. On the other hand, it provides an effective visualization that facilitates a better understanding of how constraint violations correlate with the objective function. We demonstrate the feasibility of this approach on a large set of benchmark problems, in various dimensionalities, and with different algorithmic configurations. As expected, numerical results show that a basic version of MAP-Elites cannot compete on all problems (especially those with equality constraints) with state-of-the-art algorithms that use gradient information or advanced constraint handling techniques. Nevertheless, it has a higher potential at finding constraint violations versus objectives trade-offs and providing new problem information. As such, it could be used in the future as an effective building-block for designing new constrained optimization algorithms.
Bibtex:
```
"@article{fioravanzomap,
 title={MAP-Elites for Constrained Optimization},
 author={Fioravanzo, Stefano and Iacca, Giovanni},
 journal={Constraint Handling in Metaheuristics and Applications},
 pages={151},
 publisher={Springer}
 }
"
```
Monte Carlo Elites: Quality-Diversity Selection as a Multi-Armed Bandit Problem Robotics
Authors:
- Konstantinos Sfikas
- Antonios Liapis
- Georgios N. Yannakakis
Abstract:
A core challenge of evolutionary search is the need to balance between exploration of the search space and exploitation of highly fit regions. Quality-diversity search has explicitly walked this tightrope between a population's diversity and its quality. This paper extends a popular quality-diversity search algorithm, MAP-Elites, by treating the selection of parents as a multi-armed bandit problem. Using variations of the upper-confidence bound to select parents from under-explored but potentially rewarding areas of the search space can accelerate the discovery of new regions as well as improve its archive's total quality. The paper tests an indirect measure of quality for parent selection: the survival rate of a parent's offspring. Results show that maintaining a balance between exploration and exploitation leads to the most diverse and high-quality set of solutions in three different testbeds.
Links:
- Paper
Bibtex:
```
"@inproceedings{sfikas2021monte,
 title={Monte Carlo Elites: Quality-Diversity Selection as a Multi-Armed Bandit Problem},
 author={Sfikas, Konstantinos and Liapis, Antonios and Yannakakis, Georgios N},
 booktitle={Genetic and Evolutionary Computation Conference},
 year={2021}
 }
"
```
Multi-Emitter MAP-Elites: Improving quality, diversity and convergence speed with heterogeneous sets of emitters Robotics
Authors:
- Antoine Cully
Abstract:
Quality-Diversity (QD) optimisation is a new family of learning algorithms that aims at generating collections of diverse and high-performing solutions. Among those algorithms, the recently introduced Covariance Matrix Adaptation MAP-Elites (CMA-ME) algorithm proposes the concept of emitters, which uses a predefined heuristic to drive the algorithm’s exploration. This algorithm was shown to outperform MAP-Elites, a popular QD algorithm that has demonstrated promising results in numerous applications. In this paper, we introduce Multi-Emitter MAP-Elites (ME-MAP-Elites), an algorithm that directly extends CMA-ME and improves its quality, diversity and data efficiency. It leverages the diversity of a heterogeneous set of emitters, in which each emitter type improves the optimisation process in different ways. A bandit algorithm dynamically finds the best selection of emitters depending on the current situation. We evaluate the performance of ME-MAP-Elites on six tasks, ranging from standard optimisation problems (in 100 dimensions) to complex locomotion tasks in robotics. Our comparisons against CMA-ME and MAP-Elites show that ME-MAP-Elites is faster at providing collections of solutions that are significantly more diverse and higher performing. Moreover, in cases where no fruitful synergy can be found between the different emitters, ME-MAP-Elites is equivalent to the best of the compared algorithms.
Links:
- Paper
Bibtex:
```
"@inproceedings{cully2020multi,
 title={Multi-Emitter MAP-Elites: Improving quality, diversity and convergence speed with heterogeneous sets of emitters},
 author={Cully, Antoine},
 booktitle={Genetic and Evolutionary Computation Conference},
 year={2020}
 }
"
```
On the Importance of Environments in Human-Robot Coordination Robotics
Authors:
- Matthew Fontaine*
- Ya-Chuan Hsu*
- Yulun Zhang*
- Bryon Tjanaka
- Stefanos Nikolaidis
Abstract:
When studying robots collaborating with humans, much of the focus has been on robot policies that coordinate fluently with human teammates in collaborative tasks. However, less emphasis has been placed on the effect of the environment on coordination behaviors. To thoroughly explore environments that result in diverse behaviors, we propose a framework for procedural generation of environments that are (1) stylistically similar to human-authored environments, (2) guaranteed to be solvable by the human-robot team, and (3) diverse with respect to coordination measures. We analyze the procedurally generated environments in the Overcooked benchmark domain via simulation and an online user study. Results show that the environments result in qualitatively different emerging behaviors and statistically significant differences in collaborative fluency metrics, even when the robot runs the same planning algorithm.
Links:
- Paper
- Webpage
Bibtex:
```
"@INPROCEEDINGS{FontaineB-RSS-21,
AUTHOR    = {Matthew Fontaine AND Ya-Chuan Hsu AND Yulun Zhang AND Bryon Tjanaka AND Stefanos Nikolaidis},
TITLE     = {{On the Importance of Environments in Human-Robot Coordination}},
BOOKTITLE = {Proceedings of Robotics: Science and Systems},
YEAR      = {2021}, 
ADDRESS   = {Virtual}, 
MONTH     = {July}, 
DOI       = {10.15607/RSS.2021.XVII.038} 
}
"
```
On the use of feature-maps and parameter control for improved quality-diversity meta-evolution Robotics
Authors:
- David M. Bossens
- Danesh Tarapore
Abstract:
In Quality-Diversity (QD) algorithms, which evolve a behaviourally diverse archive of high-performing solutions, the behaviour space is a difficult design choice that should be tailored to the target application. In QD meta-evolution, one evolves a population of QD algorithms to optimise the behaviour space based on an archive-level objective, the meta-fitness. This paper proposes an improved meta-evolution system such that (i) the database used to rapidly populate new archives is reformulated to prevent loss of quality-diversity; (ii) the linear transformation of base-features is generalised to a feature-map, a function of the base-features parametrised by the meta-genotype; and (iii) the mutation rate of the QD algorithm and the number of generations per meta-generation are controlled dynamically. Experiments on an 8-joint planar robot arm compare feature-maps (linear, non-linear, and feature-selection), parameter control strategies (static, endogenous, reinforcement learning, and annealing), and traditional MAP-Elites variants, for a total of 49 experimental conditions. Results reveal that non-linear and feature-selection feature-maps yield a 15-fold and 3-fold improvement in meta-fitness, respectively, over linear feature-maps. Reinforcement learning ranks among top parameter control methods. Finally, our approach allows the robot arm to recover a reach of over 80% for most damages and at least 60% for severe damages.
Links:
- Paper
Bibtex:
```
"@article{bossens2021use,
 title={On the use of feature-maps and parameter control for improved quality-diversity meta-evolution},
 author={Bossens, David M and Tarapore, Danesh},
 journal={arXiv preprint arXiv:2105.10317},
 year={2021}
 }
"
```
Policy Gradient Assisted MAP-Elites Robotics
Authors:
- Olle Nilsson
- Antoine Cully
Abstract:
Quality-Diversity optimization algorithms such as MAP-Elites, aimto generate collections of both diverse and high-performing solu-tions to an optimization problem. MAP-Elites has shown promisingresults in a variety of applications. In particular in evolutionaryrobotics tasks targeting the generation of behavioral repertoiresthat highlight the versatility of robots. However, for most robot-ics applications MAP-Elites is limited to using simple open-loopor low-dimensional controllers. Here we present Policy GradientAssisted MAP-Elites (PGA-MAP-Elites), a novel algorithm that en-ables MAP-Elites to efficiently evolve large neural network con-trollers by introducing a gradient-based variation operator inspiredby Deep Reinforcement Learning. This operator leverages gradi-ent estimates obtained from a critic neural network to rapidly findhigher-performing solutions and is paired with a traditional geneticvariation to maintain a divergent search behavior. The synergy ofthese operators makes PGA-MAP-Elites an efficient yet powerfulalgorithm for finding diverse and high-performing behaviors. Weevaluate our method on four different tasks for building behavioralrepertoires that use deep neural network controllers. The resultsshow that PGA-MAP-Elites significantly improves the quality ofthe generated repertoires compared to existing methods.
Links:
- Paper
Bibtex:
```
"@inproceedings{nilsson2021policy,
 title={Policy Gradient Assisted MAP-Elites},
 author={Nilsson, Olle and Cully, Antoine},
 booktitle={Genetic and Evolutionary Computation Conference},
 year={2021}
 }
"
```
Policy Manifold Search: Exploring the Manifold Hypothesis for Diversity-based Neuroevolution Robotics
Authors:
- Nemanja Rakicevic
- Antoine Cully
- Petar Kormushev
Abstract:
Neuroevolution is an alternative to gradient-based optimisation that has the potential to avoid local minima and allows parallelisation. The main limiting factor is that usually it does not scale well with parameter space dimensionality. Inspired by recent work examining neural network intrinsic dimension and loss landscapes, we hypothesise that there exists a low-dimensional manifold, embedded in the policy network parameter space, around which a high-density of diverse and useful policies are located. This paper proposes a novel method for diversity-based policy search via Neuroevolution, that leverages learned representations of the policy network parameters, by performing policy search in this learned representation space. Our method relies on the Quality-Diversity (QD) framework which provides a principled approach to policy search, and maintains a collection of diverse policies, used as a dataset for learning policy representations. Further, we use the Jacobian of the inverse-mapping function to guide the search in the representation space. This ensures that the generated samples remain in the high-density regions, after mapping back to the original space. Finally, we evaluate our contributions on four continuous-control tasks in simulated environments, and compare to diversity-based baselines.
Links:
- Paper
Bibtex:
```
"@inproceedings{rakicevic2021policy,
 title={Policy Manifold Search: Exploring the Manifold Hypothesis for Diversity-based Neuroevolution},
 author={Rakicevic, Nemanja and Cully, Antoine and Kormushev, Petar},
 booktitle={Genetic and Evolutionary Computation Conference},
 year={2021}
 }
"
```
Quality Diversity Genetic Programming forLearning Decision Tree Ensembles
Authors:
- Stephen Boisvert
- John W. Sheppard
Abstract:
Quality Diversity (QD) algorithms are a class of population-based evolutionary algorithms designed to generate sets of solutions thatare both fit and diverse. In this paper, we describe a strategy for apply-ing QD concepts to the generation of decision tree ensembles by op-timizing collections of trees for both individually accurate and collec-tively diverse predictive behavior. We compare three variants of this QDstrategy with two existing ensemble generation strategies over severalclassification data sets. We then briefly highlight the effect of the evolu-tionary algorithm at the core of the strategy. The examined algorithmsgenerate ensembles with distinct predictive behaviors as measured byclassification accuracy and intrinsic diversity. The plotted behaviors hintat highly data-dependent relationships between these metrics. QD-basedstrategies are suggested as a means to optimize classifier ensembles alongthis performance curve along with other suggestions for future work.
Links:
- Paper
Bibtex:
```
"@inproceedings{boisvert2021quality,
 title={Quality Diversity Genetic Programming for Learning Decision Tree Ensembles.},
 author={Boisvert, Stephen and Sheppard, John W},
 booktitle={EuroGP},
 pages={3--18},
 year={2021}
 }
"
```
Quality-Diversity Optimization: A Novel Branch of Stochastic Optimization Review
Authors:
- Konstantinos Chatzilygeroudis
- Antoine Cully
- Vassilis Vassiliades
- Jean-Baptiste Mouret
Abstract:
Traditional optimization algorithms search for a single global optimum that maximizes (or minimizes) the objective function. Multimodal optimization algorithms search for the highest peaks in the search space that can be more than one. Quality-Diversity algorithms are a recent addition to the evolutionary computation toolbox that do not only search for a single set of local optima, but instead try to illuminate the search space. In effect, they provide a holistic view of how high-performing solutions are distributed throughout a search space. The main differences with multimodal optimization algorithms are that (1) Quality-Diversity typically works in the behavioral space (or feature space), and not in the genotypic (or parameter) space, and (2) Quality-Diversity attempts to fill the whole behavior space, even if the niche is not a peak in the fitness landscape. In this chapter, we provide a gentle introduction to Quality-Diversity optimization, discuss the main representative algorithms, and the main current topics under consideration in the community. Throughout the chapter, we also discuss several successful applications of Quality-Diversity algorithms, including deep learning, robotics, and reinforcement learning.
Links:
- Paper
Bibtex:
```
"@incollection{chatzilygeroudis2021quality,
 title={Quality-Diversity Optimization: a novel branch of stochastic optimization},
 author={Chatzilygeroudis, Konstantinos and Cully, Antoine and Vassiliades, Vassilis and Mouret, Jean-Baptiste},
 booktitle={Black Box Optimization, Machine Learning, and No-Free Lunch Theorems},
 pages={109--135},
 year={2021},
 publisher={Springer}
 }
"
```
Seeking Quality Diversity in Evolutionary Co-design of Morphology and Control of Soft Tensegrity Modular Robots Robotics
Authors:
- Enrico Zardini
- Davide Zappetti
- Davide Zambrano
- Giovanni Iacca
- Dario Floreano
Abstract:
Designing optimal soft modular robots is difficult, due to non-trivial interactions between morphology and controller. Evolutionary algorithms (EAs), combined with physical simulators, represent a valid tool to overcome this issue. In this work, we investigate algorithmic solutions to improve the Quality Diversity of co-evolved designs of Tensegrity Soft Modular Robots (TSMRs) for two robotic tasks, namely goal reaching and squeezing trough a narrow passage. To this aim, we use three different EAs, i.e., MAP-Elites and two custom algorithms: one based on Viability Evolution (ViE) and NEAT (ViE-NEAT), the other named Double Map MAP-Elites (DM-ME) and devised to seek diversity while co-evolving robot morphologies and neural network (NN)-based controllers. In detail, DM-ME extends MAP-Elites in that it uses two distinct feature maps, referring to morphologies and controllers respectively, and integrates a mechanism to automatically define the NN-related feature descriptor. Considering the fitness, in the goal-reaching task ViE-NEAT outperforms MAP-Elites and results equivalent to DM-ME. Instead, when considering diversity in terms of 'illumination' of the feature space, DM-ME outperforms the other two algorithms on both tasks, providing a richer pool of possible robotic designs, whereas ViE-NEAT shows comparable performance to MAP-Elites on goal reaching, although it does not exploit any map.
Links:
- Paper
Bibtex:
```
"@inproceedings{zardini2021seeking,
 title={Seeking Quality Diversity in Evolutionary Co-design of Morphology and Control of Soft Tensegrity Modular Robots},
 author={Zardini, Enrico and Zappetti, Davide and Zambrano, Davide and Iacca, Giovanni and Floreano, Dario},
 booktitle={Genetic and Evolutionary Computation Conference},
 year={2021}
 }
"
```
Sparse Reward Exploration via Novelty Search and Emitters Robotics
Authors:
- Giuseppe Paolo
- Alexandre Coninx
- Stephane Doncieux
- Alban Laflaquière
Abstract:
Reward-based optimization algorithms require both exploration, to find rewards, and exploitation, to maximize performance. The need for efficient exploration is even more significant in sparse reward settings, in which performance feedback is given sparingly, thus rendering it unsuitable for guiding the search process. In this work, we introduce the SparsE Reward Exploration via Novelty and Emitters (SERENE) algorithm, capable of efficiently exploring a search space, as well as optimizing rewards found in potentially disparate areas. Contrary to existing emitters-based approaches, SERENE separates the search space exploration and reward exploitation into two alternating processes. The first process performs exploration through Novelty Search, a divergent search algorithm. The second one exploits discovered reward areas through emitters, i.e. local instances of population-based optimization algorithms. A meta-scheduler allocates a global computational budget by alternating between the two processes, ensuring the discovery and efficient exploitation of disjoint reward areas. SERENE returns both a collection of diverse solutions covering the search space and a collection of high-performing solutions for each distinct reward area. We evaluate SERENE on various sparse reward environments and show it compares favorably to existing baselines.
Links:
- Paper
Bibtex:
```
"@inproceedings{paolo2021sparse,
 title={Sparse Reward Exploration via Novelty Search and Emitters},
 author={Paolo, Giuseppe and Coninx, Alexandre and Doncieux, St{\'e}phane and Laflaqui{\`e}re, Alban},
 booktitle={Genetic and Evolutionary Computation Conference},
 year={2021}
 }
"
```
Unsupervised Behaviour Discovery with Quality-Diversity Optimisation Robotics
Authors:
- Luca Grillotti
- Antoine Cully
Abstract:
Quality-Diversity algorithms refer to a class of evolutionary algorithms designed to find a collection of diverse and high-performing solutions to a given problem. In robotics, such algorithms can be used for generating a collection of controllers covering most of the possible behaviours of a robot. To do so, these algorithms associate a behavioural descriptor to each of these behaviours. Each behavioural descriptor is used for estimating the novelty of one behaviour compared to the others. In most existing algorithms, the behavioural descriptor needs to be hand-coded, thus requiring prior knowledge about the task to solve. In this paper, we introduce: Autonomous Robots Realising their Abilities, an algorithm that uses a dimensionality reduction technique to automatically learn behavioural descriptors based on raw sensory data. The performance of this algorithm is assessed on three robotic tasks in simulation. The experimental results show that it performs similarly to traditional hand-coded approaches without the requirement to provide any hand-coded behavioural descriptor. In the collection of diverse and high-performing solutions, it also manages to find behaviours that are novel with respect to more features than its hand-coded baselines. Finally, we introduce a variant of the algorithm which is robust to the dimensionality of the behavioural descriptor space.
Links:
- Paper
Bibtex:
```
"@article{grillotti2021unsupervised,
 title={Unsupervised Behaviour Discovery with Quality-Diversity Optimisation},
 author={Grillotti, Luca and Cully, Antoine},
 journal={arXiv preprint arXiv:2106.05648},
 year={2021}
 }
"
```

2020: 42 Papers

A Framework for Automatic Behavior Generation in Multi-Function Swarms Robotics
Authors:
- Sondre A. Engebraaten
- Jonas Moen
- Oleg A. Yakimenko
- Kyrre Glette
Abstract:
Multi-function swarms are swarms that solve multiple tasks at once. For example, a quadcopter swarm could be tasked with exploring an area of interest while simultaneously functioning as ad-hoc relays. With this type of multi-function comes the challenge of handling potentially conflicting requirements simultaneously. Using the Quality-Diversity algorithm MAP-elites in combination with a suitable controller structure, a framework for automatic behavior generation in multi-function swarms is proposed. The framework is tested on a scenario with three simultaneous tasks: exploration, communication network creation and geolocation of RF emitters. A repertoire is evolved, consisting of a wide range of controllers, or behavior primitives, with different characteristics and trade-offs in the different tasks. This repertoire would enable the swarm to transition between behavior trade-offs online, according to the situational requirements. Furthermore, the effect of noise on the behavior characteristics in MAP-elites is investigated. A moderate number of re-evaluations is found to increase the robustness while keeping the computational requirements relatively low. A few selected controllers are examined, and the dynamics of transitioning between these controllers are explored. Finally, the study develops a methodology for analyzing the makeup of the resulting controllers. This is done through a parameter variation study where the importance of individual inputs to the swarm controllers is assessed and analyzed.
Links:
- Paper
Bibtex:
```
"@article{engebraaten2020framework,
 title={A Framework for Automatic Behavior Generation in Multi-Function Swarms},
 author={Engebraaten, Sondre A and Moen, Jonas and Yakimenko, Oleg A and Glette, Kyrre},
 journal={arXiv preprint arXiv:2007.08656},
 year={2020}
 }
"
```
An Analysis of Phenotypic Diversity in Multi-Solution Optimization
Authors:
- Alexander Hagg
- Mike Preuss
- Alexander Asteroth
- Thomas Bäck
Abstract:
More and more, optimization methods are used to find diverse solution sets. We compare solution diversity in multi-objective optimization, multimodal optimization, and quality diversity in a simple domain. We show that multiobjective optimization does not always produce much diversity, multimodal optimization produces higher fitness solutions, and quality diversity is not sensitive to genetic neutrality and creates the most diverse set of solutions. An autoencoder is used to discover phenotypic features automatically, producing an even more diverse solution set with quality diversity. Finally, we make recommendations about when to use which approach.
Links:
- Paper
Bibtex:
```
"@inproceedings{hagg2020analysis,
 title={An Analysis of Phenotypic Diversity in Multi-solution Optimization},
 author={Hagg, Alexander and Preuss, Mike and Asteroth, Alexander and B{\"a}ck, Thomas},
 booktitle={International Conference on Bioinspired Methods and Their Applications},
 pages={43--55},
 year={2020},
 organization={Springer}
 }
"
```
BOP-Elites, a Bayesian Optimisation algorithm for Quality-Diversity search
Authors:
- Paul Kent
- Juergen Branke
Abstract:
Quality Diversity (QD) algorithms such as MAP-Elites are a class of optimisation techniques that attempt to find a set of high-performing points from an objective function while enforcing behavioural diversity of the points over one or more interpretable, user chosen, feature functions. In this paper we propose the Bayesian Optimisation of Elites (BOP-Elites) algorithm that uses techniques from Bayesian Optimisation to explicitly model both quality and diversity with Gaussian Processes. By considering user defined regions of the feature space as 'niches' our task is to find the optimal solution in each niche. We propose a novel acquisition function to intelligently choose new points that provide the highest expected improvement to the ensemble problem of identifying the best solution in every niche. In this way each function evaluation enriches our modelling and provides insight to the whole problem, naturally balancing exploration and exploitation of the search space. The resulting algorithm is very effective in identifying the parts of the search space that belong to a niche in feature space, and finding the optimal solution in each niche. It is also significantly more sample efficient than simpler benchmark approaches. BOP-Elites goes further than existing QD algorithms by quantifying the uncertainty around our predictions and offering additional illumination of the search space through surrogate models.
Links:
- Paper
Bibtex:
```
"@article{kent2020bop,
 title={Bop-elites, a bayesian optimisation algorithm for quality-diversity search},
 author={Kent, Paul and Branke, Juergen},
 journal={arXiv preprint arXiv:2005.04320},
 year={2020}
 }
"
```
Baba is Y'all: Collaborative Mixed-Initiative Level Design
Authors:
- Megan Charity
- Ahmed Khalifa
- Julian Togelius
Abstract:
We present a collaborative mixed-initiative system for building levels for the puzzle game 'Baba is You'. Unlike previous mixed-initiative systems, Baba is Y'all is designed for collaborative asynchronous creation by multiple users over the internet. The system includes several AI-assisted features to help designers, including a level evolver and an automated player for playtesting. The level archives catalogues levels according to which mechanics are implemented and not implemented, allowing the system to ask users to design levels with specific combinations of mechanics. We describe the operation of the system and the results of small-scale informal user test, and discuss future development paths for this system as well as for collaborative mixed-initiative systems in general.
Links:
- Paper
Bibtex:
```
"@article{charity2020baba,
title={Baba is Y'all: Collaborative Mixed-Initiative Level Design},
author={Charity, Megan and Khalifa, Ahmed and Togelius, Julian},
journal={arXiv preprint arXiv:2003.14294},
year={2020}}"      
```
Behavioral Repertoires for Soft Tensegrity Robots Robotics
Authors:
- Kyle Doney
- Aikaterini Petridou
- Jacob Karaul
- Ali Khan
- Geoffrey Liu
- John Rieffel
Abstract:
Mobile soft robots offer compelling applications in fields ranging from urban search and rescue to planetary exploration. A critical challenge of soft robotic control is that the nonlinear dynamics imposed by soft materials often result in complex behaviors that are counter-intuitive and hard to model or predict. As a consequence, most behaviors for mobile soft robots are discovered through empirical trial and error and handtuning. A second challenge is that soft materials are difficult to simulate with high fidelity - leading to a significant reality gap when trying to discover or optimize new behaviors. In this work we employ a Quality Diversity Algorithm running model-free on a physical soft tensegrity robot that autonomously generates a behavioral repertoire with no a priori knowledge of the robot’s dynamics, and minimal human intervention. The resulting behavior repertoire displays a diversity of unique locomotive gaits useful for a variety of tasks. These results help provide a road map for increasing the behavioral capabilities of mobile soft robots through real-world automation.
Links:
- Paper
Bibtex:
```
"@article{doney2020behavioral,
title={Behavioral Repertoires for Soft Tensegrity Robots},
author={Doney, Kyle and Petridou, Aikaterini and Karaul, Jacob and Khan, Ali and Liu, Geoffrey and Rieffel, John},
journal={arXiv preprint arXiv:2009.10864},
year={2020}} 
"
```
CPPN2GAN: Combining Compositional Pattern Producing Networks and GANs for Large-scale Pattern Generation
Authors:
- Jacob Schrum
- Vanessa Volz
- Sebastian Risi
Abstract:
Generative Adversarial Networks (GANs) are proving to be a powerful indirect genotype-to-phenotype mapping for evolutionary search, but they have limitations. In particular, GAN output does not scale to arbitrary dimensions, and there is no obvious way of combining multiple GAN outputs into a cohesive whole, which would be useful in many areas, such as the generation of video game levels. Game levels often consist of several segments, sometimes repeated directly or with variation, organized into an engaging pattern. Such patterns can be produced with Compositional Pattern Producing Networks (CPPNs). Specifically, a CPPN can define latent vector GAN inputs as a function of geometry, which provides a way to organize level segments output by a GAN into a complete level. This new CPPN2GAN approach is validated in both Super Mario Bros. and The Legend of Zelda. Specifically, divergent search via MAP-Elites demonstrates that CPPN2GAN can better cover the space of possible levels. The layouts of the resulting levels are also more cohesive and aesthetically consistent.
Links:
- Paper
Bibtex:
```
"@article{schrum2020cppn2gan,
 title={CPPN2GAN: Combining Compositional Pattern Producing Networks and GANs for Large-scale Pattern Generation},
 author={Schrum, Jacob and Volz, Vanessa and Risi, Sebastian},
 booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
 year={2020},
 organization={ACM}}"
```
Competitiveness of MAP-Elites against Proximal Policy Optimization on locomotion tasks in deterministic simulations Robotics
Authors:
- Szymon Brych
- Antoine Cully
Abstract:
The increasing importance of robots and automation creates a demand for learnable controllers which can be obtained through various approaches such as Evolutionary Algorithms (EAs) or Reinforcement Learning (RL). Unfortunately, these two families of algorithms have mainly developed independently and there are only a few works comparing modern EAs with deep RL algorithms. We show that Multidimensional Archive of Phenotypic Elites (MAP-Elites), which is a modern EA, can deliver better-performing solutions than one of the state-of-the-art RL methods, Proximal Policy Optimization (PPO) in the generation of locomotion controllers for a simulated hexapod robot. Additionally, extensive hyper-parameter tuning shows that MAP-Elites displays greater robustness across seeds and hyper-parameter sets. Generally, this paper demonstrates that EAs combined with modern computational resources display promising characteristics and have the potential to contribute to the state-of-the-art in controller learning.
Links:
- Paper
Bibtex:
```
"@article{brych2020competitiveness,
 title={Competitiveness of MAP-Elites against Proximal Policy Optimization on locomotion tasks in deterministic simulations},
 author={Brych, Szymon and Cully, Antoine},
 journal={arXiv preprint arXiv:2009.08438},
 year={2020}
 }
"
```
Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space Games
Authors:
- Matthew C. Fontaine
- Julian Togelius
- Stefanos Nikolaidis
- Amy K. Hoover
Abstract:
We focus on the challenge of finding a diverse collection of quality solutions on complex continuous domains. While quality diver-sity (QD) algorithms like Novelty Search with Local Competition (NSLC) and MAP-Elites are designed to generate a diverse range of solutions, these algorithms require a large number of evaluations for exploration of continuous spaces. Meanwhile, variants of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) are among the best-performing derivative-free optimizers in single-objective continuous domains. This paper proposes a new QD algorithm called Covariance Matrix Adaptation MAP-Elites (CMA-ME). Our new algorithm combines the self-adaptation techniques of CMA-ES with archiving and mapping techniques for maintaining diversity in QD. Results from experiments based on standard continuous optimization benchmarks show that CMA-ME finds better-quality solutions than MAP-Elites; similarly, results on the strategic game Hearthstone show that CMA-ME finds both a higher overall quality and broader diversity of strategies than both CMA-ES and MAP-Elites. Overall, CMA-ME more than doubles the performance of MAP-Elites using standard QD performance metrics. These results suggest that QD algorithms augmented by operators from state-of-the-art optimization algorithms can yield high-performing methods for simultaneously exploring and optimizing continuous search spaces, with significant applications to design, testing, and reinforcement learning among other domains.
Links:
- Paper
Bibtex:
```
"@article{fontaine2019covariance,
 title={Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space},
 author={Fontaine, Matthew C and Togelius, Julian and Nikolaidis, Stefanos and Hoover, Amy K},
 booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
 year={2020},
 organization={ACM}}"
```
DREAM Architecture: a Developmental Approach to Open-Ended Learning in Robotics Robotics
Authors:
- Stephane Doncieux
- Nicolas Bredeche
- Léni Le Goff
- Benoît Girard
- Alexandre Coninx
- Olivier Sigaud
- Mehdi Khamassi
- Natalia Díaz-Rodríguez
- David Filliat
- Timothy Hospedales
- A. Eiben
- Richard Duro
Abstract:
Robots are still limited to controlled conditions, that the robot designer knows with enough details to endow the robot with the appropriate models or behaviors. Learning algorithms add some flexibility with the ability to discover the appropriate behavior given either some demonstrations or a reward to guide its exploration with a reinforcement learning algorithm. Reinforcement learning algorithms rely on the definition of state and action spaces that define reachable behaviors. Their adaptation capability critically depends on the representations of these spaces: small and discrete spaces result in fast learning while large and continuous spaces are challenging and either require a long training period or prevent the robot from converging to an appropriate behavior. Beside the operational cycle of policy execution and the learning cycle, which works at a slower time scale to acquire new policies, we introduce the redescription cycle, a third cycle working at an even slower time scale to generate or adapt the required representations to the robot, its environment and the task. We introduce the challenges raised by this cycle and we present DREAM (Deferred Restructuring of Experience in Autonomous Machines), a developmental cognitive architecture to bootstrap this redescription process stage by stage, build new state representations with appropriate motivations, and transfer the acquired knowledge across domains or tasks or even across robots. We describe results obtained so far with this approach and end up with a discussion of the questions it raises in Neuroscience.
Links:
- Paper
Bibtex:
```
"@article{doncieux2020dream,
 title={Dream architecture: a developmental approach to open-ended learning in robotics},
 author={Doncieux, Stephane and Bredeche, Nicolas and Goff, L{\'e}ni Le and Girard, Beno{\^\i}t and Coninx, Alexandre and Sigaud, Olivier and Khamassi, Mehdi and D{\'\i}az-Rodr{\'\i}guez, Natalia and Filliat, David and Hospedales, Timothy and others},
 journal={arXiv preprint arXiv:2005.06223},
 year={2020}
 }
"
```
Discovering Representations for Black-box Optimization
Authors:
- Adam Gaier
- Alexander Asteroth
- Jean-Baptiste Mouret
Abstract:
The encoding of solutions in black-box optimization is a delicate, handcrafted balance between expressiveness and domain knowledge between exploring a wide variety of solutions, and ensuring that those solutions are useful. Our main insight is that this process can be automated by generating a dataset of high-performing solutions with a quality diversity algorithm (here, MAP-Elites), then learning a representation with a generative model (here, a Varia-tional Autoencoder) from that dataset. Our second insight is that this representation can be used to scale quality diversity optimization to higher dimensions-but only if we carefully mix solutions generated with the learned representation and those generated with traditional variation operators. We demonstrate these capabilities by learning an low-dimensional encoding for the inverse kinemat-ics of a thousand joint planar arm. The results show that learned representations make it possible to solve high-dimensional problems with orders of magnitude fewer evaluations than the standard MAP-Elites, and that, once solved, the produced encoding can be used for rapid optimization of novel, but similar, tasks. The presented techniques not only scale up quality diversity algorithms to high dimensions, but show that black-box optimization encodings can be automatically learned, rather than hand designed.
Links:
- Paper
Bibtex:
```
"@inproceedings{gaier:hal-02555221,
 TITLE = {{Discovering Representations for Black-box Optimization}},
 AUTHOR = {Gaier, Adam and Asteroth, Alexander and Mouret, Jean-Baptiste},
 URL = {https://hal.inria.fr/hal-02555221},
 BOOKTITLE = {{GECCO'20 - Genetic and Evolutionary Computation Conference}},
 ADDRESS = {Cancun, Mexico},
 VOLUME = {11},
 YEAR = {2020},
 MONTH = Jul,
 DOI = {10.1145/3377930.3390221},
 PDF = {https://hal.inria.fr/hal-02555221/file/dde_gecco.pdf},
 HAL_ID = {hal-02555221},
 HAL_VERSION = {v1}}"
```
Diversity-based Design Assist for Large Legged Robots
Authors:
- David Howard
- Thomas Lowe
- Wade Geles
Abstract:
We combine MAP-Elites and highly parallelisable simulation to explore the design space of a class of large legged robots, which stand at around 2m tall and whose design and construction is not well-studied. The simulation is modified to account for factors such as motor torque and weight, and presents a reasonable fidelity search space. A novel robot encoding allows for bio-inspired features such as legs scaling along the length of the body. The impact of three possible control generation schemes are assessed in the context of body-brain co-evolution, showing that even constrained problems benefit strongly from coupling-promoting mechanisms. A two stage process in implemented. In the first stage, a library of possible robots is generated, treating user requirements as constraints. In the second stage, the most promising robot niches are analysed and a suite of human-understandable design rules generated related to the values of their feature variables. These rules, together with the library, are then ready to be used by a (human) robot designer as a Design Assist tool.
Links:
- Paper
Bibtex:
```
"@article{howard2020diversity,
title={Diversity-based Design Assist for Large Legged Robots},
author={Howard, David and Lowe, Thomas and Geles, Wade},
journal={arXiv preprint arXiv:2004.08057},
year={2020}}"       
```
EGAD! an Evolved Grasping Analysis Dataset for diversity and reproducibility in robotic manipulation
Authors:
- Douglas Morrison
- Peter Corke
- Jürgen Leitner
Abstract:
We present the Evolved Grasping Analysis Dataset (EGAD), comprising over 2000 generated objects aimed at training and evaluating robotic visual grasp detection algorithms. The objects in EGAD are geometrically diverse, filling a space ranging from simple to complex shapes and from easy to difficult to grasp, compared to other datasets for robotic grasping, which may be limited in size or contain only a small number of object classes. Additionally, we specify a set of 49 diverse 3D-printable evaluation objects to encourage reproducible testing of robotic grasping systems across a range of complexity and difficulty. The dataset, code and videos can be found at this URL
Links:
- Paper
Bibtex:
```
"@article{morrison2020egad,
title={EGAD! an Evolved Grasping Analysis Dataset for diversity and reproducibility in robotic manipulation},
author={Morrison, Douglas and Corke, Peter and Leitner, Jurgen},
journal={IEEE Robotics and Automation Letters},
year={2020},
publisher={IEEE}}"       
```
Effective Diversity in Population Based Reinforcement Learning
Authors:
- Jack Parker-Holder
- Aldo Pacchiano
- Krzysztof Choromanski
- Stephen Roberts
Abstract:
Exploration is a key problem in reinforcement learning, since agents can only learn from data they acquire in the environment. With that in mind, maintaining a population of agents is an attractive method, as it allows data be collected with a diverse set of behaviors. This behavioral diversity is often boosted via multi-objective loss functions. However, those approaches typically leverage mean field updates based on pairwise distances, which makes them susceptible to cycling behaviors and increased redundancy. In addition, explicitly boosting diversity often has a detrimental impact on optimizing already fruitful behaviors for rewards. As such, the reward-diversity trade off typically relies on heuristics. Finally, such methods require behavioral representations, often handcrafted and domain specific. In this paper, we introduce an approach to optimize all members of a population simultaneously. Rather than using pairwise distance, we measure the volume of the entire population in a behavioral manifold, defined by task-agnostic behavioral embeddings. In addition, our algorithm Diversity via Determinants (DvD), adapts the degree of diversity during training using online learning techniques. We introduce both evolutionary and gradient-based instantiations of DvD and show they effectively improve exploration without reducing performance when better exploration is not required.
Links:
- Paper
Bibtex:
```
"@article{2020arXiv200200632P,
  author = {{Parker-Holder}, Jack and {Pacchiano}, Aldo and
  {Choromanski}, Krzysztof and {Roberts}, Stephen},
  title = "{Effective Diversity in Population Based Reinforcement Learning}",
  journal = {arXiv e-prints},
  keywords = {Computer Science - Machine Learning, Statistics - Machine Learning},
  year = 2020,
  month = feb,
  eid = {arXiv:2002.00632},
  pages = {arXiv:2002.00632},
  archivePrefix = {arXiv},
  eprint = {2002.00632},
  primaryClass = {cs.LG},
  adsurl = {https://ui.adsabs.harvard.edu/abs/2020arXiv200200632P},
  adsnote = {Provided by the SAO/NASA Astrophysics Data System}
  }"
```
Enhanced POET: Open-Ended Reinforcement Learning through Unbounded Invention of Learning Challenges and their Solutions Robotics
Authors:
- Rui Wang
- Joel Lehman
- Aditya Rawal
- Jiale Zhi
- Yulun Li
- Jeff Clune
- Kenneth O. Stanley
Abstract:
Creating open-ended algorithms, which generate their own never-ending stream of novel and appropriately challenging learning opportunities, could help to automate and accelerate progress in machine learning. A recent step in this direction is the Paired Open-Ended Trailblazer (POET), an algorithm that generates and solves its own challenges, and allows solutions to goal-switch between challenges to avoid local optima. However, the original POET was unable to demonstrate its full creative potential because of limitations of the algorithm itself and because of external issues including a limited problem space and lack of a universal progress measure. Importantly, both limitations pose impediments not only for POET, but for the pursuit of open-endedness in general. Here we introduce and empirically validate two new innovations to the original algorithm, as well as two external innovations designed to help elucidate its full potential. Together, these four advances enable the most open-ended algorithmic demonstration to date. The algorithmic innovations are (1) a domain-general measure of how meaningfully novel new challenges are, enabling the system to potentially create and solve interesting challenges endlessly, and (2) an efficient heuristic for determining when agents should goal-switch from one problem to another (helping open-ended search better scale). Outside the algorithm itself, to enable a more definitive demonstration of open-endedness, we introduce (3) a novel, more flexible way to encode environmental challenges, and (4) a generic measure of the extent to which a system continues to exhibit open-ended innovation. Enhanced POET produces a diverse range of sophisticated behaviors that solve a wide range of environmental challenges, many of which cannot be solved through other means.
Links:
- Paper
Bibtex:
```
"@inproceedings{wang2020enhanced,
 title={Enhanced POET: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions},
 author={Wang, Rui and Lehman, Joel and Rawal, Aditya and Zhi, Jiale and Li, Yulun and Clune, Jeffrey and Stanley, Kenneth},
 booktitle={International Conference on Machine Learning},
 pages={9940--9951},
 year={2020},
 organization={PMLR}
 }
"
```
Environmental Adaptation of Robot Morphology and Control through Real-world Evolution
Authors:
- Tønnes F. Nygaard
- Charles P. Martin
- David Howard
- Jim Torresen
- Kyrre Glette
Abstract:
Robots operating in the real world will experience a range of different environments and tasks. It is essential for the robot to have the ability to adapt to its surroundings to work efficiently in changing conditions. Evolutionary robotics aims to solve this by optimizing both the control and body (morphology) of a robot, allowing adaptation to internal, as well as external factors. Most work in this field has been done in physics simulators, which are relatively simple and not able to replicate the richness of interactions found in the real world. Solutions that rely on the complex interplay between control, body, and environment are therefore rarely found. In this paper, we rely solely on real-world evaluations and apply evolutionary search to yield combinations of morphology and control for our mechanically self-reconfiguring quadruped robot. We evolve solutions on two very different physical surfaces and analyze the results in terms of both control and morphology. We then transition to two previously unseen surfaces to demonstrate the generality of our method. We find that the evolutionary search adapts both control and body to the different physical environments, yielding significantly different morphology-controller configurations. Moreover, we observe that the solutions found by our method work well on previously unseen terrains.
Links:
- Paper
Bibtex:
```
"@article{nygaard2020environmental,
title={Environmental Adaptation of Robot Morphology and Control through Real-world Evolution},
author={Nygaard, T{\o}nnes F and Martin, Charles P and Howard, David and Torresen, Jim and Glette, Kyrre},
journal={arXiv preprint arXiv:2003.13254},
year={2020}}"          
```
Evolving the behavior of machines: from micro to macroevolution Review
Authors:
- Jean-Baptiste Mouret
Abstract:
Evolution gave rise to creatures that are arguably more sophisticated than the greatest human-designed systems. This feat has inspired computer scientists since the advent of computing and led to optimization tools that can evolve complex neural networks for machines—an approach known as “neuroevolution.” After a few successes in designing evolvable representations for high-dimensional artifacts, the field has been recently revitalized by going beyond optimization: to many, the wonder of evolution is less in the perfect optimization of each species than in the creativity of such a simple iterative process, that is, in the diversity of species. This modern view of artificial evolution is moving the field away from microevolution, following a fitness gradient in a niche, to macroevolution, filling many niches with highly different species. It already opened promising applications, like evolving gait repertoires, video game levels for different tastes, and diverse designs for aerodynamic bikes.
Links:
- Paper
Bibtex:
```
"@article{mouret2020evolving,
  title={Evolving the behavior of machines: from micro to macroevolution},
  author={Mouret, Jean-Baptiste},
  journal={Iscience},
  pages={101731},
  year={2020},
  publisher={Elsevier}
}"
```

Exploring the BipedalWalker benchmark with MAP-Elites and Curiosity-driven A3C

Authors:

Vikas Gupta
Nathanael Aubert-Kato
Leo Cazenille

Bibtex:

"@article{gupta2020exploring,
title={Exploring the BipedalWalker benchmark with MAP-Elites and Curiosity-driven A3C},
author={Gupta, Vikas and Aubert-Kato, Nathanael and Cazenille, Leo},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
year={2020},
organization={ACM}}"

Exploring the Evolution of GANs through Quality Diversity

Authors:

Victor Costa
Nuno Lourenço
Joao Correia
Penousal Machado

Bibtex:

"@inproceedings{justesen2019map,
 title={Exploring the Evolution of GANs through Quality Diversity},
 author={Costa, Victor and Lourenço, Nuno and Correia, Joao and Machado, Penousal},
 booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
 year={2020},
 organization={ACM}}"

Fast and stable MAP-Elites in noisy domains using deep grids
Authors:
- Manon Flageat
- Antoine Cully
Abstract:
Quality-Diversity optimisation algorithms enable the evolution of collections of both high-performing and diverse solutions. These collections offer the possibility to quickly adapt and switch from one solution to another in case it is not working as expected. It therefore finds many applications in real-world domain problems such as robotic control. However, QD algorithms, like most optimisation algorithms, are very sensitive to uncertainty on the fitness function, but also on the behavioural descriptors. Yet, such uncertainties are frequent in real-world applications. Few works have explored this issue in the specific case of QD algorithms, and inspired by the literature in Evolutionary Computation, mainly focus on using sampling to approximate the true value of the performances of a solution. However, sampling approaches require a high number of evaluations, which in many applications such as robotics, can quickly become impractical. In this work, we propose Deep-Grid MAP-Elites, a variant of the MAP-Elites algorithm that uses an archive of similar previously encountered solutions to approximate the performance of a solution. We compare our approach to previously explored ones on three noisy tasks: a standard optimisation task, the control of a redundant arm and a simulated Hexapod robot. The experimental results show that this simple approach is significantly more resilient to noise on the behavioural descriptors, while achieving competitive performances in terms of fitness optimisation, and being more sample-efficient than other existing approaches.
Links:
- Paper
Bibtex:
```
"@article{flageat2020fast,
title={Fast and stable MAP-Elites in noisy domains using deep grids},
author={Flageat, Manon and Cully, Antoine},
booktitle={Proceedings of the 2020 Conference on Artificial Life},
year={2020}}"   
```
Finding Game Levels with the Right Difficulty in a Few Trials through Intelligent Trial-and-Error
Authors:
- Miguel González-Duque
- Rasmus Berg Palm
- David Ha
- Sebastian Risi
Abstract:
Methods for dynamic difficulty adjustment allow games to be tailored to particular players to maximize their engagement. However, current methods often only modify a limited set of game features such as the difficulty of the opponents, or the availability of resources. Other approaches, such as experience-driven Procedural Content Generation (PCG), can generate complete levels with desired properties such as levels that are neither too hard nor too easy, but require many iterations. This paper presents a method that can generate and search for complete levels with a specific target difficulty in only a few trials. This advance is enabled by through an Intelligent Trial-and-Error algorithm, originally developed to allow robots to adapt quickly. Our algorithm first creates a large variety of different levels that vary across predefined dimensions such as leniency or map coverage. The performance of an AI playing agent on these maps gives a proxy for how difficult the level would be for another AI agent (e.g. one that employs Monte Carlo Tree Search instead of Greedy Tree Search); using this information, a Bayesian Optimization procedure is deployed, updating the difficulty of the prior map to reflect the ability of the agent. The approach can reliably find levels with a specific target difficulty for a variety of planning agents in only a few trials, while maintaining an understanding of their skill landscape.
Links:
- Paper
Bibtex:
```
"@article{gonzalez2020finding,
title={Finding Game Levels with the Right Difficulty in a Few Trials through Intelligent Trial-and-Error},
author={Gonz{\'a}lez-Duque, Miguel and Palm, Rasmus Berg and Ha, David and Risi, Sebastian},
journal={arXiv preprint arXiv:2005.07677},
year={2020}}"   
```
Generating and Adapting to Diverse Ad-Hoc Cooperation Agents in Hanabi
Authors:
- Rodrigo Canaan
- Xianbo Gao
- Julian Togelius
- Andy Nealen
- Stefan Menzel
Abstract:
Hanabi is a cooperative game that brings the problem of modeling other players to the forefront. In this game, coordinated groups of players can leverage pre-established conventions to great effect, but playing in an ad-hoc setting requires agents to adapt to its partner's strategies with no previous coordination. Evaluating an agent in this setting requires a diverse population of potential partners, but so far, the behavioral diversity of agents has not been considered in a systematic way. This paper proposes Quality Diversity algorithms as a promising class of algorithms to generate diverse populations for this purpose, and generates a population of diverse Hanabi agents using MAP-Elites. We also postulate that agents can benefit from a diverse population during training and implement a simple 'meta-strategy' for adapting to an agent's perceived behavioral niche. We show this meta-strategy can work better than generalist strategies even outside the population it was trained with if its partner's behavioral niche can be correctly inferred, but in practice a partner's behavior depends and interferes with the meta-agent's own behavior, suggesting an avenue for future research in characterizing another agent's behavior during gameplay.
Links:
- Paper
Bibtex:
```
"@article{canaan2020generating,
title={Generating and Adapting to Diverse Ad-Hoc Cooperation Agents in Hanab},
author={Canaan, Rodrigo and Gao, Xianbo and Togelius, Julian and Nealen, Andy and Menzel, Stefan},
journal={arXiv preprint arXiv:2004.13710},
year={2020}}"  
```
Harnessing Distribution Ratio Estimators for Learning Agents with Quality and Diversity Robotics
Authors:
- Tanmay Gangwani
- Jian Peng
- Yuan Zhou
Abstract:
Quality-Diversity (QD) is a concept from Neuroevolution with some intriguing applications to Reinforcement Learning. It facilitates learning a population of agents where each member is optimized to simultaneously accumulate high task-returns and exhibit behavioral diversity compared to other members. In this paper, we build on a recent kernel-based method for training a QD policy ensemble with Stein variational gradient descent. With kernels based on f-divergence between the stationary distributions of policies, we convert the problem to that of efficient estimation of the ratio of these stationary distributions. We then study various distribution ratio estimators used previously for off-policy evaluation and imitation and re-purpose them to compute the gradients for policies in an ensemble such that the resultant population is diverse and of high-quality.
Links:
- Paper
Bibtex:
```
"@inproceedings{gangwani2020harnessing,
 title={Harnessing Distribution Ratio Estimators for Learning Agents with Quality and Diversity},
 author={Gangwani, Tanmay and Peng, Jian and Zhou, Yuan},
 booktitle={Proceedings of the CoRL 2020},
 year={2020}
 }
"
```
Illuminating Elite Patches of Chemical Space
Authors:
- Jonas Verhellen
- Jeriek Van den Abeele
Abstract:
In the past few years, there has been considerable activity in both academic and industrial research to develop innovative machine learning approaches to locate novel, high-performing molecules in chemical space. Here we describe a new and fundamentally different type of approach that provides a holistic overview of how high-performing molecules are distributed throughout a search space. Based on an open-source, graph-based implementation [Jensen, Chem. Sci., 2019, 12, 3567-3572] of a traditional genetic algorithm for molecular optimisation, and influenced by state-of-the-art concepts from soft robot design [Mouret et al., IEEE Trans. Evolut. Comput., 2016, 22, 623-630], we provide an algorithm that (i) produces a large diversity of high-performing, yet qualitatively different molecules, (ii) illuminates the distribution of optimal solutions, and (iii) improves search efficiency compared to both machine learning and traditional genetic algorithm approaches.
Links:
- Paper
Bibtex:
```
"@article{Verhellen2020,
author = "Jonas Verhellen and Jeriek Van den Abeele",
title = "{Illuminating Elite Patches of Chemical Space}",
year = "2020",
month = "7",
url = "https://chemrxiv.org/articles/preprint/Illuminating_Elite_Patches_of_Chemical_Space/12608228",
doi = "10.26434/chemrxiv.12608228.v1"}"   
```
Illuminating Mario Scenes in the Latent Space of a Generative Adversarial Network
Authors:
- Matthew C. Fontaine
- Ruilin Liu
- Ahmed Khalifa
- Jignesh Modi
- Julian Togelius
- Amy K. Hoover
- Stefanos Nikolaidis
Abstract:
Generative adversarial networks (GANs) are now a ubiquitous approach to procedurally generating video game levels. While GAN generated levels are stylistically similar to human-authored examples, human designers often want to explore the generative design space of GANs to extract interesting levels. However, human designers find latent vectors opaque and would rather explore along dimensions the designer specifies, such as number of enemies or obstacles. We propose using state-of-the-art quality diversity algorithms designed to optimize continuous spaces, i.e. MAP-Elites with a directional variation operator and Covariance Matrix Adaptation MAP-Elites, to efficiently explore the latent space of a GAN to extract levels that vary across a set of specified gameplay measures. In the benchmark domain of Super Mario Bros, we demonstrate how designers may specify gameplay measures to our system and extract high-quality (playable) levels with a diverse range of level mechanics, while still maintaining stylistic similarity to human authored examples. An online user study shows how the different mechanics of the automatically generated levels affect subjective ratings of their perceived difficulty and appearance.
Links:
- Paper
Bibtex:
```
"@misc{fontaine2020illuminating,
title={Illuminating Mario Scenes in the Latent Space of a Generative Adversarial Network}, 
author={Matthew C. Fontaine and Ruilin Liu and Ahmed Khalifa and Jignesh Modi and Julian Togelius and Amy K. Hoover and Stefanos Nikolaidis},
year={2020},
eprint={2007.05674},
archivePrefix={arXiv},
primaryClass={cs.AI}
}"
```

Illuminating Super Mario Bros - Quality-Diversity Within Platformer Level Generation

Authors:

Oliver Henry Withington

Bibtex:

"@article{Withington2020illuminating,
title={Illuminating Super Mario Bros - Quality-Diversity Within Platformer Level Generation},
author={Withington, Oliver Henry},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
year={2020},
organization={ACM}}"

Interactive Constrained MAP-Elites Analysis and Evaluation of the Expressiveness of the Feature Dimensions
Authors:
- Alberto Alvarez
- Steve Dahlskog
- Jose Font
- Julian Togelius
Abstract:
We propose the Interactive Constrained MAP-Elites, a quality-diversity solution for game content generation, implemented as a new feature of the Evolutionary Dungeon Designer: a mixed-initiative co-creativity tool for designing dungeons. The feature uses the MAP-Elites algorithm, an illumination algorithm that segregates the population among several cells depending on their scores with respect to different behavioral dimensions. Users can flexibly and dynamically alternate between these dimensions anytime, thus guiding the evolutionary process in an intuitive way, and then incorporate suggestions produced by the algorithm in their room designs. At the same time, any modifications performed by the human user will feed back into MAP-Elites, closing a circular workflow of constant mutual inspiration. This paper presents the algorithm followed by an in-depth analysis of its behaviour, with the aims of evaluating the expressive range of all possible dimension combinations in several scenarios, as well as discussing their influence in the fitness landscape and in the overall performance of the mixed-initiative procedural content generation.
Links:
- Paper
Bibtex:
```
"@article{alvarez2020interactive,
title={Interactive Constrained MAP-Elites Analysis and Evaluation of the Expressiveness of the Feature Dimensions},
author={Alvarez, Alberto and Dahlskog, Steve and Font, Jose and Togelius, Julian},
journal={arXiv preprint arXiv:2003.03377},
year={2020}}"       
```
Interactive Constrained MAP-Elites: Analysis and Evaluation of the Expressiveness of the Feature Dimensions Games
Authors:
- Alberto Alvarez
- Steve Dahlskog
- Jose Font
- Julian Togelius
Abstract:
We propose the Interactive Constrained MAP-Elites, a quality-diversity solution for game content generation, implemented as a new feature of the Evolutionary Dungeon Designer: a mixed-initiative co-creativity tool for designing dungeons. The feature uses the MAP-Elites algorithm, an illumination algorithm that segregates the population among several cells depending on their scores with respect to different behavioral dimensions. Users can flexibly and dynamically alternate between these dimensions anytime, thus guiding the evolutionary process in an intuitive way, and then incorporate suggestions produced by the algorithm in their room designs. At the same time, any modifications performed by the human user will feed back into MAP-Elites, closing a circular workflow of constant mutual inspiration. This paper presents the algorithm followed by an in-depth analysis of its behaviour, with the aims of evaluating the expressive range of all possible dimension combinations in several scenarios, as well as discussing their influence in the fitness landscape and in the overall performance of the mixed-initiative procedural content generation.
Links:
- Paper
Bibtex:
```
"@article{alvarez2020interactive,
 title={Interactive constrained map-elites: Analysis and evaluation of the expressiveness of the feature dimensions},
 author={Alvarez, Alberto and Fernandez, Jose Maria Maria Font and Dahlskog, Steve and Togelius, Julian},
 journal={IEEE Transactions on Games},
 year={2020},
 publisher={IEEE}
 }
"
```
Learning a Behavioral Repertoire from Demonstrations Games
Authors:
- Niels Justesen
- Miguel Gonzalez Duque
- Daniel Cabarcas Jaramillo
- Jean-Baptiste Mouret
- Sebastian Risi
Abstract:
Imitation Learning (IL) is a machine learning approach to learn a policy from a dataset of demonstrations. IL can be useful to kick-start learning before applying reinforcement learning (RL) but it can also be useful on its own, e.g. to learn to imitate human players in video games. However, a major limitation of current IL approaches is that they learn only a single 'average' policy based on a dataset that possibly contains demonstrations of numerous different types of behaviors. In this paper, we propose a new approach called Behavioral Repertoire Imitation Learning (BRIL) that instead learns a repertoire of behaviors from a set of demonstrations by augmenting the state-action pairs with behavioral descriptions. The outcome of this approach is a single neural network policy conditioned on a behavior description that can be precisely modulated. We apply this approach to train a policy on 7,777 human replays to perform build-order planning in StarCraft II. Principal Component Analysis (PCA) is applied to construct a low-dimensional behavioral space from the high-dimensional army unit composition of each demonstration. The results demonstrate that the learned policy can be effectively manipulated to express distinct behaviors. Additionally, by applying the UCB1 algorithm, we are able to adapt the behavior of the policy - in-between games - to reach a performance beyond that of the traditional IL baseline approach.
Links:
- Paper
Bibtex:
```
"@inproceedings{justesen2020learning,
 title={Learning a Behavioral Repertoire from Demonstrations},
 author={Justesen, Niels and Gonz{\'a}lez-Duque, Miguel and Cabarcas, Daniel and Mouret, Jean-Baptiste and Risi, Sebastian},
 booktitle={2020 IEEE Conference on Games (CoG)},
 pages={383--390},
 year={2020},
 organization={IEEE}
 }
"
```
Learning behaviour-performance maps with meta-evolution
Authors:
- David Bossens
- Jean-Baptiste Mouret
- Danesh Tarapore
Abstract:
The MAP-Elites quality-diversity algorithm has been successful in robotics because it can create a behaviorally diverse set of solutions that later can be used for adaptation, for instance to unanticipated damages. In MAP-Elites, the choice of the behaviour space is essential for adaptation, the recovery of performance in unseen environments , since it defines the diversity of the solutions. Current practice is to hand-code a set of behavioural features, however, given the large space of possible behaviour-performance maps, the designer does not know a priori which behavioural features maximise a map's adaptation potential. We introduce a new meta-evolution algorithm that discovers those behavioural features that maximise future adaptations. The proposed method applies Covari-ance Matrix Adaptation Evolution Strategy to evolve a population of behaviour-performance maps to maximise a meta-fitness function that rewards adaptation. The method stores solutions found by MAP-Elites in a database which allows to rapidly construct new behaviour-performance maps on-the-fly. To evaluate this system , we study the gait of the RHex robot as it adapts to a range of damages sustained on its legs. When compared to MAP-Elites with user-defined behaviour spaces, we demonstrate that the meta-evolution system learns high-performing gaits with or without damages injected to the robot.
Links:
- Paper
Bibtex:
```
"@inproceedings{bossens:hal-02555231,
 TITLE = {{Learning behaviour-performance maps with meta-evolution}},
 AUTHOR = {Bossens, David M and Mouret, Jean-Baptiste and Tarapore, Danesh},
 URL = {https://hal.inria.fr/hal-02555231},
 BOOKTITLE = {{GECCO'20 - Genetic and Evolutionary Computation Conference}},
 ADDRESS = {Cancun, Mexico},
 YEAR = {2020},
 MONTH = Jul,
 KEYWORDS = {Learning paradigms ; quality-diversity algorithms ; behavioural diversity ; meta-learning ; evolutionary robotics ; damage recovery},
 PDF = {https://hal.inria.fr/hal-02555231/file/pap349s3-file1.pdf},
 HAL_ID = {hal-02555231},
 HAL_VERSION = {v1}}"
 
```
Learning the Designer's Preferences to Drive Evolution
Authors:
- Alberto Alvarez
- Jose Font
Abstract:
This paper presents the Designer Preference Model, a data-driven solution that pursues to learn from user generated data in a Quality-Diversity Mixed-Initiative Co-Creativity (QD MI-CC) tool, with the aims of modelling the user's design style to better assess the tool's procedurally generated content with respect to that user's preferences. Through this approach, we aim for increasing the user's agency over the generated content in a way that neither stalls the user-tool reciprocal stimuli loop nor fatigues the user with periodical suggestion handpicking. We describe the details of this novel solution, as well as its implementation in the MI-CC tool the Evolutionary Dungeon Designer. We present and discuss our findings out of the initial tests carried out, spotting the open challenges for this combined line of research that integrates MI-CC with Procedural Content Generation through Machine Learning.
Links:
- Paper
Bibtex:
```
"@inproceedings{alvarez2020learning,
title={Learning the designer’s preferences to drive evolution},
author={Alvarez, Alberto and Font, Jose},
booktitle={International Conference on the Applications of Evolutionary Computation (Part of EvoStar)},
pages={431--445},
year={2020},
organization={Springer}}"                 
```
Mech-Elites: Illuminating the Mechanic Space of GVGAI
Authors:
- Megan Charity
- Michael Cerny Green
- Ahmed Khalifa
- Julian Togelius
Abstract:
This paper introduces a fully automatic method of mechanic illumination for general video game level generation. Using the Constrained MAP-Elites algorithm and the GVG-AI framework, this system generates the simplest tile based levels that contain specific sets of game mechanics and also satisfy playability constraints. We apply this method to illuminate mechanic space for 4 different games in GVG-AI: Zelda, Solarfox, Plants, and RealPortals.
Links:
- Paper
Bibtex:
```
"@article{charity2020mech,
title={Mech-Elites: Illuminating the Mechanic Space of GVGAI},
author={Charity, Megan and Green, Michael Cerny and Khalifa, Ahmed and Togelius, Julian},
journal={arXiv preprint arXiv:2002.04733},
year={2020}}"       
```
Mech-Elites: Illuminating the Mechanic Space of GVGAI Games
Authors:
- Megan Charity
- Michael Cerny Green
- Ahmed Khalifa
- Julian Togelius
Abstract:
This paper introduces a fully automatic method of mechanic illumination for general video game level generation. Using the Constrained MAP-Elites algorithm and the GVG-AI framework, this system generates the simplest tile based levels that contain specific sets of game mechanics and also satisfy playability constraints. We apply this method to illuminate mechanic space for 4 different games in GVG-AI: Zelda, Solarfox, Plants, and RealPortals.
Links:
- Paper
Bibtex:
```
"@inproceedings{charity2020mech,
 title={Mech-Elites: Illuminating the Mechanic Space of GVG-AI},
 author={Charity, Megan and Green, Michael Cerny and Khalifa, Ahmed and Togelius, Julian},
 booktitle={International Conference on the Foundations of Digital Games},
 pages={1--10},
 year={2020}
 }
"
```
Model-Based Quality-Diversity Search for Efficient Robot Learning
Authors:
- Leon Keller
- Daniel Tanneberg
- Svenja Stark
- Jan Peters
Abstract:
Despite recent progress in robot learning, it still remains a challenge to program a robot to deal with open-ended object manipulation tasks. One approach that was recently used to autonomously generate a repertoire of diverse skills is a novelty based Quality-Diversity (QD) algorithm. However, as most evolutionary algorithms, QD suffers from sample- inefficiency and, thus, it is challenging to apply it in real-world scenarios. This paper tackles this problem by integrating a neural network that predicts the behavior of the perturbed parameters into a novelty based QD algorithm. In the proposed Model-based Quality-Diversity search (M-QD), the network is trained concurrently to the repertoire and is used to avoid executing unpromising actions in the novelty search process. Furthermore, it is used to adapt the skills of the final repertoire in order to generalize the skills to different scenarios. Our experiments show that enhancing a QD algorithm with such a forward model improves the sample-efficiency and performance of the evolutionary process and the skill adaptation.
Links:
- Paper
Bibtex:
```
"@inproceedings{keller2021,
title={Model-Based Quality-Diversity Search for Efficient Robot Learning}, 
author={Keller, Leon and Tanneberg, Daniel and Stark, Svenja and Peters, Jan},
year={2020},
booktitle={IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)}
}"
```
Path Towards Multilevel Evolution of Robots Robotics
Authors:
- Shelvin Chand
- David Howard
Abstract:
Multi-level evolution is a bottom-up robotic design paradigm which decomposes the design problem into layered sub-tasks that involve concurrent search for appropriate materials, component geometry and overall morphology. Each of the three layers operate with the goal of building a library of diverse candidate solutions which will be used either as building blocks for the layer above or provided to the decision maker for final use. In this paper we provide a theoretical discussion on the concepts and technologies that could potentially be used as building blocks for this framework.
Links:
- Paper
Bibtex:
```
"@inproceedings{chand2020path,
 title={Path towards multilevel evolution of robots},
 author={Chand, Shelvin and Howard, David},
 booktitle={Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion},
 pages={1381--1382},
 year={2020}
 }
"
```
Policy Manifold Search for Improving Diversity-based Neuroevolution Robotics
Authors:
- Nemanja Rakicevic
- Antoine Cully
- Petar Kormushev
Abstract:
Diversity-based approaches have recently gained popularity as an alternative paradigm to performance-based policy search. A popular approach from this family, Quality-Diversity (QD), maintains a collection of high-performing policies separated in the diversity-metric space, defined based on policies' rollout behaviours. When policies are parameterised as neural networks, i.e. Neuroevolution, QD tends to not scale well with parameter space dimensionality. Our hypothesis is that there exists a low-dimensional manifold embedded in the policy parameter space, containing a high density of diverse and feasible policies. We propose a novel approach to diversity-based policy search via Neuroevolution, that leverages learned latent representations of the policy parameters which capture the local structure of the data. Our approach iteratively collects policies according to the QD framework, in order to (i) build a collection of diverse policies, (ii) use it to learn a latent representation of the policy parameters, (iii) perform policy search in the learned latent space. We use the Jacobian of the inverse transformation (i.e.reconstruction function) to guide the search in the latent space. This ensures that the generated samples remain in the high-density regions of the original space, after reconstruction. We evaluate our contributions on three continuous control tasks in simulated environments, and compare to diversity-based baselines. The findings suggest that our approach yields a more efficient and robust policy search process.
Links:
- Paper
Bibtex:
```
"@article{rakicevic2020policy,
 title={Policy Manifold Search for Improving Diversity-based Neuroevolution},
 author={Rakicevic, Nemanja and Cully, Antoine and Kormushev, Petar},
 journal={Beyond Backpropagation: Novel Ideas for Training Neural Architectures Workshop at NeurIPS 2020},
 year={2020}
 }
"
```
QED: using Quality-Environment-Diversity to evolve resilient robot swarms
Authors:
- David M. Bossens
- Danesh Tarapore
Abstract:
In swarm robotics, any of the robots in a swarm may be affected by different faults, resulting in significant performance declines. To allow fault recovery from randomly injected faults to different robots in a swarm, a model-free approach may be preferable due to the accumulation of faults in models and the difficulty to predict the behaviour of neighbouring robots. One model-free approach to fault recovery involves two phases: during simulation, a quality-diversity algorithm evolves a behaviourally diverse archive of controllers; during the target application, a search for the best controller is initiated after fault injection. In quality-diversity algorithms, the choice of the behavioural descriptor is a key design choice that determines the quality of the evolved archives, and therefore the fault recovery performance. Although the environment is an important determinant of behaviour, the impact of environmental diversity is often ignored in the choice of a suitable behavioural descriptor. This study compares different behavioural descriptors, including two generic descriptors that work on a wide range of tasks, one hand-coded descriptor which fits the domain of interest, and one novel type of descriptor based on environmental diversity, which we call Quality-Environment-Diversity (QED). Results demonstrate that the above-mentioned model-free approach to fault recovery is feasible in the context of swarm robotics, reducing the fault impact by a factor 2-3. Further, the environmental diversity obtained with QED yields a unique behavioural diversity profile that allows it to recover from high-impact faults.
Links:
- Paper
Bibtex:
```
"@article{bossens2020qed,
 title={QED: using Quality-Environment-Diversity to evolve resilient robot swarms},
 author={Bossens, David M and Tarapore, Danesh},
 journal={arXiv preprint arXiv:2003.02341},
 year={2020}}"         
```
Quality Diversity for Multi-task Optimization
Authors:
- Jean-Baptiste Mouret
- Glenn Maguire
Abstract:
Quality Diversity (QD) algorithms are a recent family of optimization algorithms that search for a large set of diverse but high-performing solutions. In some specific situations, they can solve multiple tasks at once. For instance, they can find the joint positions required for a robotic arm to reach a set of points, which can also be solved by running a classic optimizer for each target point. However, they cannot solve multiple tasks when the fitness needs to be evaluated independently for each task (e.g., optimizing policies to grasp many different objects). In this paper, we propose an extension of the MAP-Elites algorithm, called Multi-task MAP-Elites, that solves multiple tasks when the fitness function depends on the task. We evaluate it on a simulated parameterized planar arm (10-dimensional search space; 5000 tasks) and on a simulated 6-legged robot with legs of different lengths (36-dimensional search space; 2000 tasks). The results show that in both cases our algorithm outperforms the optimization of each task separately with the CMA-ES algorithm.
Links:
- Paper
Bibtex:
```
"@article{mouret2020quality,
title={Quality Diversity for Multi-task Optimization},
author={Mouret, Jean-Baptiste and Maguire, Glenn},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
year={2020},
organization={ACM}}"
```
Quality and Diversity in Evolutionary Modular Robotics Robotics
Authors:
- Jørgen Nordmoen
- Frank Veenstra
- Kai Olav Ellefsen
- Kyrre Glette
Abstract:
In Evolutionary Robotics a population of solutions is evolved to optimize robots that solve a given task. However, in traditional Evolutionary Algorithms, the population of solutions tends to converge to local optima when the problem is complex or the search space is large, a problem known as premature convergence. Quality Diversity algorithms try to overcome premature convergence by introducing additional measures that reward solutions for being different while not necessarily performing better. In this paper we compare a single objective Evolutionary Algorithm with two diversity promoting search algorithms; a Multi-Objective Evolutionary Algorithm and MAP-Elites a Quality Diversity algorithm, for the difficult problem of evolving control and morphology in modular robotics. We compare their ability to produce high performing solutions, in addition to analyze the evolved morphological diversity. The results show that all three search algorithms are capable of evolving high performing individuals. However, the Quality Diversity algorithm is better adept at filling all niches with high-performing solutions. This confirms that Quality Diversity algorithms are well suited for evolving modular robots and can be an important means of generating repertoires of high performing solutions that can be exploited both at design- and runtime.
Links:
- Paper
Bibtex:
```
"@inproceedings{nordmoen2020quality,
  title={Quality and Diversity in Evolutionary Modular Robotics},
  author={Nordmoen, J{\o}rgen and Veenstra, Frank and Ellefsen, Kai Olav and Glette, Kyrre},
  booktitle={2020 IEEE Symposium Series on Computational Intelligence (SSCI)},
  pages={2109--2116},
  year={2020},
  organization={IEEE}}
"
```
Rapidly adapting robot swarms with Swarm Map-based Bayesian Optimisation Robotics
Authors:
- David M. Bossens
- Danesh Tarapore
Abstract:
Rapid performance recovery from unforeseen environmental perturbations remains a grand challenge in swarm robotics. To solve this challenge, we investigate a behaviour adaptation approach, where one searches an archive of controllers for potential recovery solutions. To apply behaviour adaptation in swarm robotic systems, we propose two algorithms: (i) Swarm Map-based Optimisation (SMBO), which selects and evaluates one controller at a time, for a homogeneous swarm, in a centralised fashion; and (ii) Swarm Map-based Optimisation Decentralised (SMBO-Dec), which performs an asynchronous batch-based Bayesian optimisation to simultaneously explore different controllers for groups of robots in the swarm. We set up foraging experiments with a variety of disturbances: injected faults to proximity sensors, ground sensors, and the actuators of individual robots, with 100 unique combinations for each type. We also investigate disturbances in the operating environment of the swarm, where the swarm has to adapt to drastic changes in the number of resources available in the environment, and to one of the robots behaving disruptively towards the rest of the swarm, with 30 unique conditions for each such perturbation. The viability of SMBO and SMBO-Dec is demonstrated, comparing favourably to variants of random search and gradient descent, and various ablations, and improving performance up to 80% compared to the performance at the time of fault injection within at most 30 evaluations.
Links:
- Paper
Bibtex:
```
"@article{bossens2020rapidly,
 title={Rapidly adapting robot swarms with Swarm Map-based Bayesian Optimisation},
 author={Bossens, David M and Tarapore, Danesh},
 journal={arXiv preprint arXiv:2012.11444},
 year={2020}
 }
"
```
Reality-assisted evolution of soft robots through large-scale physical experimentation: a review Robotics
Authors:
- Toby Howison
- Simon Hauser
- Josie Hughes
- Fumiya Iida
Abstract:
In this review we introduce the framework of reality-assisted evolution to summarize a growing trend towards combining model-based and model-free approaches to improve the design of physically embodied soft robots. In silico, data-driven models build, adapt and improve representations of the target system using real-world experimental data. By simulating huge numbers of virtual robots using these data-driven models, optimization algorithms can illuminate multiple design candidates for transference to the real world. In reality, large-scale physical experimentation facilitates the fabrication, testing and analysis of multiple candidate designs. Automated assembly and reconfigurable modular systems enable significantly higher numbers of real-world design evaluations than previously possible. Large volumes of ground-truth data gathered via physical experimentation can be returned to the virtual environment to improve data-driven models and guide optimization. Grounding the design process in physical experimentation ensures the complexity of virtual robot designs does not outpace the model limitations or available fabrication technologies. We outline key developments in the design of physically embodied soft robots under the framework of reality-assisted evolution.
Links:
- Paper
Bibtex:
```
"@article{howison2020reality,
 title={Reality-assisted evolution of soft robots through large-scale physical experimentation: a review},
 author={Howison, Toby and Hauser, Simon and Hughes, Josie and Iida, Fumuiya},
 journal={arXiv preprint arXiv:2009.13960},
 year={2020}
 }
"
```
Scaling MAP-Elites to Deep Neuroevolution
Authors:
- Cédric Colas
- Joost Huizinga
- Vashisht Madhavan
- Jeff Clune
Abstract:
Quality-Diversity (QD) algorithms, and MAP-Elites (ME) in particular, have proven very useful for a broad range of applications including enabling real robots to recover quickly from joint damage, solving strongly deceptive maze tasks or evolving robot morphologies to discover new gaits. However, present implementations of MAP-Elites and other QD algorithms seem to be limited to low-dimensional controllers with far fewer parameters than modern deep neural network models. In this paper, we propose to leverage the efficiency of Evolution Strategies (ES) to scale MAP-Elites to high-dimensional controllers parameterized by large neural networks. We design and evaluate a new hybrid algorithm called MAP-Elites with Evolution Strategies (ME-ES) for post-damage recovery in a difficult high-dimensional control task where traditional ME fails. Additionally, we show that ME-ES performs efficient exploration, on par with state-of-the-art exploration algorithms in high-dimensional control tasks with strongly deceptive rewards.
Links:
- Paper
Bibtex:
```
"@article{colas2020scaling,
title={Scaling MAP-Elites to Deep Neuroevolution},
author={Colas, C{\'e}dric and Huizinga, Joost and Madhavan, Vashisht and Clune, Jeff},
journal={arXiv preprint arXiv:2003.01825},
year={2020}}"
```
Using MAP-Elites to support policymaking around Workforce Schedulingand Routing
Authors:
- Neil Urquhart
- Emma Hart
- William Hutcheson
Abstract:
Algorithms such as MAP-Elites provide a means of allowing users toexplore a solution space by returning an archive of high-performing solutions. Suchan archive, can allow the user an overview of the solution space which may beuseful when formulating policy around the problem itself. The number of solutionsthat can potentially be returned by MAP-Elites is controlled by a parameter𝑑that discretises the user-defined features into ‘bins’. For a fixed evaluation budget,increasing the number of bins increases user-choice, but at the same time, maylead to a reduction in overall quality of solutions. We undertake a study of theapplication of Map-Elites to a Workforce Scheduling and Routing problem, using aset of realistic instances based in London.
Links:
- Paper
Bibtex:
```
"@article{urquhart2020using,
 title={Using MAP-Elites to support policy making around Workforce Scheduling and Routing},
 author={Urquhart, Neil and Hart, Emma and Hutcheson, William},
 journal={at-Automatisierungstechnik},
 volume={68},
 number={2},
 pages={110--117},
 year={2020},
 publisher={De Gruyter Oldenbourg}
 }
"
```

2019: 28 Papers

Adaptive Prior Selection for Repertoire-based Online Adaptation in Robotics Robotics
Authors:
- Rituraj Kaushik
- Pierre Desreumaux
- Jean-Baptiste Mouret
Abstract:
Repertoire-based learning is a data-efficient adaptation approach based on a two-step process in which (1) a large and diverse set of policies is learned in simulation, and (2) a planning or learning algorithm chooses the most appropriate policies according to the current situation (e.g., a damaged robot, a new object, etc.). In this paper, we relax the assumption of previous works that a single repertoire is enough for adaptation. Instead, we generate repertoires for many different situations (e.g., with a missing leg, on different floors, etc.) and let our algorithm selects the most useful prior. Our main contribution is an algorithm, APROL (Adaptive Prior selection for Repertoire-based Online Learning) to plan the next action by incorporating these priors when the robot has no information about the current situation. We evaluate APROL on two simulated tasks: (1) pushing unknown objects of various shapes and sizes with a robotic arm and (2) a goal reaching task with a damaged hexapod robot. We compare with "Reset-free Trial and Error" (RTE) and various single repertoire-based baselines. The results show that APROL solves both the tasks in less interaction time than the baselines. Additionally, we demonstrate APROL on a real, damaged hexapod that quickly learns to pick compensatory policies to reach a goal by avoiding obstacles in the path.
Links:
- Paper
Bibtex:
```
"@article{kaushik2019,
author = {Rituraj Kaushik and Pierre Desreumaux and Jean-Baptiste Mouret},
title     = {Adaptive Prior Selection for Repertoire-based Online Learning in Robotics},
journal   = {arXiV},
volume    = {abs/1907.07029},
year      = {2019},
url       = {http://arxiv.org/abs/1907.07029}}"
```
Alphastar: An evolutionary computation perspective Games
Authors:
- Kai Arulkumaran
- Antoine Cully
- Julian Togelius
Abstract:
In January 2019, DeepMind revealed AlphaStar to the world-the first artificial intelligence (AI) system to beat a professional player at the game of StarCraft II-representing a milestone in the progress of AI. AlphaStar draws on many areas of AI research, including deep learning, reinforcement learning, game theory, and evolutionary computation (EC). In this paper we analyze AlphaStar primarily through the lens of EC, presenting a new look at the system and relating it to many concepts in the field. We highlight some of its most interesting aspects-the use of Lamarckian evolution, competitive co-evolution, and quality diversity. In doing so, we hope to provide a bridge between the wider EC community and one of the most significant AI systems developed in recent times.
Links:
- Paper
Bibtex:
```
"@article{arulkumaran2019alphastar,
title={Alphastar: An evolutionary computation perspective},
author={Arulkumaran, Kai and Cully, Antoine and Togelius, Julian},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
year={2019},
organization={ACM} }"
```

An illumination algorithm approach to solving the micro-depot routing problem

Authors:

Neil Urquhart
Silke Hohl
Emma Hart

Bibtex:

"@inproceedings{urquhart2019illumination,
title={An illumination algorithm approach to solving the micro-depot routing problem},
author={Urquhart, Neil and H{\"o}hl, Silke and Hart, Emma},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
pages={1347--1355},
year={2019},
organization={ACM} }"

Are quality diversity algorithms better at generating stepping stones than objective-based search?

Authors:

Adam Gaier
Alexander Asteroth
Jean-Baptiste Mouret

Bibtex:

"@inproceedings{gaier2019quality,
title={Are quality diversity algorithms better at generating stepping stones than objective-based search?},
author={Gaier, Adam and Asteroth, Alexander and Mouret, Jean-Baptiste},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
pages={115--116},
year={2019},
organization={ACM} }"

Automatic Calibration of Artificial Neural Networks for Zebrafish Collective Behaviours Using a Quality Diversity Algorithm Robotics
Authors:
- Leo Cazenille
- Nicolas Bredeche
- Jose Halloy
Abstract:
During the last two decades, various models have been proposed for fish collective motion. These models are mainly developed to decipher the biological mechanisms of social interaction between animals. They consider very simple homogeneous unbounded environments and it is not clear that they can simulate accurately the collective trajectories. Moreover when the models are more accurate, the question of their scalability to either larger groups or more elaborate environments remains open. This study deals with learning how to simulate realistic collective motion of collective of zebrafish, using real-world tracking data. The objective is to devise an agent-based model that can be implemented on an artificial robotic fish that can blend into a collective of real fish. We present a novel approach that uses Quality Diversity algorithms, a class of algorithms that emphasise exploration over pure optimisation. In particular, we use CVT-MAP-Elites, a variant of the state-of-the-art MAP-Elites algorithm for high dimensional search space. Results show that Quality Diversity algorithms not only outperform classic evolutionary reinforcement learning methods at the macroscopic level (i.e. group behaviour), but are also able to generate more realistic biomimetic behaviours at the microscopic level (i.e. individual behaviour).
Links:
- Paper
Bibtex:
```
"@inproceedings{cazenille2019automatic,
title={Automatic Calibration of Artificial Neural Networks for Zebrafish Collective Behaviours Using a Quality Diversity Algorithm},
author={Cazenille, Leo and Bredeche, Nicolas and Halloy, Jos{\'e}},
booktitle={Conference on Biomimetic and Biohybrid Systems},
pages={38--50},
year={2019},
organization={Springer} }"
```
Autonomous Skill Discovery with Quality-diversity and Unsupervised Descriptors Robotics
Authors:
- Antoine Cully
Abstract:
Quality-Diversity optimization is a new family of optimization algorithms that, instead of searching for a single optimal solution to solving a task, searches for a large collection of solutions that all solve the task in a different way. This approach is particularly promising for learning behavioral repertoires in robotics, as such a diversity of behaviors enables robots to be more versatile and resilient. However, these algorithms require the user to manually define behavioral descriptors, which is used to determine whether two solutions are different or similar. The choice of a behavioral descriptor is crucial, as it completely changes the solution types that the algorithm derives. In this paper, we introduce a new method to automatically define this descriptor by combining Quality-Diversity algorithms with unsupervised dimensionality reduction algorithms. This approach enables robots to autonomously discover the range of their capabilities while interacting with their environment. The results from two experimental scenarios demonstrate that robot can autonomously discover a large range of possible behaviors, without any prior knowledge about their morphology and environment. Furthermore, these behaviors are deemed to be similar to handcrafted solutions that uses domain knowledge and significantly more diverse than when using existing unsupervised methods.
Links:
- Paper
Bibtex:
```
"@inproceedings{cully2019Autonomous,
author = {Cully, Antoine},
title = {Autonomous Skill Discovery with Quality-diversity and Unsupervised Descriptors},
booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
year = {2019},
location = {Prague, Czech Republic},
pages = {81--89},
doi = {10.1145/3321707.3321804},
publisher = {ACM} }"
```
Behavioral Repertoire via Generative Adversarial Policy Networks Robotics
Authors:
- Marija Jegorova
- Stephane Doncieux
- Timothy Hospedales
Abstract:
Learning algorithms are enabling robots to solve increasingly challenging real-world tasks. These approaches often rely on demonstrations and reproduce the behavior shown. Unexpected changes in the environment may require using different behaviors to achieve the same effect, for instance to reach and grasp an object in changing clutter. An emerging paradigm addressing this robustness issue is to learn a diverse set of successful behaviors for a given task, from which a robot can select the most suitable policy when faced with a new environment. In this paper, we explore a novel realization of this vision by learning a generative model over policies. Rather than learning a single policy, or a small fixed repertoire, our generative model for policies compactly encodes an unbounded number of policies and allows novel controller variants to be sampled. Leveraging our generative policy network, a robot can sample novel behaviors until it finds one that works for a new environment. We demonstrate this idea with an application of robust ball-throwing in the presence of obstacles. We show that this approach achieves a greater diversity of behaviors than an existing evolutionary approach, while maintaining good efficacy of sampled behaviors, allowing a Baxter robot to hit targets more often when ball throwing in the presence of obstacles.
Links:
- Paper
Bibtex:
```
"@article{jegorovabehavioral,
title={Behavioral Repertoire via Generative Adversarial Policy Networks},
author={Jegorova, Marija and Doncieux, St{\'e}phane and Hospedales, Timothy M} }"
```
Comparing reliability of grid-based Quality-Diversity algorithms using artificial landscapes
Authors:
- Leo Cazenille
Abstract:
Quality-Diversity (QD) algorithms are a recent type of optimisation methods that search for a collection of both diverse and high performing solutions. They can be used to effectively explore a target problem according to features defined by the user. However, the field of QD still does not possess extensive methodologies and reference benchmarks to compare these algorithms. We propose a simple benchmark to compare the reliability of QD algorithms by optimising the Rastrigin function, an artificial landscape function often used to test global optimisation methods.
Links:
- Paper
Bibtex:
```
"@inproceedings{cazenille2019comparing,
title={Comparing reliability of grid-based Quality-Diversity algorithms using artificial landscapes},
author={Cazenille, Leo},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
pages={249--250},
year={2019},
organization={ACM} }"
```
Designing neural networks through neuroevolution
Authors:
- Kenneth Stanley
- Jeff Clune
- Joel Lehman
- Risto Miikkulainen
Abstract:
Much of recent machine learning has focused on deep learning, in which neural network weights are trained through variants of stochastic gradient descent. An alternative approach comes from the field of neuroevolution, which harnesses evolutionary algorithms to optimize neural networks, inspired by the fact that natural brains themselves are the products of an evolutionary process. Neuroevolution enables important capabilities that are typically unavailable to gradient-based approaches, including learning neural network building blocks (for example activation functions), hyperparameters, architectures and even the algorithms for learning themselves. Neuroevolution also differs from deep learning (and deep reinforcement learning) by maintaining a population of solutions during search, enabling extreme exploration and massive parallelization. Finally, because neuroevolution research has (until recently) developed largely in isolation from gradient-based neural network research, it has developed many unique and effective techniques that should be effective in other machine learning areas too. This Review looks at several key aspects of modern neuroevolution, including large-scale computing, the benefits of novelty and diversity, the power of indirect encoding, and the field’s contributions to meta-learning and architecture search. Our hope is to inspire renewed interest in the field as it meets the potential of the increasing computation available today, to highlight how many of its ideas can provide an exciting resource for inspiration and hybridization to the deep learning, deep reinforcement learning and machine learning communities, and to explain how neuroevolution could prove to be a critical tool in the long-term pursuit of artificial general intelligence.
Links:
- Paper
Bibtex:
```
"@article{stanley2019designing,
title={Designing neural networks through neuroevolution},
author={Stanley, Kenneth O and Clune, Jeff and Lehman, Joel and Miikkulainen, Risto},
journal={Nature Machine Intelligence},
volume={1},
number={1},
pages={24--35},
year={2019} }"
```
Empowering Quality Diversity in Dungeon Design with Interactive Constrained MAP-Elites Games
Authors:
- Alberto Alvarez
- Steve Dahlskog
- Jose Font
- Julian Togelius
Abstract:
We propose the use of quality-diversity algorithms for mixed-initiative game content generation. This idea is implemented as a new feature of the Evolutionary Dungeon Designer, a system for mixed-initiative design of the type of levels you typically find in computer role playing games. The feature uses the MAP-Elites algorithm, an illumination algorithm which divides the population into a number of cells depending on their values along several behavioral dimensions. Users can flexibly and dynamically choose relevant dimensions of variation, and incorporate suggestions produced by the algorithm in their map designs. At the same time, any modifications performed by the human feed back into MAP-Elites, and are used to generate further suggestions.
Links:
- Paper
Bibtex:
```
"@article{alvarez2019empowering,
title={Empowering Quality Diversity in Dungeon Design with Interactive Constrained MAP-Elites},
author={Alvarez, Alberto and Dahlskog, Steve and Font, Jose and Togelius, Julian},
journal={arXiv preprint arXiv:1906.05175},
year={2019} }"
```
Evaluating MAP-Elites on Constrained Optimization Problems
Authors:
- Stefano Fioravanzo
- Giovanni Iacca
Abstract:
Constrained optimization problems are often characterized by multiple constraints that, in the practice, must be satisfied with different tolerance levels. While some constraints are hard and as such must be satisfied with zero-tolerance, others may be soft, such that non-zero violations are acceptable. Here, we evaluate the applicability of MAP-Elites to "illuminate" constrained search spaces by mapping them into feature spaces where each feature corresponds to a different constraint. On the one hand, MAP-Elites implicitly preserves diversity, thus allowing a good exploration of the search space. On the other hand, it provides an effective visualization that facilitates a better understanding of how constraint violations correlate with the objective function. We demonstrate the feasibility of this approach on a large set of benchmark problems, in various dimensionalities, and with different algorithmic configurations. As expected, numerical results show that a basic version of MAP-Elites cannot compete on all problems (especially those with equality constraints) with state-of-the-art algorithms that use gradient information or advanced constraint handling techniques. Nevertheless, it has a higher potential at finding constraint violations vs. objectives trade-offs and providing new problem information. As such, it could be used in the future as an effective building-block for designing new constrained optimization algorithms.
Links:
- Paper
Bibtex:
```
"@article{fioravanzo2019evaluating,
title={Evaluating MAP-Elites on Constrained Optimization Problems},
author={Fioravanzo, Stefano and Iacca, Giovanni},
journal={arXiv preprint arXiv:1902.00703},
year={2019} }"
```

Evolving embodied intelligence from materials to machines Robotics

Authors:

David Howard
Agoston Eiben
Danielle Frances Kennedy
Jean-Baptiste Mouret
Philip Valencia
Dave Winkler

Bibtex:

"@article{howard2019evolving,
title={Evolving embodied intelligence from materials to machines},
author={Howard, David and Eiben, Agoston E and Kennedy, Danielle Frances and Mouret, Jean-Baptiste and Valencia, Philip and Winkler, Dave},
journal={Nature Machine Intelligence},
volume={1},
number={1},
pages={12--19},
year={2019},
publisher={Nature Publishing Group} }"

Exploration and Exploitation in Symbolic Regression using Quality-Diversity and Evolutionary Strategies Algorithms
Authors:
- J.-P. Bruneton
- L. Cazenille
- A. Douin
- V. Reverdy
Abstract:
By combining Genetic Programming, MAP-Elites and Covariance Matrix Adaptation Evolution Strategy, we demonstrate very high success rates in Symbolic Regression problems. MAP-Elites is used to improve exploration while preserving diversity and avoiding premature convergence and bloat. Then, a Covariance Matrix Adaptation-Evolution Strategy is used to evaluate free scalars through a non-gradient-based black-box optimizer. Although this evaluation approach is not computationally scalable to high dimensional problems, our algorithm is able to find exactly most of the 31 targets extracted from the literature on which we evaluate it.
Links:
- Paper
Bibtex:
```
"@article{bruneton2019exploration,
title={Exploration and Exploitation in Symbolic Regression using Quality-Diversity and Evolutionary Strategies Algorithms},
author={Bruneton, J-P and Cazenille, L and Douin, A and Reverdy, V},
journal={arXiv preprint arXiv:1906.03959},
year={2019 }"
```
Exploring Self-Assembling Behaviors in a Swarm of Bio-micro-robots using Surrogate-Assisted MAP-Elites Robotics
Authors:
- Leo Cazenille
- Nicolas Bredeche
- Nathanael Aubert-Kato
Abstract:
Swarms of molecular robots are a promising approach to create specific shapes at the microscopic scale through self-assembly. However, controlling their behavior is a challenging problem as it involves complex non-linear dynamics and high experimental variability. Hand-crafting a molecular controller will often be time-consuming and give sub-optimal results. Optimization methods, like the bioNEAT algorithm, were previously employed to partially overcome these difficulties, but they still had to cope with deceptive high-dimensional search spaces and computationally expensive simulations. Here, we describe a novel approach to solve this problem by using MAP-Elites, an algorithm that searches for both high-performing and diverse solutions. We then apply it to a molecular robotic framework we recently introduced that allows sensing, signaling and self-assembly at the micro-scale and show that MAP-Elites outperforms previous approaches. Additionally, we propose a surrogate model of micro-robots physics and chemical reaction dynamics to reduce the computational costs of simulation. We show that the resulting methodology is capable of optimizing controllers with similar accuracy as when using only a full-fledged realistic model, with half the computational budget.
Links:
- Paper
Bibtex:
```
"@article{cazenille2019exploring,
title={Exploring Self-Assembling Behaviors in a Swarm of Bio-micro-robots using Surrogate-Assisted MAP-Elites},
author={Cazenille, Leo and Bredeche, Nicolas and Aubert-Kato, Nathanael},
journal={arXiv preprint arXiv:1910.00230},
year={2019} }"
```

Exploring genetic programming systems with MAP-Elites

Authors:

Emily Dolson
Alexander Lalejini
Charles Ofria

Bibtex:

"@incollection{dolson2019exploring,
title={Exploring genetic programming systems with MAP-Elites},
author={Dolson, Emily and Lalejini, Alexander and Ofria, Charles},
booktitle={Genetic Programming Theory and Practice XVI},
pages={1--16},
year={2019},
publisher={Springer} }"

From exploration to control: learning object manipulation skills through novelty search and local adaptation
Authors:
- Seungsu Kim
- Alexandre Coninx
- Stephane Doncieux
Abstract:
Programming a robot to deal with open-ended tasks remains a challenge, in particular if the robot has to manipulate objects. Launching, grasping, pushing or any other object interaction can be simulated but the corresponding models are not reversible and the robot behavior thus cannot be directly deduced. These behaviors are hard to learn without a demonstration as the search space is large and the reward sparse. We propose a method to autonomously generate a diverse repertoire of simple object interaction behaviors in simulation. Our goal is to bootstrap a robot learning and development process with limited informations about what the robot has to achieve and how. This repertoire can be exploited to solve different tasks in reality thanks to a proposed adaptation method or could be used as a training set for data-hungry algorithms. The proposed approach relies on the definition of a goal space and generates a repertoire of trajectories to reach attainable goals, thus allowing the robot to control this goal space. The repertoire is built with an off-the-shelf simulation thanks to a quality diversity algorithm. The result is a set of solutions tested in simulation only. It may result in two different problems: (1) as the repertoire is discrete and finite, it may not contain the trajectory to deal with a given situation or (2) some trajectories may lead to a behavior in reality that differs from simulation because of a reality gap. We propose an approach to deal with both issues by using a local linearization between the motion parameters and the observed effects. Furthermore, we present an approach to update the existing solution repertoire with the tests done on the real robot. The approach has been validated on two different experiments on the Baxter robot: a ball launching and a joystick manipulation tasks.
Links:
- Paper
Bibtex:
```
"@article{kim2019exploration,
title={From exploration to control: learning object manipulation skills through novelty search and local adaptation},
author={Kim, Seungsu and Coninx, Alexandre and Doncieux, St{\'e}phane},
journal={arXiv preprint arXiv:1901.00811},
year={2019}}"         
```
Go-Explore: a New Approach for Hard-Exploration Problems Games
Authors:
- Adrien Ecoffet
- Joost Huizinga
- Joel Lehman
- Kenneth Stanley
- Jeff Clune
Abstract:
A grand challenge in reinforcement learning is intelligent exploration, especially when rewards are sparse or deceptive. Two Atari games serve as benchmarks for such hard-exploration domains: Montezuma's Revenge and Pitfall. On both games, current RL algorithms perform poorly, even those with intrinsic motivation, which is the dominant method to improve performance on hard-exploration domains. To address this shortfall, we introduce a new algorithm called Go-Explore. It exploits the following principles: (1) remember previously visited states, (2) first return to a promising state (without exploration), then explore from it, and (3) solve simulated environments through any available means (including by introducing determinism), then robustify via imitation learning. The combined effect of these principles is a dramatic performance improvement on hard-exploration problems. On Montezuma's Revenge, Go-Explore scores a mean of over 43k points, almost 4 times the previous state of the art. Go-Explore can also harness human-provided domain knowledge and, when augmented with it, scores a mean of over 650k points on Montezuma's Revenge. Its max performance of nearly 18 million surpasses the human world record, meeting even the strictest definition of "superhuman" performance. On Pitfall, Go-Explore with domain knowledge is the first algorithm to score above zero. Its mean score of almost 60k points exceeds expert human performance. Because Go-Explore produces high-performing demonstrations automatically and cheaply, it also outperforms imitation learning work where humans provide solution demonstrations. Go-Explore opens up many new research directions into improving it and weaving its insights into current RL algorithms. It may also enable progress on previously unsolvable hard-exploration problems in many domains, especially those that harness a simulator during training (e.g. robotics).
Links:
- Paper
- Source-code
Bibtex:
```
"@article{ecoffet2019go,
title={Go-Explore: a New Approach for Hard-Exploration Problems},
author={Ecoffet, Adrien and Huizinga, Joost and Lehman, Joel and Stanley, Kenneth O and Clune, Jeff},
journal={arXiv preprint arXiv:1901.10995},
year={2019} }"
```
MAP-Elites for Noisy Domains by Adaptive Sampling
Authors:
- Niels Justesen
- Sebastian Risi
- Jean-Baptiste Mouret
Abstract:
Quality Diversity algorithms (QD) evolve a set of high-performing phenotypes that each behaves as differently as possible. However, current algorithms are all elitist, which make them unable to cope with stochastic fitness functions and behavior evaluations. In fact, many of the promising applications of QD algorithms, for instance, games and robotics, are stochastic. Here we propose two new extensions to the QD-algorithm MAP-Elites adaptive sampling and drifting-elites — and demonstrate empirically that these extensions increase the quality of solutions in a noisy artificial test function and the behavioral diversity in a 2D bipedal walker environment.
Links:
- Paper
Bibtex:
```
"@inproceedings{justesen2019map,
 title={MAP-Elites for noisy domains by adaptive sampling},
 author={Justesen, Niels and Risi, Sebastian and Mouret, Jean-Baptiste},
 booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
 pages={121--122},
 year={2019},
 organization={ACM}}"
```
Mapping Hearthstone Deck Spaces with Map-Elites with Sliding Boundaries Games
Authors:
- Matthew Fontaine
- Lee Scott
- Lisa Soros
- Fernando De Mesentier Silva
- Julian Togelius
- Amy Hoover
Abstract:
Quality diversity (QD) algorithms such as MAP-Elites have emerged as a powerful alternative to traditional single-objective optimization methods. They were initially applied to evolutionary robotics problems such as locomotion and maze navigation, but have yet to see widespread application. We argue that these algorithms are perfectly suited to the rich domain of video games, which contains many relevant problems with a multitude of successful strategies and often also multiple dimensions along which solutions can vary. This paper introduces a novel modification of the MAP-Elites algorithm called MAP-Elites with Sliding Boundaries (MESB) and applies it to the design and rebalancing of Hearthstone, a popular collectible card game chosen for its number of multidimensional behavior features relevant to particular styles of play. To avoid overpopulating cells with conflated behaviors, MESB slides the boundaries of cells based on the distribution of evolved individuals. Experiments in this paper demonstrate the performance of MESB in Hearthstone. Results suggest MESB finds diverse ways of playing the game well along the selected behavioral dimensions. Further analysis of the evolved strategies reveals common patterns that recur across behavioral dimensions and explores how MESB can help rebalance the game.
Links:
- Paper
Bibtex:
```
"@inproceedings{fontaine2019,
title={Mapping Hearthstone Deck Spaces with Map-Elites with Sliding Boundaries},
author={Matthew C. Fontaine and Scott Lee and L. B. Soros and Fernando De Mesentier Silva and Julian Togelius and Amy K. Hoover},
booktitle={Proceedings of The Genetic and Evolutionary Computation Conference},
year={2019},
organization={ACM} }"
```
Modeling user selection in quality diversity
Authors:
- Alexander Hagg
- Alexander Alexander
- Thomas Back
Abstract:
The initial phase in real world engineering optimization and design is a process of discovery in which not all requirements can be made in advance, or are hard to formalize. Quality diversity algorithms, which produce a variety of high performing solutions, provide a unique chance to support engineers and designers in the search for what is possible and high performing. In this work we begin to answer the question how a user can interact with quality diversity and turn it into an interactive innovation aid. By modeling a user's selection it can be determined whether the optimization is drifting away from the user's preferences. The optimization is then constrained by adding a penalty to the objective function. We present an interactive quality diversity algorithm that can take into account the user's selection. The approach is evaluated in a new multimodal optimization benchmark that allows various optimization tasks to be performed. The user selection drift of the approach is compared to a state of the art alternative on both a planning and a neuroevolution control task, thereby showing its limits and possibilities.
Links:
- Paper
Bibtex:
```
"@inproceedings{hagg2019modeling,
title={Modeling user selection in quality diversity},
author={Hagg, Alexander and Asteroth, Alexander and B{\"a}ck, Thomas},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
pages={116--124},
year={2019},
organization={ACM} }"
```
Novelty Search for Deep Reinforcement Learning Policy Network Weights by Action Sequence Edit Metric Distance Games
Authors:
- Ethan Jackson
- Mark Daley
Abstract:
Reinforcement learning (RL) problems often feature deceptive local optima, and learning methods that optimize purely for reward signal often fail to learn strategies for overcoming them. Deep neuroevolution and novelty search have been proposed as effective alternatives to gradient-based methods for learning RL policies directly from pixels. In this paper, we introduce and evaluate the use of novelty search over agent action sequences by string edit metric distance as a means for promoting innovation. We also introduce a method for stagnation detection and population resampling inspired by recent developments in the RL community that uses the same mechanisms as novelty search to promote and develop innovative policies. Our methods extend a state-of-the-art method for deep neuroevolution using a simple-yet-effective genetic algorithm (GA) designed to efficiently learn deep RL policy network weights. Experiments using four games from the Atari 2600 benchmark were conducted. Results provide further evidence that GAs are competitive with gradient-based algorithms for deep RL. Results also demonstrate that novelty search over action sequences is an effective source of selection pressure that can be integrated into existing evolutionary algorithms for deep RL.
Links:
- Paper
Bibtex:
```
"@article{jackson2019novelty,
title={Novelty Search for Deep Reinforcement Learning Policy Network Weights by Action Sequence Edit Metric Distance},
author={Jackson, Ethan C and Daley, Mark},
journal={arXiv preprint arXiv:1902.03142},
year={2019} }"
```

Novelty search: a theoretical perspective

Authors:

Stephane Doncieux
Alban Laflaquiere
Alexandre Coninx

Bibtex:

"@inproceedings{doncieux2019novelty,
title={Novelty search: a theoretical perspective},
author={Doncieux, Stephane and Laflaquiere, Alban and Coninx, Alexandre},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
pages={99--106},
year={2019},
organization={ACM} }"

POET: open-ended coevolution of environments and their optimized solutions

Authors:

Rui Wang
Joel Lehman
Jeff Clune
Kenneth Stanley

Bibtex:

"@inproceedings{wang2019poet,
title={POET: open-ended coevolution of environments and their optimized solutions},
author={Wang, Rui and Lehman, Joel and Clune, Jeff and Stanley, Kenneth O},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
pages={142--151},
year={2019},
organization={ACM} }"

PlayMapper: Illuminating Design Spaces of Platform Games
Authors:
- Vivek R. Warriar
- Carmen Ugarte
- John R. Woodward
- Laurissa Tokarchuk
Abstract:
In this paper, we present PlayMapper, a novel variant of the MAP-Elites algorithm that has been adapted to map the level design space of the Super Mario Bros game. Our approach uses player and level based features to create a map of playable levels. We conduct an experiment to compare the effect of different sets of input features on the range of levels generated using this technique. In this work, we show that existing search-based techniques for PCG can be improved to allow for more control and creative freedom for designers. Current limitations of the system and directions for future work are also discussed.
Links:
- Paper
Bibtex:
```
"@INPROCEEDINGS{8848118,
author={V. R. {Warriar} and C. {Ugarte} and J. R. {Woodward} and L. {Tokarchuk}},
booktitle={2019 IEEE Conference on Games (CoG)}, 
title={PlayMapper: Illuminating Design Spaces of Platform Games}, 
year={2019},
volume={},
number={},
pages={1-4}}"       
```
Policy search in continuous action domains: An overview
Authors:
- Olivier Sigaud
- Freek Stulp
Abstract:
Continuous action policy search is currently the focus of intensive research, driven both by the recent success of deep reinforcement learning algorithms and the emergence of competitors based on evolutionary algorithms. In this paper, we present a broad survey of policy search methods, providing a unified perspective on very different approaches, including also Bayesian Optimization and directed exploration methods. The main message of this overview is in the relationship between the families of methods, but we also outline some factors underlying sample efficiency properties of the various approaches.
Links:
- Paper
Bibtex:
```
"@article{SIGAUD201928,
title = "Policy search in continuous action domains: An overview",
journal = "Neural Networks",
volume = "113",
pages = "28 - 40",
year = "2019",
issn = "0893-6080",
doi = "https://doi.org/10.1016/j.neunet.2019.01.011",
url = "https://hal.sorbonne-universite.fr/hal-02182466/document",
author = "Olivier Sigaud and Freek Stulp",
keywords = "Policy search, Sample efficiency, Deep reinforcement learning, Deep neuroevolution"}"  
```
Procedural content generation through quality diversity Games
Authors:
- Daniele Gravina
- Ahmed Khalifa
- Antonios Liapis
- Julian Togelius
- Georgios Yannakakis
Abstract:
Quality-diversity (QD) algorithms search for a set of good solutions which cover a space as defined by behavior metrics. This simultaneous focus on quality and diversity with explicit metrics sets QD algorithms apart from standard single- and multi-objective evolutionary algorithms, as well as from diversity preservation approaches such as niching. These properties open up new avenues for artificial intelligence in games, in particular for procedural content generation. Creating multiple systematically varying solutions allows new approaches to creative human-AI interaction as well as adaptivity. In the last few years, a handful of applications of QD to procedural content generation and game playing have been proposed; we discuss these and propose challenges for future work.
Links:
- Paper
Bibtex:
```
"@article{gravina2019procedural,
title={Procedural content generation through quality diversity},
author={Gravina, Daniele and Khalifa, Ahmed and Liapis, Antonios and Togelius, Julian and Yannakakis, Georgios N},
journal={arXiv preprint arXiv:1907.04053},
year={2019} }"
```

Quantifying the Effects of Increasing User Choice in MAP-Elites Applied to a Workforce Scheduling and Routing Problem

Authors:

Neil Urquhart
Emma Hart
William Hutcheson

Bibtex:

"@inproceedings{urquhart2019quantifying,
title={Quantifying the Effects of Increasing User Choice in MAP-Elites Applied to a Workforce Scheduling and Routing Problem},
author={Urquhart, Neil and Hart, Emma and Hutcheson, William},
booktitle={International Conference on the Applications of Evolutionary Computation (Part of EvoStar)},
pages={49--63},
year={2019},
organization={Springer} }"

Unsupervised Learning and Exploration of Reachable Outcome Space Robotics
Authors:
- Giuseppe Paolo
- Alban Laflaquiere
- Alexandre Coninx
- Stephane Doncieux
Abstract:
Performing Reinforcement Learning in sparse rewards settings, with very little prior knowledge, is a challenging problem since there is no signal to properly guide the learning process. In such situations, a good search strategy is fundamental. At the same time, not having to adapt the algorithm to every single problem is very desirable. Here we introduce TAXONS, a Task Agnostic eXploration of Outcome spaces through Novelty and Surprise algorithm. Based on a population-based divergent-search approach, it learns a set of diverse policies directly from high-dimensional observations, without any task-specific information. TAXONS builds a repertoire of policies while training an autoencoder on the high-dimensional observation of the final state of the system to build a low-dimensional outcome space. The learned outcome space, combined with the reconstruction error, is used to drive the search for new policies. Results show that TAXONS can find a diverse set of controllers, covering a good part of the ground-truth outcome space, while having no information about such space.
Links:
- Paper
Bibtex:
```
"@article{paolo2019unsupervised,
title={Unsupervised Learning and Exploration of Reachable Outcome Space},
author={Paolo, Giuseppe and Laflaquiere, Alban and Coninx, Alexandre and Doncieux, Stephane},
journal={algorithms},
volume={24},
pages={25},
year={2019} }"
```

2018: 24 Papers

An approach to evolve and exploit repertoires of general robot behaviours Robotics
Authors:
- Jorge Gomes
- Sancho Moura Oliveira
- Anders Lyhne Christensen
Abstract:
Recent works in evolutionary robotics have shown the viability of evolution driven by behavioural novelty and diversity. These evolutionary approaches have been successfully used to generate repertoires of diverse and high-quality behaviours, instead of driving evolution towards a single, task-specific solution.Having repertoires of behaviours can enable new forms of robotic control, in which high-level controllers continually decide which behaviour to execute. To date, however, only the use of repertoires of open-loop locomotion primitives has been studied. We propose EvoRBC-II, an approach that enables the evolution of repertoires composed of general closed-loop behaviours, that can respond to the robot’s sensory inputs. The evolved repertoire is then used as a basis to evolve a transparent higher-level controller that decides when and which behaviours of the repertoire to execute. Relying on experiments in a simulated domain, we show that the evolved repertoires are composed of highly diverse and useful behaviours. The same repertoire contains sufficiently diverse behaviours to solve a wide range of tasks, and the EvoRBC-II approach can yield a performance that is comparable to the standard tabula-rasa evolution. EvoRBC-II enables automatic generation of hierarchical control through a two-step evolutionary process, thus opening doors for the further exploration of the advantages that can be brought by hierarchical control.
Links:
- Paper
Bibtex:
```
"@article{gomes2018approach,
title={An approach to evolve and exploit repertoires of general robot behaviours},
author={Gomes, Jorge and Oliveira, Sancho Moura and Christensen, Anders Lyhne},
journal={Swarm and Evolutionary Computation},
year={2018},
publisher={Elsevier} }"
```
Bayesian optimization with automatic prior selection for data-efficient direct policy search Robotics
Authors:
- Remi Pautrat
- Konstantinos Konstantinos
- Jean-Baptiste Mouret
Abstract:
One of the most interesting features of Bayesian optimization for direct policy search is that it can leverage priors (e.g., from simulation or from previous tasks) to accelerate learning on a robot. In this paper, we are interested in situations for which several priors exist but we do not know in advance which one fits best the current situation. We tackle this problem by introducing a novel acquisition function, called Most Likely Expected Improvement (MLEI), that combines the likelihood of the priors and the expected improvement. We evaluate this new acquisition function on a transfer learning task for a 5-DOF planar arm and on a possibly damaged, 6-legged robot that has to learn to walk on flat ground and on stairs, with priors corresponding to different stairs and different kinds of damages. Our results show that MLEI effectively identifies and exploits the priors, even when there is no obvious match between the current situations and the priors.
Links:
- Paper
Bibtex:
```
"@inproceedings{pautrat2018bayesian,
title={Bayesian optimization with automatic prior selection for data-efficient direct policy search},
author={Pautrat, R{\'e}mi and Chatzilygeroudis, Konstantinos and Mouret, Jean-Baptiste},
booktitle={2018 IEEE International Conference on Robotics and Automation (ICRA)},
pages={7571--7578},
year={2018},
organization={IEEE} }"
```
Combining map-elites and incremental evolution to generate gaits for a mammalian quadruped robot Robotics
Authors:
- Jorgen Nordmoen
- Kai Olav Ellefsen
- Kyrre Glette
Abstract:
Four-legged mammals are capable of showing a great variety of movement patterns, ranging from a simple walk to more complex movement such as trots and gallops. Imbuing this diversity to quadruped robots is of interest in order to improve both mobility and reach. Within the field of Evolutionary Robotics, Quality Diversity techniques have shown a remarkable ability to produce not only effective, but also highly diverse solutions. When applying this approach to four-legged robots an initial problem is to create viable movement patterns that do not fall. This difficulty stems from the challenging fitness gradient due to the mammalian morphology. In this paper we propose a solution to overcome this problem by implementing incremental evolution within the QualityDiversity framework. This allows us to evolve controllers that become more complex while at the same time utilizing the diversity produced byQuality Diversity. We show that our approach is able to generate high fitness solutions early in the search process, keep these solutions and perform a more open-ended search towards the end of evolution.
Links:
- Paper
Bibtex:
```
"@inproceedings{nordmoen2018combining,
title={Combining map-elites and incremental evolution to generate gaits for a mammalian quadruped robot},
author={Nordmoen, Jorgen and Ellefsen, Kai Olav and Glette, Kyrre},
booktitle={International Conference on the Applications of Evolutionary Computation},
pages={719--733},
year={2018},
organization={Springer} }"
```

Comparing Approaches for Evolving High-Level Robot Control Based on Behaviour Repertoires Robotics

Authors:

Jorge Gomes
Anders Lyhne Christensen

Bibtex:

"@inproceedings{gomes2018comparing,
title={Comparing Approaches for Evolving High-Level Robot Control Based on Behaviour Repertoires},
author={Gomes, Jorge and Christensen, Anders Lyhne},
booktitle={2018 IEEE Congress on Evolutionary Computation (CEC)},
pages={1--6},
year={2018},
organization={IEEE} }"

Data-Efficient Design Exploration through Surrogate-Assisted Illumination
Authors:
- Adam Gaier
- Alexander Asteroth
- Jean-Baptiste Mouret
Abstract:
Design optimization techniques are often used at the beginning of the design process to explore the space of possible designs. In these domains illumination algorithms, such as MAP-Elites, are promising alternatives to classic optimization algorithms because they produce diverse, high-quality solutions in a single run, instead of only a single near-optimal solution. Unfortunately, these algorithms currently require a large number of function evaluations, limiting their applicability. In this article we introduce a new illumination algorithm, Surrogate-Assisted Illumination (SAIL), that leverages surrogate modeling techniques to create a map of the design space according to user-defined features while minimizing the number of fitness evaluations. On a 2-dimensional airfoil optimization problem SAIL produces hundreds of diverse but high-performing designs with several orders of magnitude fewer evaluations than MAP-Elites or CMA-ES. We demonstrate that SAIL is also capable of producing maps of high-performing designs in realistic 3-dimensional aerodynamic tasks with an accurate flow simulation. Data-efficient design exploration with SAIL can help designers understand what is possible, beyond what is optimal, by considering more than pure objective-based optimization.
Links:
- Paper
Bibtex:
```
"@article{gaier2018data,
title={Data-Efficient Design Exploration through Surrogate-Assisted Illumination},
author={Gaier, Adam and Asteroth, Alexander and Mouret, Jean-Baptiste},
journal={Evolutionary computation},
pages={1--30},
year={2018},
publisher={MIT Press} }"
```
Discovering the Elite Hypervolume by Leveraging Interspecies Correlation Robotics
Authors:
- Vassilis Vassiliades
- Jean-Baptiste Mouret
Abstract:
Evolution has produced an astonishing diversity of species, each filling a different niche. Algorithms like MAP-Elites mimic this divergent evolutionary process to find a set of behaviorally diverse but high-performing solutions, called the elites. Our key insight is that species in nature often share a surprisingly large part of their genome, in spite of occupying very different niches; similarly, the elites are likely to be concentrated in a specific "elite hypervolume" whose shape is defined by their common features. In this paper, we first introduce the elite hypervolume concept and propose two metrics to characterize it: the genotypic spread and the genotypic similarity. We then introduce a new variation operator, called "directional variation", that exploits interspecies (or inter-elites) correlations to accelerate the MAP-Elites algorithm. We demonstrate the effectiveness of this operator in three problems (a toy function, a redundant robotic arm, and a hexapod robot)
Links:
- Paper
Bibtex:
```
"@article{vassiliades2018discovering,
title={Discovering the Elite Hypervolume by Leveraging Interspecies Correlation},
author={Vassiliades, Vassilis and Mouret, Jean-Baptiste},
journal={Proceedings of the Genetic and Evolutionary Computation Conference },
year={2018},
organization={ACM} }"
```
Dynamic mutation in MAP-Elites for robotic repertoire generation Robotics
Authors:
- Jorgen Nordmoen
- Eivind Samuelsen
- Kai Olav Ellefsen
- Kyrre Glette
Abstract:
One of the core functions in most Evolutionary Algorithms is mutation. In complex search spaces, which are common in Evolutionary Robotics, mutation is often used both for optimizing existing solutions, described as exploitation, and for spanning the search space, called exploration. This presents a difficult challenge for researchers as mutation parameters must be selected with care in order to balance the two, often contradictory, effects. Strategies that vary mutation during the search often try to estimate these effects in order to modify the mutation parameters. In this regard MAP-Elites, aQuality Diversity algorithm, presents an interesting opportunity. Because factors related to exploration and exploitation are readily available during the search, optimization based on these factors could be utilized to improve the search. In this paper we study how online adaptation of mutation rate, dynamic mutation, affects MAP-Elites in order to gain insightinto how the search process is affected by the mutation rate.Our study compares fixed and dynamic mutation parameters for two different complex gait controllers. The results show that dynamic mutation combines favorably with MAP-Elites and that there is a strong relation between mutation parameters and exploration that can be utilized.
Links:
- Paper
Bibtex:
```
"@inproceedings{nordmoen2018dynamic,
title={Dynamic mutation in MAP-Elites for robotic repertoire generation},
author={Nordmoen, Jorgen and Samuelsen, Eivind and Ellefsen, Kai Olav and Glette, Kyrre},
booktitle={Artificial Life Conference Proceedings},
pages={598--605},
year={2018},
organization={MIT Press} }"
```
Evolution of a Functionally Diverse Swarm via a Novel Decentralised Quality-Diversity Algorithm Robotics
Authors:
- Emma Hart
- Andreas Steyven
- Ben Paechter
Abstract:
The presence of functional diversity within a group has been demonstrated to lead to greater robustness, higher performance and increased problem-solving ability in a broad range of studies that includes insect groups, human groups and swarm robotics. Evolving group diversity however has proved challenging within Evolutionary Robotics, requiring reproductive isolation and careful attention to population size and selection mechanisms. To tackle this issue, we introduce a novel, decentralised, variant of the MAP-Elites illumination algorithm which is hybridised with a well-known distributed evolutionary algorithm (mEDEA). The algorithm simultaneously evolves multiple diverse behaviours for multiple robots, with respect to a simple token-gathering task. Each robot in the swarm maintains a local archive defined by two pre-specified functional traits which is shared with robots it come into contact with. We investigate four different strategies for sharing, exploiting and combining local archives and compare results to mEDEA. Experimental results show that in contrast to previous claims, it is possible to evolve a functionally diverse swarm without geographical isolation, and that the new method outperforms mEDEA in terms of the diversity, coverage and precision of the evolved swarm.
Links:
- Paper
Bibtex:
```
"@article{hart2018evolution,
title={Evolution of a Functionally Diverse Swarm via a Novel Decentralised Quality-Diversity Algorithm},
author={Hart, Emma and Steyven, Andreas SW and Paechter, Ben},
journal={Proceedings of the Genetic and Evolutionary Computation Conference },
year={2018},
organization={ACM} }"
```

Evolution of repertoire-based control for robots with complex locomotor systems Robotics

Authors:

Miguel Duarte
Jorge Gomes
Sancho Moura Oliveira
Anders Lyhne Christensen

Bibtex:

"@article{duarte2018evolution,
title={Evolution of repertoire-based control for robots with complex locomotor systems},
author={Duarte, Miguel and Gomes, Jorge and Oliveira, Sancho Moura and Christensen, Anders Lyhne},
journal={IEEE Transactions on Evolutionary Computation},
volume={22},
number={2},
pages={314--328},
year={2018},
publisher={IEEE} }"

Evolving Multimodal Robot Behavior via Many Stepping Stones with the Combinatorial Multi-Objective Evolutionary Algorithm Robotics
Authors:
- Joost Huizinga
- Jeff Clune
Abstract:
An important challenge in reinforcement learning, including evolutionary robotics, is to solve multimodal problems, where agents have to act in qualitatively different ways depending on the circumstances. Because multimodal problems are often too difficult to solve directly, it is helpful to take advantage of staging, where a difficult task is divided into simpler subtasks that can serve as stepping stones for solving the overall problem. Unfortunately, choosing an effective ordering for these subtasks is difficult, and a poor ordering can reduce the speed and performance of the learning process. Here, we provide a thorough introduction and investigation of the Combinatorial Multi-Objective Evolutionary Algorithm (CMOEA), which avoids ordering subtasks by allowing all combinations of subtasks to be explored simultaneously. We compare CMOEA against two algorithms that can similarly optimize on multiple subtasks simultaneously: NSGA-II and Lexicase Selection. The algorithms are tested on a multimodal robotics problem with six subtasks as well as a maze navigation problem with a hundred subtasks. On these problems, CMOEA either outperforms or is competitive with the controls. Separately, we show that adding a linear combination over all objectives can improve the ability of NSGA-II to solve these multimodal problems. Lastly, we show that, in contrast to NSGA-II and Lexicase Selection, CMOEA can effectively leverage secondary objectives to achieve state-of-the-art results on the robotics task. In general, our experiments suggest that CMOEA is a promising, state-of-the-art algorithm for solving multimodal problems.
Links:
- Paper
Bibtex:
```
"@article{huizinga2018evolving,
title={Evolving Multimodal Robot Behavior via Many Stepping Stones with the Combinatorial Multi-Objective Evolutionary Algorithm},
author={Huizinga, Joost and Clune, Jeff},
journal={arXiv preprint arXiv:1807.03392},
year={2018} }"
```
Evolving a Repertoire of Controllers for a Multi-function Swarm Robotics
Authors:
- Sondre Engebraten
- Jonas Moen
- Oleg Yakimenko
- Kyrre Glette
Abstract:
Automated design of swarm behaviors with a top-down approach is a challenging research question that has not yet been fully addressed in the robotic swarm literature. This paper seeks to explore the possibility of using an evolutionary algorithm to evolve, rather than hand code, a wide repertoire of behavior primitives enabling more effective control of a large group or swarm of unmanned systems. We use the MAP-elites algorithm to generate a repertoire of controllers with varying abilities and behaviors allowing the swarm to adapt to user-defined preferences by selection of a new appropriate controller. To test the proposed method we examine two example applications: perimeter surveillance and network creation. Perimeter surveillance require agents to explore, while network creation requires them to disperse without los-ing connectivity. These are distinct application that have drastically different requirements on agent behavior, and are a good benchmark for our swarm controller optimization framework. We show a performance com-parison between a simple weighted controller and a parametric controller.Evolving controllers allows for specifying desired behaviors top-down, in terms of objectives to solve, rather than bottom-up.
Links:
- Paper
Bibtex:
```
"@inproceedings{engebraaten2018evolving,
title={Evolving a Repertoire of Controllers for a Multi-function Swarm},
author={Engebr{\aa}ten, Sondre A and Moen, Jonas and Yakimenko, Oleg and Glette, Kyrre},
booktitle={International Conference on the Applications of Evolutionary Computation},
pages={734--749},
year={2018},
organization={Springer} }"
```

Exploring genetic programming systems with MAP-Elites

Authors:

Emily Dolson
Alexander Lalejini
Charles Ofria

Bibtex:

"@article{dolson2018exploring,
title={Exploring genetic programming systems with MAP-Elites},
author={Dolson, Emily and Lalejini, Alexander and Ofria, Charles},
journal={PeerJ Preprints},
volume={6},
pages={e27154v1},
year={2018},
publisher={PeerJ Inc. San Francisco, USA} }"

Hierarchical Behavioral Repertoires with Unsupervised Descriptors Robotics
Authors:
- Antoine Cully
- Yiannis Demiris
Abstract:
Enabling artificial agents to automatically learn complex, versatile and high-performing behaviors is a long-lasting challenge. This paper presents a step in this direction with hierarchical behavioral repertoires that stack several behavioral repertoires to generate sophisticated behaviors. Each repertoire of this architecture uses the lower repertoires to create complex behaviors as sequences of simpler ones, while only the lowest repertoire directly controls the agent's movements. This paper also introduces a novel approach to automatically define behavioral descriptors thanks to an unsupervised neural network that organizes the produced high-level behaviors. The experiments show that the proposed architecture enables a robot to learn how to draw digits in an unsupervised manner after having learned to draw lines and arcs. Compared to traditional behavioral repertoires, the proposed architecture reduces the dimensionality of the optimization problems by orders of magnitude and provides behaviors with a twice better fitness. More importantly, it enables the transfer of knowledge between robots: a hierarchical repertoire evolved for a robotic arm to draw digits can be transferred to a humanoid robot by simply changing the lowest layer of the hierarchy. This enables the humanoid to draw digits although it has never been trained for this task.
Links:
- Paper
Bibtex:
```
"@article{cully2018hierarchical,
title={Hierarchical Behavioral Repertoires with Unsupervised Descriptors},
author={Cully, Antoine and Demiris, Yiannis},
journal={Proceedings of the Genetic and Evolutionary Computation Conference },
year={2018},
organization={ACM} }"
```
Mapping structural diversity in networks sharing a given degree distribution and global clustering: Adaptive resolution grid search evolution with Diophantine equation-based mutations
Authors:
- Peter Overbury
- Istvan Kiss
- Luc Berthouze
Abstract:
Methods that generate networks sharing a given degree distribution and global clustering can induce changes in structural properties other than that controlled for. Diversity in structural properties, in turn, can affect the outcomes of dynamical processes operating on those networks. Since exhaustive sampling is not possible, we propose a novel evolutionary framework for mapping this structural diversity. The three main features of this framework are: (a) subgraph-based encoding of networks, (b) exact mutations based on solving systems of Diophantine equations, and (c) heuristic diversity-driven mechanism to drive resolution changes in the MapElite algorithm. We show that our framework can elicit networks with diversity in their higher-order structure and that this diversity affects the behaviour of the complex contagion model. Through a comparison with state of the art clustered network generation methods, we demonstrate that our approach can uncover a comparably diverse range of networks without needing computationally unfeasible mixing times. Further, we suggest that the subgraph-based encoding provides greater confidence in the diversity of higher-order network structure for low numbers of samples and is the basis for explaining our results with complex contagion model. We believe that this framework could be applied to other complex landscapes that cannot be practically mapped via exhaustive sampling.
Links:
- Paper
Bibtex:
```
"@article{overbury2018mapping,
title={Mapping structural diversity in networks sharing a given degree distribution and global clustering: Adaptive resolution grid search evolution with Diophantine equation-based mutations},
author={Overbury, Peter and Kiss, Istv{\'a}n Z and Berthouze, Luc},
journal={arXiv preprint arXiv:1809.06293},
year={2018} }"
```
Multi-objective Analysis of MAP-Elites Performance Robotics
Authors:
- Eivind Samuelsen
- Kyrre Glette
Abstract:
In certain complex optimization tasks, it becomes necessary to use multiple measures to characterize the performance of different algorithms. This paper presents a method that combines ordinal effect sizes with Pareto dominance to analyze such cases. Since the method is ordinal, it can also generalize across different optimization tasks even when the performance measurements are differently scaled. Through a case study, we show that this method can discover and quantify relations that would be difficult to deduce using a conventional measure-by-measure analysis. This case study applies the method to the evolution of robot controller repertoires using the MAP-Elites algorithm. Here, we analyze the search performance across a large set of parametrizations; varying mutation size and operator type, as well as map resolution, across four different robot morphologies. We show that the average magnitude of mutations has a bigger effect on outcomes than their precise distributions.
Links:
- Paper
Bibtex:
```
"@article{samuelsen2018multi,
title={Multi-objective Analysis of MAP-Elites Performance},
author={Samuelsen, Eivind and Glette, Kyrre},
journal={arXiv preprint arXiv:1803.05174},
year={2018} }"
```

Open-ended evolution with multi-containers QD Robotics

Authors:

Stephane Doncieux
Alexandre Coninx

Bibtex:

"@inproceedings{doncieux2018open,
title={Open-ended evolution with multi-containers QD},
author={Doncieux, Stephane and Coninx, Alexandre},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
pages={107--108},
year={2018},
organization={ACM} }"

Optimisation and Illumination of a Real-World Workforce Scheduling and Routing Application (WSRP) via Map-Elites
Authors:
- Neil Urquhart
- Emma Hart
Abstract:
Workforce Scheduling and Routing Problems (WSRP) are very common in many practical domains, and usually, have a number of objectives. Illumination algorithms such as Map-Elites (ME) have recently gained traction in application to {m design} problems, in providing multiple diverse solutions as well as illuminating the solution space in terms of user-defined characteristics, but typically require significant computational effort to produce the solution archive. We investigate whether ME can provide an effective approach to solving WSRP, a {m repetitive} problem in which solutions have to be produced quickly and often. The goals of the paper are two-fold. The first is to evaluate whether ME can provide solutions of competitive quality to an Evolutionary Algorithm (EA) in terms of a single objective function, and the second to examine its ability to provide a repertoire of solutions that maximise user choice. We find that very small computational budgets favour the EA in terms of quality, but ME outperforms the EA at larger budgets, provides a more diverse array of solutions, and lends insight to the end-user.
Links:
- Paper
Bibtex:
```
"@inproceedings{urquhart2018optimisation,
title={Optimisation and Illumination of a Real-World Workforce Scheduling and Routing Application (WSRP) via Map-Elites},
author={Urquhart, Neil and Hart, Emma},
booktitle={International Conference on Parallel Problem Solving from Nature},
pages={488--499},
year={2018},
organization={Springer} }"
```
Prototype discovery using quality-diversity
Authors:
- Alexander Hagg
- Alexander Asteroth
- Thomas Back
Abstract:
An iterative computer-aided ideation procedure is introduced, building on recent quality-diversity algorithms, which search for diverse as well as high-performing solutions. Dimensionality reduction is used to define a similarity space, in which solutions are clustered into classes. These classes are represented by prototypes, which are presented to the user for selection. In the next iteration, quality-diversity focuses on searching within the selected class. A quantitative analysis is performed on a 2D airfoil, and a more complex 3D side view mirror domain shows how computer-aided ideation can help to enhance engineers' intuition while allowing their design decisions to influence the design process.
Bibtex:
```
"@inproceedings{hagg2018prototype,
title={Prototype discovery using quality-diversity},
author={Hagg, Alexander and Asteroth, Alexander and B{\"a}ck, Thomas},
booktitle={International Conference on Parallel Problem Solving from Nature},
pages={500--511},
year={2018},
organization={Springer} }"
```
Quality Diversity Through Surprise Robotics
Authors:
- Daniele Gravina
- Antonios Liapis
- Georgios Yannakakis
Abstract:
Quality diversity is a recent family of evolutionary search algorithms which focus on finding several well-performing (quality) yet different (diversity) solutions with the aim to maintain an appropriate balance between divergence and convergence during search. While quality diversity has already delivered promising results in complex problems, the capacity of divergent search variants for quality diversity remains largely unexplored. Inspired by the notion of surprise as an effective driver of divergent search and its orthogonal nature to novelty this paper investigates the impact of the former to quality diversity performance. For that purpose we introduce three new quality diversity algorithms which employ surprise as a diversity measure, either on its own or combined with novelty, and compare their performance against novelty search with local competition, the state of the art quality diversity algorithm. The algorithms are tested in a robot navigation task across 60 highly deceptive mazes. Our findings suggest that allowing surprise and novelty to operate synergistically for divergence and in combination with local competition leads to quality diversity algorithms of significantly higher efficiency, speed and robustness.
Links:
- Paper
Bibtex:
```
"@article{gravina2018quality,
title={Quality Diversity Through Surprise},
author={Gravina, Daniele and Liapis, Antonios and Yannakakis, Georgios N},
journal={arXiv preprint arXiv:1807.02397},
year={2018} }"
```
Quality and diversity optimization: A unifying modular framework Review Robotics
Authors:
- Antoine Cully
- Yiannis Demiris
Abstract:
The optimization of functions to find the best solution according to one or several objectives has a central role in many engineering and research fields. Recently, a new family of optimization algorithms, named Quality-Diversity optimization, has been introduced, and contrasts with classic algorithms. Instead of searching for a single solution, Quality-Diversity algorithms are searching for a large collection of both diverse and high-performing solutions. The role of this collection is to cover the range of possible solution types as much as possible, and to contain the best solution for each type. The contribution of this paper is threefold. Firstly, we present a unifying framework of Quality-Diversity optimization algorithms that covers the two main algorithms of this family (Multi-dimensional Archive of Phenotypic Elites and the Novelty Search with Local Competition), and that highlights the large variety of variants that can be investigated within this family. Secondly, we propose algorithms with a new selection mechanism for Quality-Diversity algorithms that outperforms all the algorithms tested in this paper. Lastly, we present a new collection management that overcomes the erosion issues observed when using unstructured collections. These three contributions are supported by extensive experimental comparisons of Quality-Diversity algorithms on three different experimental scenarios.
Links:
- Paper
Bibtex:
```
"@article{cully2018quality,
title={Quality and diversity optimization: A unifying modular framework},
author={Cully, Antoine and Demiris, Yiannis},
journal={IEEE Transactions on Evolutionary Computation},
volume={22},
number={2},
pages={245--259},
year={2018},
publisher={IEEE} }"
```
Reset-free trial-and-error learning for robot damage recovery Robotics
Authors:
- Konstantinos Chatzilygeroudis
- Vassilis Vassiliades
- Jean-Baptiste Mouret
Abstract:
The high probability of hardware failures prevents many advanced robots (e.g., legged robots) from being confidently deployed in real-world situations (e.g., post-disaster rescue). Instead of attempting to diagnose the failures, robots could adapt by trial-and-error in order to be able to complete their tasks. In this situation, damage recovery can be seen as a Reinforcement Learning (RL) problem. However, the best RL algorithms for robotics require the robot and the environment to be reset to an initial state after each episode, that is, the robot is not learning autonomously. In addition, most of the RL methods for robotics do not scale well with complex robots (e.g., walking robots) and either cannot be used at all or take too long to converge to a solution (e.g., hours of learning). In this paper, we introduce a novel learning algorithm called “Reset-free Trial-and-Error” (RTE) that (1) breaks the complexity by pre-generating hundreds of possible behaviors with a dynamics simulator of the intact robot, and (2) allows complex robots to quickly recover from damage while completing their tasks and taking the environment into account. We evaluate our algorithm on a simulated wheeled robot, a simulated six-legged robot, and a real six-legged walking robot that are damaged in several ways (e.g., a missing leg, a shortened leg, faulty motor, etc.) and whose objective is to reach a sequence of targets in an arena. Our experiments show that the robots can recover most of their locomotion abilities in an environment with obstacles, and without any human intervention.
Links:
- Paper
Bibtex:
```
"@article{chatzilygeroudis2018reset,
  title={Reset-free trial-and-error learning for robot damage recovery},
  author={Chatzilygeroudis, Konstantinos and Vassiliades, Vassilis and Mouret, Jean-Baptiste},
  journal={Robotics and Autonomous Systems},
  volume={100},
  pages={236--250},
  year={2018},
  publisher={Elsevier}}"
```
Talakat: Bullet Hell Generation through Constrained Map-Elites Games
Authors:
- Ahmed Khalifa
- Scott Lee
- Andy Nealen
- Julian Togelius
Abstract:
We describe a search-based approach to generating new levels for bullet hell games, which are action games characterized by and requiring avoidance of a very large amount of projectiles. Levels are represented using a domain-specific description language, and search in the space defined by this language is performed by a novel variant of the Map-Elites algorithm which incorporates a feasible- infeasible approach to constraint satisfaction. Simulation-based evaluation is used to gauge the fitness of levels, using an agent based on best-first search. The performance of the agent can be tuned according to the two dimensions of strategy and dexterity, making it possible to search for level configurations that require a specific combination of both. As far as we know, this paper describes the first generator for this game genre, and includes several algorithmic innovations.
Links:
- Paper
Bibtex:
```
"@article{khalifa2018talakat,
title={Talakat: Bullet Hell Generation through Constrained Map-Elites},
author={Khalifa, Ahmed and Lee, Scott and Nealen, Andy and Togelius, Julian},
journal={Proceedings of the Genetic and Evolutionary Computation Conference },
year={2018},
organization={ACM} }"
```
The surprising creativity of digital evolution: A collection of anecdotes from the evolutionary computation and artificial life research communities
Authors:
- Joel Lehman
- Jeff Clune
- Dusan Misevic
- and many others
Abstract:
Biological evolution provides a creative fount of complex and subtle adaptations, often surprising the scientists who discover them. However, because evolution is an algorithmic process that transcends the substrate in which it occurs, evolution's creativity is not limited to nature. Indeed, many researchers in the field of digital evolution have observed their evolving algorithms and organisms subverting their intentions, exposing unrecognized bugs in their code, producing unexpected adaptations, or exhibiting outcomes uncannily convergent with ones in nature. Such stories routinely reveal creativity by evolution in these digital worlds, but they rarely fit into the standard scientific narrative. Instead they are often treated as mere obstacles to be overcome, rather than results that warrant study in their own right. The stories themselves are traded among researchers through oral tradition, but that mode of information transmission is inefficient and prone to error and outright loss. Moreover, the fact that these stories tend to be shared only among practitioners means that many natural scientists do not realize how interesting and lifelike digital organisms are and how natural their evolution can be. To our knowledge, no collection of such anecdotes has been published before. This paper is the crowd-sourced product of researchers in the fields of artificial life and evolutionary computation who have provided first-hand accounts of such cases. It thus serves as a written, fact-checked collection of scientifically important and even entertaining stories. In doing so we also present here substantial evidence that the existence and importance of evolutionary surprises extends beyond the natural world, and may indeed be a universal property of all complex evolving systems.
Links:
- Paper
Bibtex:
```
"@article{lehman2018surprising,
title={The surprising creativity of digital evolution: A collection of anecdotes from the evolutionary computation and artificial life research communities},
author={Lehman, Joel and Clune, Jeff and Misevic, Dusan and others},
journal={arXiv preprint arXiv:1803.03453},
year={2018} }"
```
Using Centroidal Voronoi Tessellations to Scale Up the Multidimensional Archive of Phenotypic Elites Algorithm
Authors:
- Vassilis Vassiliades
- Konstantinos Chatzilygeroudis
- Jean-Baptiste Mouret
Abstract:
The recently introduced Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) is an evolutionary algorithm capable of producing a large archive of diverse, high-performing solutions in a single run. It works by discretizing a continuous feature space into unique regions according to the desired discretization per dimension. While simple, this algorithm has a main drawback: it cannot scale to high-dimensional feature spaces since the number of regions increase exponentially with the number of dimensions. In this paper, we address this limitation by introducing a simple extension of MAP-Elites that has a constant, pre-defined number of regions irrespective of the dimensionality of the feature space. Our main insight is that methods from computational geometry could partition a high-dimensional space into well-spread geometric regions. In particular, our algorithm uses a centroidal Voronoi tessellation (CVT) to divide the feature space into a desired number of regions; it then places every generated individual in its closest region, replacing a less fit one if the region is already occupied. We demonstrate the effectiveness of the new " CVT-MAP-Elites " algorithm in high-dimensional feature spaces through comparisons against MAP-Elites in maze navigation and hexapod locomotion tasks.
Links:
- Paper
Bibtex:
```
"@article{vassiliades2018using,
title={Using Centroidal Voronoi Tessellations to Scale Up the Multidimensional Archive of Phenotypic Elites Algorithm},
author={Vassiliades, Vassilis and Chatzilygeroudis, Konstantinos and Mouret, Jean-Baptiste},
journal={IEEE Transactions on Evolutionary Computation},
volume={22},
number={4},
pages={623--630},
year={2018},
publisher={IEEE} }"
```

2017: 7 Papers

A comparison of illumination algorithms in unbounded spaces
Authors:
- Vassilis Vassiliades
- Konstantinos Chatzilygeroudis
- Jean-Baptiste Mouret
Abstract:
Illumination algorithms are a new class of evolutionary algorithms capable of producing large archives of diverse and high-performing solutions. Examples of such algorithms include Novelty Search with Local Competition (NSLC), the Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) and the newly introduced Cen-troidal Voronoi Tessellation (CVT) MAP-Elites. While NSLC can be used in unbounded behavioral spaces, MAP-Elites and CVT-MAP-Elites require the user to manually specify the bounds. In this study, we introduce variants of these algorithms that expand their bounds based on the discovered solutions. In addition, we introduce a novel algorithm called "Cluster-Elites" that can adapt its bounds to non-convex spaces. We compare all algorithms in a maze navigation problem and illustrate that Cluster-Elites and the expansive variants of MAP-Elites and CVT-MAP-Elites have comparable or better performance than NSLC, MAP-Elites and CVT-MAP-Elites.
Links:
- Paper
Bibtex:
```
"@inproceedings{vassiliades2017comparison,
title={A comparison of illumination algorithms in unbounded spaces},
author={Vassiliades, Vassilis and Chatzilygeroudis, Konstantinos and Mouret, Jean-Baptiste},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
pages={1578--1581},
year={2017},
organization={ACM} }"
```
Aerodynamic design exploration through surrogate-assisted illumination
Authors:
- Adam Gaier
- Alexander Asteroth
- Jean-Baptiste Mouret
Abstract:
A new method for design space exploration and optimization, Surrogate-Assisted Illumination (SAIL), is presented. Inspired by robotics techniques designed to produce diverse repertoires of behaviors for use in damage recovery, SAIL produces diverse designs that vary according to features specified by the designer. By producing high-performing designs with varied combinations of user-defined features a map of the design space is created. This map illuminates the relationship between the chosen features and performance, and can aid designers in identifying promising design concepts. SAIL is designed for use with compu-tationally expensive design problems, such as fluid or structural dynamics, and integrates approximative models and intelligent sampling of the objective function to minimize the number of function evaluations required. On a 2D airfoil optimization problem SAIL is shown to produce hundreds of diverse designs which perform competitively with those found by state-of-the-art black box optimization. Its capabilities are further illustrated in a more expensive 3D aerodynamic optimization task.
Links:
- Paper
Bibtex:
```
"@inproceedings{gaier2017aerodynamic,
title={Aerodynamic design exploration through surrogate-assisted illumination},
author={Gaier, Adam and Asteroth, Alexander and Mouret, Jean-Baptiste},
booktitle={18th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference},
pages={3330},
year={2017} }"
```
Comparing multimodal optimization and illumination Robotics
Authors:
- Vassilis Vassiliades
- Konstantinos Chatzilygeroudis
- Jean-Baptiste Mouret
Abstract:
Illumination algorithms are a recent addition to the evolutionary computation toolbox that allows the generation of many diverse and high-performing solutions in a single run. Nevertheless, traditional multimodal optimization algorithms also search for diverse and high-performing solutions: could some multimodal optimization algorithms be beeer at illumination than illumination algorithms? In this study, we compare two illumination algorithms (Novelty Search with Local Competition (NSLC), MAP-Elites) with two multimodal optimization ones (Clearing, Restricted Tournament Selection) in a maze navigation task. e results show that Clearing can have comparable performance to MAP-Elites and NSLC.
Links:
- Paper
Bibtex:
```
"@inproceedings{vassiliades2017comparing,
title={Comparing multimodal optimization and illumination},
author={Vassiliades, Vassilis and Chatzilygeroudis, Konstantinos and Mouret, Jean-Baptiste},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
pages={97--98},
year={2017},
organization={ACM} }"
```
Data-efficient exploration, optimization, and modeling of diverse designs through surrogate-assisted illumination
Authors:
- Adam Gaier
- Alexander Asteroth
- Jean-Baptiste Mouret
Abstract:
The MAP-Elites algorithm produces a set of high-performing solutions that vary according to features deened by the user. This technique to 'illuminate' the problem space through the lens of chosen features has the potential to be a powerful tool for exploring design spaces, but is limited by the need for numerous evaluations. The Surrogate-Assisted Illumination (SAIL) algorithm, introduced here, integrates approximative models and intelligent sampling of the objective function to minimize the number of evaluations required by MAP-Elites. The ability of SAIL to efficiently produce both accurate models and diverse high-performing solutions is illustrated on a 2D airfoil design problem. The search space is divided into bins, each holding a design with a diierent combination of features. In each bin SAIL produces a better performing solution than MAP-Elites, and requires several orders of magnitude fewer evaluations. The CMA-ES algorithm was used to produce an optimal design in each bin: with the same number of evaluations required by CMA-ES to find a near-optimal solution in a single bin, SAIL finds solutions of similar quality in every bin.
Links:
- Paper
Bibtex:
```
"@inproceedings{gaier2017data,
title={Data-efficient exploration, optimization, and modeling of diverse designs through surrogate-assisted illumination},
author={Gaier, Adam and Asteroth, Alexander and Mouret, Jean-Baptiste},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
pages={99--106},
year={2017},
organization={ACM} }"
```
Discovering evolutionary stepping stones through behavior domination
Authors:
- Elliot Meyerson
- Risto Miikkulainen
Abstract:
Behavior domination is proposed as a tool for understanding and harnessing the power of evolutionary systems to discover and exploit useful stepping stones. Novelty search has shown promise in overcoming deception by collecting diverse stepping stones, and several algorithms have been proposed that combine novelty with a more traditional fitness measure to refocus search and help novelty search scale to more complex domains. However, combinations of novelty and fitness do not necessarily preserve the stepping stone discovery that novelty search affords. In several existing methods, competition between solutions can lead to an unintended loss of diversity. Behavior domination defines a class of algorithms that avoid this problem, while inheriting theoretical guarantees from multiobjective optimization. Several existing algorithms are shown to be in this class, and a new algorithm is introduced based on fast non-dominated sorting. Experimental results show that this algorithm outperforms existing approaches in domains that contain useful stepping stones, and its advantage is sustained with scale. The conclusion is that behavior domination can help illuminate the complex dynamics of behavior-driven search, and can thus lead to the design of more scalable and robust algorithms.
Links:
- Paper
Bibtex:
```
"@inproceedings{meyerson2017discovering,
title={Discovering evolutionary stepping stones through behavior domination},
author={Meyerson, Elliot and Miikkulainen, Risto},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference},
pages={139--146},
year={2017},
organization={ACM} }"
```
Feature space modeling through surrogate illumination
Authors:
- Adam Gaier
- Alexander Asteroth
- Jean-Baptiste Mouret
Abstract:
The MAP-Elites algorithm produces a set of high-performing solutions that vary according to features defined by the user.This technique has the potential to be a powerful tool for design space exploration, but is limited by the need for numerous evaluations. The Surrogate-Assisted Illumination algorithm (SAIL),introduced here, integrates approximative models and intelligent sampling of the objective function to minimize the number of evaluations required by MAP-Elites.The ability of SAIL to efficiently produce both accurate models and diverse high performing solutions is illustrated on a 2D air-foil design problem. The search space is divided into bins, each holding a design with a different combination of features. In each bin SAIL produces a better performing solution than MAP-Elites, and requires several orders of magnitude fewer evaluations. TheCMA-ES algorithm was used to produce an optimal design in each bin: with the same number of evaluations required by CMA-ES to find a near-optimal solution in a single bin, SAIL finds solutions of similar quality in every bin.
Links:
- Paper
Bibtex:
```
"@inproceedings{gaier2017feature,
title={Feature space modeling through surrogate illumination},
author={Gaier, Adam and Asteroth, Alexander and Mouret, Jean-Baptiste},
booktitle={Proc. of GECCO},
year={2017} }"
```

Learning highly diverse robot throwing movements through quality diversity search Robotics

Authors:

Seungsu Kim
Stephane Doncieux

Bibtex:

"@inproceedings{kim2017learning,
title={Learning highly diverse robot throwing movements through quality diversity search},
author={Kim, Seungsu and Doncieux, St{\'e}phane},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference Companion},
pages={1177--1178},
year={2017},
organization={ACM} }"

2016: 11 Papers

An Extended Study of Quality Diversity Algorithms
Authors:
- Justin Pugh
- Lisa Soros
- Kenneth Stanley
Abstract:
In a departure from conventional optimization where the goal is to find the best possible solution, a new class of evolutionary algorithms instead search for quality diversity(QD) – a maximally diverse collection of individuals in which each member is as high-performing as possible. In QD, diversity of behaviors or phenotypes is defined by a behavior characterization (BC) that is typically unaligned with (i.e.orthogonal to) the notion of quality. As experiments in a difficult maze task reinforce, QD algorithms driven by such an unaligned BC are unable to discover the best solutions on sufficiently deceptive problems. This study comprehensively surveys known QD algorithms and introduces several novel variants thereof, including a method for successfully confronting deceptive QD landscapes: driving search with multiple BCs simultaneously.
Links:
- Paper
Bibtex:
```
"@inproceedings{pugh2016extended,
title={An Extended Study of Quality Diversity Algorithms},
author={Pugh, Justin K and Soros, Lisa B and Stanley, Kenneth O},
booktitle={Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion},
pages={19--20},
year={2016},
organization={ACM} }"
```

EvoRBC: evolutionary repertoire-based control for robots with arbitrary locomotion complexity Robotics

Authors:

Miguel Duarte
Jorge Gomes
Sancho Moura Oliveira
Anders Lyhne Christensen

Bibtex:

"@inproceedings{duarte2016evorbc,
title={EvoRBC: evolutionary repertoire-based control for robots with arbitrary locomotion complexity},
author={Duarte, Miguel and Gomes, Jorge and Oliveira, Sancho Moura and Christensen, Anders Lyhne},
booktitle={Proceedings of the Genetic and Evolutionary Computation Conference 2016},
pages={93--100},
year={2016},
organization={ACM} }"

Gaining insight into quality diversity
Authors:
- Joshua Auerbach
- Giovanni Iacca
- Dario Floreano
Abstract:
Recently there has been a growing movement of researchers that believes innovation and novelty creation, rather than pure optimization, are the true strengths of evolutionary algorithms relative to other forms of machine learning. This idea also provides one possible explanation for why evolutionary processes may exist in nervous systems on top of other forms of learning. One particularly exciting corollary of this, is that evolutionary algorithms may be used to produce what Pugh et al have dubbed Quality Diversity (QD): as many as possible different solutions (according to some characterization), which are all as fit as possible. While the notion of QD implies choosing the dimensions on which to measure diversity and performance, we propose that it may be possible (and desirable) to free the evolutionary process from requiring defining these dimensions. Toward that aim, we seek to understand more about QD in general by investigating how algorithms informed by different measures of diversity (or none at all) create QD, when that QD is mea- sured in a diversity of ways.
Links:
- Paper
Bibtex:
```
"@inproceedings{auerbach2016gaining,
title={Gaining insight into quality diversity},
author={Auerbach, Joshua E and Iacca, Giovanni and Floreano, Dario},
booktitle={Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion},
pages={1061--1064},
year={2016},
organization={ACM} }"
```
How Do Different Encodings Influence the Performance of the MAP-Elites Algorithm? Robotics
Authors:
- Danesh Tarapore
- Jeff Clune
- Antoine Cully
- Jean-Baptiste Mouret
Abstract:
The recently introduced Intelligent Trial and Error algorithm (IT&E) both improves the ability to automatically generate controllers that transfer to real robots, and enables robots to creatively adapt to damage in less than 2 minutes. A key component of IT&E is a new evolutionary algorithm called MAP-Elites, which creates a behavior-performance map that is provided as a set of " creative " ideas to an online learning algorithm. To date, all experiments with MAP-Elites have been performed with a directly encoded list of parameters: it is therefore unknown how MAP-Elites would behave with more advanced encodings, like HyperNeat and SUPG. In addition, because we ultimately want robots that respond to their environments via sensors, we investigate the ability of MAP-Elites to evolve closed-loop controllers, which are more complicated, but also more powerful. Our results show that the encoding critically impacts the quality of the results of MAP-Elites, and that the differences are likely linked to the locality of the encoding (the likelihood of generating a similar behavior after a single mutation). Overall, these results improve our understanding of both the dynamics of the MAP-Elites algorithm and how to best harness MAP-Elites to evolve effective and adaptable robotic controllers.
Links:
- Paper
Bibtex:
```
"@inproceedings{tarapore2016different,
title={How Do Different Encodings Influence the Performance of the MAP-Elites Algorithm?},
author={Tarapore, Danesh and Clune, Jeff and Cully, Antoine and Mouret, Jean-Baptiste},
booktitle={Genetic and Evolutionary Computation Conference},
year={2016} }"
```
On the critical role of divergent selection in evolvability Robotics
Authors:
- Joel Lehman
- Bryan Wilder
- Kenneth Stanley
Abstract:
An ambitious goal in evolutionary robotics (ER) is to evolve increasingly complex robotic behaviors with minimal human design effort. Reaching this goal requires evolutionary algorithms that can unlock from genetic encodings their latent potential for evolvability. One issue clouding this goal is conceptual confusion about evolvability that often obscures important or desirable aspects of evolvability. The danger from such confusion is that it may establish unrealistic goals for evolvability that prove unproductive in practice. An important issue separate from conceptual confusion is the common misalignment between selection and evolvability in ER. While more expressive encodings can represent higher-level adaptations (e.g. sexual reproduction or developmental systems) that increase long-term evolutionary potential (i.e. evolvability), realizing such potential requires gradients of fitness and evolvability to align. In other words, selection is often a critical factor limiting increasing evolvability. Thus, drawing from a series of recent papers, this article seeks to both (1) clarify and focus the ways in which the term evolvability is used within artificial evolution and (2) argue for the importance of one type of selection, i.e. divergent selection, for enabling evolvability. The main argument is that there is a fundamental connection between divergent selection and evolvability (on both the individual and population level) that does not hold for typical goal-oriented selection. The conclusion is that selection pressure plays a critical role in realizing the potential for evolvability and that divergent selection in particular provides a principled mechanism for encouraging evolvability in artificial evolution.
Links:
- Paper
Bibtex:
```
"@article{lehman2016critical,
title={On the critical role of divergent selection in evolvability},
author={Lehman, Joel and Wilder, Bryan and Stanley, Kenneth O},
journal={Frontiers in Robotics and AI},
volume={3},
pages={45},
year={2016},
publisher={Frontiers} }"
```
Quality Diversity: A New Frontier for Evolutionary Computation Robotics
Authors:
- Justin PughK
- Lisa Soros
- Kenneth Stanley
Abstract:
While evolutionary computation and evolutionary robotics take inspiration from nature, they have long focused mainly on problems of performance optimization. Yet, evolution in nature can be interpreted as more nuanced than a process of simple optimization. In particular, natural evolution is a divergent search that optimizes locally within each niche as it simultaneously diversifies. This tendency to discover both quality and diversity at the same time differs from many of the conventional algorithms of machine learning, and also thereby suggests a different foundation for inferring the approach of greatest potential for evolutionary algorithms. In fact, several recent evolutionary algorithms called quality diversity (QD) algorithms (e.g., novelty search with local competition and MAP-Elites) have drawn inspiration from this more nuanced view, aiming to fill a space of possibilities with the best possible example of each type of achievable behavior. The result is a new class of algorithms that return an archive of diverse, high-quality behaviors in a single run. The aim in this paper is to study the application of QD algorithms in challenging environments (in particular complex mazes) to establish their best practices for ambitious domains in the future. In addition to providing insight into cases when QD succeeds and fails, a new approach is investigated that hybridizes multiple views of behaviors (called behavior characterizations) in the same run, which succeeds in overcoming some of the challenges associated with searching for QD with respect to a behavior characterization that is not necessarily sufficient for generating both quality and diversity at the same time.
Links:
- Paper
Bibtex:
```
"@article{pugh2016quality,
title={Quality Diversity: A New Frontier for Evolutionary Computation},
author={Pugh, Justin K and Soros, Lisa B and Stanley, Kenneth O},
journal={Frontiers in Robotics and AI},
volume={3},
pages={40},
year={2016},
publisher={Frontiers} }"
```
Rapid Phenotypic Landscape Exploration Through Hierarchical Spatial Partitioning
Authors:
- Davy Smith
- Laurissa Tokarchuk
- Geraint Wiggins
Abstract:
Exploration of the search space through the optimisation of phenotypic diversity is of increasing interest within the field of evolutionary robotics. Novelty search and the more recent MAP-Elites are two state of the art evolutionary algorithms which diversify low dimensional phenotypic traits for divergent exploration. In this paper we introduce a novel alternative for rapid divergent search of the feature space. Unlike previous phenotypic search procedures, our proposed Spatial, Hierarchical, Illuminated Neuro-Evolution (SHINE) algorithm utilises a tree structure for the maintenance and selection of potential candidates. SHINE penalises previous solutions in more crowded areas of the landscape. Our experimental results show that SHINE significantly outperforms novelty search and MAP-Elites in both performance and exploration. We conclude that the SHINE algorithm is a viable method for rapid divergent search of low dimensional, phenotypic landscapes.
Links:
- Paper
Bibtex:
```
"@inproceedings{smith2016rapid,
 title={Rapid phenotypic landscape exploration through hierarchical spatial partitioning},
 author={Smith, Davy and Tokarchuk, Laurissa and Wiggins, Geraint},
 booktitle={International conference on parallel problem solving from nature},
 pages={911--920},
 year={2016},
 organization={Springer}}"  
```
Safety-aware robot damage recovery using constrained bayesian optimization and simulated priors Robotics
Authors:
- Vaios Papaspyros
- Konstantinos Chatzilygeroudis
- Vassilis Vassiliades
- Jean-Baptiste Mouret
Abstract:
The recently introduced Intelligent Trial-and-Error (IT&E) algorithm showed that robots can adapt to damage in a matter of a few trials. The success of this algorithm relies on two components: prior knowledge acquired through simulation with an intact robot, and Bayesian optimization (BO) that operates on-line, on the damaged robot. While IT&E leads to fast damage recovery, it does not incorporate any safety constraints that prevent the robot from attempting harmful behaviors. In this work, we address this limitation by replacing the BO component with a constrained BO procedure. We evaluate our approach on a simulated damaged humanoid robot that needs to crawl as fast as possible, while performing as few unsafe trials as possible. We compare our new "safety-aware IT&E" algorithm to IT&E and a multi-objective version of IT&E in which the safety constraints are dealt as separate objectives. Our results show that our algorithm outperforms the other approaches, both in crawling speed within the safe regions and number of unsafe trials.
Links:
- Paper
Bibtex:
```
"@inproceedings{papaspyros2016safety,
title={Safety-aware robot damage recovery using constrained bayesian optimization and simulated priors},
author={Papaspyros, Vaios and Chatzilygeroudis, Konstantinos and Vassiliades, Vassilis and Mouret, Jean-Baptiste},
booktitle={
Bayesian Optimization: Black-box Optimization and Beyond (workshop at NIPS), 2016, Barcelone, Spain.},
year={2016} }"
```
Searching for quality diversity when diversity is unaligned with quality
Authors:
- Justin Pugh
- Lisa Soros
- Kenneth Stanley
Abstract:
Inspired by natural evolution’s affinity for discovering a wide variety of successful organisms, a new evolutionary search paradigm has emerged wherein the goal is not to find the single best solution but rather to collect a diversity of unique phenotypes where each variant is as good as it can be. These quality diversity(QD) algorithms therefore must explore multiple promising niches simultaneously. A QD algorithm’s diversity component, formalized by specifying a behavior characterization (BC), not only generates diversity but also promotes quality by helping to overcome deception in the fitness landscape. However, some BCs (particularly those that are unaligned with the notion of quality) do not adequately mitigate deception, rendering QD algorithms unable to discover the best-performing solutions on difficult problems. This paper introduces a solution that enables QD algorithms to pursue arbitrary notions of diversity without compromising their ability to solve hard problems: driving search with multiple BCs simultaneously
Links:
- Paper
Bibtex:
```
"@inproceedings{pugh2016searching,
title={Searching for quality diversity when diversity is unaligned with quality},
author={Pugh, Justin K and Soros, Lisa B and Stanley, Kenneth O},
booktitle={International Conference on Parallel Problem Solving from Nature},
pages={880--889},
year={2016},
organization={Springer} }"
```
Towards semi-episodic learning for robot damage recovery Robotics
Authors:
- Konstantinos Chatzilygeroudis
- Antoine Cully
- Jean-Baptiste Mouret
Abstract:
The recently introduced Intelligent Trial and Error algorithm (IT&E) enables robots to creatively adapt to damage in a matter of minutes by combining an off-line evolutionary algorithm and an on-line learning algorithm based on Bayesian Optimization. We extend the IT&E algorithm to allow for robots to learn to compensate for damages while executing their task(s). This leads to a semi-episodic learning scheme that increases the robot's lifetime autonomy and adaptivity. Preliminary experiments on a toy simulation and a 6-legged robot locomotion task show promising results.
Links:
- Paper
Bibtex:
```
"@inproceedings{chatzilygeroudis2016towards,
title={Towards semi-episodic learning for robot damage recovery},
author={Chatzilygeroudis, Konstantinos and Cully, Antoine and Mouret, Jean-Baptiste},
booktitle={IEEE International Conference on Robotics and Automation (ICRA) Workshop on AI for Long-Term Autonomy},
year={2016} }"
```
Understanding innovation engines: Automated creativity and improved stochastic optimization via deep learning
Authors:
- Anh Nguyen
- Jason Yosinski
- Jeff Clune
Abstract:
The Achilles Heel of stochastic optimization algorithms is getting trapped on local optima. Novelty Search mitigates this problem by encouraging exploration in all interest-ing directions by replacing the performance objective with a reward for novel behaviors. This reward for novel behaviors has traditionally required a human-crafted, behavioral distance function. While Novelty Search is a major conceptual breakthrough and outperforms traditional stochastic optimization on certain problems, it is not clear how to apply it to challenging, high-dimensional problems where specifying a useful behavioral distance function is difficult. For example, in the space of images, how doy ou encourage novelty to produce hawks and heroes instead of endless pixel static?Here we propose a new algorithm, the Innovation Engine, that builds on NoveltySearch by replacing the human-crafted behavioral distance with a Deep Neural Net-work (DNN) that can recognize interesting differences between phenotypes. The key insight is that DNNs can recognize similarities and differences between phenotypesat an abstract level, wherein novelty means interesting novelty. For example, a DNN-based novelty search in the image space does not explore in the low-level pixel space, but instead creates a pressure to create new types of images (e.g. churches, mosques, obelisks, etc.). Here we describe the long-term vision for the Innovation Engine algorithm, which involves many technical challenges that remain to be solved. We then implement a simplified version of the algorithm that enables us to explore some of the algorithm’s key motivations. Our initial results, in the domain of images, suggest that Innovation Engines could ultimately automate the production of endless streams of interesting solutions in any domain: e.g. producing intelligent software, robot con-trollers, optimized physical components, and art.
Links:
- Paper
Bibtex:
```
"@article{nguyen2016understanding,
title={Understanding innovation engines: Automated creativity and improved stochastic optimization via deep learning},
author={Nguyen, Anh and Yosinski, Jason and Clune, Jeff},
journal={Evolutionary computation},
volume={24},
number={3},
pages={545--572},
year={2016},
publisher={MIT Press} }"
```

2015: 8 Papers

Confronting the challenge of quality diversity
Authors:
- Justin Pugh
- Lisa Soros
- Paul Szerlip
- Kenneth Stanley
Abstract:
In contrast to the conventional role of evolution in evolution-ary computation (EC) as an optimization algorithm, a newclass of evolutionary algorithms has emerged in recent yearsthat instead aim to accumulate as diverse a collection of dis-coveries as possible, yet where each variant in the collection isas fit as it can be. Often applied in both neuroevolution andmorphological evolution, these newquality diversity(QD)algorithms are particularly well-suited to evolution’s inherentstrengths, thereby offering a promising niche for EC withinthe broader field of machine learning. However, because QDalgorithms are so new, until now no comprehensive studyhas yet attempted to systematically elucidate their relativestrengths and weaknesses under different conditions. Tak-ing a first step in this direction, this paper introduces anew benchmark domain designed specifically to compare andcontrast QD algorithms. It then shows how the degree ofalignment between the measure of quality and the behaviorcharacterization (which is an essential component of all QDalgorithms to date) impacts the ultimate performance ofdifferent such algorithms. The hope is that this initial studywill help to stimulate interest in QD and begin to unify thedisparate ideas in the area.
Links:
- Paper
Bibtex:
```
"@inproceedings{pugh2015confronting,
title={Confronting the challenge of quality diversity},
author={Pugh, Justin K and Soros, LB and Szerlip, Paul A and Stanley, Kenneth O},
booktitle={Proceedings of the 2015 on Genetic and Evolutionary Computation Conference},
pages={967--974},
year={2015},
organization={ACM} }"
```
Constrained novelty search: A study on game content generation Games
Authors:
- Antonios Liapis
- Georgios Yannakakis
- Julian Togelius
Abstract:
Novelty search is a recent algorithm geared towards exploring search spaces without regard to objectives. When the presence of constraints divides a search space into feasible space and infeasible space, interesting implications arise regarding how novelty search explores such spaces. This paper elaborates on the problem of constrained novelty search and proposes two novelty search algorithms which search within both the feasible and the infeasible space. Inspired by the FI-2pop genetic algorithm, both algorithms maintain and evolve two separate populations, one with feasible and one with infeasible individuals, while each population can use its own selection method. The proposed algorithms are applied to the problem of generating diverse but playable game levels, which is representative of the larger problem of procedural game content generation. Results show that the two-population constrained novelty search methods can create, under certain conditions, larger and more diverse sets of feasible game levels than current methods of novelty search, whether constrained or unconstrained. However, the best algorithm is contingent on the particularities of the search space and the genetic operators used. Additionally, the proposed enhancement of offspring boosting is shown to enhance performance in all cases of two-population novelty search.
Links:
- Paper
Bibtex:
```
"@article{liapis2015constrained,
title={Constrained novelty search: A study on game content generation},
author={Liapis, Antonios and Yannakakis, Georgios N and Togelius, Julian},
journal={Evolutionary computation},
volume={23},
number={1},
pages={101--129},
year={2015},
publisher={MIT Press} }"
```
Enhancing divergent search through extinction events Robotics
Authors:
- Joel Lehman
- Risto Miikkulainen
Abstract:
A challenge in evolutionary computation is to create representations as evolvable as those in natural evolution. This paper hypothesizes that extinction events, i.e. mass extinctions, can significantly increase evolvability, but only when combined with a divergent search algorithm, i.e. a search driven towards diversity (instead of optimality). Extinctions amplify diversity-generation by creating unpredictable evolutionary bottlenecks. Persisting through multiple such bottlenecks is more likely for lineages that diversify across many niches, resulting in indirect selection pressure for the capacity to evolve. This hypothesis is tested through experiments in two evolutionary robotics domains. The results show that combining extinction events with divergent search increases evolvability, while combining them with convergent search offers no similar benefit. The conclusion is that extinction events may provide a simple and effective mechanism to enhance performance of divergent search algorithms.
Links:
- Paper
Bibtex:
```
"@inproceedings{lehman2015enhancing,
title={Enhancing divergent search through extinction events},
author={Lehman, Joel and Miikkulainen, Risto},
booktitle={Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation},
pages={951--958},
year={2015},
organization={ACM} }"
```
Evolving a behavioral repertoire for a walking robot Robotics
Authors:
- Antoine Cully
- Jean-Baptiste Mouret
Abstract:
Numerous algorithms have been proposed to allow legged robots to learn to walk. However, the vast majority of these algorithms is devised to learn to walk in a straight line, which is not sufficient to accomplish any real-world mission. Here we introduce the Transferability-based Behavioral Repertoire Evolution algorithm (TBR-Evolution), a novel evolutionary algorithm that simultaneously discovers several hundreds of simple walking controllers, one for each possible direction. By taking advantage of solutions that are usually discarded by evolutionary processes, TBR-Evolution is substantially faster than independently evolving each controller. Our technique relies on two methods: (1) novelty search with local competition, which searches for both high-performing and diverse solutions, and (2) the transferability approach, which com-bines simulations and real tests to evolve controllers for a physical robot. We evaluate this new technique on a hexapod robot. Results show that with only a few dozen short experiments performed on the robot, the algorithm learns a repertoire of con-trollers that allows the robot to reach every point in its reachable space. Overall, TBR-Evolution opens a new kind of learning algorithm that simultaneously optimizes all the achievable behaviors of a robot.
Links:
- Paper
Bibtex:
```
"@article{cully2015evolving,
title={Evolving a behavioral repertoire for a walking robot},
author={Cully, Antoine and Mouret, Jean-Baptiste},
journal={Evolutionary Computation},
year={2015},
publisher={MIT Press} }"
```
Extinction events can accelerate evolution
Authors:
- Joel Lehman
- Risto Miikkulainen
Abstract:
Extinction events impact the trajectory of biological evolution significantly. They are often viewed as upheavals to the evolutionary process. In contrast, this paper supports the hypothesis that although they are unpredictably destructive, extinction events may in the long term accelerate evolution by increasing evolvability. In particular, if extinction events extinguish indiscriminately many ways of life, indirectly they may select for the ability toe xpand rapidly through vacated niches. Lineages with such an ability are more likely to persist through multiple extinctions. Lending computational support for this hypothesis, this paper shows how increased evolvability will result from simulated extinction events in two computational models of evolved behavior. The conclusion is that although they are destructive in the short term, extinction events may make evolution more prolific in the long term.
Links:
- Paper
Bibtex:
```
"@article{lehman2015extinction,
title={Extinction events can accelerate evolution},
author={Lehman, Joel and Miikkulainen, Risto},
journal={PloS one},
volume={10},
number={8},
pages={e0132886},
year={2015},
publisher={Public Library of Science} }"
```
Illuminating search spaces by mapping elites Robotics
Authors:
- Jean-Baptiste Mouret
- Jeff Clune
Abstract:
Many fields use search algorithms, which automatically explore a search space to find high-performing solutions: chemists search through the space of molecules to discover new drugs; engineers search for stronger, cheaper, safer designs, scientists search for models that best explain data, etc. The goal of search algorithms has traditionally been to return the single highest-performing solution in a search space. Here we describe a new, fundamentally different type of algorithm that is more useful because it provides a holistic view of how high-performing solutions are distributed throughout a search space. It creates a map of high-performing solutions at each point in a space defined by dimensions of variation that a user gets to choose. This Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) algorithm illuminates search spaces, allowing researchers to understand how interesting attributes of solutions combine to affect performance, either positively or, equally of interest, negatively. For example, a drug company may wish to understand how performance changes as the size of molecules and their cost-to-produce vary. MAP-Elites produces a large diversity of high-performing, yet qualitatively different solutions, which can be more helpful than a single, high-performing solution. Interestingly, because MAP-Elites explores more of the search space, it also tends to find a better overall solution than state-of-the-art search algorithms. We demonstrate the benefits of this new algorithm in three different problem domains ranging from producing modular neural networks to designing simulated and real soft robots. Because MAP- Elites (1) illuminates the relationship between performance and dimensions of interest in solutions, (2) returns a set of high-performing, yet diverse solutions, and (3) improves finding a single, best solution, it will advance science and engineering.
Links:
- Paper
Bibtex:
```
"@article{mouret2015illuminating,
title={Illuminating search spaces by mapping elites},
author={Mouret, Jean-Baptiste and Clune, Jeff},
journal={arXiv preprint arXiv:1504.04909},
year={2015} }"
```
Innovation engines: Automated creativity and improved stochastic optimization via deep learning
Authors:
- Anh Nguyen
- Jason Yosinski
- Jeff Clune
Abstract:
The Achilles Heel of stochastic optimization algorithms is etting trapped on local optima. Novelty Search avoids this problem by encouraging a search in all interesting directions.That occurs by replacing a performance objective with a reward for novel behaviors, as defined by a human-crafted, and often simple, behavioral distance function. While NoveltySearch is a major conceptual breakthrough and outperforms traditional stochastic optimization on certain problems, it is not clear how to apply it to challenging, high-dimensional problems where specifying a useful behavioral distance function is difficult. For example, in the space of images, how do you encourage novelty to produce hawks and heroes instead of endless pixel static? Here we propose a new algorithm, the Innovation Engine, that builds on Novelty Search by re-placing the human-crafted behavioral distance with a DeepNeural Network (DNN) that can recognize interesting differences between phenotypes. The key insight is that DNNs can recognize similarities and differences between phenotypes at an abstract level, wherein novelty means interesting novelty. For example, a novelty pressure in image space does not explore in the low-level pixel space, but instead creates a pressure to create new types of images (e.g. churches, mosques, obelisks, etc.). Here we describe the long-term vision for the Innovation Engine algorithm, which involves many technical challenges that remain to be solved. We then implement a simplified version of the algorithm that enables us to explore some of the algorithm’s key motivations. Our initial results, in the domain of images, suggest that Innovation Engines could ultimately automate the production of endless streams of interesting solutions in any domain: e.g.producing intelligent software, robot controllers, optimized physical components, and art.
Links:
- Paper
Bibtex:
```
"@inproceedings{nguyen2015innovation,
title={Innovation engines: Automated creativity and improved stochastic optimization via deep learning},
author={Nguyen, Anh Mai and Yosinski, Jason and Clune, Jeff},
booktitle={Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation},
pages={959--966},
year={2015},
organization={ACM} }"
```
Robots that can adapt like animals Robotics
Authors:
- Antoine Cully
- Jeff Clune
- Danesh Tarapore
- Jean-Baptiste Mouret
Abstract:
As robots leave the controlled environments of factories to autonomously function in more complex, natural environments, they will have to respond to the inevitable fact that they will become damaged. However, while animals can quickly adapt to a wide variety of injuries, current robots cannot "think outside the box" to find a compensatory behavior when damaged: they are limited to their pre-specified self-sensing abilities, can diagnose only anticipated failure modes, and require a pre-programmed contingency plan for every type of potential damage, an impracticality for complex robots. Here we introduce an intelligent trial and error algorithm that allows robots to adapt to damage in less than two minutes, without requiring self-diagnosis or pre-specified contingency plans. Before deployment, a robot exploits a novel algorithm to create a detailed map of the space of high-performing behaviors: This map represents the robot's intuitions about what behaviors it can perform and their value. If the robot is damaged, it uses these intuitions to guide a trial-and-error learning algorithm that conducts intelligent experiments to rapidly discover a compensatory behavior that works in spite of the damage. Experiments reveal successful adaptations for a legged robot injured in five different ways, including damaged, broken, and missing legs, and for a robotic arm with joints broken in 14 different ways. This new technique will enable more robust, effective, autonomous robots, and suggests principles that animals may use to adapt to injury.
Links:
- Paper
Bibtex:
```
"@article{cully2015robots,
title={Robots that can adapt like animals},
author={Cully, Antoine and Clune, Jeff and Tarapore, Danesh and Mouret, Jean-Baptiste},
journal={Nature},
volume={521},
number={7553},
pages={503--507},
year={2015},
publisher={Nature Publishing Group} }"
```

2013: 2 Papers

Behavioral repertoire learning in robotics Robotics
Authors:
- Antoine Cully
- Jean-Baptiste Mouret
Abstract:
Learning in robotics typically involves choosing a simple goal(e.g. walking) and assessing the performance of each con-troller with regard to this task (e.g. walking speed). How-ever, learning advanced, input-driven controllers (e.g. walk-ing in each direction) requires testing each controller on a large sample of the possible input signals. This costly pro-cess makes difficult to learn useful low-level controllers in robotics. Here we introduce BR-Evolution, a new evolutionary learn-ing technique that generates a behavioral repertoire by taking advantage of the candidate solutions that are usually discarded. Instead of evolving a single, general controller,BR-evolution thus evolves a collection of simple controllers, one for each variant of the target behavior; to distinguish similar controllers, it uses a performance objective that al-lows it to produce a collection of diverse but high-performing behaviors. We evaluated this new technique by evolving gait controllers for a simulated hexapod robot. Results show that a single run of the EA quickly finds a collection of controllers that allows the robot to reach each point of the reachable space. Overall, BR-Evolution opens a new kind of learning algorithm that simultaneously optimizes all the achievable behaviors of a robot.
Links:
- Paper
Bibtex:
```
"@inproceedings{cully2013behavioral,
title={Behavioral repertoire learning in robotics},
author={Cully, Antoine and Mouret, Jean-Baptiste},
booktitle={Proceedings of the 15th annual conference on Genetic and Evolutionary Computation},
pages={175--182},
year={2013},
organization={ACM} }"
```
Transforming exploratory creativity with DeLeNoX Games
Authors:
- Antonios Liapis
- Hector Martinez
- Julian Togelius
- Georgios Yannakakis
Abstract:
We introduce DeLeNoX (Deep Learning Novelty Explorer), a system that autonomously creates artifacts in constrained spaces according to its own evolving interestingness criterion. DeLeNoX proceeds in alternating phases of exploration and transformation. In the exploration phases, a version of novelty search augmented with constraint handling searches for maximally diverse artifacts using a given distance function. In the transformation phases, a deep learning autoencoder learns to compress the variation between the found artifacts into a lower-dimensional space. The newly trained encoder is then used as the basis for a new distance function, transforming the criteria for the next exploration phase. In the current paper, we apply DeLeNoX to the creation of spaceships suitable for use in two-dimensional arcade-style computer games, a representative problem in procedural content generation in games. We also situate DeLeNoX in relation to the distinction between exploratory and transformational creativity, and in relation to Schmidhuber’s theory of creativity through the drive for compression progress.
Links:
- Paper
Bibtex:
```
"@inproceedings{liapis2013transforming,
title={Transforming exploratory creativity with DeLeNoX},
author={Liapis, Antonios and Mart{\i}nez, H{\'e}ctor P and Togelius, Julian and Yannakakis, Georgios N},
booktitle={Proceedings of the Fourth International Conference on Computational Creativity},
pages={56--63},
year={2013},
organization={AAAI Press} }"
```

2011: 3 Papers

Abandoning objectives: Evolution through the search for novelty alone Robotics
Authors:
- Joel Lehman
- Kenneth Stanley
Abstract:
In evolutionary computation, the fitness function normally measures progress towards an objective in the search space, effectively acting as an objective function. Through deception, such objective functions may actually prevent the objective from being reached. While methods exist to mitigate deception, they leave the underlying pathology untreated: Objective functions themselves may actively misdirect search towards dead ends. This paper proposes an approach to circumventing deception that also yields a new perspective on open-ended evolution: Instead of either explicitly seeking an objective or modeling natural evolution to capture open-endedness, the idea is to simply search for behavioral novelty. Even in an objective-based problem, such novelty search ignores the objective. Because many points in the search space collapse to a single behavior, the search for novelty is often feasible. Furthermore, because there are only so many simple behaviors, the search for novelty leads to increasing complexity. By decoupling open-ended search from artificial life worlds, the search for novelty is applicable to real world problems. Counterintuitively, in the maze navigation and biped walking tasks in this paper, novelty search significantly outperforms objective-based search, suggesting the strange conclusion that some problems are best solved by methods that ignore the objective. The main lesson is the inherent limitation of the objective-based paradigm and the unexploited opportunity to guide search through other means.
Links:
Bibtex:
```
"@article{lehman2011abandoning,
title={Abandoning objectives: Evolution through the search for novelty alone},
author={Lehman, Joel and Stanley, Kenneth O},
journal={Evolutionary computation},
volume={19},
number={2},
pages={189--223},
year={2011},
publisher={MIT Press} }"
```
Evolving a diversity of virtual creatures through novelty search and local competition Robotics
Authors:
- Joel Lehman
- Kenneth Stanley
Abstract:
An ambitious challenge in artificial life is to craft an evolutionary process that discovers a wide diversity of welladapted virtual creatures within a single run. Unlike in nature, evolving creatures in virtual worlds tend to converge to a single morphology because selection therein greedily rewards the morphology that is easiest to exploit. However, novelty search, a technique that explicitly rewards diverging, can potentially mitigate such convergence. Thus in this paper an existing creature evolution platform is extended with multi-objective search that balances drives for both novelty and performance. However, there are different ways to combine performance-driven search and novelty search. The suggested approach is to provide evolution with both a novelty objective that encourages diverse morphologies and a local competition objective that rewards individuals outperforming those most similar in morphology. The results in an experiment evolving locomoting virtual creatures show that novelty search with local competition discovers more functional morphological diversity within a single run than models with global competition, which are more predisposed to converge. The conclusions are that novelty search with local competition may complement recent advances in evolving virtual creatures and may in general be a principled approach to combining novelty search with pressure to achieve.
Links:
- Paper
Bibtex:
```
"@inproceedings{lehman2011evolving,
title={Evolving a diversity of virtual creatures through novelty search and local competition},
author={Lehman, Joel and Stanley, Kenneth O},
booktitle={Proceedings of the 13th annual conference on Genetic and evolutionary computation},
pages={211--218},
year={2011},
organization={ACM} }"
```
Novelty-based multiobjectivization Robotics
Authors:
- Jean-Baptiste Mouret
Abstract:
Novelty search is a recent and promising approach to evolve neurocontrollers, especially to drive robots. The main idea is to maximize the novelty of behaviors instead of the efficiency. However, abandoning the efficiency objective(s) may be too radical in many contexts. In this paper, a Pareto-based multi-objective evolutionary algorithmis employed to reconcile novelty search with objective-based optimization by following a multiobjectivization process. Several multiobjectivizations based on behavioral novelty and on behavioral diversity are compared on a maze navigation task. Results show that the bi-objective variant “Novelty + Fitness” is better at fine-tuning behaviors than basic novelty search, while keeping a comparable number of iterations to converge.
Links:
- Paper
Bibtex:
```
"@incollection{mouret2011novelty,
title={Novelty-based multiobjectivization},
author={Mouret, Jean-Baptiste},
booktitle={New horizons in evolutionary robotics},
pages={139--154},
year={2011},
publisher={Springer} }"
```