Tech Report CS-91-13

Cost-Based Abduction and Linear Constraint Satisfaction

Eugene Santos Jr.

February 1991


Abduction is the problem of finding the best explanation for a given set of observations. Cost-based abduction approaches attempt to prove the observation by assuming some hypotheses. Hypotheses have associated ``costs'' and the best proof is the one which assumes the least costly set. Previous approaches have formalized minimum cost-based abduction as a search problem. Heuristics were then sought to aid in the search for the best proof. However, efficient admissible heuristics seem to be difficult to find.

In this paper, we present an approach to the problem from the standpoint of optimization. By using linear constraints to represent causal relationships, we provide a new framework capable of modeling cost-based abduction. Moreover, we are able to utilize the highly efficient optimization tools of operations research, thus yielding a computationally efficient method for solving cost-based abduction problems.

(complete text in pdf)