Time-Bounded Best-First Search for Reversible and Non-reversible Search Graphs
Authors: Carlos Hernández, Jorge A. Baier, Roberto Asín
JAIR 2016 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate TB(WA) in both grid pathfinding and the 15-puzzle. In addition, we evaluate TBR (WA*) on the racetrack problem. We compare our algorithms to LSS-LRTWA*, a variant of LRTA* that can exploit lookahead search and a weighted heuristic. A general observation is that the performance of both TB(WA*) and TBR (WA*) improves as the weight parameter is increased. In addition, our time-bounded algorithms almost always outperform LSS-LRTWA* by a significant margin. |
| Researcher Affiliation | Academia | Carlos Hern andez EMAIL Departamento de Ciencias de la Ingenier ıa, Universidad Andr es Bello, Santiago, Chile Jorge A. Baier EMAIL Departamento de Ciencia de la Computaci on Pontificia Universidad Cat olica de Chile Santiago, Chile Roberto As ın EMAIL Departamento de Ingenier ıa Inform atica Universidad Cat olica de la Sant ısima Concepci on Concepci on, Chile |
| Pseudocode | Yes | Algorithm 1: Best-First Search Algorithm 2: Weighted A* Algorithm 4: Time-Bounded Best-First Search Algorithm 5: Restarting Time-Bounded Weighted A* |
| Open Source Code | No | The paper mentions extending "Richard Korf s implementation available from Carlos Linares s homepage.2" for the 15-puzzle, but this is a third-party implementation and not the authors' own code for the core methodology (TB(BFS), TB(WA*), TBR(WA*)) described in the paper. No explicit statement or link is provided for the authors' own source code. |
| Open Datasets | Yes | We used all 512 512 maps from the video game Baldurs Gate (BG), all the Room maps (ROOMS), and all maps of different size from the Starcraft (SC) available from N. Sturtevant s path-finding repository (Sturtevant, 2012). We use the 100 test cases presented by Korf (1993), which uses the Manhattan distance as a heuristic. |
| Dataset Splits | No | For each map we generated 50 random solvable search problems, resulting in 1800 problems for BG, 2000 problems for ROOMS, 3250 problems for SC, and 350 problems for CS. |
| Hardware Specification | Yes | All experiments were run on an Intel(R) Core(TM) i72600 @ 3.4Ghz machine, with 8Gbytes of RAM running Linux. |
| Software Dependencies | No | The paper mentions using "Linux" as the operating system and that "All algorithms have a common code base and use a standard binary heap for Open." It also mentions extending "Richard Korf s implementation" for the 15-puzzle. However, it does not provide specific version numbers for any software libraries, programming languages, or solvers used in their experiments. |
| Experiment Setup | Yes | We evaluated six lookahead values (1, 4, 16, 64, 128, 256) for the 512 512 maps and six lookahead values (1, 32, 128, 256, 512, 1024) for SC and CS maps. We used six weight values (1.0, 1.4, 1.8, 2.2, 2.6, 3.0). We evaluated TBR (WA*) and LSS-LRTAWA* with four weight values (1.0, 3.0, 5.0, 7.0). We use lookahead values in {16, 32, 64, 128, 256, 512} and weights in {2, 3, 4, 5}. |