×

Generating efficient diagnostic procedures from model-based knowledge using logic programming techniques. (English) Zbl 0728.68117

Summary: We describe how model-based reasoning knowledge (represented in the form of Horn clauses) can be transformed into efficient diagnostic procedures. These procedures, in the form of generalized decision trees, are produced by partial evaluation of a declarative system model. These decision trees are constructed incrementally based on diagnostic sessions and the system model. Both optimal measurement point selection and fault localization are included in these diagnostic procedures. Using this approach we produce a diagnosis system which integrates both model-based structural and behavioral knowledge and generates explicit diagnostic knowledge. This structure guarantees both high flexibility and a good runtime behavior.
Conventional inductive learning algorithms produce decision trees with constant attribute labels for decision making. In contrast our algorithm generates generalized expression labels leading to much smaller and more understandable decision trees. This is done by exploiting the logic representation of the model and an extension of well-known partial evaluation techniques.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T30 Knowledge representation
68N17 Logic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Davis, R., Diagnostic reasoning based on structure and behaviour, Artif. Intell., 24, 347-410 (1984)
[2] Genesereth, M. R., The use of design descriptions in automated diagnosis, Artif. Intell., 24, 411-436 (1984)
[3] de Kleer, J.; Williams, B. C., Diagnosing multiple faults, Artif. Intell., 32, 97-130 (1987) · Zbl 0642.94045
[4] Reiter, R., A theory of diagnosis from first principles, Artif. Intell., 32, 57-95 (1987) · Zbl 0643.68122
[5] Quinlan, J. R., Learning efficient classification procedures and their application to chess end games, (Michalski, R. S.; Carbonell, J. G.; Mitchell, T. M., Machine Learning—An Artificial Intelligence Approach (1983), Morgan Kaufmann), 463-482, Chap. 15
[6] van Harmelen, F.; Bundy, A., Explanation-based generalisation = partial evaluation, Artif. Intell., 36, 401-412 (1988) · Zbl 0655.68106
[7] Retti, J.; Nejdl, W.; Friedrich, G., ARTEX—Knowledge based fault detection and correction in a switching system, (Proc. Int. GI Conf. Knowledge Based Systems (1987), Springer: Springer Berlin), Munich
[8] Fleischanderl, G.; Friedrich, G.; Retti, J., ARTEX—Configuration-driven diagnosis for routing systems, (Proc. Austrian Conf. Artificial Intelligence (1989), Springer: Springer Berlin)
[9] Pearce, D. A., The induction of fault diagnosis systems from qualitative models, (Proc. natn Conf. Artificial Intelligence (Aug. 1988)), 353-357, St Paul, Minneapolis
[10] Jaffar, J.; Lassez, J.-L., Constraint logic programming, (Proc. Principles of Programming Languages (May 1987)), Melbourne · Zbl 0900.68127
[11] Nejdl, W., Recursive strategies for answering recursive queries—the RQA/FQI strategy, (Proc. Int. Conf. Very Large Databases (Sept. 1987)), Brighton
[12] Smith, D. E.; Genesereth, M. R.; Ginsberg, M. L., Controlling recursive inference, Artif. Intell., 30, 343-389 (1986) · Zbl 0635.68104
[13] Gottlob, G.; Leitsch, A., On the efficiency of subsumption algorithms, Jl ACM, 32, 280-295 (1985) · Zbl 0633.68028
[14] Shannon, C. E., A mathematical theory of communication, Bell Syst. tech. J., 27, 379-623 (1948) · Zbl 1154.94303
[15] Pipitone, F., The FIS electronics troubleshooting system, IEEE Comput., 68-76 (July 1986)
[16] Koseki, Y., (Learning experimental knowledge in model-based diagnostic systems (Sept. 1988), Stanford University), Unpublished document
[17] Singh, N., Generating diagnostic procedures for discrete devices, (Technical Report Logic-88-7 (Aug. 1988), Stanford University)
[18] Schlimmer, J. C.; Fisher, D., A case study of incremental concept induction, (Proc. natn Conf. Artificial Intelligence (1986), Morgan Kaufmann: Morgan Kaufmann Los Altos, Calif), 496-501
[19] Utgoff, P. E., ID5: an incremental ID3, (Laird, J., Proc. Int. Conf. Machine Learnings (1988), Morgan Kaufmann: Morgan Kaufmann Los Altos, Calif), 107-120
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.