A Quality Diversity Approach to Automatically Generate Multi-Agent Path Finding Benchmark Maps (Extended Abstract)

Abstract

Multi-Agent Path Finding (MAPF) is a complex problem aiming at searching for paths where teams of agents navigate to their goal locations without collisions. Recent advancements in MAPF have highlighted the necessity for robust benchmarks to evaluate their performance. Previously, the benchmarks used to evaluate MAPF algorithms are predominantly fixed, human-designed maps, which cannot evaluate the behavior of the algorithms comprehensively, leading to potential failures in diverse map scenarios. Meanwhile, quality diversity (QD) algorithm is used to generate maps of high solution quality for MAPF. We employ this technique to automatically generate diverse benchmark maps and explore the detailed behavior of MAPF algorithms in the generated maps. As a preliminary result, we concentrate on EECBS, a popular sub-optimal MAPF algorithm, and observe several findings regarding the runtime and solution quality of EECBS, and difficulty of the generated maps.