Windowed MAPF with Completeness Guarantees
Authors: Rishi Veerapaneni, Muhammad Suhail Saleem, Jiaoyang Li, Maxim Likhachev
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments demonstrate the empirical performance of our theoretically complete SS-CBS algorithm. We first evaluate SS-CBS on standard benchmark maps (Stern et al. 2019) and observe that SS-CBS is indeed able to outperform the windowed baselines. We then evaluate SS-CBS on high-congestion small maps and showcase SS-CBS’s superiority in this regime. Our appendix contains additional analysis and results. |
| Researcher Affiliation | Academia | Carnegie Mellon University EMAIL |
| Pseudocode | Yes | Algorithm 1: Windowed Complete MAPF Framework |
| Open Source Code | No | The paper mentions "All algorithms were implemented in C++" but does not provide any explicit statement about open-source code availability, a repository link, or reference to supplementary materials containing code for the described methodology. |
| Open Datasets | Yes | We first evaluate SS-CBS on standard benchmark maps (Stern et al. 2019) and observe that SS-CBS is indeed able to outperform the windowed baselines. We then evaluate SS-CBS on high-congestion small maps and thus evaluated it on small maps with high congestion from Okumura (2022). |
| Dataset Splits | No | The paper describes running experiments on |
| Hardware Specification | Yes | All algorithms were implemented in C++ and run on a PC with a 2.30 GHz Intel i7-11800K CPU. |
| Software Dependencies | No | The paper states, "All algorithms were implemented in C++" but does not specify any version numbers for C++ compilers, libraries, or other software components used. |
| Experiment Setup | Yes | We evaluate on 4 benchmark maps (each column: random-32-32-20, ht chantry, den520d, warehouse-10-20-10-2-1) with a 1 minute timeout across 25 scenarios. We additionally end w CBS in failure when it repeats previously visited configurations 100 times (i.e. deadlock or livelock). ... We compare against CBS with window W = {1, 2, 4, 8, 16} (w CBS). ... Table 1 shows the average success from 20 seeds with a timeout of 1 minute... |