On the role of modeling causal independence for system model compilation with OBDDs

Issue title: Model-Based Systems

Article type: Research Article

Authors: Torta, Gianluca | Torasso, Pietro

Affiliations: Dipartimento di Informatica, Università di Torino, C.so Svizzera 185, 10149 Torino, Italy E-mail: {torta,torasso}@di.unito.it

Note: [] Corresponding author.

Abstract: Model-Based Reasoning requires as input a formal model of the system often expressed as a propositional logic theory. Exploiting the presence of structure in such a theory is fundamental in order to have a compact representation of the model and, more important, to speed-up the reasoning task. In this paper we introduce the notion of causal independence (derived from the Bayesian Networks formalism) in order to allow the modeling of an important class of local relations among system variables. In particular we focus our analysis on MAX families, where the value of a common effect is determined as the maximum among the independent contributions of a set of causing variables. We show formal and experimental results on the positive effects of causal independence on the size of the compilation of the system model in terms of an Ordered Binary Decision Diagram and connect them with the computational efficiency of Model-Based Diagnosis. Such benefits hold also when we relax the notion of causal independence in order to cover a broader class of systems which includes combinatorial digital circuits.

Keywords: Model-Based Reasoning, Causal Independence, Model Compilation

Journal: AI Communications, vol. 20, no. 1, pp. 17-26, 2007