On the efficiency of logic-based diagnosis

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.

REFERENCES

• BS84: B.G. Buchanan and E. H. Shortliffe. Rule- Based Expert Systems. Addison Wesley, Reading, MA, 1984.
• CB82: W. Clancy and C. Bock. MRS/NEOMYCIN: Representing metacontrol in predicate calculus. Report No. HPP-82-3, Stanford Heuristic Programming Project, Stanford, 1982.
• CM83: B. Chandrasekaran and Sanjay Mittal. Deep versus compiled knowledge approaches to diagnostic problem-solving. Int. J. Man- Machine Studies, 19:425-436, 1983.
• CP87: P.T. Cox and T. Pietrzkowski. General diagnosis by abductive inference. Technical Report CS8701, School of Computer Science, University of Nova Scotia, 1987.
• Dav80: R. Davis. Meta-rules: Reasoning about control. Artificial Intelligence, 15:179-222, 1980.
• Dav84: Randall Davis, Diagnostic reasoning based on structure and behavior, Artificial Intelligence, v.24 n.1-3, p.347-410, Dec. 1984 [doi>10.1016/0004-3702(84)90042-0]
• de 86: Johan de Kleer, An assumption-based TMS, Artificial Intelligence, v.28 n.2, p.127-162, March 1986 [doi>10.1016/0004-3702(86)90080-9]
• Doy79: J. Doyle. A truth maintenance system. Artificial Intelligence, 12:231-272, 1979.
• dW87: J de Kleer , B C Williams, Diagnosing multiple faults, Artificial Intelligence, v.32 n.1, p.97-130, April 1987 [doi>10.1016/0004-3702(87)90063-4]
• Fer89: G. Ferguson. Identity and skolem functions in resolution-based hypothetical reasoning. Master's thesis, Department of Computing Science, University of Alberta, August 1989.
• Gen84: Michael R. Genesereth, The use of design descriptions in automated diagnosis, Artificial Intelligence, v.24 n.1-3, p.411-436, Dec. 1984 [doi>10.1016/0004-3702(84)90043-2]
• GFP86: Randy Goebel , Koichi Furukawa , David Poole, Using definite clauses and integrity constraints as the basis for a theory formation approach to diagnostic reasoning, Proceedings on Third international conference on logic programming, p.211-222, September 1986, London, United Kingdom
• GS83: M. Genesereth and D. Smith. An overview of recta-level architecture. In Prcoceedings of AAAI-83, pages 119-124, 1983.
• 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.
• 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.
• LB87: H.J. Levesque and R. J. Brachman. Expressiveness and tractability in knowledge representation and reasoning. Computational Intelligence, 3(2):78-93, 1987.
• Lev89: H.J. Levesque. Logic and the complexity of reasoning. Research Report KRR-TR-89- 2, University of Toronto, Toronto, Canada, 1989.
• Lov78: Donald W Loveland, Automated theorem proving: A logical basis (Fundamental studies in computer science), sole distributor for the U.S.A. and Canada, Elsevier North-Holland, 1978
• Mac85: Alan K. Mackworth, Constraint Satisfaction, University of British Columbia, Vancouver, BC, Canada, 1985
• Pea87: J. Pearl. Embracing causality in formal reasoning. In Proceedings of the AAAi-87, pages 369-373, 1987.
• 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.
• Poo87: D.L. Poole. Variables in hypotheses. In Proceedings of the Tenth IJCAI, pages 905-908, Milan, Italy, August 23-28 1987.
• Poo88a: David Poole, A logical framework for default reasoning, Artificial Intelligence, v.36 n.1, p.27-47, August 1988 [doi>10.1016/0004-3702(88)90077-X]
• 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.
• 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.
• PS87: P.F. Patel-Schneider. A hybrid, decidable, logic-based knowledge representation system. Compulational Inlelligence, 3(2):64-77, 1987.
• Rei87: R Reiter, A theory of diagnosis from first principles, Artificial Intelligence, v.32 n.1, p.57-95, April 1987 [doi>10.1016/0004-3702(87)90062-2]
• 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.
• 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}.
• Sha82: Ehud Y. Shapiro, Algorithmic Program DeBugging, MIT Press, Cambridge, MA, 1983
• SK88: Bart Selman , Henry A. Kautz, The Complexity of Model-Preference Default Theories, Proceedings of the 2nd International Workshop on Non-Monotonic Reasoning, p.115-130, June 13-15, 1988
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Industrial automation

Additional Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.3 Reliability and Testing**
          Subjects: Error-checking**

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Reliability, Theory