Generalized and Sub-Optimal Bipartite Constraints for Conflict-Based Search
Authors: Thayne T. Walker, Nathan R. Sturtevant, Ariel Felner7277-7284
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Empirical results show that BR yields significant speedups in 2k connected grids over the previous state-of-the-art for both optimal and suboptimal search. |
| Researcher Affiliation | Academia | 1University of Denver, Denver, USA 2University of Alberta, Edmonton, Canada 3Ben-Gurion University, Be er-Sheva, Israel |
| Pseudocode | Yes | Algorithm 1 Compute Largest Time Annotated Biclique |
| Open Source Code | Yes | Code available at https://github.com/thaynewalker/hog2 |
| Open Datasets | Yes | Table 1 shows results on the MAPF benchmarks (Stern et al. 2019) which consists of 25 tests on each of 28 grid-based maps of various types. |
| Dataset Splits | No | The paper describes running experiments on '25 tests on each of 28 grid-based maps of various types. Each test consists of up to 1,000 problem instances with increasing numbers of agents.' However, it does not specify explicit training, validation, and test dataset splits as would be typical for machine learning models, as this is a search algorithm paper. |
| Hardware Specification | No | All tests were performed on virtual machines with 2.8GHz processors. This describes a general processor speed but lacks specific models, numbers of cores, or memory details to be considered a specific hardware specification. |
| Software Dependencies | No | The paper mentions using specific algorithms like A* and SIPP, but it does not list any software dependencies or libraries with specific version numbers. |
| Experiment Setup | Yes | All tests were performed on virtual machines with 2.8GHz processors. Tests were run by incrementally adding one agent at a time until it becomes unsolvable within the allotted time limit of 30 seconds. Our implementation uses A* with a fixed duration of 1 for wait actions at the low level instead of SIPP. All CBS-based test implementations run in the independence detection framework (Standley 2010). We found that the conflict avoidance table (CAT) (Standley 2010), the bypass enhancement (Boyarski et al. 2015a) and the conflict prioritization enhancement (Boyarski et al. 2015b) were either ineffective or detrimental in 2k neighborhood environments of 8-connected and higher. Our analysis showed that turning these enhancements off increases average performance. |