Scalable Mechanism Design for Multi-Agent Path Finding
Authors: Paul Friedrich, Yulun Zhang, Michael Curry, Ludwig Dierks, Stephen McAleer, Jiaoyang Li, Tuomas Sandholm, Sven Seuken
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments verify that our mechanisms behavior follows our claims on optimality, scalability, and payments. Our benchmarks are strategyproof mechanisms whose allocation rule solves classical MAPF, i Bundle [Amir et al., 2015] being the most advanced competition. Figure 1 compares the success rate, runtime and welfare over FCFS of MCPP with different sample sizes m on the random-32-32-20 map. |
| Researcher Affiliation | Collaboration | 1ETH AI Center 2University of Zurich 3Carnegie Mellon University 4Harvard University 5University of Illinois at Chicago 6Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc. |
| Pseudocode | Yes | Mechanism 1: MCPP Input: Agent reports ( 1, . . . , n), No. of samples m Output: Conflict-free paths ( 1, . . . , n) and payments (p1, . . . , pn) Allocation rule: Prioritized Planning |
| Open Source Code | Yes | Code at https://github.com/lunjohnzhang/MAPF-Mechanism. |
| Open Datasets | Yes | We evaluate payment-CBS (PCBS), exhaustive-PBS (EPBS) and Monte-Carlo prioritized planning (MCPP) on four 2D maps selected from the commonly used MAPF benchmarks by Stern et al. [2019]. |
| Dataset Splits | No | The paper evaluates mechanisms on instances but does not provide specific train/validation/test dataset splits (percentages or counts), nor does it describe cross-validation setups or predefined split files. It mentions '100 instances' for each run but not how those instances are split for training, validation, or testing. |
| Hardware Specification | Yes | Our code was implemented in C++ and ran on a 2x12-core Intel Xeon E5-2650v4 machine with 128 GB of RAM. |
| Software Dependencies | No | Our code was implemented in C++ and ran on a 2x12-core Intel Xeon E5-2650v4 machine with 128 GB of RAM. The paper only mentions 'C++' as the implementation language but does not provide specific software dependencies with version numbers (e.g., specific compilers, libraries, or frameworks with their versions). |
| Experiment Setup | Yes | MCPP uses a sample size of m = 100, except in Figure 1. Each run uses a set of 100 instances. We set a runtime limit for all mechanisms at 3600 seconds for the random-32-32-20 and dens312d maps and 5400 seconds for the dens520d and Paris-1-256 maps. |