Deep-Grid MAP-Elites: An algorithm to produce collections of diverse and high performing solutions in noisy domains

Over the past few decades, research teams worldwide have developed a wide variety of computational tools and technological solutions. Quality-diversity (QD) optimization algorithms are an approach that can generate large collections of diverse and highly performing solutions to computational problems rather than identifying a single high-quality solution, as a more conventional optimization algorithm would.

These fairly new optimization approaches have significant advantages over traditional optimization tools, which make them desirable for a wide range of applications. For instance, they have so far proved useful for product design, robotic control and video game content generation, as well as to tackle routing problems.

Unfortunately, like most other optimization algorithms, QD approaches tend to be highly sensitive to uncertainties that are often present in real-world situations. While past studies introduced optimization algorithms that can still perform well on tasks that entail a high level of uncertainty, only a few of these were based on QD techniques.

With this in mind, two researchers at Imperial College London recently developed a new QD algorithm that can generate a collection of diverse and high-performing solutions, even in the presence of uncertainty. Their algorithm, presented in a paper published on Artificial Life Conference Proceedings, extends MAP-Elites, an optimization technique that produces a collection of solutions to a given problem, allowing it to rapidly approximate the true performance and diversity of the solutions without requiring a large number of evaluations.

"When the evaluation of a solution's quality and diversity is noisy, the overall optimization task becomes significantly more challenging," Antoine Cully, one of the researchers who carried out the study, told TechXplore. "For instance, if a solution is evaluated as high-performing because the noise has worked in its favour, then this solution will be maintained in the resulting collection of solutions, while more legitimate solutions should have been found instead. The new algorithm we developed, Deep-Grid MAP-Elites, extends the well-known MAP-Elites algorithm to address this challenge, while being significantly faster than alternative approaches."

A straightforward way of overcoming the impact of noise on the performance of QD algorithms would be to evaluate every possible solution several times in order to collect a number of meaningful statistics, such as the average performance of each solution. This approach, however, is quite time-consuming, thus it can significantly slow down a QD algorithm's learning process.

Cully and Manon Flageat, lead author of the paper, proposed an alternative method that approximates the 'true' performance of a solution by storing several solution instances of the same type together as a 'collection' or 'sub-population'. This allows their algorithm to implicitly approximate statistics about previously proposed solutions that would otherwise need to be calculated.

"Deep-Grid MAP-Elites uses specific mechanisms to add and remove solutions from the collections that allow the sub-population to progressively converge to the 'true' performance, without the need of multi-evaluations," Cully said. "This method proved to be significantly faster than all the approaches it was compared to."

So far, the researchers tested their QD optimization algorithm on a number of tasks characterized by varying degrees of uncertainty, including a standard optimization problem, a task that entailed controlling a redundant arm and one that involved teaching a simulated hexapod to walk in all directions. Remarkably, their algorithm outperformed a number of previously developed QD optimization methods, as it was more resilient to noise and sample efficient.

"There are several applications in which the evaluation is noisy," Cully said. "For instance, the performance of a robot is likely to change depending on its environment or its initial state. Similarly, the quality of automatically designed drugs or products is also usually subject to external factors, making these domains noisy as well. Deep-Grid MAP-Elites is a new tool that allows the application of QD optimization in different domains, without the prohibitive cost of performing multiple evaluations, which makes many other existing methods impracticable."

The recent study carried out by this team of researchers could eventually enable the use of QD for evaluating solutions to a wider range of real-world problems. For example, the Deep-Grid MAP-Elites algorithm could be used to estimate the performance of sophisticated computational tools or to conduct initial screenings of pharmaceutical drugs.

"We currently have two main directions for future research in mind," Cully said. "First, we will explore how Deep-Grid MAP-Elites can be used to solve complex noisy domains such as closed-loop control in robotics. Second, we will study the new exploration dynamics created by Deep-Grid MAP-Elites as it appears to be relatively different from existing quality-diversity approaches and we think there are certain aspects that can be leveraged to improve Deep-Grid MAP-Elites further."