A Formal Framework for Representing Diagnosis Strategies in Model-Based Diagnosis Systems
Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Qualitative Reasoning and Diagnosis. Pages 1721-1726.
© 1995 International Joint Conferences on Artificial Intelligence
Abstract
Rece nt work has point ed out that diagnosis strategies are a necessary tool for the diagnosis of comp lex systems. Nevertheless, though current diagnosis systems are able to use exp li cit system models, their representation of diagnosis strategies is only implicit . In this paper we introduce a formal meta- language to express strategic knowledge in an explicit way. This language is sufficient to formalize all strategies introduced in previous work, and extends previous diagnosis strategies by the integration of empirical knowledge and by explicit statements about dependencies between actions. We provide a declarative semantics for this language and an architecture for implementation.
- C. Bottcher and 0 . Dressler. Diagnosis process dy- namics: Holding the diagnostic trackhound in leash. In Proceedings of the International Joint Conference on Artificial Intelligence, volume 2, pages 1460-1471. IJCAI
- C . Bottcher and 0. Dressler . A framework for con- trolling model-based diagnosis systems with multi- ple actions . Annals of Mathematics and Artificial Intelligence, special Issue on Model-based Diagnosis, 11(1 -4), 1994.
- C. V. Damasio, W. Nejdl, L. Pereira, and M. Schroeder. Model-based diagnosis preferences and strategies representation with meta logic program- ming. In K . R . Apt and F. Turini, editors, Meta- logics and Logic Programming, chapter 11, pages 269-311. The MIT Press, 1995.
- C . V. Damasio, L. M. Pereira, and W. Nejdl. Revise: An extended logic programming system for revising knowledge bases. In Proceedings of the International Conference on Principles of Knowledge Representa- tion and ReCisoning, pages 607-618, Bonn, Germany, May 1994.
- J. de Kleer and B. C. Williams. Diagnosing multiple faults. Artificial Intelligence, 32:97-130, 1987.
- P. Frohlich, W . Nejdl, and M. Schroder. A formal se- mantics for preferences and strategies in model-based diagnosis. In 5th International Workshop on Prin- ciples of Diagnosis (DX-94), pages 106-113, New Paltz, NY, Oct. 1994.
- R . Reiter. A theory of diagnosis from first principles. Artificial Intelligence, 32:57-95 , 1987.
- P. Struss. Diagnosis as a process . In W . Ham- scher, L. Console, and J. de Kleer, editors, Readings in Model-Based Diagnosis, pages 408-418 .
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
In order to handle the complexity of large-scale diag nosis we have to use more than one system model and see diagnosis as a dynamic process controlled by diag nosis assumptions made explicit as working hypotheses (as formalized first by Struss in [8]) . In the same spirit Boettcher and Dressler {[1], [2]} developed a catalogue of diagnosis strategies and proviqed an intuitive semantics and an ATMS-based implementation for these strate gies. The disadvantage of their approach is that they use a static set of strategies which is coded into the diagnosis algorithm. Missing a declarative semantics for these di agnosis strategies independent of a particular implemen tation makes the definition of new or application-specific strategies more difficult than it should be.
In this paper we extend this approach by introducing a formal meta-language for the definition of diagnosis strategies. This language makes strategies explicit and allows to define strategies specific to an application simi lar to defining system models . So our framework extends model- based diagnosis in the sense that not only the be havior of the system but also the strategic knowledge about the system model is represented explicitly.
2 Working Hypotheses
We consider a system described by a set of formulas S D in a language£. An observation OBS of the system SD
is a finite set of formulas in £. C is a first order language with equality. For simplicity we postulate that £ con tains no function symbols with variable interpretation. Functions with standard interpretation like mathemati cal operators etc. are allowed. By ATOMS we denote the set of atoms of C. Our theory does not depend on a particular diagnosis definition. We encapsulate the underlying diagnosis concept by a function diag, which maps a theory T to a set of diagnoses 7J:
This general definition allows for a wide range of diag nosis concepts like minimal diagnoses [7], most probable diagnoses [5], preferred diagnoses [4] and others.
Struss introduced the concept of working hypotheses into model-based diagnosis in order to make diagnostic assumptions explicit [8] . The diagnostic assumptions are necessary in the diagnostic process for evaluating hier archies, using simplified behavioral models , focusing on a particular kind of diagnoses, etc.
Definition 2.1 Working Hypothesis
Let WHY P ~ ATOMS(£) be a set of atoms. We call each ground atom wh E WHY P a Working Hypothesis.
We name the general set of working hypotheses WHY P, a subset W H and elements of theses sets wh . Working Hypotheses can be used to represent multiple models of the system within one system description as is shown by the following example.
Example 2.2 Use of Working Hypotheses

