Empirical-Measure Search States for Quality-Diversity Optimization

Quality-Diversity (QD) optimization seeks collections of solutions that are both high-performing and behaviorally diverse. Many QD methods use an archive both to retain solutions and to guide subsequent search through archive improvement. Useful search, however, does not always look like immediate improvement. When evaluated candidates fail to improve the archive, they may not be retained, so search may stop pursuing those directions, leaving valuable regions undiscovered. We therefore need to separate search-state representation from result retention, allowing past search effort to continue guiding where to search even without immediate archive improvement. We introduce Quality-Diversity Empirical Measure (QDEM), which separates search-state representation from result retention, target-relative valuation, and search control. Under a fixed reference projection, QDEM recursively maintains a fixed-dimensional state of cumulative target support from all valid evaluations, guiding search toward under-supported targets. Our experiments demonstrate that QDEM outperforms state-of-the-art methods on a broad range of standard QD benchmarks and high-dimensional visual reference tasks, while remaining competitive where quality improvement already guides search effectively. In robot morphology evolution, QDEM allows lower-fitness intermediate designs rejected by the archive to remain part of the search process, enabling controller adaptation on the new morphology to recover and exceed pre-change performance.