Search and Learn: On Dead-End Detectors, the Traps they Set, and Trap Learning

Search and Learn: On Dead-End Detectors, the Traps they Set, and Trap Learning

Marcel Steinmetz, Jörg Hoffmann

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 4398-4404. https://doi.org/10.24963/ijcai.2017/614

A key technique for proving unsolvability in classical planning are dead-end detectors \Delta: effectively testable criteria sufficient for unsolvability, pruning (some) unsolvable states during search. Related to this, a recent proposal is the identification of traps prior to search, compact representations of non-goal state sets T that cannot be escaped. Here, we create new synergy across these ideas. We define a generalized concept of traps, relative to a given dead-end detector \Delta, where T can be escaped, but only into dead-end states detected by \Delta. We show how to learn compact representations of such T during search, extending the reach of \Delta. Our experiments show that this can be quite beneficial. It improves coverage for many unsolvable benchmark planning domains and dead-end detectors \Delta, in particular on resource-constrained domains where it outperforms the state of the art.
Keywords:
Planning and Scheduling: Planning Algorithms
Combinatorial & Heuristic Search: Heuristic Search
Planning and Scheduling: Search in Planning and Scheduling