A component C consists of the subcomponents C1 , ... C3 . The working hypothesis refine( C) can be used to switch between the abstract model of C and the detailed model of c in which its subcomponents cl, ... c3 are visible. In the system description SD for some de vice containing C the behavior of C is modeled depending on refine(C):
c ~
·refine( C) -+ Rules for the abstract model of C re fin e( C) -+ Rules for the detailed model of C
Now if we want to compute the diagnoses for the sys tem based on the detailed model of C we add refine( C) to the system description, i.e. we compute diag(SD U OBS U {refine( C)}) .
In general, to compute the diagnoses under a set of working hypotheses W H we add W H to the sys tem description. Additionally we add { -,whl wh E WHY P\W H}, i.e. we make sure that W His exactly the set of working hypotheses which are true in the sys tem model.
Definition 2.3 Diagnosis under a Set W H of Working Hypotheses
Consider a system described by (SD, COM PS, OBS) , where SD is the system description, COM PSis the set of the system components and OBS is c1 set of obser vations. Let W H be a set of Working Hypotheses. Let W H = WHY P\ W H. Then the set of diagnoses un der working hypotheses W H , called diagw H is defined as follows:
We include the set W H itself in the diagnosis, so that it is obvious from the diagnoses to which system model they belong. So diagw H provides a valid diag nosis concept as SD U OBS U D is consistent , where DE diagwH(SD U OBS) .
Working hypotheses are an important concept for making the current diagnosis assumptions explicit. But the selection of suitable working hypotheses for a given situation is implicit in current diagnosis systems. In the next section we introduce a language that makes the knowledge for selecting the right hypotheses explicit and thus provides a flexible and declarative way of specifying strategic knowledge for the diagnostic process .
3 A Formal Language for Strategies
3.1 Preliminary Considerations
Diagnosis strategies control the diagnostic process by specifying which diagnosis assumptions should be used in a given situation. The state of the diagnostic process manifests itself in the current set of possible diagnoses. Thus the specification of a diagnosis strategy consists of
- a property of the current set of diagnoses, character izing a certain situation that can occur during the diagnostic process
- an assumption or action modeled by a working hypothesis that is suitable for handling that situation
Example 3.1 Diagnosis Stmtegy
Consider an abstract component C as described in ex ample 2.2. By default, we only use the abstract model of this component for diagnosis, i.e. -,refine( C) is used as working hypothesis. The detailed model is only used when C is identified as faulty. This can be captured by the following rule:
If an abstract component C occurs in all di agnoses, activate a more detailed model for C

