Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem
This provides theoretical foundations for QD algorithms, which are incremental but address a gap in understanding for robotics, games, and combinatorial optimization.
The paper tackles the lack of theoretical understanding of quality diversity (QD) algorithms by analyzing their behavior on the all-pairs-shortest-paths (APSP) problem, showing that Map-Elites QD algorithms can compute a shortest path for each pair of nodes efficiently in parallel and that specific parent selection techniques for crossover lead to significant speed ups compared to standard approaches.
Quality diversity (QD) algorithms have shown to provide sets of high quality solutions for challenging problems in robotics, games, and combinatorial optimisation. So far, theoretical foundational explaining their good behaviour in practice lack far behind their practical success. We contribute to the theoretical understanding of these algorithms and study the behaviour of QD algorithms for a classical planning problem seeking several solutions. We study the all-pairs-shortest-paths (APSP) problem which gives a natural formulation of the behavioural space based on all pairs of nodes of the given input graph that can be used by Map-Elites QD algorithms. Our results show that Map-Elites QD algorithms are able to compute a shortest path for each pair of nodes efficiently in parallel. Furthermore, we examine parent selection techniques for crossover that exhibit significant speed ups compared to the standard QD approach.