PaperlayerView exact revision on arXiv

Source-linked AI summary

Using Centroidal Voronoi Tessellations to Scale Up the Multi-dimensional Archive of Phenotypic Elites Algorithm

Vassilis Vassiliades, Konstantinos Chatzilygeroudis, Jean-Baptiste Mouret

arXiv:1610.05729v2cs.NE

TL;DR

MAP-Elites struggles with high-dimensional feature spaces because grid niches grow exponentially with descriptor dimensionality. The paper introduces CVT-MAP-Elites, which uses a centroidal Voronoi tessellation to maintain a fixed number of regions, and reports stronger high-dimensional performance in maze and hexapod tasks. Its centroids must represent feasible behaviors when constructing the tessellation.

  • Problem

    MAP-Elites’ grid causes exponentially increasing niche counts as feature dimensionality grows, limiting its use in high-dimensional spaces.

  • Method

    CVT-MAP-Elites partitions the feature space into a pre-specified number of centroidal Voronoi regions and assigns each individual to its closest region.

  • Results

    CVT-MAP-Elites remains effective as descriptor dimensionality increases, including application where MAP-Elites is prohibitive and faster hexapod gaits across evaluation settings.

  • Takeaways & Limitations

    A fixed number of well-spread regions enables MAP-Elites-style archives in feature spaces whose dimensionality makes grid-based MAP-Elites impractical.

  • Takeaways & Limitations

    CVT construction requires samples whose centroids represent potential behaviors that make sense in the behavior space.

Abstract

from arXiv · show

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.

I. INTRODUCTION

MAP-Elites searches for many diverse, high-performing solutions by maintaining elites across behavior-space niches, but its grid representation scales poorly with descriptor dimensionality. The paper introduces CVT-MAP-Elites to maintain a fixed number of well-spread niches in arbitrary-dimensional spaces and evaluates it in maze navigation and hexapod locomotion.

  • Evolutionary robotics increasingly uses algorithms that search for many diverse, high-performing individuals rather than a single optimum.
  • MAP-Elites maintains locally optimal solutions across many behavior-space niches, balancing diversity with task performance.
  • MAP-Elites discretizes each behavior-space dimension into ranges and retains the fittest solution in each resulting bin.
  • The number of grid niches grows exponentially with feature dimensions, reducing selective pressure and limiting MAP-Elites to typically 2 to 6 dimensions.
  • CVT-MAP-Elites addresses this limitation by spreading a desired number of niches across arbitrary-dimensional feature spaces and is evaluated in maze and hexapod tasks.

II. CENTROIDAL VORONOI TESSELLATION MAP-ELITES

CVT-MAP-Elites replaces MAP-Elites’ axis-aligned grid with k Voronoi regions whose centroids are computed before evolution. Individuals are assigned to their nearest region, and each region stores only its best-performing solution.

  • A CVT partitions bounded space into regions defined by distance to k sites that are also the regions’ centroids.
  • The algorithm approximates the CVT by sampling feature-space points, assigning each to its closest centroid, and updating centroids iteratively.
  • CVT-MAP-Elites first constructs k centroids and creates an archive with capacity k, making archive size independent of feature-space dimensionality.
  • During initialization and evolution, evaluated individuals are inserted into the region corresponding to their feature descriptor, replacing the stored individual only when the newcomer performs better.
  • Unlike MAP-Elites’ O(1) bin indexing, CVT-MAP-Elites assigns descriptors using a distance function to the centroids.

III. EVALUATION

The evaluation tests CVT-MAP-Elites in maze navigation and hexapod locomotion while using archive-quality measures designed for generalization and task-specific diversity. Existing MAP-Elites-grid metrics are unsuitable for comparing different descriptors and dimensionalities.

  • The experiments assess scalability in maze navigation and hexapod locomotion, two task classes used to test diverse, high-performing archives.
  • Coverage and quality diversity score depend on a particular behavior-space discretization, preventing direct comparison across evolutionary algorithms and descriptor dimensionalities.
  • Archive quality must also reflect task-specific diversity, such as distinct maze trajectories or damage-robust hexapod behaviors.
  • The proposed evaluation treats evolution as training and tests archive generalization in simulator settings that were not experienced during evolution.