making its subcomponents visible to the diag nostic process.
In order to check if a given strategy should be applied we have to evaluate a condition on the current set of diagnoses. Such a condition cannot be modeled as part of the system description. So Boettcher and Dressler implement the check of these conditions as part of the diagnosis system.
However, the only flexible way of evaluating these con ditions is by introducing a meta-level in the diagnosis system as shown in figure 1. So the strategies are de fined on the meta level and they are evaluated using the knowledge obtained so far during the diagnostic process which is represented by the current possible diagnoses.
So diagw H ( S D U 0 B S) as defined in the previous section is the information on which the decisions on the meta-level are based . For some strategies it is not sufficient to have information about the faulty compo nents only. For example, one necessary precondition for proposing a measurement point is that the value at that point is not known . To evaluate this condition we need to extend the diagnoses by the values predicted in the corresponding system models. So we postulate that diagwH(SD U OBS) contains all predicates needed by the preconditions of the diagnosis strategies.
3.2 ·The Meta Language
The language .Cstrat for defining diagnosis strategies de fines modal logic operators specifying properties of the current diagnoses as well as for proposing working hy potheses. Before we give a formal definition of the lan guage we motivate the need for these modal operators informally.
Modal Operators for Characterizing the Current State of the Diagnostic Process:
As already stated the preconditions for the application of diagnosis strategies are statements about the current set of possible diagnoses. The atomic statements in these conditions are:
- a property p(x) is true under all possible diagnoses, or
- a property p( x) is true under at least one possible diagnosis.
These statements can be formalized using the usual S5 modal operators (0 for knowledge, 0 for belief):
Op p is true under all diagnoses of S D U 0 B S U W H.
Op p is true under at least one diagnosis of SD U OBSUWH.
Modal Operators for Proposing Working Hypotheses
Strategy formulas specify which working hypotheses should be assumed in a given situation. This is achieved by the following (informally described) modal operators:
- ·owh wh is a necessary working hypotheses in the current situation, i.e. the diagnostic process cannot be continued without assuming wh.
- +Dwh wh is a possible (allowed) working hypotheses in the current situation.
Actions can also be expressed in this approach by us ing a restricted form of procedural attachment in the system description. For example, we have a working hypotheses measure(x) for proposing a measurement. The measurement itself is then implemented by a pro cedure get_value, which executes the measurement and remembers the value. The combination of the two con cepts is modeled by a rule
in the system description. Thus, from the logical view point, the only effect of the predicate get_ value is that it tests if v is the value of x. Our language allows to ex plicitly represent dependencies between actions, e.g. it is possible to express that action a is to be preferred over action b if both are possible (see section 5).
Syntax of Cstrat
Besides the modal operators Cstrat contains the usual logical connectives and quantifiers. In the following def initions we only consider V, -., 1\ since this is already a complete set.
Definition 3.2 Cstrat-Formula
- Let L be a formula in the language£. Then DL and 0 L are Cstrat -Formulas.
- Let S be a Cstrat-Formula, then +S and ·s are Cstrat -Formulas.
- Let S1, S2 be Cstrat-Formulas. Then also -..'~h and S1 1\ S2 are Cstrat-Formulas.
- 4- Let v1, v2 be variables. Then v1 = v2 is an Cstrat Formula
- Let v be a variable, S an Cstrat -Formula. Then Vv : S is an Cstrat-Formula.
- Nothing else is an Cstrat - Formula.
Note, that Cstrat has the same predicate symbols and constants as the system description language £. The variables denote objects of £. This will be ensured in the formal semantics presented in the next section. The following is an example for a strategy formula:
Example 3.3 Cstrat-Formula for Structural Refine ment
For component C the strategy "Structural Refinement" can be expressed by the strategy formula
By introducing a predicate refinable(c) in the system description, which is true for all components that have subcomponents, we can generalize this rule:
More examples for the formalization of diagnosis strategies can be found in section 5. In the next sec tion we define the declarative semantics for the strategy language.
4 Declarative Semantics for Strategies
We consider a diagnosis problem that is now described by
where SD is the system description, ST RAT is a set of Cstrat-Formulas, COM PSis a set of components and OBS is a set of observations.
Diagnosis strategies are used to guide the diagnostic process. The semantics introduced in this section an swers two questions:
- What are the possible sequences of diagnostic de cisions implied by the given diagnosis strategies, i.e. which diagnostic process is consistent with re spect to the given strategies STRAT (and with SD, COMPS, OBS)?
- Which diagnoses are the result of such a consistent diagnostic process?
4.1 Characterization of the Diagnostic Process
The state of the diagnostic process can be characterized by a set of working hypotheses. Then, given SD U OBS the diagnoses can be inferred by applying diagw H.
The diagnostic process as a whole can be characterized by specifying which states can be adopted or which tran sitions between states are considered. We will therefore define a state transition relation as follows:
Definition 4.1 State Tmnsition Relation
A State Transition Relation is a binary relation R ~ 2 WHY P x 2 WHY P, i.e. a relation among sets of working hypotheses.
In the next example we show how a diagnostic process can be encoded by a state transition relation:
Example 4.2 Diagnostic Process

