PaperlayerView exact revision on arXiv

Source-linked AI summary

Quality and Diversity Optimization: A Unifying Modular Framework

Antoine Cully, Yiannis Demiris

arXiv:1708.09251v1cs.NEcs.AI

TL;DR

Quality-Diversity optimization addresses the need for collections of diverse, high-performing solutions rather than a single optimum. The paper unifies MAP-Elites and NSLC in a modular framework, introduces curiosity-based selection and new archive management, and reports that curiosity score outperformed existing QD algorithms across the presented experiments.

  • Problem

    Most optimization techniques output a single solution, while many applications require diverse behaviors and existing QD studies provide limited systematic comparisons.

  • Method

    The paper unifies QD algorithms through modular containers and selection operators, then proposes curiosity score selection and improved management for unstructured archives.

  • Results

    Curiosity score outperformed all existing QD algorithms on every experiment presented in the paper.

  • Takeaways & Limitations

    Collection-wise selection showed better performance than population-based selection across all experimental scenarios.

  • Takeaways & Limitations

    Container choice depends on the application, so the paper does not directly compare grid and unstructured container results.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Quality-Diversity optimization searches for collections of diverse, high-performing solutions rather than a single optimum. This approach addresses applications requiring behavioral variety and can exploit diversity during exploration.

  • I. INTRODUCTION: Quality-Diversity algorithms seek large collections of diverse, high-performing solutions rather than one effective solution.The collection aims to cover possible solution types and retain strong solutions for those types.
  • I. INTRODUCTION: A diverse collection provides alternatives when solutions learned in simulation fail to transfer to reality.This reality gap can make a large collection useful for quickly finding a working solution.
  • I. INTRODUCTION: Most optimization techniques for learned behaviors output only the solution maximizing the objective, limiting behavioral variety.Robots may need multiple directions, speeds, or target locations rather than one predefined behavior.
  • I. INTRODUCTION: Diversity can also provide stepping stones toward higher-performing solutions and accelerate adaptation from related designs.The paper illustrates this with modifying an existing car design to make it lighter.
  • I. INTRODUCTION: QD research includes Novelty Search with Local Competition and MAP-Elites, formalizing the challenge of generating diverse, high-performing collections.This problem is identified as the Quality-Diversity challenge.
  • I. INTRODUCTION: Local-optima search may miss useful solution types when the performance function is mono-modal.For walking robots, optimizing speed can omit slow behaviors needed for manoeuvrability.

B. Searching for Diverse Solutions

Novelty-based methods search for behavioral differences and combine novelty with local performance. Archive-based variants improve stored solutions, but archive quality and coverage can trade off.

  • B. Searching for Diverse Solutions: Novelty Search favors solutions differing from previously encountered solutions without considering their quality.A novelty archive stores encountered solutions, and novelty is computed from distances to k-nearest neighbors.
  • B. Searching for Diverse Solutions: NSLC combines novelty with local quality by comparing each solution only with nearby solutions in descriptor space.A multi-objective optimizer considers novelty and the number of nearby lower-performing solutions.
  • B. Searching for Diverse Solutions: 1,000 different species were generated in an early NSLC application evolving diverse virtual creatures.The solutions ranged from slow, massive quadrupeds to fast, lightweight unipedal hoppers.
  • B. Searching for Diverse Solutions: The novelty archive can cover solution types, but original NSLC does not replace an existing type with a better solution.Consequently, the archive can cover the descriptor space while failing to improve its stored quality over time.
  • B. Searching for Diverse Solutions: BR-Evolution progressively replaces archived solutions with better ones and has been used to build effective behavioral repertoires.Applications include collections of walking gaits supporting movement in every direction and at different speeds.
  • B. Searching for Diverse Solutions: BR-Evolution generated effective behavior collections at least 5 times faster and about 10 times more accurately than independent optimization.The paper relates this result to recycling solutions that traditional evolutionary algorithms would discard.
  • B. Searching for Diverse Solutions: Archive improvement can erode descriptor-space borders when better replacements are less novel than the solutions they replace.This can increase density in high-performance regions while reducing coverage near borders.

D. Evolving the Collection

