Tech Report CS-92-24

A Linear Constraint Satisfaction Approach for Abductive Reasoning

Eugene Santos Jr.

April 1992


Abductive explanation has been formalized in AI as the process of searching for a set of assumptions that can prove a given observation. A basic problem which naturally arises is that there maybe many different possible sets available. Thus, some preferential ordering on the explanations is necessary to precisely determine which one is best. Unfortunately, any model with sufficient representational power is in general NP-hard.

Causal trees and AND/OR graphs are among the most commonly used for representing causal knowledge. Consequently, finding a best explanation has been treated as some heuristic search through the graph. However, this approach exhibits an expected exponential run-time growth rate.

In this thesis, we present a new approach to modeling abductive reasoning which admits an extremely efficient implementation. We treat the problem in terms of constrained optimization instead of graph traversal. Our approach models knowledge using linear constraints and finds a best explanation by optimizing some measure within these constraints. Although finding the best explanation remains NP-hard, our approach allows us to utilize the highly efficient tools developed in operations research. Such tools as the Simplex method and Karmarkar's projective scaling algorithm form the foundations for the practical realization of our approach. Experimental results strongly indicate that our linear constraint satisfaction approach is quite promising. Studies comparing our approach against heuristic search techniques has shown our approach to be superior in both time and space, and actually exhibiting an expected polynomial run-time growth rate.

Our goal is to show that our framework is both flexible and representationally powerful. We can model both cost-based abduction and Bayesian networks. Furthermore, it is possible for us to handle difficult problems such as alternative explanations, continuous random variables, consistency, partial covering and cyclicity which are commonly encountered in abductive (diagnostic) domains.

(complete text in pdf or gzipped postscript)