Exponential Deepening A* for Real-Time Agent-Centered Search
Authors: Guni Sharon, Ariel Felner, Nathan Sturtevant
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results supporting this bound are presented and demonstrate up to 10x reduction over existing RTACS solvers wrt distance traveled, states expanded and CPU runtime.Our first experiment is intended to support the claim that EDA* is efficient in polynomial domains. For this we used a large grid (2000 × 2000) with no obstacles so as to clearly show the trends of the algorithms. As we aim to prove the worst case performance bounds for the different algorithms, the heuristic values of all states were set to zero (h ≈ 0). The distance d between start and goal varied from 1 to 500. Figure 1(left) presents the number of expanded states (y-axis) as a function of the distance from start to the goal (d) (x-axis) for IDA*, RIBS (+dead-state pruning), and EDA* with C = 2. Clearly, EDA* outperforms RIBS which in turn outperforms IDA*. |
| Researcher Affiliation | Academia | Guni Sharon ISE Department Ben-Gurion University Israel gunisharon@gmail.com Ariel Felner ISE Department Ben-Gurion University Israel felner@bgu.ac.il Nathan R. Sturtevant Department of Computer Science University of Denver USA sturtevant@cs.du.edu |
| Pseudocode | Yes | Algorithm 1: LRTA* with lookahead radius 1; Algorithm 2: IDA*/RIBS/EDA*; Algorithm 3: BDFS for EDA* with DD |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository. |
| Open Datasets | No | The paper mentions using "Dragon-Age: Origins (DAO) problems" and refers to a publication by Sturtevant (2012) for benchmarks, but it does not provide concrete access information (link, DOI, or specific repository) for the dataset itself. It implicitly refers to a benchmark set but doesn't provide direct access details. |
| Dataset Splits | No | The paper does not provide specific details on training, validation, and test splits (e.g., percentages, sample counts, or predefined splits). It mentions using 'the entire set of Dragon-Age: Origins (DAO) problems (all buckets, all instances)' for experiments. |
| Hardware Specification | No | The paper does not provide any specific hardware details such as CPU/GPU models, memory, or cloud computing instance types used for running the experiments. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies, libraries, or programming languages used in the implementation or experiments. |
| Experiment Setup | Yes | For EDA*, the number in parenthesis denotes the size of the constant factor C. C was chosen from {1.1, 1.5, 2, 4, 8, 16}. For all algorithms, lookahead (sensing radius) was set to 1. h was set to octile distance. |