Abstract
The paper introduces an AND/OR search space perspective for graphical models that include probabilistic networks (directed or undirected) and constraint networks. In contrast to the traditional (OR) search space view, the AND/OR search tree displays some of the independencies present in the graphical model explicitly and may sometime reduce the search space exponentially. Indeed, most algorithmic advances in searchbased constraint processing and probabilistic inference can be viewed as searching an AND/OR search tree or graph. Familiar parameters such as the depth of a spanning tree, tree-width and path-width are shown to play a key role in characterizing the effect of AND/OR search graphs vs the traditional OR search graphs.