A. Expected best performance of an EA-descriptor pair in an evaluation scenario e

Expected best performance measures how well the best solution in each archive performs in an evaluation scenario, using the median across evolutionary runs.

  • Expected best performance is the median, across evolutionary runs, of each archive’s best fitness in evaluation scenario e.

B. Expected quality of an EA-descriptor pair

The expected quality metric estimates how many archive solutions meet a task-specific fitness threshold, and its CDF or CCDF summarizes performance across thresholds.

  • The expected best performance metric is the probability that an archive solution meets a specified fitness threshold.It uses X ≤ x for minimization and X > x for maximization.
  • CDFs summarize threshold performance for minimization, whereas CCDFs summarize it for maximization.The functions generalize threshold queries across a range of possible fitness values.
  • The functions are calculated as ratios of archive solutions meeting each threshold, using medians across evolutionary runs and evaluation scenarios.This aggregation reduces dependence on a particular archive and evaluation environment.
  • Querying a CDF or CCDF at a good fitness value estimates the expected percentage of good solutions returned by an algorithm.For hexapod locomotion, a CCDF query at 0.3 m/s estimates the percentage reaching at least that walking speed.

IV. MAZE NAVIGATION EXPERIMENTS

The maze experiment evolves neural-network controllers for a robot that must reach a central goal, then tests the resulting archives in environments with selectively blocked paths.

  • The simulated robot starts at the bottom of a 1000 × 1000 arena and must reach the goal at its center.Its neural-network controller is evolved, and fitness is the smallest distance to the goal during 3000 simulation steps.
  • Fitness is measured as the smallest Euclidean distance between the robot and the goal over its lifetime.Lower distances indicate better maze-navigation performance.
  • The archives are evaluated in 16 environments formed by selectively blocking openings in the open maze.Each environment effectively permits one realizable trajectory to the goal.
  • The robot uses laser range finders and goal-oriented compass sensors, while its neural network sets the speeds of two motors.The three range finders report normalized obstacle distances, and four pie-slice sensors indicate the goal direction.

3) Behavioral Descriptors:

The maze study compares descriptors from 2D through 1000D, showing that CVT-MAP-Elites maintains performance and archive coverage as descriptor dimensionality increases.

  • The six maze descriptors sample trajectory points at dimensionalities of 2D, 10D, 20D, 50D, 250D, and 1000D.MAP-Elites is evaluated only through 20D because higher-dimensional descriptors exceed available RAM.
  • CVT-MAP-Elites maintains near-constant expected best performance across all evaluation scenarios, including descriptors up to 1000D.Median distance is below 2 units in most scenarios and below 10 units in the two hardest environments.
  • 0.72 to 0.005: MAP-Elites’ median filled-niche percentage falls from 0.72 (2D) to 0.005 (20D), while CVT-MAP-Elites remains at 0.36 (1000D).CVT-MAP-Elites values are 0.73 (2D), 0.46 (10D), 0.40 (20D), 0.38 (50D), 0.36 (250D), and 0.36 (1000D).
  • 0.34 to 0.45: CVT-MAP-Elites’ median solution spread increases from 0.34 (2D) to 0.45 (1000D).The corresponding values are 0.41 (10D), 0.40 (20D), 0.43 (50D), and 0.44 (250D).
  • CVT-MAP-Elites has slightly higher expected archive quality overall while performing as well as MAP-Elites and scaling to high dimensions.For distance at most 20 units, representative values are 0.02 vs 0.02 (2D), 0.01 vs 0.02 (10D), and 0.02 vs 0.03 (20D).

