# QD-MAPPER: A Quality Diversity Framework to Automatically Evaluate Multi-Agent Path Finding Algorithms in Diverse Maps

arXiv: https://arxiv.org/abs/2409.06888 · HTML: https://mlsanity.com/paper/2409.06888/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 48 references that are in the map.
- First posted on arXiv 10 Sep 2024.

## Builds on (most cited first, 19 of 19)

- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions](https://mlsanity.com/paper/1901.01753/) (2019)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [Illuminating Mario Scenes in the Latent Space of a Generative Adversarial Network](https://mlsanity.com/paper/2007.05674/) (2020)
- [Deep Surrogate Assisted Generation of Environments](https://mlsanity.com/paper/2206.04199/) (2022)
- [On the Importance of Environments in Human-Robot Coordination](https://mlsanity.com/paper/2106.10853/) (2021)
- [SCRIMP: Scalable Communication for Reinforcement- and Imitation-Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2303.00605/) (2023)
- [Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning](https://mlsanity.com/paper/2310.01207/) (2023)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [Multi-Robot Coordination and Layout Design for Automated Warehousing](https://mlsanity.com/paper/2305.06436/) (2023)
- [MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees](https://mlsanity.com/paper/1401.3905/) (2014)
- [Arbitrarily Scalable Environment Generators via Neural Cellular Automata](https://mlsanity.com/paper/2310.18622/) (2023)
- [Surrogate Assisted Generation of Human-Robot Interaction Scenarios](https://mlsanity.com/paper/2304.13787/) (2023)
- [Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks](https://mlsanity.com/paper/2110.08802/) (2021)
- [Accelerating Search-Based Planning for Multi-Robot Manipulation by Leveraging Online-Generated Experiences](https://mlsanity.com/paper/2404.00143/) (2024)

## Built on by (most cited first, 1 of 1)

- [Advancing MAPF Toward the Real World: A Scalable Multi-Agent Realistic Testbed (SMART)](https://mlsanity.com/paper/2503.04798/) (2025)

## Abstract (arXiv)

We use the Quality Diversity (QD) algorithm with Neural Cellular Automata (NCA) to automatically evaluate Multi-Agent Path Finding (MAPF) algorithms by generating diverse maps. Previously, researchers typically evaluate MAPF algorithms on a set of specific, human-designed maps at their initial stage of algorithm design. However, such fixed maps may not cover all scenarios, and algorithms may overfit to the small set of maps. To seek further improvements, systematic evaluations on a diverse suite of maps are needed. In this work, we propose Quality-Diversity Multi-Agent Path Finding Performance EvaluatoR (QD-MAPPER), a general framework that takes advantage of the QD algorithm to comprehensively understand the performance of MAPF algorithms by generating maps with patterns, be able to make fair comparisons between two MAPF algorithms, providing further information on the selection between two algorithms and on the design of the algorithms. Empirically, we employ this technique to evaluate and compare the behavior of different types of MAPF algorithms, including search-based, priority-based, rule-based, and learning-based algorithms. Through both single-algorithm experiments and comparisons between algorithms, researchers can identify patterns that each MAPF algorithm excels and detect disparities in runtime or success rates between different algorithms.