Probabilistic Nogood Store as a Heuristic

Nogood stores are frequently used to avoid revisiting states that were previously discovered to be inconsistent. In this paper we consider the usefulness of learned nogoods as a heuristic to guide search. In particular, we look at learning nogoods probabilistically and examine heuristic utility of such nogoods. We define how probabilistic nogoods can be derived from real nogoods and then introduce an approximate implementation. This implementation is used to compare behavior of heuristics using classic nogoods and then probabilistic nogoods on random binary CSPs and QWH problems. Empirical results show improvement in both problem domains over original heuristics.