Illuminating search spaces by mapping elites

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.

Early draft

References in corpus (1)

• Community structure in directed networks

Cited by in corpus (108)

• Robots that can adapt like animals
• Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning
• Go-Explore: a New Approach for Hard-Exploration Problems
• Intrinsically Motivated Goal Exploration Processes with Automatic Curriculum Learning
• Procedural Content Generation through Quality Diversity
• Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions
• Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space
• Controversial stimuli: pitting neural networks against each other as models of human recognition
• Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents
• Reset-free Trial-and-Error Learning for Robot Damage Recovery
• Discovering the Elite Hypervolume by Leveraging Interspecies Correlation
• AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence
• Effective Diversity in Population Based Reinforcement Learning
• Interactive Constrained MAP-Elites: Analysis and Evaluation of the Expressiveness of the Feature Dimensions
• Enhanced POET: Open-Ended Reinforcement Learning through Unbounded Invention of Learning Challenges and their Solutions
• Diversity Policy Gradient for Sample Efficient Quality-Diversity Optimization
• Fast and stable MAP-Elites in noisy domains using deep grids
• Hierarchical Behavioral Repertoires with Unsupervised Descriptors
• Adaptive Prior Selection for Repertoire-based Online Adaptation in Robotics
• From exploration to control: learning object manipulation skills through novelty search and local adaptation
• Multi-Objective Quality Diversity Optimization
• Differentiable Quality Diversity
• Multi-Emitter MAP-Elites: Improving quality, diversity and convergence speed with heterogeneous sets of emitters
• Policy Manifold Search: Exploring the Manifold Hypothesis for Diversity-based Neuroevolution
• CPPN2GAN: Combining Compositional Pattern Producing Networks and GANs for Large-scale Pattern Generation
• The Emergence of Canalization and Evolvability in an Open-Ended, Interactive Evolutionary System
• Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding
• Multi-Robot Coordination and Layout Design for Automated Warehousing
• Evolution of a Functionally Diverse Swarm via a Novel Decentralised Quality-Diversity Algorithm
• Exploring the Evolution of GANs through Quality Diversity
• Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms
• Innate Motivation for Robot Swarms by Minimizing Surprise: From Simple Simulations to Real-World Experiments
• Procedural Content Generation using Neuroevolution and Novelty Search for Diverse Video Game Levels
• Explore, Discover and Learn: Unsupervised Discovery of State-Covering Skills
• Open-Ended Evolution for Minecraft Building Generation
• Comparing and Combining Lexicase Selection and Novelty Search
• Dynamics-Aware Quality-Diversity for Efficient Learning of Skill Repertoires
• Monte Carlo Elites: Quality-Diversity Selection as a Multi-Armed Bandit Problem
• Hierarchical Quality-Diversity for Online Damage Recovery
• Evolving the Behavior of Machines: From Micro to Macroevolution
• Few-shot Quality-Diversity Optimization
• COIL: Constrained Optimization in Learned Latent Space: Learning Representations for Valid Solutions
• Workspace Optimization Techniques to Improve Prediction of Human Motion During Human-Robot Collaboration
• Diverse Auto-Curriculum is Critical for Successful Real-World Multiagent Learning Systems
• Rapidly adapting robot swarms with Swarm Map-based Bayesian Optimisation
• Automatic Calibration of Artificial Neural Networks for Zebrafish Collective Behaviours using a Quality Diversity Algorithm
• Preference-Learning Emitters for Mixed-Initiative Quality-Diversity Algorithms
• Quality-Diversity Meta-Evolution: customising behaviour spaces to a meta-objective
• Hybrid Encoding For Generating Large Scale Game Level Patterns With Local Variations
• Surrogate Infeasible Fitness Acquirement FI-2Pop for Procedural Content Generation
• Concept Identification for Complex Engineering Datasets
• A Unified Substrate for Body-Brain Co-evolution
• Active Divergence with Generative Deep Learning -- A Survey and Taxonomy
• Regenerating Soft Robots through Neural Cellular Automata
• Using Centroidal Voronoi Tessellations to Scale Up the Multi-dimensional Archive of Phenotypic Elites Algorithm
• Searching for test data with feature diversity
• Parametric-Task MAP-Elites
• BOP-Elites, a Bayesian Optimisation algorithm for Quality-Diversity search
• Safety-Aware Robot Damage Recovery Using Constrained Bayesian Optimization and Simulated Priors
• Language-Conditioned Goal Generation: a New Approach to Language Grounding for RL
• On the Importance of Environments in Human-Robot Coordination
• Optimization of a Hydrodynamic Computational Reservoir through Evolution
• Adaptive and Resilient Soft Tensegrity Robots
• Relevance-guided Unsupervised Discovery of Abilities with Quality-Diversity Algorithms
• Self-Organizing Intelligent Matter: A blueprint for an AI generating algorithm
• Fiber: A Platform for Efficient Development and Distributed Training for Reinforcement Learning and Population-Based Methods
• Multi-Task Multi-Behavior MAP-Elites
• Generating and Adapting to Diverse Ad-Hoc Cooperation Agents in Hanabi
• AutoAlpha: an Efficient Hierarchical Evolutionary Algorithm for Mining Alpha Factors in Quantitative Investment
• Runtime Analysis of Quality Diversity Algorithms
• Evaluating the Rainbow DQN Agent in Hanabi with Unseen Partners
• Towards semi-episodic learning for robot damage recovery
• Central pattern generators evolved for real-time adaptation to rhythmic stimuli
• FormulaZero: Distributionally Robust Online Adaptation via Offline Population Synthesis
• Harnessing Distribution Ratio Estimators for Learning Agents with Quality and Diversity
• Multi-objective Analysis of MAP-Elites Performance
• Novelty Producing Synaptic Plasticity
• Adaptable Agent Populations via a Generative Model of Policies
• From Language Games to Drawing Games
• Prototype Discovery using Quality-Diversity
• Competitiveness of MAP-Elites against Proximal Policy Optimization on locomotion tasks in deterministic simulations
• Learning Diverse Representations for Fast Adaptation to Distribution Shift
• Open-ended search for environments and adapted agents using MAP-Elites
• MAP-Elites with Transverse Assessment for Multimodal Problems in Creative Domains
• Untangling the Effects of Down-Sampling and Selection in Genetic Programming
• Regularized Evolutionary Population-Based Training
• Comparing reliability of grid-based Quality-Diversity algorithms using artificial landscapes
• Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value
• Evolutionary Self-Replication as a Mechanism for Producing Artificial Intelligence
• Many-objective Optimization via Voting for Elites
• Quality-Diversity Optimisation on a Physical Robot Through Dynamics-Aware and Reset-Free Learning
• Controllability, Multiplexing, and Transfer Learning in Networks using Evolutionary Learning
• EvoRobogami: Co-designing with Humans in Evolutionary Robotics Experiments
• Rinascimento: searching the behaviour space of Splendor
• Self-Referential Quality Diversity Through Differential Map-Elites
• Conceptual Expansion Neural Architecture Search (CENAS)
• Meta-Reinforcement Learning for Adaptive Motor Control in Changing Robot Dynamics and Environments
• Exploration and Exploitation in Symbolic Regression using Quality-Diversity and Evolutionary Strategies Algorithms
• Tester Interactivity makes a Difference in Search-Based Software Testing: A Controlled Experiment
• Ridge Rider: Finding Diverse Solutions by Following Eigenvectors of the Hessian
• Policy Manifold Search for Improving Diversity-based Neuroevolution
• Evolution of linkages for prototyping of linkage based robots
• Hierarchical Surrogate Modeling for Illumination Algorithms
• Mapping structural diversity in networks sharing a given degree distribution and global clustering: Adaptive resolution grid search evolution with Diophantine equation-based mutations
• Learning in Sparse Rewards settings through Quality-Diversity algorithms
• Discovering Evolutionary Stepping Stones through Behavior Domination
• Diversity-based Design Assist for Large Legged Robots
• Say "Sul Sul!" to SimSim, A Sims-Inspired Platform for Sandbox Game AI