Rina Dechter (University of California), Generalizing BDD Trees Using Minimal AND/OR Graphs

Graphical models, including constraint networks, CNF formulas, Bayesian networks, Markov random fields and influence diagrams, are knowledge representation schemes that capture independencies in the knowledge base and support efficient, graph-based algorithms for a variety of reasoning tasks, including scheduling, planning, diagnosis and situation assessment, design, and hardware and software verification.

In this talk I will present AND/OR search graphs, a recently introduced principle for decomposing search spaces for graphical models, which are closely related to BDD-trees and is thus superior to OBDDs. Specifically, minimal AND/OR graphs are canonical, their size is exponentially bounded by the graph-model.s tree-width, and they can be generated in time exponential in the tree-width using advanced cache-based search algorithms.