Title | ||
---|---|---|
"Distance"? Who Cares? Tailoring Merge-and-Shrink Heuristics to Detect Unsolvability. |
Abstract | ||
---|---|---|
Research on heuristic functions is all about estimating the length (or cost) of solution paths. But what if there is no such path? Many known heuristics have the ability to detect (some) unsolvable states, but that ability has always been treated as a by-product. No attempt has been made to design heuristics specifically for that purpose, where there is no need to preserve distances. As a case study towards leveraging that advantage, we investigate merge-and-shrink abstractions in classical planning. We identify safe abstraction steps (no information loss regarding solvability) that would not be safe for traditional heuristics. We design practical algorithm configurations, and run extensive experiments showing that our heuristics outperform the state of the art for proving planning tasks unsolvable. |
Year | DOI | Venue |
---|---|---|
2014 | 10.3233/978-1-61499-419-0-441 | Frontiers in Artificial Intelligence and Applications |
Field | DocType | Volume |
Mathematical optimization,Heuristic,Information loss,Abstraction,Computer science,Heuristics,Merge (version control) | Conference | 263 |
ISSN | Citations | PageRank |
0922-6389 | 17 | 0.62 |
References | Authors | |
16 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jörg Hoffmann | 1 | 133 | 13.17 |
Peter Kissmann | 2 | 181 | 13.93 |
Álvaro Torralba | 3 | 81 | 15.12 |