Suppose we have two components C1 and C2 , each hav ing a structure as used in example 2.2. For this sys tem we use strategies for structural refinement and a measurement strategy that proposes Y as a measurement point if its value is unknown. Having made some obser vation we start the diagnosis in the most abstract model without assuming any hypotheses. A look at the result ing diagnoses reveals that we do not know the value of y and so we cannot say whether C1 or C2 is faulty. So we measure the value of Y, i.e. we adopt the hypothesis measure(Y) and compute the diagnoses again. Now we identify C2 as the faulty component. Therefore we look at a more detailed model of c2 to find out which subcom ponent of C2 caused the error. So we additionally adopt the hypothesis refine(C2)· After recomputing the diag noses we know that C22 is the faulty component. This diagnostic process can be characterized by the following state transition relation n:
The first element of n denotes that in the state described by the empty set of working hypotheses we adopted the hypothesis measure(Y) which caused a mea surement. After measuring we additionally considered the hypothesis refine( C2 ). The termination of the diag nostic process in the state { measure(Y), refine( C2)} is modeled by the cycle in that state.
The course of the diagnostic process need not be linear. If we had also considered refining component C1 instead of making the measurement, we would character·ize the diagnostic process by
So, the state transition relation is just an encod ing of the working hypotheses we used in each step of the diagnostic process and is influenced by the diag noses found and the strategies given. In the declar ative semantics we judge whether or not a diagnos tic process (represented by a state transition relation) is correct wrt a diagnosis problem characterized by (SD, STRAT, COM PS, OBS).
The procedural semantics which is only briefly dis cussed in this paper computes correct diagnostic pro cesses based on this semantics. The user of the diagnosis system only has to provide the system description and the strategies.
In order to check if the decisions made during the eli agnostic process are consistent with the given diagnosis problem, we define how strategies can be interpreted as statements about the diagnostic process. First we de fine logical structures which provide the interpretation for the strategies.
Definition 4.3 LStrat-Model
A model for Lstrat is a structure M = (W, D, R1, R2, F), where W is a set of individuals (called worlds), D is c1 domain of individuals, R1 and R2 are accessibility rela tions on the worlds, i.e. subsets of W x W and F is an interpretation function.
F provides the interpretation for predicates and ground terms (in our case all ground terms are con stants). The values of the variables are given by an assignment:
Definition 4.4 Assignment
Given a domain D an Assignment is a mapping from the set of variables into D. By a(xld} we denote the assign ment that maps variable x to an element d E D and zs defined in the same way as a on the other variables.
The semantics of an £strat-Mode1 is defined as fol lows:
Definition 4.5 Semantics of LStrat
Let M = (W, D, R1, R2, F) be an £strat-model, S, S1, S2 LStrat-Formulas, L an £-Formula, a an assignment and wE W. Let
We will use the following abbreviations:
M f=w S
iff M Fw,a S for every assignment a .
M f= STRAT iff M f= S for every S E STRAT
M f= S
iff M Fw S for every w E W
The connection between the state transition relation and the £strat-mode1 is established in the following way: The possible diagnoses are interpreted as possible worlds, where all the diagnoses under one set of working hy potheses are connected wrt. the 0-operator (relation R2). The accessibility relation for the ·-Operator (re lation Rt) is given by the state transition relation n, i.e. diagnoses under different working hypotheses are connected by R1 iff the underlying sets of working hy potheses are connected by n.
Definition 4.6 Induced Lstrat -Model Mn
Let n be a state transition relation. For W H ~ WHY P let { M w H, 1 , . . . Mw H,mw H} be the set of models obtained from the system description, the observations and the diagnoses in diagwH(SD U OBS), where mwH is the number of diagnoses. If diagwH(SD U OBS) = 0, then mw H = 0. The Induced LStrat-Model Mn is defined as Mn = (Wn,Dn,Rk,R~,Fn), where
U { l_}, i.e. for every diagnosis under a set of working hypotheses W H ~ WHY P there is a world. There is one world l_ representing the inconsistent states (an inconsistent state is a state, where diagwH(SD U OBS) = 0).
Dn =CONST(£), the set of constants of the lan guage£.
u {(1., 1.)}
That means the accessibility relation on the di agnoses under different sets of working hypothe ses is given by the state transition relation n. Note, that the inconsistent world is a dead end, i.e. no other world is accessible from l.
- U {(1., 1.)}, that is, all diagnoses under the same set of working hypotheses are connected.
Fn : Interpretation of predicate P of arity n:
The semantics just defined is a correct formalization of the concepts we introduced in section 3 as is summarized by the following proposition.
Proposition 4. 7 Properties of the semantics Let L E £ be a formula , whEW HY P a working hypoth esis, n a state transition relation and W H ~ WHY P a set of working hypotheses. Then
Mn F=w H DL, iff L is true under all diagnoses in diagwH(SD U OBS)
Mn FWH ()L, iff L is true in at least one diag nosis in diagwH(SD U OBS)
- Mn F=w H ·owh, iff For all W H' ~ WHY P with W HR W H': wh is true under all diagnoses in diagw H' (SDU OBS)
- Mn f=w H +Dwh , iff There is at least one W H' ~ WHYP, s. th. WHRWH' and wh is true under all diag noses zn diagwH·(SDUOBS).
If a working hypothesis wh is known to be derivable under any diagnosis, then we want to conclude that wh has to be part of the current state. Formally, we want to garantee that M-t f=w H Owh implies wh E W H.
Problems occur if working hypotheses influence each other on the level of the system description . Assum ing the system description contains a rule wh' -+ wh, the strategy formula Owh is satisfied if either wh' or wh is part of the current state. This is a disadvan tage as the different levels of the system description and the strategies are mixed. The strategy formula Owh' -+ Owh expresses the same on the strategy level as wh' -+ wh does on the Ievie of the system description. The advantage of the strategy formula is that the for mula Owh A (Dwh' -+ Owh) can only be satisfied if wh is part of the current state. In the remainder we assume that working hypotheses do not interfere.
Definition 4.8 No interference
Let -+ be a transition relation. Working hypotheses do not interfere each other, if
To conclude the definition of the semantics we answer the first question posed at the beginning of this section. We can now characterize the diagnostic processes: A di agnostic process is consistent with the underlying strate gies if its transition relation satisfies the semantics.
Definition 4.9 Consistent Transition Relation Let (SD,STRAT,COMPS,OBS) be the description of a diagnosis problem. Let the transition relation n be the encoding of the diagnostic process. n is a Con sistent Transition Relation for the given problem, iff Mn f= STRAT.
Example 4.10 Consistent State Transition Relation The state transition relation n in example 4.2 is con sistent wrt. the given problem. Consider for ex ample the transition from the state { measure(Y)} to {measure(Y), refine(C2)}: In the strategy for struc tural refinement we say that a component should be re fined, if it is known to be abnormal:
Since C2 is refinable and known to be abnormal, this strategy formula postulates that it is refined in all states reachable from the current state. This strategy formula is satisfied by n, because the only transition we consider is to the state {measure(Y), refine(C2)} . The measure ment strategy
is also satisfied by R. because we know the value ofY and consequently the left side of this rule is not true.
4.2 Results of the Diagnostic Process
So far we characterized which state transitions are al lowed during the diagnostic process. In example 4.2 the diagnostic process terminated after a unique diagnosis was identified. In general this would be a too restrictive criterion for terminating the diagnostic process because we might not have enough knowledge to discriminate among all the diagnoses. Therefore we define, that the diagnostic process terminates in a state where we already assume all the hypotheses supported by the strategy for mulas, because in that situation we cannot reach a more preferred state by applying another strategy.
Definition 4.11 Stable State
Let W H ~ WHY P be a set of working hypotheses, n a consistent state transition relation and ST RAT a set of strategy formulas . The state characterized by W H (diagwH(SD U OBS)) is a stable state wrt. n, iff
- diagwH(SD,OBS) # 0
Note, that the underlying transition relation is consis tent. The first condition states that SD U OBS U W H is consistent and the second condition is a fixpoint con dition : W H is already the set of all working hypotheses suitable for the state described by W H. For complexity reasons we want the set W H to be as small as possible.
This will be discussed in section 4.4. The result of the di agnostic process is given by the diagnoses corresponding to the stable states:
Definition 4.12 Result of the Diagnostic Process Let (SD, STRAT, OBS, COM P) be a diagnosis prob lem. Let R be a consistent state transition relation for this problem. Then

is the result of the diagnostic process described by R.
Now we are going to show that for a big subclass of the strategies that is suitable for specifying all the strategies presented in this paper, we can guarantee that the di agnostic process will reach a stable state if the system description is not contradictory in itself.
4.3 Monotonicity
By monotonicity, we mean that on each transition in the diagnostic process we only add some new working hypotheses to the set of hypotheses we already assume.
Definition 4.13 Monotonicity of a State Transition Relation
A state transition relation R is monotonic, iff WHRWH' implies WH ~ WH'
We want the effect of strategies to be persistent, un less this leads to inconsistency. When applying struc tural refinement, we do not want to switch back to the abstract model we already used. When applying a focus ing assumption we want to keep this assumption until we have either found a diagnosis, or we know that this as sumption leads to inconsistency. Even actions like mea surements can be described in a monotonic way by a hypothesis which has the effect that we know the mea sured value of a component c. Our meta-language is powerful enough to express the monotonicity of a set of strategies by adding additional formulas.
Definition 4.14 Monotonic Extension of a Set of Strategies
Let ST RAT be a set of strategies. The monotonic ex tension M on(ST RAT) of ST RAT is defined as follows:
Lemma 4.15 Let ST RAT be a set of strategy for mulas, R a state transition relation. Then Mn f= M on(ST RAT) implies R monotonic
Proof: (by contradiction) Suppose we have Mn f= Mon(STRAT), but for some WH, WH' we have W HRW H' and W H' is no superset of W H, i.e. 3wh : wh E WH\WH'. As wh E WH, we have Mn f=w H Ow h. As M on(ST RAT) is satisfied we con clude that Mn f=w H ·owh and as W HRW H' we know Mn f=w H' Ow h . Because working hypothesis do not interfere each other we have wh E W H'. This is a con tradiction to the choice of wh.
For monotonic strategies we have the property that every path of the diagnostic process terminates, i.e. it leads to a stable or inconsistent state:
Theorem 4.16 Termination of the Diagnostic Process Let ST RAT be a set of strategy formulas and R a tran sition relation, such that Mn f= Mon(STRAT). Then every transition sequence guided by R leads into a stable or inconsistent state.
Proof: WHY P is finite and R is monotonic. So if we only add hypotheses in each step we will reach a fixpoint (WHY Pin the worst case).
4.4 Minimality
The diagnostic process shall be guided by the strategies. Only the hypotheses necessary to satisfy the strategies shall be assumed in each step. This is captured by the concept of local minimality. We first define a notation for the working hypotheses entailed by the strategies wrt. our declarative semantics.
Definition 4.17 Supported
Let R be a state transition relation and W H ~ WHY P.
The set suppor·ted(W H, R) denotes the hypotheses as sumed in at least one of the successor states.
Proposition 4.18 wh E supported(W H, R), iff for at least one W H': W HRW H' 1\ whEW H'.
Definition 4.19 Locally Minimal
A state transition relation R is locally minimal, iff
- R is consistent.
- For every set of working hypotheses W H, supported(W H, R) is a minimal set of hy potheses, i. e. there is no consistent R', such that supported(W H, R') C supported(W H, R).
5 Examples of Strategies
First we give the formalization of some additional strate gies introduced by Boettcher and Dressler [2].
5.1 Behavioral Refinement
Behavioral Refinement is useful if we have behavioral models at different levels of detail for a component C. For complexity reasons we initially use the simplest model available. But when different diagnoses predict different behavioral modes for C, we activate a more de tailed model for C's behavior in order to discriminate between these diagnoses. This can be expressed by
In the system description, ref _fm( C) activates the de tailed behavioral model for a component C.
5.2 Physical Negation
If a behavioral model other than the unknown mode can be assigned to a component C, we do not consider the unknown mode (i.e. we assume the specified fault models are complete).
If fm-complete is active for a component C, we can assure that C is assigned a known fault mode by adding the following rule to the system description:
Vc fm_complete(c) --t (ok(c) V 3m: (mode(m, c) 1\ m #unknown))
Our approach allows to formalize all other strategies presented by Boettcher and Dressler as well. However in some cases we find it more appropriate to express them by preferences on diagnoses (see [6] for a discussion of this issue). The next strategies are completely new ones.
5.3 Integrating Heuristic Knowledge into Model-Based Diagnosis
Consider an electronic device, where a single chip con tains a number of gates (e.g. and-gates). Assume we have n such chips. From experience we know that a diag nosis containing two and-gates on different chips is much less likely than a diagnosis containing two and-gates on the same chip, as the latter can be explained by a sin gle cause that damaged the whole chip. Such heuristic knowledge is easy to describe in our strategy language. We use location(A, C) to denote that component A is located on chip C. The heuristic assumption expressing our belief that all faulty and-gates are on one chip is represented by the working hypothesis focus_chip . The effect of this assumption is expressed in the system de scription as follows :
The following strategy specifies that the hypothesis focus_chip should be assumed if consistent :
(31: Vc: O((type(c, And_gate) 1\ ab(c)) --t location(a, l))) --t +Dfocus_chip
Using +Dfocus_chip instead of ·Dfocus_chip allows us to explore states not containing Dfocus_chip.
5.4 Measurements and Dependent Actions
If different consistent models· of the system predict dif ferent values for some measure point X we can discrimi nate between these values by making a measurement, as represented by the following strategy rule
Vx: ()val(x, 1) 1\ ()val(x, 0) --t +Dmeasure(x)
Since measurements require interaction with the user, we want to express that measurements should only be made when no other strategies are available.
In some situations, more than one assumption is sup ported at the same time . .Cstrat allows to explicitly spec ify that a working hypotheses wh should only be consid ered, if wh' is not supported . For example the follow ing formulas specify the strategies structural refinement and measurements so that measurements are only per formed, if all useful structural refinements have already been considered.
Vc: (Drefinable(c) 1\ Dab( c) --t ·orefine(c)) Vc: (Drefinable(c) 1\ O·ab(c) --t ·+Drefine(c)) Vx : ( ()val(x, 0) 1\ ()val(x, 1)) /\(Vc: +Drefine(c) --+ Drefine(c)) --t ·omeasure(x)
Since we only consider minimal models of these formu las, measure(x) will only be assumed if all the conditions on the left side of the last formula are satisfied.
6 Conclusion and Further Work
This paper defines the concept of diagnosis strategies us ing a modal logic language that makes strategic knowl edge explicit. Our approach allows not only to express system models in a declarative way (which is one of the main advantages of model-based diagnosis), but ex tends this declarativity to the meta level by allowing the declarative description of diagnosis strategies.
We are currently working on an efficient implementa tion of the formal concepts introduced in this paper us ing transformations of our meta- language into first order logic and minimal model semantics within our DRUM diagnosis system.
Finally, we want to thank Carlos Damasio and Luis Pereira for their fruitful cooperation within the INIDA project on the topics discussed in this paper and in a companion paper ([3]).
@inproceedings{ijcai1995p221,
title = {A Formal Framework for Representing Diagnosis Strategies in Model-Based Diagnosis Systems},
author = {Nejdl, Wolfgang and Fröhlich, Peter and Schroeder, Michael},
booktitle = {Proceedings of the Fourteenth International Joint Conference on
Artificial Intelligence, {IJCAI-95}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Chris S. Mellish},
pages = {1721--1726},
year = {1995},
note = {Qualitative Reasoning and Diagnosis},
url = {https://ijcai.org/proceedings/1995/221},
}
TY - CPAPER TI - A Formal Framework for Representing Diagnosis Strategies in Model-Based Diagnosis Systems AU - Nejdl, Wolfgang AU - Fröhlich, Peter AU - Schroeder, Michael T2 - Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95 PB - International Joint Conferences on Artificial Intelligence PY - 1995 SP - 1721 EP - 1726 UR - https://ijcai.org/proceedings/1995/221 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: