Probabilistic Arc Consistency: A Connection between Constraint Reasoning and Probabilistic Reasoning
This work bridges two fields, offering a novel approach for constraint problems, but it appears incremental as it builds on existing algorithms without demonstrating broad SOTA impact.
The paper connects constraint reasoning and probabilistic reasoning by introducing probabilistic arc consistency, an algorithm that generalizes arc consistency and specializes belief updating for singly-connected networks, showing it is exact for singly-connected problems and works well as an approximation for arbitrary ones.
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.