Towards Clause-Learning State Space Search: Learning to Recognize Dead-Ends

By Marcel Steinmetz, Jörg Hoffmann. 2016

22 citations recorded by the source corpus.

We introduce a state space search method that identifies dead-end states, analyzes the reasons for failure, and learns to avoid similar mistakes in the future. Our work is placed in classical planning. The key technique are critical-path heuristics hC, relative to a set C of conjunctions. These recognize a dead-end state s, returning hC(s) = infty, if s has no solution even when allowing to break up conjunctive subgoals into the elements of C. Our key idea is to learn C during search. Starting from a simple initial C, we augment search to identify unrecognized dead-ends s, where hC(s) < infinity. We design methods analyzing the situation at such s, adding new conjunctions into C to obtain hC(s) = infty, thus learning to recognize s as well as similar dead-ends search may encounter in the future. We furthermore learn clauses phi where s' not satisfying phi implies hC(s') = infty, to avoid the prohibitive overhead of computing hC on every search state. Arranging these techniques in a depth-first search, we obtain an algorithm approaching the elegance of clause learning in SAT, learning to refute search subtrees. Our experiments show that this can be quite powerful. On problems where dead-ends abound, the learning reliably reduces the search space by several orders of magnitude.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Explainable Planning (2017, background): “To this end, we suggest that a promising direction is given by the work being done in proving plan non-existence (see, among others, [Bäckström et al., 2013], [Steinmetz and Hoffmann, 2016], [Hoffmann et al., 2014]).”