Integrating Probabilistic Reasoning with Constraint Satisfaction

IJCAI Tutorial T7 / Sunday Afternoon, July 17, 2011
Eric I. Hsu, University of Toronto




Lecture Notes




An active and promising line of recent research has been to combine techniques for probabilistic reasoning over graphical models with techniques from constraint satisfaction, in order to solve problems from either area. This tutorial will first present a formal synthesis of probabilistic and constraint reasoning in terms of the factor graph representation, and then will proceed to review the emerging line of combined research in light of this framework, while identifying opportunities for future research along the way. The tutorial is directed to a broad AI audience. The basic concepts will be easily approachable for novices, while experts may be interested in the more advanced topics within their own areas of specialization, as well as the entire set of foundational techniques in the area other than their main specialization.

The figure exemplifies the basic point of departure for the tutorial: that a constraint satisfaction problem (here a Boolean satisfiability problem) can be profitably interpreted as a set of local 0/1 functions whose product defines a global function representing the set of solutions to the problem.

Lecture Notes:

Part 1
Part 2