https://roamresearch.com/#/app/PCG_and_AEC/page/va8MW7-sJ
CVT Map Elites
paper: https://arxiv.org/abs/1610.05729
code implementations:
Main idea
Uses centroidal voronoi tesselation to create a more efficient feature space that scales better to high-dimensional feature spaces. Also proposes a new evaluation method that allows for task specific diversity evaluation and comparison across feature spaces of different dimensionality.
Important features
- fixed feature space: the number of niches, or more specifically the number of centers of the voronoi cells (called sites), is decided up front (a hyperparameter) and does not change over time
- monte carlo method to approximate a CVT of the feature space:
- randomly initialize k centroids and generate K random points uniformly
- assign each point (elite) to the closest cell and update centroid center to be the mean of its points
- iteratively pick a cell and mutate current elite, evalute it and place it in the map and re-evaluate centers
- requires a distance function to assign elites to niches
- evaluation methodology: at each evaluation phase slightly modify the simulator (i.e. environment) without modifying the fitness function (reward)
- examples: in maze navigation change block certain paths, in hexapod locomotion remove a leg
- archive performance: use CDF or cumulative CDF to compare between different archives
Discussion points
-
has more precise control over the balance between diversity and performance due to higher selective pressure for performance when selecting from smaller archives
-
Euclidean norm was used, other fractional distance functions might be better (e.g. Minkowski of order p<1) since they provide a better contrast between farthest and nearest neighbor
-
a routine could be designed in a way that places more centers along certain dimensions and periodically recalculate the CVT throughout the evolutionary run (including allowing bounds to change)