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 [1].
Worst-Case Solution Quality Analysis When Not Re-Expanding Nodes in Best-First Search
Authors: Richard Valenzano, Nathan Sturtevant, Jonathan Schaeffer
AAAI 2014 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we formally show that the loss in solution quality can be bounded based on the amount of inconsistency along optimal solution paths. This bound holds regardless of whether the heuristic is admissible or inadmissible, though if the heuristic is admissible the bound can be used to show that not re-expanding nodes can have at most a quadratic impact on the quality of solutions found when using A . We then show that the bound is tight by describing a process for the construction of graphs for which a best-first search that does not re-expand nodes will find solutions whose quality is arbitrarily close to that given by the bound. |
| Researcher Affiliation | Academia | Richard Valenzano University of Alberta EMAIL; Nathan R. Sturtevant University of Denver EMAIL; Jonathan Schaeffer University of Alberta EMAIL |
| Pseudocode | Yes | Pseudocode for this framework is shown in Algorithm 1 |
| Open Source Code | No | The paper does not provide any information about open-source code for the described methodology. |
| Open Datasets | Yes | consider the use of WA on the 35, 360 pathfinding problems from the 10 8-connected, 512 512 maps with 40% random obstacles given by Sturtevant (2012). |
| Dataset Splits | No | The paper describes using a set of pathfinding problems from Sturtevant (2012) for evaluation but does not specify any training, validation, or test splits for these problems. |
| Hardware Specification | No | The paper does not provide any details regarding the hardware specifications used for the experiments. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies used in the experiments. |
| Experiment Setup | No | The paper mentions characteristics of the problems (e.g., 'weight 10 WA', 'octile heuristic') but does not provide specific experimental setup details such as hyperparameters, learning rates, or batch sizes. |