Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
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 | Venue PDF | 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. |