A General Abductive system with application to plan recognition and diagnosis (1992)
A diverse set of intelligent activities, including natural language understanding, and scientific theory formation, requires the ability to construct explanations for observed phoenomena. In this thesis, we view explanation as abduction, where an abductive explanation is a consistent set of assumptions which, together with background knowledge, logically entials a set of observations.
To explore the practical feasibility of such a general abductive approach to explanation, we have successfully built a domain-independent system called ACCEL. In our system, knowledge about a variety of domains in uniformly encoded in first-order Horn-clause axioms. A general-purpose abduction algorithm, AAA, efficiently constructs explanations in the various domians by caching partial explanations to avoid redundant work. Empirical results show that caching of partial explanations can achieve more than an order of magnitude speedup in run time. We have applied our abductive system to two general tasks: plan recognition in text understanding, and diagnosis of medical diseases, logic circuits, and dynamic systems. The results indicate that ACCEL is a general-purpose system capable of plan recognition and diagnosis, yet efficient enough to be of pratical utility.
In the plan recognition domain, we defined a novel evaluation criterion, called explanatory coherence, and tested ACCEL on 50 short narrative texts. Empirical results demonstrate that coherence is a better evaluation metric than simplicity in the plan recognition domain, and that our system is sufficiently general to be able to handle similar plan recognition problems not known to the system developer in advance.
In medical diagnosis, we prove that ACCEL computes the same diagnoses as the GSC model of Reggia, and present empirical results demonstrating the efficiency of ACCEL in diagnosing 50 real-world patient cases using a sizable knowledge base with over six hundred symptom-disease rules.
ACCEL also realizes model-based diagnosis, which concerns inferring faults form first principles given knowledge about the correct structure and behavior of a system. ACCEL has successfully diagnosed logic circuits (a full adder) and dynamic systems (a proportional temperature controller and the water balance system of the human kidney).
PhD Thesis, Department of Computer Sciences, University of Texas at Austin. 154 pages.

Hwee Tou Ng Ph.D. Alumni nght [at] comp nus edu sg