QD-MAPPER: A Quality Diversity Framework to Automatically Evaluate Multi-Agent Path Finding Algorithms in Diverse Maps
#Multi‑Agent Path Finding (MAPF) #Quality‑Diversity (QD) Algorithm #Neural Cellular Automata (NCA) #Benchmarking Framework #Algorithm Evaluation #Search‑Based MAPF #Priority‑Based MAPF #Rule‑Based MAPF #Learning‑Based MAPF #Over‑Fitting #Map Generation #Artificial Intelligence #Computer Science – Multi‑Agent Systems
📌 Key Takeaways
- Introduces QD‑MAPPER, a Quality‑Diversity driven framework for evaluating MAPF algorithms on automatically generated, diverse map sets.
- Combines a Quality‑Diversity search algorithm with Neural Cellular Automata to produce maps with varied structural patterns.
- Addresses the limitation of current MAPF benchmarks that rely on a small set of hand‑crafted maps, thereby mitigating over‑fitting.
- Benchmarks a range of MAPF strategies—search‑based, priority‑based, rule‑based, and learning‑based—across the generated maps.
- Finds observable performance disparities (success rate, runtime) across algorithm families, revealing strengths and weaknesses for specific map types.
- Provides a reproducible, automated pipeline that facilitates fair comparison and informed algorithm selection in research and deployment.
📖 Full Retelling
First paragraph: Cheng Qian, Yulun Zhang, Varun Bhatt, Matthew C. Fontaine, Stefanos Nikolaidis, and Jiaoyang Li authored *QD‑MAPPER: A Quality Diversity Framework to Automatically Evaluate Multi‑Agent Path Finding Algorithms in Diverse Maps*, a preprint posted to arXiv under the Computer Science – Multi‑Agent Systems (cs.MA) and Artificial Intelligence (cs.AI) categories. The paper was first submitted on September 10, 2024, and the current version (v5) was revised on February 14, 2026. It introduces a framework that automatically generates a broad range of synthetic maps using a Quality‑Diversity algorithm combined with Neural Cellular Automata, allowing researchers to test Multi‑Agent Path Finding (MAPF) algorithms on a diverse suite of environments instead of a limited set of manually designed maps, thereby reducing the risk of algorithm over‑fitting and improving the reliability of comparative evaluations.
Second paragraph: The authors demonstrate QD‑MAPPER’s utility by benchmarking search‑based, priority‑based, rule‑based, and learning‑based MAPF algorithms across the generated maps. They report systematic differences in success rates and runtimes, highlighting patterns where specific algorithm families excel or underperform. By providing a scalable, reproducible evaluation pipeline, QD‑MAPPER equips the multi‑agent research community with a tool to better understand algorithmic trade‑offs and guide future design choices.
🏷️ Themes
Multi‑Agent Systems, Artificial Intelligence, Quality‑Diversity Optimization, Neural Cellular Automata, Benchmarking & Evaluation, Algorithmic Comparisons, Path Planning, Runtime Performance, Success Rate Analysis, Systematic Testing
Entity Intersection Graph
No entity connections available yet for this article.
Original Source
--> Computer Science > Multiagent Systems arXiv:2409.06888 [Submitted on 10 Sep 2024 ( v1 ), last revised 14 Feb 2026 (this version, v5)] Title: QD-MAPPER: A Quality Diversity Framework to Automatically Evaluate Multi-Agent Path Finding Algorithms in Diverse Maps Authors: Cheng Qian , Yulun Zhang , Varun Bhatt , Matthew Christopher Fontaine , Stefanos Nikolaidis , Jiaoyang Li View a PDF of the paper titled QD-MAPPER: A Quality Diversity Framework to Automatically Evaluate Multi-Agent Path Finding Algorithms in Diverse Maps, by Cheng Qian and 5 other authors View PDF HTML Abstract: We use the Quality Diversity algorithm with Neural Cellular Automata to automatically evaluate Multi-Agent Path Finding 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. Comments: 14 pages, 23 figures Subjects: Multiagent Sys...
Read full article at source