Abdul Sattar
ABSTRACT
Diagnosis is a problem in which one must explain the discrepancy between the observed and correct system behavior by assuming some component (possibly multiple components) of the system is functioning abnormally. A diagnostic reasoning system must deal with two issues concerning computational efficiency. The first is efficient search in a complex space for all possible diagnoses for a given set of observations about the faulty system. The second is efficient discrimination amongst multiple competing diagnoses.
We consider the problem of diagnosis from the perspective of the Theorist hypothetical reasoning framework which provides a simple and intuitive diagnostic method. We propose an extension to the Theorist framework that modifies the consistency check mechanism to incrementally compute inconsistencies, sometimes referred to as nogoods, and to identify crucial literals to perform tests for discriminating among competing diagnoses. A prototype is implemented in Cprolog and its empirical efficiency is shown by considering examples from two different domains of diagnosis.
- BS84.B.G. Buchanan and E. H. Shortliffe. Rule- Based Expert Systems. Addison Wesley, Reading, MA, 1984.Google Scholar
- CB82.W. Clancy and C. Bock. MRS/NEOMYCIN: Representing metacontrol in predicate calculus. Report No. HPP-82-3, Stanford Heuristic Programming Project, Stanford, 1982.Google Scholar
- CM83.B. Chandrasekaran and Sanjay Mittal. Deep versus compiled knowledge approaches to diagnostic problem-solving. Int. J. Man- Machine Studies, 19:425-436, 1983.Google ScholarCross Ref
- CP87.P.T. Cox and T. Pietrzkowski. General diagnosis by abductive inference. Technical Report CS8701, School of Computer Science, University of Nova Scotia, 1987.Google Scholar
- Dav80.R. Davis. Meta-rules: Reasoning about control. Artificial Intelligence, 15:179-222, 1980.Google ScholarCross Ref
- Dav84.R. Davis. Diagnostic reasoning based on structure and behavior. Artificial intelligence, 24:347-410, 1984. Google ScholarDigital Library
- de 86.J. de Kleer. An assumption-based tins. Artificial Intelligence, 28:127-162, 1986. Google ScholarDigital Library
- Doy79.J. Doyle. A truth maintenance system. Artificial Intelligence, 12:231-272, 1979.Google ScholarCross Ref
- dW87.J. de Kleer and B.C. Williams. Diagnosing multiple faults. Artificial Intelligence, 32(1):97-1a0, Igs?. Google ScholarDigital Library
- Fer89.G. Ferguson. Identity and skolem functions in resolution-based hypothetical reasoning. Master's thesis, Department of Computing Science, University of Alberta, August 1989.Google Scholar
- Gen84.M.R. Genesereth. The use of design descriptions in automated diagnosis. Artificial Intelligence, 24:411-436, 1984. Google ScholarDigital Library
- GFP86.R. Goebel, K. Furukawa, and D. Poole. Using definite clauses and integrity constraints as the basis for a theory formation approach to diagnostic reasoning, in Proceedings of the Third International Conference on Logic Programming, pages 211-222, London, England, July 14-18 1986. hnperial College. Google ScholarDigital Library
- GS83.M. Genesereth and D. Smith. An overview of recta-level architecture. In Prcoceedings of AAAI-83, pages 119-124, 1983.Google Scholar
- Hay73.P.J. Hayes. Computation and deduction. In Procedings of the Symposium on the Maihemaiical Foundations of Computer Science, pages 105-117, Czechoslovakian Academy of Sciences, 1973.Google Scholar
- Kon85.K. Konolige. Belief and incompleteness. In J. R. Hobbs and R. C. Moore, editors, Formal Theories of the Commonsense World. Ablex, Norwood, NJ, 1985.Google Scholar
- LB87.H.J. Levesque and R. J. Brachman. Expressiveness and tractability in knowledge representation and reasoning. Computational Intelligence, 3(2):78-93, 1987.Google ScholarCross Ref
- Lev89.H.J. Levesque. Logic and the complexity of reasoning. Research Report KRR-TR-89- 2, University of Toronto, Toronto, Canada, 1989.Google ScholarCross Ref
- Lov78.D.W. Loveland. Automated theorem proving: a logical basis. North-Holland, Amsterdam, The Netherlands, 1978. Google ScholarDigital Library
- Mac85.A. Mackworth. Constraint satisfaction. Technical Report 85-15, Department of Computer Science, University of British Columbia, Vancouer, B.C., September 1985. Google ScholarDigital Library
- Pea87.J. Pearl. Embracing causality in formal reasoning. In Proceedings of the AAAi-87, pages 369-373, 1987.Google Scholar
- PGA87.D. Poole, R. Goebel, and R. Aleliunas. Theorist' A logical reasoning system for defaults and diagnosis. In N.J. Cercone and G. McCalla, editors, The Knowledge Frontier: Essays in the Representation of Knowledge, pages 331-352. Springer Verlag, New York, 1987.Google ScholarCross Ref
- Poo87.D.L. Poole. Variables in hypotheses. In Proceedings of the Tenth IJCAI, pages 905-908, Milan, Italy, August 23-28 1987.Google Scholar
- Poo88a.D. Poole. A logical framework for default reasoning. Artificial Intelligence, 36(1):27-47, 1988. Google ScholarDigital Library
- Poo88b.D.L. Poole. Representing knowledge for logicbased diagnosis. In Proceedings of the lnlernational Conference on Fifth Generation Compuler Syslems, Tokyo, Japan, November 28-December 2 1988. ICOT. to appear.Google Scholar
- Pop85.H.E. Jr. Pople. Coming to grips with the multiple-diagnosis problem. In Kenneth F. Schaffner, editor, The Logic of Discovery and Diagnosis in Medicine, pages 181-198. University of California Press, Brekeley, 1985.Google Scholar
- PS87.P.F. Patel-Schneider. A hybrid, decidable, logic-based knowledge representation system. Compulational Inlelligence, 3(2):64-77, 1987.Google ScholarCross Ref
- Rei87.R. Reiter. A theory of diagnosis from first principles. Ariificial Intelligence, 32(1):57- 95, 1987. Google ScholarDigital Library
- RNW83.J. A. Reggia, D. S. Nau, and P. Y. Wang. Diagnostic expert system based on a set covering model. Int. J. Man-Machine Studies, 19:437-460, 1983.Google ScholarCross Ref
- SG89.A. Sattar and R. Goebel. Using crucial literals to select better theories. Technical Report TR-89-27, Department of Computing Science, Edmonton, Alberta, 1989. {Submitted to Journal}.Google Scholar
- Sha82.E.Y. Shapiro. Algorithmic Program Debugging. MIT Press, Cambridge, Massachusetts, 1982. Google ScholarDigital Library
- SK88.B. Selman and H. Kautz. The complexity of model-preference default theories, in Proceedings of the C$C$I-88, Edmonton, Alberta, 1988. Google ScholarDigital Library
- ST85.H. Seki and A. Takeuchi. An algorithm for finding a query which discriminates competing hypotheses. Techincal report TR-143, Institute for New Generation Computer Technology, Tokyo, Japan, October 1985.Google Scholar
Comments