On the Optimal Efficiency of Cost-Algebraic A*
Authors: Robert C. Holte, Sandra Zilles2288-2295
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we investigate cost-algebraic A* s optimal efficiency: in the cost-algebraic setting, under what conditions is A* guaranteed to expand the fewest possible states? ... We show that three of them continue to hold in the cost-algebraic setting, but that one does not. We also show that one of them is false, it does not hold even in the traditional setting. We introduce an alternative that does hold in the cost-algebraic setting. Finally, we show that a well-known result due to Nilsson does not hold in the general cost-algebraic setting but does hold in a slightly less general setting. |
| Researcher Affiliation | Academia | Robert C. Holte Computing Science Dept. University of Alberta Edmonton, Canada T6G 2E8 (rholte@ualberta.ca) Sandra Zilles Computer Science Dept. University of Regina Regina, Canada S4S 0A2 (zilles@cs.uregina.ca) |
| Pseudocode | Yes | Algorithm 1: Generic DXBB Search Algorithm |
| Open Source Code | No | The paper does not provide any specific links to source code, nor does it state that the code for the described methodology is publicly available or in supplementary materials. It mentions 'A technical report with all the proofs is available from the authors on request,' but this refers to proofs, not code. |
| Open Datasets | No | This paper is theoretical and does not utilize or refer to any publicly available datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper that does not involve empirical experiments with datasets, and therefore no dataset split information (training, validation, test) is provided. |
| Hardware Specification | No | This is a theoretical paper that does not describe empirical experiments requiring specific hardware. Therefore, no hardware specifications are provided. |
| Software Dependencies | No | This is a theoretical paper that does not describe empirical experiments or require specific software dependencies with version numbers for replication. |
| Experiment Setup | No | This is a theoretical paper that does not describe empirical experiments with specific setup details such as hyperparameters or training configurations. |