Uncertain quality-diversity: accounting for real-world uncertainties in diversity search
File(s)
Author(s)
Flageat, Manon
Type
Thesis
Abstract
Within the broad field of Evolutionary Computation, Quality-Diversity (QD) has proven to be a powerful approach to uncovering collections of diverse and high-performing solutions to an optimisation problem. To do so, for any solution, QD relies on quantifying both its performance at the task, known as its fitness, but also its way of solving the task, known as its feature descriptor. QD algorithms have been successfully applied in various domains, ranging from robotics control to procedural content generation. However, these applications have been largely confined to deterministic settings, where each solution is consistently assigned fixed deterministic fitness and feature descriptor values. While convenient, such setups are, in fact, infrequent in real-world optimisation problems, where stochasticity, randomness and noise are omnipresent and induce various uncertainties on fitness and feature descriptors. As a result, extending QD algorithms to uncertain domains could significantly expand their applicability, opening the door to a wide range of new applications across various real-world scenarios. Yet, to the best of our knowledge, this challenge remains largely unexplored. This Manuscript seeks to address this gap under the term Uncertain Quality-Diversity (UQD). We first illustrate the issue faced by standard QD approaches in UQD setups. We then decompose them into three core problems: Performance Estimation, Reproducibility Maximisation, and Fitness-Reproducibility Trade-Off. For each of these problems, we develop a toolbox of tailored mechanisms to address them. We further consolidate these approaches into a general framework designed to improve the accessibility of UQD approaches. Then, we demonstrate the effectiveness of this framework and of the insights it encompasses through two practical applications. Overall, this Manuscript aims to advance the understanding of QD in uncertain tasks and provide practical tools for enhancing the performance and applicability of QD algorithms in real-world settings.
Version
Open Access
Date Issued
2025-03-23
Date Awarded
01/11/2025
License URL
Advisor
Cully, Antoine
Publisher Department
Department of Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)