MAP-Elites evolves a grid-based collection that preserves the best solution in each descriptor cell. The paper emphasizes coverage regularity while identifying discretization and selection limits.

  • D. Evolving the Collection: MAP-Elites treats the population as the collection and directly applies selection, mutation, and preservation to stored solutions.This distinguishes it from NSLC and BR-Evolution, whose populations and archives have different roles.
  • D. Evolving the Collection: MAP-Elites discretizes descriptor space into a grid and keeps the best evaluated solution in each cell.Empty cells receive solutions, while occupied cells retain the better of the existing and new solutions.
  • D. Evolving the Collection: MAP-Elites collections have supported adaptation to unforeseen robot damage by providing alternative walking gaits.The algorithm has also been used to generate turning gaits and other behavioral repertoires.
  • D. Evolving the Collection: Descriptor-space behaviors can serve as locomotion primitives that are combined by an arbitrator for maze navigation.EvoRBC evolves a neural network to select appropriate repertoire behaviors.
  • D. Evolving the Collection: MAP-Elites reduces dimensionality by selecting behaviors in descriptor spaces with fewer than a dozen dimensions.The cited applications reduce 36 to 6 dimensions and 8 to 2 dimensions.
  • D. Evolving the Collection: Discretization can limit MAP-Elites, while uniform random selection can dilute selection pressure in very large collections.Alternatives include biased selection and partitions with a predefined number of regions.
  • E. Quality-Diversity Optimization: QD performance is defined by descriptor-space coverage, coverage uniformity, and the performance of each solution type.The paper stresses uniformity because locomotion tasks require an even range of abilities.
  • E. Quality-Diversity Optimization: The paper identifies limited same-application comparisons and limited investigation of alternative collection-generation approaches.It positions a common framework and broader comparisons as responses to this gap.

III. A UNITED AND MODULAR FRAMEWORK FOR QD-OPTIMIZATION ALGORITHMS

The paper formulates QD algorithms as modular combinations of containers and selection operators. This formulation represents MAP-Elites and NSLC as configurations of one algorithm and supports systematic variants.

  • III. A UNITED AND MODULAR FRAMEWORK FOR QD-OPTIMIZATION ALGORITHMS: Existing comparisons of MAP-Elites and NSLC provide limited insight into the properties distinguishing their performance.The framework is introduced to expose those properties and encourage more informative comparisons.
  • III. A UNITED AND MODULAR FRAMEWORK FOR QD-OPTIMIZATION ALGORITHMS: A common framework expresses MAP-Elites and NSLC as the same algorithm with different operator combinations.It also permits variants using alternative selection and aggregation operators.
  • III. A UNITED AND MODULAR FRAMEWORK FOR QD-OPTIMIZATION ALGORITHMS: The framework has two main operators: a container that gathers and orders solutions, and a selection operator that chooses solutions for variation.Selection considers all solutions in the container, not only the current population.
  • III. A UNITED AND MODULAR FRAMEWORK FOR QD-OPTIMIZATION ALGORITHMS: Each iteration selects parents, creates and evaluates offspring, potentially adds offspring to the container, and updates scores.The cycle repeats until a stopping criterion is reached, after which the stored collection is output.

1) The Grid:

The framework distinguishes grid-based and unstructured archive containers, then proposes archive management that preserves spacing while allowing quality-based replacement. The new management achieves coverage and quality similar to grid-based containers.

  • The Grid: MAP-Elites discretizes descriptor space into an N-dimensional grid, with each cell representing one solution type.
  • The Grid: When a cell is empty, the individual is added; otherwise, only the highest-performing individual is retained.
  • The Grid: Grid structure enables novelty estimation from the density of filled cells in a local sub-grid rather than average distance to k-nearest neighbors.
  • The Archive: The novelty archive is unstructured: descriptor-space organization emerges from encountered solutions rather than predefined discretization.
  • The Archive: The prior archive approach can create uneven density and erode collection borders when better central solutions replace less novel boundary solutions.
  • The Archive: The proposed archive adds solutions whose nearest-neighbor distance exceeds threshold l, while closer candidates may replace neighbors when spacing and collection quality are preserved.
  • The Archive: Exclusive ϵ-dominance permits a bounded loss on one objective only when the new individual gains at least as much on the other objective.
  • The Archive: The new archive management produces collections with similar coverage and quality compared with the grid-based container.

3) Partial Conclusion:

Grid and archive containers trade predefined structure for descriptor-space flexibility, so the suitable choice depends on the application rather than performance alone. The framework considers both containers and selection operators as separable design choices.

  • 3) Partial Conclusion:: Grid containers simplify collection management but require descriptor-space discretization that may be inadequate or need revision.
  • 3) Partial Conclusion:: Archive containers require only a descriptor-space distance and can compare complex descriptors without detailed knowledge of dimensionality or limits.
  • 3) Partial Conclusion:: The appropriate container depends on the application, so the paper does not directly compare container results because such comparisons may be unfair or irrelevant.
  • 3) Partial Conclusion:: The paper focuses on single-container variants, although multiple containers could separate density accumulation for exploration from the collection returned to users.
  • Selection Operators: MAP-Elites selects randomly from the full collection, whereas NSLC selects current individuals that are novel and locally high-performing.
  • Selection Operators: Selection operators can be used with either container, while containers affect result type and selection operators affect collection quality.

