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].
Achieving Goals Quickly Using Real-time Search: Experimental Results in Video Games
Authors: Scott Kiesel, Ethan Burns, Wheeler Ruml
JAIR 2015 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Using both the classic benchmarks and the new domains, we investigate several enhancements to a leading real-time search algorithm, LSS-LRTA*. We show experimentally that 1) it is better to plan after each action or to use a dynamically sized lookahead, 2) A*-based lookahead can cause undesirable actions to be selected, and 3) on-line de-biasing of the heuristic can lead to improved performance. |
| Researcher Affiliation | Academia | Scott Kiesel skiesel at cs.unh.edu Ethan Burns eaburns at cs.unh.edu Wheeler Ruml ruml at cs.unh.edu Department of Computer Science University of New Hampshire Durham, NH 03824 USA |
| Pseudocode | Yes | Figure 1: Pseudocode for LSS-LRTA*. Figure 9: Pseudocode for LSS-LRTA* with a dynamic lookahead using ˆf. |
| Open Source Code | Yes | The C++ source code is available on Git Hub (Kiesel, Burns, & Ruml, 2015a). Kiesel, S., Burns, E., & Ruml, W. (2015a). Research code for heuristic search. https://github.com/eaburns/search. Accessed September 2, 2015. |
| Open Datasets | Yes | We compare the different techniques on the platform pathfinding benchmark of Burns et al. (2013b). [...] For the 15-puzzle, we used the 94 instances from Korf s 100 instances (Korf, 1985) that our implementation of A* was able to solve using a 6GB memory limit. For grid pathfinding, we ran on the orz100d grid map from the video game Dragon Age: Origins (Sturtevant, 2012). |
| Dataset Splits | Yes | For our experiments we used 25 test instances created using the level generator described by Burns et al. (2013b), where the maze for each instance was unique and had a random start and goal location. We used the offline training techniques described above to learn the amount of time required to perform different amounts of lookahead search. For the offline training, we generated an additional 25 training instances. |
| Hardware Specification | Yes | All experiments were run on a Core2 duo E8500 3.16 GHz with 8GB RAM running Ubuntu 10.04. |
| Software Dependencies | Yes | All experiments were run on a Core2 duo E8500 3.16 GHz with 8GB RAM running Ubuntu 10.04. |
| Experiment Setup | Yes | The lookahead values used were 1, 5, 10, 20, 50, 100, 200, 400, 800, 1000, 1500, 2000, 3000, 4000, 8000 10000, 16000, 32000, 48000, 64000, 128000, 196000, 256000, and 512000. For algorithms that use a fixed-size lookahead, the lookahead value was selected by choosing the largest lookahead size for which the mean step time on the training instances was within a single action duration. [...] We consider a variety of action durations, these are shown on the x axis, also on a log10 scale. Smaller action durations represent an agent that moves slowly and a small unit action duration models an agent that moves quickly, relative to its planning speed. |