Open Collections

A formal characterization of a domain independent abductive reasoning system

University of British Columbia

Abduction is a logical inference technique used in explanation finding and a variety of consequence finding. One application domain that stands out in utilizing abduction is automated diagnostic reasoning. This thesis provides a formal specification and methods of computation for a domain independent propositional abductive reasoning system. On the competence level, specifications are defined for domain independent abductive reasoning in terms of finding assumption-based explanations, direct consequences, extensions and a protocol for revising assumptions. On the performance level, computational strategies for performing abduction according to the defined specifications are studied. The computational framework for a propositional abductive inference engine, the Clause Management System (CMS), is presented. The computational framework of the CMS uses the notion of prime implicates to represent its knowledge base. As a result, the algorithm to update the CMS knowledge base is an incremental algorithm for generating prime implicates - the first reported. Coupled with the notion of reasoning with assumptions, the abduction framework is extended to include inquiry about defeasible assumptions. The notion of assumption-based reasoning presented includes finding assumption-based explanations, direct consequences and extensions. Extending the computational framework of the CMS, an Assumption-based Clause Management System (ACMS) that computes the above functions, is presented. A simple protocol for use by domain specific applications interacting with the ACMS is proposed. Included in the protocol is a method to perform revision of assumptions. The first algorithm to perform incremental deletion of prime implicates is also presented. Additionally, a new notion of approximated abduction together with a set of approximation strategies, namely knowledge-guided and resource-bounded approximation, are proposed. The goal of these studies is to propose a framework for incorporating knowledge-guided and resource-bounded approximation into computational abduction. The potential benefit might be the discovery of a useful and tractable approximation strategy. The specification of a domain independent propositional abductive reasoning system is the main achievement of this thesis. The resulting abductive reasoning system, the ACMS, is adaptable to a wide spectrum of domain specific applications. The ACMS can free designers from repeatedly building specialized abductive inference engines, and instead allow them to concentrate their effort on knowledge engineering and problem solving.

Thesis/Dissertation

application/pdf

2008-09-10

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/1751

Computer Science

University of British Columbia

UBCV

DSpace