Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem

In recent years, computing diverse sets of high quality solutions for combinatorial optimisation problems has gained significant attention in the area of artificial intelligence from both theoretical (Baste et al., 2022, 2019; Fomin et al., 2024; Hanaka et al., 2023) and experimental (Vonásek and Saska, 2018; Ingmar et al., 2020) perspectives. Prominent examples where diverse sets of high quality solutions are sought come from the area of path planning (Hanaka et al., 2021; Gao et al., 2022). Particularly, quality diversity (QD) algorithms have shown to produce excellent results for challenging problems in the areas such as robotics (Miao et al., 2022; Shen et al., 2020), games (Cully and Demiris, 2018) and combinatorial optimisation (Nikfarjam et al., 2024a). This work contributes to the theoretical understanding of QD algorithms. Such algorithms compute several solutions that occupy different areas of a so-called behavioural space. Approaches that use a multidimensional archive of phenotypic elites, called Map-Elites (Mouret and Clune, 2015), are among the most commonly used QD algorithms.