Dieter Fensel and Richard Benjamins
University of Amsterdam, Department SWI
Roetersstraat 15, 1018
WB Amsterdam, the Netherlands,
E-mail: {fensel | richard}@swi.psy.uva.nl
In [Fensel & Straatman, 1996] we discussed the idea of viewing the development process of an efficient knowledge-based reasoner as a process of introducing and refining assumptions. A simple generate & test problem solver is modified to a more efficient problem-solving method (a variant of propose & revise for parametric design by introducing assumptions that weaken the task and that strengthen the requirements on domain knowledge. In this paper, we review the work on diagnostic reasoning systems. We focus on assumptions that are introduced to define the effect of diagnostic reasoners and to improve their efficiency. The work on diagnostic reasoning provides an interesting empirical basis for our approach as it provides a more than ten years long history on developing knowledge-based reasoners for a complex task. During this process, several assumptions have been identified and refined in the literature on model-based diagnostic systems.
The first diagnostic systems built were heuristic systems, in the sense that they contained compiled knowledge which linked symptoms directly to hypotheses (usually in rules). In these systems, only foreseen symptoms can be diagnosed and heuristic knowledge that links symptoms with possible faults needs to be available. One of the main principles underlying model-based diagnosis is the use of a domain model (called SBF models in [Chandrasekaran, 1991]). Heuristic knowledge that links symptoms with causes is no longer necessarily. The domain model is used for predicting the desired device behaviour, which is then compared to the observed device behaviour. A discrepancy indicates a symptom. General reasoning techniques as constraint satisfaction or truth maintenance can be used to derive diagnoses that explain the actual behaviour of the device using its model. Because the reasoning part is represented separately from domain knowledge, it can be reused for different domains. This paradigm of model-based diagnosis gave rise to the development of general approaches to diagnosis, such as ``constraint suspension`` [Davis, 1984], DART [Genesereth, 1984], GDE [de Kleer & Williams, 1987], and several extensions to GDE (GDE+ [Struss & Dressler, 1989], Sherlock [de Kleer & Williams, 1989]).
These assumptions are also necessary for the meta-level decision whether a diagnosis problem is given at all (i.e., whether there is an abnormality in system behaviour). This decision relies on a further assumption: the no-design-error assumption [Davis, 1984] which says that if no fault occurs, then the device must be able to achieve the desired behaviour. In other words, the discrepancy must be the result of a fault situation where some parts of the system are defect. It cannot be the result of a situation where the system works correctly, but cannot achieve the desired functionality because it is not designed for this. If this assumption does not hold, one has a design problem and not a diagnostic problem.
First, the localised-failure-of-function assumption: the device must be decomposable in well-defined and localised entities (i.e., a component) that can be treated as causes of faulty behaviour. Second, these components have a functional description that provides the (correct) output for their possible inputs. If this functional description is local, that is, it does not refer to the functioning of the whole device, the no-function-in-structure assumption [de Kleer & Brown, 1984] is satisfied. Several diagnostic methods can also use the reverse of the functional descriptions, thus, rules that derive the expected input from the provided output. If only correct functional descriptions are available, fault behaviour is defined as any other behaviour than the correct one. Fault behaviour of components can be constrained by including fault models, that is, functional descriptions of the components in case they are broken (cf. [de Kleer & Williams, 1989], [Struss & Dressler, 1989]). If one assumes that these functional descriptions are complete (the complete fault-knowledge assumption), then components can be considered innocent if none of their fault descriptions is consistent with the observed fault behaviour. A result of using fault models is that all kinds of non-specified behaviours of a component are excluded as diagnosis. For example, using fault models, it becomes impossible to conclude that a fault (one of two light bulbs is not working) is explained by a defect battery that does not provide power and a defect lamp that lights without electricity (cf. [Struss & Dressler, 1989]).
Further assumptions that are related to the functional descriptions of components are the no-fault-masking and the non-intermittency assumption. The former states that the defect of an individual or composite component, or of the entire device must be visible by changed outputs (cf. [Davis & Hamscher, 1988], [Raiman, 1992]). According to the latter, a component that gets identical inputs at different points of time, must produce identical outputs. In other words, the output is a function of the input (cf. [Raiman et al., 1991]). They argue that intermittency results from incomplete input specifications of components, but that it is impossible to get rid of it (it is impossible to represent the required additional inputs).
A third assumption underlying many diagnostic approaches is the no-faults-in-structure assumption (cf. [Davis & Hamscher, 1988]) that manifests itself in different variants according to the particular domain. The assumption states that the interactions of the components are correctly modelled and that they are complete. This assumption gives rise to three different classes of more specific assumptions. First, the no-broken-interaction assumption states that connections between the components work correctly (e.g. no wires between components are broken). If this is not the case, the assumption can be weakened by representing the connections themselves as components too. Second, the no-unexpected-directions assumption (or existence of a causal-pathway assumption) states that the directions of the interactions are correctly modelled and are complete. For example, a light-bulb gets power from a battery and there is no interaction in the opposite direction. The no-hidden-interactions assumption (cf. [Böttcher, 1996]) assumes that there are no non-represented interactions (i.e., closed-world assumptions on connections). A bridge fault [Davis, 1984] is an example of a violation of this assumption in the electronic domain. Electronic devices whose components unintendedly interact through heat exchange, is another example [Böttcher, 1996]. In the worst case, all potential unintended interaction paths between components are represented [Preist & Welhalm, 1990]. The no-hidden-interactions assumption is critical since most models (like design models of the device) describe correctly working devices and unexpected interactions are therefore precisely not mentioned. A refinement of this assumptions is that there are no assembly errors (i.e., every individual component works but they have been wired up incorrectly).
As shown by [McIlraith, 1994], the assumptions about the type of explanation relation (i.e., consistency versus derivability) and about the explanations (i.e., definition of parsimony) make also strong commitments on the domain knowledge (the device model) that is used to describe the system. If we ask for a consistent explanation with minimal sets of fault components (i.e., H1 < H2 if H1 assumes less components as being fault than H2), we need knowledge that constrains the normal behaviour of components. If we ask for a consistent explanation with minimal sets of correct components (i.e., H1 < H2 if H1 assumes less components as being correct than H2), we need knowledge that constrains the abnormal behaviour of components.
Figure 1 Assumptions for Effect
All these assumptions are necessary to relate a model of the device with the actual device under concern. ``There is no such thing as an assumption-free representation. Every model, every representation contains simplifying assumptions`` [Davis & Hamscher, 1988]. If the assumptions are too strong, one could consider weakening them. However, this raises another problem in model-based diagnosis, namely its high complexity or intractability. This will be discussed in the following section.
If the SFA has to be satisfied by the domain knowledge, then each possible fault has to be represented as a single entity. In principle this causes complexity problems for the domain knowledge as each fault combination (combination of fault components) has to be represented. However, additional domain knowledge can be used to restrict the exponential increase. [Davis, 1984] discusses an example of a representation change where a 4-fault case (i.e., 15 different combinations of faults) is transformed into a single fault. A chip with four ports can cause faults on each port. When we know that the individual ports never fail, but only the chip as a whole, a fault on four ports can be represented as one fault of the chip. Even without such a representation change, we do not necessarily have to represent all possible fault combinations. We can, for example, exclude all combinations that are not possible or likely in the specific domain (expert knowledge).
A drastic way to ensure that the minimality assumption holds, is to neglect any knowledge about the behaviour of faulty components. Thus, any behaviour that is not correct is considered as fault. A disadvantage of this is that physical rules may be violated (i.e., existing knowledge about faulty behaviour). We already mentioned the example provided in [Struss & Dressler, 1989], where a fault (one of two bulbs does not light) is explained by a broken battery that does not provide power and a broken bulb that lights without power. Knowledge about how components behave when they are faulty (called fault models) could be used to constrain the set of diagnoses derived by the system. On the other hand, it increases the complexity of the task. If for one component m possible fault behaviours are provided, this leads to m+1 possible states instead of two (correct and fault). The maximum number of candidates increases from 2n to (m+1)n.
A similar extension of GDE that includes fault models, is the Sherlock system (cf. [de Kleer & Williams, 1989]). With fault models, it is no longer guaranteed that every super-set of the faulty components that constitute the diagnosis, is also a diagnosis, and therefore the minimality assumption as such cannot be exploited. In Sherlock, a diagnosis does not only contain fault components (and implicitly assumes that all other, not mentioned, components are correct), but it contains a set of components assumed to work correctly and a set of components assumed to be fault. A conflict is now a set of some correct and fault components that is inconsistent with the provided domain knowledge and the observations. In order to accommodate to this situation, [de Kleer et al., 1992] extend the concept of minimal diagnoses to kernel diagnoses and characterise the conditions under which the minimality assumption still holds. The kernel diagnoses are given by the prime implicants of the minimal conflicts. Moreover, the minimal sets of kernel diagnoses sufficient to cover every diagnosis correspond to the irredundant sets of prime implicants of all minimal conflicts. These extensions cause drastic additional effort, because there can be exponentially more kernel diagnoses than minimal diagnoses, and finding irredundant sets of prime implicants is NP-hard. Therefore, [de Kleer et al., 1992] characterise two assumptions under which the kernel diagnoses are identical to the minimal diagnoses. The kernel diagnoses are identical to the minimal diagnoses if all conflicts contain only fault components. In this case, there is again only one irredundant set of minimal diagnoses (the set containing all minimal diagnoses). The two assumptions that can ensure these properties are the ignorance-of-abnormal-behaviour assumption and the limited-knowledge-of-abnormal-behaviour assumption.
A similar type of assumption is used by [Bylander et al., 1991] to characterise different complexity classes of component-based diagnosis. In general, finding one or all diagnoses is intractable. The independent and monotonic assumption, which have the same effect as the limited-knowledge-of-abnormal-behaviour assumption, require that each super-set of a diagnosis indicating a set of faulty components is also a diagnosis. In this case, the worst-case complexity of finding one minimal diagnosis grows polynomially with the square of the number of components. However, the task of finding all minimal diagnoses is still NP-hard in the number of components. This corresponds to the fact that the minimality assumption of GDE (i.e., the ignorance-of-abnormal-behaviour and limited-knowledge-of-abnormal-behaviour assumptions), that searches for all diagnoses, does not change the worst-case but only the average-case behaviour of the diagnostic reasoner.
Figure 2 Assumptions for Efficiency
Figure 3 The different elements of a specification of a knowledge-based system
The reasoning of a knowledge-based system can be described by a problem-solving method (PSM). A PSM consists of three parts. First, a definition of the functionality defines the competence of the PSM independent of its realisation. Second, an operational description defines the dynamic reasoning process. Such an operational description describes how the competence can be achieved in terms of the reasoning steps and their dynamic interaction (i.e., the knowledge and control flow). The third part of a PSM concerns assumptions about the domain knowledge. Each inference step requires a specific type of domain knowledge with specific characteristics. These complex requirements on the input of a problem-solving method distinguish it from usual software products. Preconditions on inputs (used in normal software to guarantee valid inputs) are in PSMs extended to complex requirements on available domain knowledge. A problem-solving method can only solve a complex task with reasonable computational effort by introducing assumptions. Such assumptions can work in two directions to achieve this result. First, they can restrict the complexity of the problem, that is, weaken the task definition in such a way that the PSM competence is sufficient to realise the task. Second, they can strengthen the competence of the PSM by the assumed (extra) domain knowledge. This is called the law of conservation of assumptions in [Benjamins et al., 1996]. In terms of dynamic logic [Harel, 1984], this law can be formulated as follows:
assumptions_{domain-knowledge} ([problem-solving method] assumptions_{task} goal)The formula states that, if the assumptions on domain knowledge hold in the initial state, then the problem-solving method must terminate in a state that fulfils the goals of the task, if the assumptions on the task are fulfilled. This formula could be weakened by either strengthening the assumptions on domain knowledge (i.e., the problem-solving method must behave well for less initial states) or strengthening the assumptions on the task (i.e., the problem-solving method must achieve the goal in less terminal states).
The description of the domain model introduces the domain knowledge as it is required by the problem-solving method and the task definition. Three elements are needed to define a domain model. First, a description of properties of the domain knowledge at a meta-level. The meta-knowledge characterises properties of the domain knowledge. It is the counterpart of the assumptions on domain knowledge made by the other parts of a KBS specification: assumptions made about domain knowledge by these parts, must be stated as properties of the domain knowledge. These properties define goals for the modelling process of domain knowledge in the case of knowledge acquisition. The second element of a domain model concerns the domain knowledge and case data necessary to define the task in the given application domain, and necessary to carry out the inference steps of the chosen problem-solving method. The third element is formed by external assumptions that link the domain knowledge with the actual domain. These external assumptions can be viewed as the missing pieces in the proof that the domain knowledge fulfils its meta-level characterisations.
The assumptions of the different parts of a KBS specification define their proper relationships and the adequate relationship of the overall specification with its environment. Their detection, verification, and validation is an important part for developing correct reasoning systems. In [Fensel et al., 1996], we used the Karlsruhe Interactive Verifier (KIV) [Reif, 1995], developed in the specifications. Besides verification, KIV was used to detect hidden assumptions which were necessary to relate the competence of a problem-solving method to the task definition. Hidden assumptions could be found by analysing failed proof attempts. The analysis of partial proofs gives some hints for the construction of possible counter examples, but also for repairing the proof by introducing further assumptions. These assumptions are the missing pieces in proofing the correctness of the specification. Verifying these specification is therefore a way to detect underlying hidden assumptions.
In [Fensel, 1995] we provided the analysis of the assumptions of one problem-solving method. In this paper we have provided a study of the role of assumptions used by a the group of problem-solving methods for model-based diagnosis. Model-based diagnostic systems were first introduced to overcome the limitations of heuristic systems. However, research on model-based systems revealed immediately that ``pure`` model-based diagnostic systems were too inefficient to be useful. Model-based diagnosis is in principle intractable, and in the last ten years, substantial effort has been devoted to optimise diagnostic algorithms in order to make them tractable. Assumptions can be viewed as the re-introduction, however controlled, of heuristics for reasons of efficiency. Looking at the history of model-based diagnostic systems in retrospect, we could describe it as follows: researchers have started with a general, but inefficient, model-based diagnostic reasoner, and then incrementally introduced and modified assumptions, until an efficient reasoner was achieved. This approach is strikingly similar to the assumption-driven development process of problem solvers recently put forward in the knowledge engineering community [Fensel & Straatman, 1996], where one starts with a general, but inefficient, specification of the reasoning process and gradually introduces and modifies assumptions until a efficient reasoner is achieved. In [Fensel et al., 1996] is shown how verification tools can be used to support the process of detecting and introducing assumptions of reasoning systems.
Acknowledgement. We would like to thank Annette ten Teije for guiding us through the literature on model-based diagnosis and for helpful comments on early drafts of the paper. Helpful comments were also provided by Claudia Böttcher, Bert Bredeweg, Joost Breuker, Kees de Koning, Remco Straatman, and anonymous reviewers.
R. Benjamins: Problem-Solving Methods for Diagnosis, PhD Thesis, University of Amsterdam, Amsterdam, the Netherlands, 1993.
R. Benjamins, D. Fensel, and R. Straatman: Assumptions of Problem-Solving Methods and Their Role in Knowledge Engineering. In Proceedings of the 12. European Conference on Artificial Intelligence (ECAI-96), Budapest, August 12-16, 1996.
R. Benjamins and C. Pierret-Golbreich: Assumptions of Problem-Solving Method. In N. Shadbolt et al. (eds.), Advances in Knowledge Acquisition, Lecture Notes in Artificial Intelligence (LNAI), no 1076, Springer-Verlag, Berlin, 1996.
C. Böttcher: No Faults in Structure? - How to Diagnose Hidden Interactions, 1996.
C. Böttcher and O. Dressler: A Framework For Controlling Model-Based Diagnosis Systems with Multiple Actions, Annals of Mathematics and Artificial Intelligence, 11:241-261, 1994.
T. Bylander: Complexity Results for Planning. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI-91), Sydney, Australia, August 1991.
T. Bylander, D. Allemang, M. C. Tanner, and J. R. Josephson: The Computational Complexity of Abduction, Artificial Intelligence, 49: 25-60, 1991.
B. Chandrasekaran: Models versus rules, deep versus compiled, content versus form, IEEE-Expert, 6(2): 75--79.
L. Console and P. Torasso: A Spectrum of Logical Definitions of Model-Based Diagnosis. In W. Hamscher et al. (eds.), Readings in Model-based Diagnosis, Morgan Kaufman Publ., San Mateo, CA, 1992.
R. Davis: Diagnostic Reasoning Based on Structure and Behavior, Artificial Intelligence, 24: 347-410, 1984.
R. Davis and W. Hamscher: Model-based Reasoning: Troubleshooting. In H. E. Shrobe (ed.), Exploring AI: Survey Talks from the National Conference on AI, Morgen Kaufman, San Mateo, CA, 1988.
D. Fensel: Assumptions and Limitations of a Problem-Solving Method: A Case Study. In Proceedings of the 9th Banff Knowledge Acquisition for Knowledge-Based System Workshop (KAW-95), Banff, Canada, February 26th - February 3th, 1995.
D. Fensel, A. Schönegge, R. Groenboom and B. Wielinga: Specification and Verification of Knowledge-Based Systems. In Proceedings of the ECAI-96 Workshop Validation, Verification and Refinement of Knowledge-Based Systems, at the 12th European Conference on Artificial Intelligence (ECAI-96), Budapest, 12.-16. August 1996. See also: Proceedings of the 10th Banff Knowledge Acquisition for Knowledge-Based System Workshop (KAW-96), Banff, Canada, November 9-14, 1996
D. Fensel und R. Straatman: The Essence of Problem-Solving Methods: Making Assumptions for Efficiency Reasons. In N. Shadbolt et al. (eds.), Advances in Knowledge Acquisition, Lecture Notes in Artificial Intelligence (LNAI), no 1076, Springer-Verlag, Berlin, 1996.
M. R. Genesereth: The Use of Design Descriptions in Automated Diagnosis, Artificial Intelligence (AI), 24:411-436, 1984.
A. Goel, N. Soundararajan, and B. Chandrasekaran: Complexity in Classificatory Reasoning. In Proceedings of the 6th National Conference on Artificial Intelligence (AAAI-87), Seattle, Washington, July 13-17, 1987.
D. Harel: Dynamic Logic. In D. Gabby et al. (eds.), Handbook of Philosophical Logic, vol. II, Extensions of Classical Logic, Publishing Company, Dordrecht (NL), 1984.
J. de Kleer and J. S. Brown: A Qualitative Physics Based on Confluences, Artificial Intelligence, 24:7-83, 1984.
J. de Kleer, A. K. Mackworth, and R. Reiter: Characterizing Diagnoses and Systems, Artificial Intelligence, 56, 1992.
J. de Kleer and B. C. Williams: Diagnosing Multiple Faults, Artificial Intelligence, 32:97-130, 1987.
J. de Kleer and B. C. Williams: Diagnosis with Behavioral Modes. In Proceedings of the 11th International Joint Conference on AI (IJCAI-89), Detroit, MI, 1989.
E. J. McCluskey: Minimizing of Boolean Functions, Bell Systems Technology Journal, 35(5):1417-1444, 1956.
S. McIlraith: Further Contribution to Characterizing Diagnosis, Annals of Mathematics and AI, special issues on model-based diagnosis, 11(1-4), 1994.
B. Nebel: Artificial intelligence: A Computational Perspective. To appear in G. Brewka (ed.), Essentials in Knowledge Representation.
W. Nejdl, P. Froehlich and M. Schroeder: A Formal Framework For Representing Diagnosis Strategies in Model-Based Diagnosis Systems. In Proceedings of the 14th International Joint Conference on AI (IJCAI-95), Montreal, Canada, August 20-25, 1995.
C. Preist and B. Welham: Modelling Bridge Faults fo Diagnosis in Electronic Circuits. In Proceedings of the 1st International Workshop on Principles of Diagnosis, Stanford, 1990.
O. Raiman: Diagnosis as a Trial. In Proceedings of the Model Based Diagnosis International Workshop, Paris, 1989.
O. Raiman: The Alibi Principle. In W. Hamscher et al. (eds.), Readings in model-based diagnosis, Morgan Kaufmann Publ., San Mateo, CA, 1992.
O. Raiman, J. de Kleer, V. Saraswat, M. Shirley: Characterizing Non-Intermittent Faults. In Proceedings of the 9th National Conference on AI (AAAI-91), Anaheim, CA, July 14-19, 1991.
W. Reif: The KIV Approach to Software Engineering. In M. Broy and S. Jähnichen (eds.): Methods, Languages, and Tools for the Construction of Correct Software, Lecture Notes in Computer Science (LNCS), no 1009, Springer-Verlag, Berlin, 1995.
R. Reiter: A Theory of Diagnosis from First Principles, Artificial Intelligence, 32:57-95,1987.
J. Sticklen, B. Chandrasekaran, and W.E. Bond: Applying a Functional Approach for Model Based Reasoning, Proc. of (IJCAI) Workshop on Model Based Reasoning, Detroit, 1989,
P. Struss: Diagnosis as a Process. In W. Hamscher etal. (eds.), Readings in Model-based Diagnosis, Morgan Kaufman Publ., San Mateo, CA, 1992.
P. Struss and O. Dressler: ``Physical Negation`` - Integrating Fault Models into the General Diagnostic Engine. In Proceedings of the 11th International Joint Conference on AI (IJCAI-89), Detroit, MI, 1989.
A. ten Teije and F. Van Harmelen: Using reflection techniques for flexible problem solving (with examples from diagnosis), Future Generation Computer Systems, to appear 1996.