Probabilistic Arc Consistency: A Connection between Constraint Reasoning and Probabilistic Reasoning
arXiv:1301.3864
Abstract
We document a connection between constraint reasoning and probabilistic reasoning. We present an algorithm, called {em probabilistic arc consistency}, which is both a generalization of a well known algorithm for arc consistency used in constraint reasoning, and a specialization of the belief updating algorithm for singly-connected networks. Our algorithm is exact for singly- connected constraint problems, but can work well as an approximation for arbitrary problems. We briefly discuss some empirical results, and related methods.
Appears in Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence (UAI2000)