Towards generating discriminating instances for multi-agent pathfinding: a case study with shelf-based warehouse scenarios

Benchmarking is central to the evaluation of multi-agent pathfinding (MAPF) solvers, yet benchmark instances are often manually designed and may not systematically expose differences between solving paradigms. Hence, gaining insight into the complementary strengths of different MAPF solving approaches is challenging. We present a preliminary study that explores the use of AutoIG, a constraint-based automated instance generation tool, as a means of generating MAPF benchmark instances that exhibit performance differences between solvers. We focus on a simple shelf based warehouse scenario and consider two representative MAPF solvers from the search-based and reduction-based paradigms, respectively. Our results indicate that, even in this restricted setting, AutoIG can identify instances with noticeable differences in solver performance. We also observe that the reduction-based solver (MAPF-encodings) tends to outperform the search-based solver (ICBS) on the generated instances, despite the latter paradigm being widely regarded as highly effective in many MAPF settings. Our work is an initial step toward a systematic understanding of the strengths and limitations of different MAPF solving paradigms through automated benchmark instance generation.