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].
Effective Heuristics for Suboptimal Best-First Search
Authors: Christopher Wilt, Wheeler Ruml
JAIR 2016 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our second contribution is to empirically characterize conditions when this occurs, knowledge that is important for anyone using a suboptimal search. This is also an important first step in a predictive theoretical understanding of the behavior of suboptimal heuristic search. ... We consider six standard benchmark domains: the sliding tile puzzle, the Towers of Hanoi puzzle, grid path planning, the pancake problem, Top Spin, and dynamic robot navigation. ... Figures 3 and 4 show the number of expansions required by A*, greedy best-first search, and Weighted A* with weights of 1.1, 1.2, 2.5, 5, 10, and 20. |
| Researcher Affiliation | Academia | Christopher Wilt wilt 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 | Algorithm 1 Hill Climbing PDB Builder 1: All Tokens = {Tokens in problem that can be abstracted} 2: Remaining Tokens = All Tokens 3: Best PDB = build PDB by abstracting All Tokens 4: Best Tau = 0 5: function try PDB(tokens) 6: pdb = build PDB by abstracting All Tokens \ tokens 7: all Nodes = nodes discovered by breadth first search backwards from the goal state(s) 8: sample = randomly sample 10% of the nodes from all Nodes 9: return calc Tau(sample, pdb) 10: while Best PDB.size < Max Allowed Size do 11: Local Best PDB, Local Best Tau, Local Best Token = (None, Best Tau, None) 12: for all Current Token Remaining Tokens do 13: Current Tau, Current PDB = try PDB(Refined Tokens {token}) 14: if Current Tau > Local Best Tau then 15: set local best variables to current 16: if Local Best PDB = None then 17: set best variables to local best variables 18: Remaining Tokens = Remaining Tokens \ Local Best Tokens 21: return Best PDB |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code, nor does it provide a link to a repository. |
| Open Datasets | Yes | We consider six standard benchmark domains: the sliding tile puzzle, the Towers of Hanoi puzzle, grid path planning, the pancake problem, Top Spin, and dynamic robot navigation. ... For the Towers of Hanoi, we considered the 14-disk-4 peg problem, and used two disjoint pattern databases, one for the bottom 12 disks, and one for the top two disks (Korf & Felner, 2002). For the pancake problem, we used the gap heuristic (Helmert, 2010). |
| Dataset Splits | No | For the sliding tile 11 puzzle (3 4), we used random instances and the Manhattan distance heuristic. ... All problems are randomly generated Towers of Hanoi states, with the goal being to get all disks onto the first peg. ... average number of nodes expanded to solve 51 12-disk Towers of Hanoi problems. |
| Hardware Specification | No | Our requirement for problem size was that the problem be solvable by A*, Weighted A*, and greedy best-first search in main memory (eight gigabytes). |
| Software Dependencies | No | approximately 25 million nodes in our Java implementation |
| Experiment Setup | Yes | Figures 3 and 4 show the number of expansions required by A*, greedy best-first search, and Weighted A* with weights of 1.1, 1.2, 2.5, 5, 10, and 20. ... For the sliding tile 11 puzzle (3 4), we used random instances and the Manhattan distance heuristic. ... For the Towers of Hanoi, we considered the 14-disk-4 peg problem, and used two disjoint pattern databases, one for the bottom 12 disks, and one for the top two disks (Korf & Felner, 2002). |