1) No Selection:

The paper contrasts random, uniform, score-biased, novelty-based, and curiosity-based selection strategies. Curiosity prioritizes individuals whose offspring repeatedly enter the collection and shifts attention when those offspring stop producing additions.

  • 1) No Selection:: Randomly generating solutions provides a baseline but reduces QD optimization to random sampling of the search space.
  • 2) Uniform Random Selection:: Uniform selection from the collection is computationally simple, but its selection pressure decreases as the collection grows.
  • 3) Score Proportionate Selection:: Selection can be biased toward quality using roulette-wheel or tournament-based principles.
  • 3) Score Proportionate Selection:: Novelty scores can replace quality scores to favor solutions that differ from others in the collection.
  • 3) Score Proportionate Selection:: The Curiosity Score measures an individual's propensity to generate offspring that are added to the collection.
  • 3) Score Proportionate Selection:: In the implementation, curiosity increases when offspring are added and decreases when offspring fail to enter the archive; the paper uses reward 1 and penalty −0.5.
  • 3) Score Proportionate Selection:: Curiosity keeps selection focused on productive search regions until they stop producing interesting results, after which attention shifts elsewhere.

4) Population-based Selection:

Population-based selection maintains populations alongside the collection and can use classic or Pareto-based operators. The experiments compare container–selection combinations across three simulated scenarios, with broader testing for selected variants.

  • 4) Population-based Selection:: Population-based selection maintains a population alongside the collection and generates each new population from current offspring and their parents.
  • 4) Population-based Selection:: Classic tournament and score-proportionate selection can choose individuals for the next population.
  • 4) Population-based Selection:: The Pareto-based operator considers both novelty and local quality, measured by the number of neighboring solutions that outperform an individual.
  • 4) Population-based Selection:: Selection operators influence collection quality, whereas container choice influences whether descriptor-space organization is unstructured or discretized.
  • Experimental Comparisons: The experiments cover a redundant robotic-arm reaching task, six-legged walking in every direction, and multiple walking styles on a straight line.
  • Experimental Comparisons: Bold variants in Table I are tested on all three scenarios, while other combinations are tested only on the first.
  • Experimental Comparisons: The experiments use only direct encodings with small, fixed-size genomes; larger, growing, or indirect encodings remain for future work.

A. Quality Metrics

The paper evaluates QD collections using metrics that jointly capture coverage, solution quality, and distribution in descriptor space. The redundant-arm experiment tests these metrics while seeking solutions across reachable gripper positions.

  • Metrics: Four metrics characterize collections by measuring coverage, maximal quality, total quality, and total novelty.They assess both the range covered and the performance of contained solutions.
  • Metrics: Collection size indicates how much of the descriptor space is covered by its solutions.
  • Metrics: Maximal quality is the quality of the best contained solution and indicates whether a known global extremum was found.
  • Metrics: Total quality sums solution qualities, improving through additional individuals or improvements to existing individuals.
  • Metrics: Total novelty sums novelty scores to indicate whether solutions are distributed or concentrated, but is omitted for grid-based containers.
  • Experimental setup: The redundant eight-degree-of-freedom arm must discover reachable gripper positions while optimizing movement quality for each position.The experiment uses 20 replications for each tested QD variant.

2) Results:

In the redundant-arm experiment, collection-based selection generally outperformed population-based selection, while curiosity selection was strongest with archive-based containers. Container-specific novelty definitions and Pareto-optimal solutions explain important differences among variants.

  • Archive management: Archive-based collections resembled grid-based collections, indicating that the proposed archive management addressed previously described erosion issues.
  • Selection results: No population-based variant both covered all reachable space and maintained high-performing solutions.Fitness-based populations tended toward high-quality regions, novelty-based populations toward collection borders, and curiosity populations could not track all high-curiosity individuals.
  • Container effects: Grid-based novelty selection focused on collection borders because discretized novelty gives central individuals similarly low scores, unlike continuous archive-based novelty.
  • Container effects: The Pareto approach underperformed partly because a solution with all joint positions set to zero was Pareto-optimal, whereas NSLC’s accumulating density reduced such solutions’ novelty over time.
  • Selection results: Collection-based selection produced the best collections among the tested variants.
  • Selection results: Coverage, maximal quality, total quality, and total novelty were generally higher for collection-based than population-based selection, with all p-values < 7e −8 except stated comparisons.Grid novelty performed significantly worse than the other collection-based approaches, while some grid/archive population-fitness comparisons were not significantly different in maximal quality.
  • Selection results: Curiosity selection was significantly better than other archive-based selection approaches across metrics, with p-values < 2e −4 except total novelty, where p-values < 0.01.Differences among grid-based variants using entire-collection selection were negligible.
  • Selection results: NSLC outperformed Pareto-based selection but remained below variants using selection over entire collections.

