Adaptive Anytime Multi-Agent Path Finding Using Bandit-Based Large Neighborhood Search
Authors: Thomy Phan, Taoan Huang, Bistra Dilkina, Sven Koenig
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate BALANCE on multiple maps from the MAPF benchmark set and empirically demonstrate performance improvements of at least 50% compared to state-of-the-art anytime MAPF in large-scale scenarios. |
| Researcher Affiliation | Academia | University of Southern California, USA {thomy.phan, taoanhua, dilkina, skoenig}@usc.edu |
| Pseudocode | Yes | Algorithm 1: BALANCE as MAPF-LNS Framework |
| Open Source Code | Yes | Code available at github.com/thomyphan/anytime-mapf. |
| Open Datasets | Yes | We evaluate BALANCE on five maps from the MAPF benchmark set of (Stern et al. 2019), namely (1) a random map (random-32-32-10), (2) a warehouse map (warehouse-10-20-10-2-1), (3) two game maps ost003d and (4) den520d as well as (5) a city map (Paris 1 256). All maps have different sizes and structures and are the same as used in (Huang et al. 2022) for comparability with state-of-the-art anytime MAPF as presented below. We conduct all experiments on the available 25 random scenarios per map. |
| Dataset Splits | No | The paper mentions evaluating on "25 random scenarios per map" but does not specify how these scenarios are split into distinct training, validation, and test sets in the traditional supervised learning sense for reproducing data partitioning. |
| Hardware Specification | Yes | All experiments were run on a x86 64 GNU/Linux (Ubuntu 18.04.5 LTS) machine with i7 @ 2.4 GHz CPU and 16 GB RAM, as in (Huang et al. 2022). |
| Software Dependencies | No | The paper mentions specific MAB algorithms and their parameters (e.g., Thompson Sampling with µ0 = 0, λ0 = 0.01, α0 = 1, β0 = 100; UCB1 with ξ = 1, 000) but does not provide specific version numbers for underlying software libraries, programming languages, or development environments (e.g., Python version, specific deep learning frameworks like PyTorch or TensorFlow, or other solvers). |
| Experiment Setup | Yes | We implemented2 different variants of BALANCE using Thompson Sampling (with µ0 = 0, λ0 = 0.01, α0 = 1, β0 = 100), UCB1 (with ξ = 1, 000), and roulette wheel selection. ... Unless stated otherwise, we always use the |H| = 3 destroy heuristics from (Li et al. 2021) and set E = 5 such that the neighborhood size is chosen from N = {2, 4, 8, 16, 32}. ... For direct comparability with MAPF-LNS and MAPFML-LNS, we set the time budget to 60 seconds (Huang et al. 2022). |