Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909430316007424 |
|---|---|
| author | Dang, Duc-Cuong Neumann, Aneta Neumann, Frank Opris, Andre Sudholt, Dirk |
| author_facet | Dang, Duc-Cuong Neumann, Aneta Neumann, Frank Opris, Andre Sudholt, Dirk |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_11446 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem Dang, Duc-Cuong Neumann, Aneta Neumann, Frank Opris, Andre Sudholt, Dirk Artificial Intelligence Neural and Evolutionary Computing 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. |
| title | Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem |
| topic | Artificial Intelligence Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2412.11446 |