C. The Robot Walking in Every Direction

The second experiment evaluates QD algorithms on a simulated six-legged robot that must walk in every direction and at different speeds. Curiosity variants produced the strongest collections, outperforming the other tested approaches on the reported quality metrics.

  • Experimental setup: The six-legged robot experiment seeks behaviors enabling walking in every direction and at different speeds.
  • Experimental setup: Solutions contain 36 controller parameters, are evaluated for three seconds, and are described by final X and Y position while quality measures orientation error.
  • Experimental setup: Only 10 variants and 10,000 generations were tested because simulator runs required 4–5 hours per variant.
  • Collection results: The “no selection” and “pop fitness” variants produced worse collections, while “random,” “curiosity,” and NSLC generated the best collections.The Pareto variant performed better here than in the previous experiment, consistent with the absence of a unique Pareto-optimal solution.
  • Collection results: Curiosity variants significantly outperformed the other algorithms on both grid and archive containers, with all p-values < 0.01 except archive-random total novelty at p-value = 0.05.The experiment also showed a clear metric gap and very low performance for naive no-selection variants.
  • Collection results: NSLC and random had no significant difference in final collection size or total quality, with p-values < 0.61, while curiosity remained better on both aspects with p-values < 0.0047.

D. The Robot Walking with Different Gaits

In the six-dimensional gait experiment, collection-wise selection generally improved coverage, total quality, and diversity, while population-based fitness selection found the highest-quality individual solutions. Curiosity-based selection accelerated total-quality progress, but Pareto-based variants performed poorly overall.

  • Experimental setup: The experiment trained a virtual robot to learn many fast straight-line gaits, using a six-dimensional leg-contact descriptor and 10 replications.Quality was measured by distance traveled after 3 seconds; the descriptor recorded each leg’s ground-contact proportion.
  • Results: Variants selecting from the whole collection significantly outperformed population-based variants in coverage, total quality, and diversity (all p-values < 2e−4).This pattern held across both archive-based and grid-based containers.
  • Results: Curiosity-based selection achieved the same total quality as random selection after 11,000 archive-based batches and 13,500 grid-based batches, versus 20,000 batches for random selection.Curiosity-based selection produced the best results with both container types.
  • Results: No-selection variants achieved about half the collection-wise coverage but had the worst total-quality and maximal-quality results.Their relatively good coverage did not translate into strong quality metrics.
  • Results: Population-based fitness selection had the worst coverage but found the best-quality solutions, significantly outperforming every other variant (p-values < 0.0017).The result indicates that collection-wise selection did not always find the global quality extremum.
  • Results: Pareto-based variants had neither good coverage nor maximal quality, whereas NSLC achieved good coverage but lower maximal quality than most variants.The six-dimensional behavioral space made the causes of Pareto-based underperformance difficult to visualize; the authors suggest premature border convergence or Pareto-optimal solutions as possibilities.

V. CONCLUSION AND DISCUSSION

The paper unifies QD algorithms in a modular framework, introduces new archive management and curiosity-based selection, and compares many QD variants experimentally. The experiments favor collection-based selection and show that archive density increases are important for NSLC effectiveness.

  • Contributions: The framework unifies MAP-Elites and NSLC as different configurations of one modular QD algorithm.It also supports new container types, selection operators, and selective pressures.
  • Contributions: The new archive management procedure addresses erosion in unstructured archives and achieves coverage comparable to grid containers.Earlier management procedures did not achieve this equivalence.
  • Contributions: The curiosity score is a QD-specific selective pressure that outperformed all existing QD algorithms across the paper’s experiments.The conclusion presents this as a consistently promising result across the evaluated scenarios.
  • Experimental conclusions: Selection operators that consider the collection rather than a population showed better performance across all experimental scenarios.The authors hypothesize that the collection’s inherent solution diversity helps avoid local extrema and find promising stepping stones.
  • Experimental conclusions: NSLC requires solution density to increase in diverse archive regions to achieve its full effectiveness.The paper identifies novelty-score thresholds and probabilistic archive addition as mechanisms that can increase density.
  • Future directions: The framework is intended to encourage research on new QD containers, selection operators, and selective pressures.The authors expect such variants to clarify which factors produce the best solution collections.
Loading 1708.09251v1…