Constraints and Probabilistic Networks: a Look at the InterfaceRina Dechter
University of California, Irvine
Abstract: I am going to discuss the interface between two types of networks; one deterministic and one probabilistic. The deterministic network, also known as constraint network, a CSP problem, or a SAT formula, represents a collection of constraints among groups of variables.
The probabilistic network is a more organized object, represents a restricted collection of probabilistic relationships among groups of variables. These two paradigms were developed separately in the past 20-30 years and are relatively mature by now, with each paradigm equipped with its own concepts, techniques, heuristics and shortcuts. For example the concept of constraint propagation is unheard of in the probabilistic community. Similarly, notions such as sampling and Monte Carlo simulation (with guaranteed convergence) are rarely examined in constraint processing.
I will start by highlighting conceptual commonalities and differences between the two frameworks, and will propose a simple hybrid framework. I will then talk about benefits that can be obtained by importing techniques from constraint networks to probabilistic networks and back. Finally, if time permits, I will discuss how sampling techniques used in probabilistic networks can inspire algorithms for sampling solution in constraint satisfaction problems.
Toward a Universal Inference EngineHenry Kautz
Department of Computer Science and Engineering
University of Washington
Abstract: In the early days of AI some researchers proposed that intelligent problem solving could be reduced to the application of general purpose theorem provers to an axiomatization of commonsense knowledge. Although automated first-order theorem proving was unwieldy, general reasoning engines for propositional logic turned out to be surprisingly efficient for a wide variety of applications. Still many problems of interest to AI involve probabilities or quantification, and would seem to be beyond propositional methods. However, recent research has shown that the basic backtrack search algorithm for satisfiability generalizes to a strikingly efficient approach for broader classes of inference. We may be on the threshold of achieving the old dream of a universal inference engine.
Towards Systematic Benchmarking in Answer Set Programming: The Dagstuhl InitiativeTorsten Schaub
Institut für Informatik
Abstract: In September 2002, participants of the Dagstuhl Seminar on Nonmonotonic Reasoning, Answer Set Programming and Constraints, agreed that in order to foster further development of Answer Set Programming (ASP), it is important to establish an infrastructure for benchmarking ASP solvers. The intention was to follow good practices already in place in neighboring fields of satisfiability testing and constraint programming. Thus, the Dagstuhl Initiative was born to set up an environment for submitting and archiving benchmarking problems and instances and in which ASP systems can be run under equal and reproducible conditions, leading to independent results. In the talk, I will be describing the existing and envisaged infrastructure for accumulating benchmarks and executing ASP solvers under the same conditions. Also, I will be reporting on the undertaken system competition and its results.