Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Uniform Solution Sampling Using a Constraint Solver As an Oracle
Stefano Ermon, Carla Gomes, Bart Selman
Abstract:
We consider the problem of sampling from solutions defined by a set of hard constraints on a combinatorial space. We propose a new sampling technique that, while enforcing a uniform exploration of the search space, leverages the reasoning power of a systematic constraint solver in a black-box scheme. We present a series of challenging domains, such as energy barriers and highly asymmetric spaces, that reveal the difficulties introduced by hard constraints. We demonstrate that standard approaches such as Simulated Annealing and Gibbs Sampling are greatly affected, while our new technique can overcome many of these difficulties. Finally, we show that our sampling scheme naturally defines a new approximate model counting technique, which we empirically show to be very accurate on a range of benchmark problems.
Keywords:
Pages: 255-264
PS Link:
PDF Link: /papers/12/p255-ermon.pdf
BibTex:
@INPROCEEDINGS{Ermon12,
AUTHOR = "Stefano Ermon and Carla Gomes and Bart Selman",
TITLE = "Uniform Solution Sampling Using a Constraint Solver As an Oracle",
BOOKTITLE = "Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "255--264"
}


hosted by DSL   •   site info   •   help