State space search nogood learning: Online refinement of critical-path dead-end detectors in planning

摘要

Conflict-directed learning is ubiquitous in constraint satisfaction problems like SAT, but has been elusive for state space search on reachability problems like classical planning. Almost all existing approaches learn nogoods relative to a fixed solution-length bound, in which case planning/reachability reduces to a constraint satisfaction problem. Here we introduce an approach to learning more powerful nogoods, that are sound regardless of solution length, i.e., that identify dead-end states for which no solution exists.