A. Experimental Setup

The experimental setup evaluates CVT-MAP-Elites on hexapod locomotion and maze navigation using multiple behavioral descriptors, fixed evolutionary budgets, and archive-based performance measures.

  • 1) Simulation and Fitness Function: The hexapod controller has 36 parameters and maximizes forward distance covered in 5 seconds.Each leg contributes six parameters describing amplitude, phase shift, and duty cycle for two joints.
  • 1) Simulation and Fitness Function: Six damage cases remove a different hexapod leg during evaluation, while archives are generated with an intact-robot model.This separates archive generation from damaged-robot evaluation.
  • 2) Evaluation phase: Figure 4 reports distance-to-goal performance across the open maze and 16 blocked-path evaluation environments.Box plots summarize 30 solutions using medians, interquartile ranges, whiskers, and outliers.
  • 2) Evaluation phase: Figure 5 measures filled-niche percentage, normalized nearest-neighbor spread, and the median CDF across evaluation scenarios.These metrics jointly describe archive occupancy, behavioral dispersion, and performance distributions.
  • 3) Behavioral Descriptors: CVT-MAP-Elites uses k = 10k niches, while MAP-Elites’ discretizations produce rapidly expanding bin counts for higher-dimensional descriptors.For 36D controller parameters, even two discretizations per dimension require more than 256 GB of RAM for MAP-Elites.
  • 3) Behavioral Descriptors: The duty-factor descriptor records each leg’s ground-contact proportion over simulation time, with MAP-Elites using 15625 bins.Contact is sampled every 15 ms and averaged over the simulation’s time steps.

B. Results

Across hexapod experiments, increasing descriptor dimensionality substantially degraded MAP-Elites performance, while CVT-MAP-Elites largely maintained performance in both evolutionary and evaluation settings.

  • Across 20 runs and 75k generations, CVT-MAP-Elites maintained approximately the same median best-individual performance with 12D, 24D, and 36D descriptors.Its 6D performance was slightly better, while MAP-Elites performance deteriorated significantly as descriptor dimensionality increased.
  • Undamaged median gaits were 0.21 vs 0.45 m/s at 12D and 0.16 vs 0.44 m/s at 24D for MAP-Elites versus CVT-MAP-Elites.At 6D, both algorithms achieved 0.47 m/s; the 36D CVT-MAP-Elites value was 0.44 m/s.
  • Damaged median gaits were 0.18 vs 0.31 m/s at 12D and 0.15 vs 0.32 m/s at 24D for MAP-Elites versus CVT-MAP-Elites.At 6D, the values were 0.34 vs 0.33 m/s, and the 36D CVT-MAP-Elites value was 0.32 m/s.
  • MAP-Elites-6D had the highest probability of finding better solutions, while CVT-MAP-Elites performance remained more stable as dimensionality increased.The lower CVT-MAP-Elites-6D performance may reflect its 10k niches versus 1.5 times more niches for MAP-Elites-6D.
  • For damaged cases at 0.2 m/s, MAP-Elites returned qualifying solutions at 21.3% for 6D but 0% for 12D and 24D, whereas CVT-MAP-Elites returned 6.5%, 10.8%, and 10.5% at 12D, 24D, and 36D.Differences between the algorithms at 12D and 24D were highly significant, with p < 10^-44 using a Mann-Whitney U test.

VI. DISCUSSION AND CONCLUSION

