Probabilistic Consistency Boosts MAC and SAC

12 years 3 months ago
Probabilistic Consistency Boosts MAC and SAC
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). Experiment...
Deepak Mehta, Marc R. C. van Dongen
Added 29 Oct 2010
Updated 29 Oct 2010
Type Conference
Year 2007
Authors Deepak Mehta, Marc R. C. van Dongen
Comments (0)