Branch-and-Cut-and-Price for Multi-Agent Pathfinding
Authors: Edward Lam, Pierre Le Bodic, Daniel D. Harabor, Peter J. Stuckey
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We formalize BCP and compare it empirically against CBSH and CBSH-RM, two leading search-based solvers. Conclusive results on standard benchmarks indicate that its performance exceeds the state-of-the-art: solving more instances on smaller grids and scaling reliably to 100 or more agents on larger game maps. The experiments compare two versions of BCP against two leading CBS variants: CBSH [Felner et al., 2018] and CBSH-RM [Li et al., 2019]. Results on 1,350 standard benchmarks across two small grids and two large game maps indicate that BCP exceeds state-of-the-art performance. |
| Researcher Affiliation | Academia | Edward Lam1,2 , Pierre Le Bodic1 , Daniel Harabor1 and Peter J. Stuckey1,2 1Monash University, Melbourne, Australia 2CSIRO Data61, Melbourne, Australia |
| Pseudocode | No | The paper describes the algorithms and their components using mathematical formulations and descriptive text, but it does not include any structured pseudocode or clearly labeled algorithm blocks. |
| Open Source Code | No | The paper states that "Codes for CBSH [Felner et al., 2018] and CBSH-RM [Li et al., 2019] are obtained from their authors" for comparison, but it does not provide any statement or link indicating that the source code for their proposed BCP algorithm is open source or publicly available. |
| Open Datasets | Yes | The solvers are evaluated on the same instances as [Li et al., 2019], which consist of 1,350 standard benchmarks over two small grids and two large game maps sourced from the Moving AI repository [Sturtevant, 2018]. |
| Dataset Splits | No | The paper mentions using "1,350 standard benchmarks" and that "Fifty instances are tested for every different number of agents," but it does not specify any training, validation, or test dataset splits (e.g., percentages, sample counts, or cross-validation setup). |
| Hardware Specification | Yes | All four solvers are single-threaded and are run on an Intel Xeon E5-2660 V3 CPU at 2.6 GHz with a time-out of five minutes. |
| Software Dependencies | Yes | BCP-B and BCP are implemented using the MIP solver SCIP 6.0.0 [Gleixner et al., 2018] with CPLEX as the LP solver. |
| Experiment Setup | Yes | All four solvers are single-threaded and are run on an Intel Xeon E5-2660 V3 CPU at 2.6 GHz with a time-out of five minutes. |