Tech Report CS-92-03

A Linear Constraint Satisfaction Approach to Cyclicity

Eugene Santos Jr.

January 1992


Abductive reasoning (or explanation) is basically a backward-chaining process on a collection of causal rules. Given an observed event, we attempt to determine the set of causes that brought about this event. {\em Cost-based abduction} is a model for abductive reasoning which provides a concrete formulation of the explanation process. However, it restricts itself to acyclic causal knowledge bases. The existence of cyclicity results in anamolous behavior by the model. For example, assume in our knowledge base that $A$ can cause $B$ and $B$ can cause $A$. Faced with having to explain the occurrence of $A$, we could postulate $B$. Now, since $A$ already exists, we can use it to explain $B$. Our backward-% chaining process to find an explanation can certainly fall into this trap. In this paper, we present a new model called {\em generalized cost-based abduction} for general causal knowledge bases. Furthermore, we provide an approach for solving this model by using {\em linear constraint satisfaction.}

(complete text in pdf or gzipped postscript)