Probabilistic Consistency Boosts MAC and SAC

Deepak Mehta, M.R.C. van Dongen

Constraint Satisfaction Problems (CSPs) are ubiquitous in Artificial Intelligence. The backtrack algorithms that maintain some local consistency during search have become the de facto standard to solve CSPs. Maintaining higher levels of consistency, generally, reduces the search effort. However, due to ineffective constraint propagation, it often penalises the search algorithm in terms of time. If we can reduce ineffective constraint propagation, then the effectiveness of a search algorithm can be enhanced significantly. In order to do so, we use a probabilistic approach to resolve when to propagate and when not to. The idea is to perform only the useful consistency checking by not seeking a support when there is a high probability that a support exists. The idea of probabilistic support inference is general and can be applied to any kind of local consistency algorithm. However, we shall study its impact with respect to arc consistency and singleton arc consistency (SAC). Experimental results demonstrate that enforcing probabilistic SAC almost always enforces SAC, but it requires significantly less time than SAC. Likewise, maintaining probabilistic arc consistency and maintaining probabilistic SAC require significantly less time than maintaining arc consistency and maintaining SAC.