Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding
Authors: Jiaoyang Li,Daniel Harabor,Peter J. Stuckey,Hang Ma,Sven Koenig6087-6095
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We show that the addition of symmetry-breaking techniques can lead to an exponential reduction in the size of the search space of CBS, a popular framework for MAPF, and report significant improvements in both runtime and success rate versus CBSH and EPEA* two recent and state-of-the-art MAPF algorithms. ... We ran experiments on a 2.80 GHz Intel Core i7-7700 laptop with 8 GB RAM with a runtime limit of 5 minutes. For every grid and every number of agents, we average over 50 instances with random start and goal locations. |
| Researcher Affiliation | Academia | Jiaoyang Li,1 Daniel Harabor,2 Peter J. Stuckey,2 Hang Ma,1 Sven Koenig1 1University of Southern California 2Monash University |
| Pseudocode | Yes | Algorithm 1: Identify rectangle conflicts for path segments. |
| Open Source Code | No | The paper does not provide any links to open-source code or explicitly state that the code for the methodology is available. |
| Open Datasets | Yes | We also compare the algorithms on two standard benchmark game grids, den520d and lak503d, from (Sturtevant 2012). |
| Dataset Splits | No | The paper mentions running experiments over "50 instances with random start and goal locations" but does not specify training, validation, or test dataset splits (e.g., percentages or counts). |
| Hardware Specification | Yes | We ran experiments on a 2.80 GHz Intel Core i7-7700 laptop with 8 GB RAM with a runtime limit of 5 minutes. |
| Software Dependencies | No | The paper mentions using algorithms like CBSH and EPEA* and proposes CBSH-CR, CBSH-R, and CBSH-RM, but it does not specify any software dependencies with version numbers (e.g., programming languages, libraries, solvers) needed for replication. |
| Experiment Setup | Yes | For every grid and every number of agents, we average over 50 instances with random start and goal locations. ... The low-level search always returns an optimal path, the high-level search always chooses a CT node with minimum f-value to expand, and the expansion does not lose any conflictfree paths (Property 1). ... CBSH-CR chooses cardinal conflicts first, then semi-cardinal conflicts and last non-cardinal conflicts. It breaks ties by preferring the earliest conflict. |