CVT-MAP-Elites extends MAP-Elites to higher-dimensional spaces with a fixed number of well-spread niches, but its use depends on realistic behavior-space sampling and known or constructible bounds.

  • VI. DISCUSSION AND CONCLUSION: CVT-MAP-Elites found hexapod gaits averaging 1.7 to 2.1 times faster in evaluation settings as feature-space dimensionality increased.The method was also applied where MAP-Elites becomes prohibitive, including 1000-dimensional maze experiments.
  • VI. DISCUSSION AND CONCLUSION: Using fewer niches with the same parent-selection method increases selective pressure for performance because each elite represents a larger region.An archive of 1000 elites therefore applies more performance pressure than an archive of 1 million elites under the same selection scheme.
  • VI. DISCUSSION AND CONCLUSION: The experiments used Euclidean distances, although fractional norms might better contrast nearest and farthest neighbors in high-dimensional spaces.Additional experiments found no qualitative or generalization-performance difference between Euclidean and fractional norms.
  • VI. DISCUSSION AND CONCLUSION: CVT construction runs once before evolution, so CVT-MAP-Elites requires no major evolutionary-algorithm modifications and has construction complexity O(ndki).The iteration count can be fixed because highly precise clustering was unnecessary with thousands of clusters.
  • VI. DISCUSSION AND CONCLUSION: Scaling to 1000 dimensions required sampling realistic trajectories so CVT centroids represented behaviors the robot could actually follow.Naively sampling trajectory elements independently would create unrealistic centroids because of the robot's maximum-speed constraint.
  • VI. DISCUSSION AND CONCLUSION: CVT-MAP-Elites may be inappropriate when behavior-space bounds are unknown or possible descriptors are heavily constrained.Realistic descriptor sampling can be difficult, especially for trajectories of dynamical systems in high-dimensional state spaces.
  • VI. DISCUSSION AND CONCLUSION: The limitation may be mitigated by defining bounds from evolved solutions and periodically recalculating the CVT when those bounds change.The bounding volume and niche density can also be varied during this process.

APPENDIX A ADDITIONAL EXPERIMENTS

Additional experiments examine how niche count, descriptor dimensionality, and distance metric affect CVT-MAP-Elites in maze navigation and hexapod locomotion.

  • Maze navigation: Maze performance improves as the number of niches k increases, while k = 50 yields more good solutions than k = 500 or k = 5000.Good solutions have distance to the goal less than 100.
  • Maze navigation: Higher-dimensional maze descriptors, 20D and 250D, produce higher expected archive quality than the 2D descriptor.The 2D descriptor cannot capture multiple trajectories reaching the same 2D location.
  • Maze navigation: There is no significant maze-navigation performance difference between the Euclidean and fractional distance metrics.The comparison uses Minkowski orders p = 2 and p = 0.5.
  • Hexapod locomotion: For undamaged hexapods, expected best performance is unchanged for k ∈ {10, 100, 1000, 10000} but significantly decreases at k = 100000.For damaged cases, k = 100000 has the worst expected performance, while k ∈ {10, 100, 1000, 10000} shows no significant difference.
  • Hexapod locomotion: In damaged hexapod cases, k = 10000 performs best and k = 10 performs worst.The undamaged and damaged settings therefore favor different niche-count choices for the reported outcomes.
  • Hexapod locomotion: The fractional norm slightly improves undamaged-robot performance, but neither norm differs significantly in damaged cases.This pattern holds for expected best performance and expected solution quality in the damaged cases.

APPENDIX B SOURCE CODE

The appendix identifies the experiment source code and summarizes the parameters used for CVT construction, niche counts, descriptors, and evolutionary runs.

  • Source code: The experiment source code is available in the paper’s cited GitHub repository.The appendix gives the repository path directly.
  • Evolutionary parameters: The appendix reports evolutionary runs with 2k initial solutions for one task and 10k for the other, followed by 200 offspring per generation.The table reports 990 generations for evaluation and 75k generations for the larger run.
  • CVT parameters: CVT construction uses 5k niches for maze experiments and 10k niches for hexapod experiments.The parameter table also lists 1000k and 100k CVT samples, respectively.
  • CVT parameters: The experiments vary maze behavioral dimensions from 2D to 1000D and hexapod dimensions from 6D to 36D.The listed niche counts are k = 5k for maze and k = 10k for hexapod.
Loading 1610.05729v2…