Diagnosis, i.e., fault localization in case of observing an unexpected behavior, is an important practical problem. During the past decades researchers have suggested several approaches for using models of the systems directly for identifying the root causes of failure. This model-based diagnosis approaches are either based on retaining consistency or on abduction. Despite their advantages both approaches are only rarely used in practical applications. In this paper, we focus on bringing abductive diagnosis closer to its application. In particular, we describe how failure mode and e ect analysis, a technique of growing interest in applications, can be directly mapped to abductive diagnosis models. We discuss the basic foundations, and also problems that occur and how to deal with them. A direct conversion of FMEAs to abductive diagnosis problems would increase the use of abduction in practice because of avoiding writing logical theories directly.
Diagnosis as the task for identifying root causes explaining observations has been
gaining lot of attention since the beginnings of Arti cial Intelligence. The rst
diagnosis approaches like MYCIN [
More recently, industry uses more and more often failure mode and e ect
analysis (FMEA) [11, 17] as a framework for identifying critical faults that might
occur. There the main focus is on the consequences of faults for the system's
behavior. FMEA are most often used for reliability analysis but also for other
purposes like measuring diagnostic coverage [
Given the growing importance of FMEAs or similar analysis methods in industry and a growing demand for automated fault localization, the question is whether FMEAs can be directly used for the purpose of fault localization. It is worth mentioning that currently FMEAs are most often used for reliability analysis and not for fault localization. The main objective of this paper is to discuss the use of FMEAs for automated fault localization, which of course requires a FMEA to comprise essential information, i.e., at least the modes of replaceable parts responsible for e ects and a description of e ects, which can be observed. In particular, we show how adductive reasoning can be used for fault localization. Hence, in all cases where FMEAs are available that t our purpose, we are able to use abductive diagnosis for practical applications, which widens the use of abductive reasoning in practice.
This paper is organized as follows. We rst discuss the FMEA. For this purpose we introduce a small example that is going to be used in the rest of this paper. Afterwards, we brie y recall the basic de nitions of abductive diagnosis. Finally, we show how FMEAs are mapped to abductive diagnosis problems, discuss some coding issues, and a property to hold in order to ensure e ective diagnosis in practice. Moreover, in case of not ful lling the property, we state several methods for solving the underlying problem. In the conclusion, we recapitulate the content of this paper and state our future research directions. 2
In the following we brie y introduce the FMEA but focus only on relevant parts we are going to use in this paper and thus ignoring all FMEA parts that belong to reliability analysis, e.g., assigning a likelihood to certain faults, the costs of the faults, and their severity. We focus on relevant parts only because the others do not provide any information used in the context of adductive diagnosis. We further assume that a FMEA describes the relationship between a fault and its e ects ignoring intermediate e ects or system internal non-observable e ects. This is not a restriction because we are only interested in observable e ects that might lead to dangerous situations. In cases where internal or intermediate e ects are relevant they must have a corresponding observable e ect, which has to considered in the FMEA.
We rst, discuss FMEAs in more detailed using a simpli ed example coming from the wastewater treatment domain. In particular, we specify a FMEA for a constructed wetland. In Figure 1 we depict the structure of a constructed wetland. A constructed wetland is an arti cial wetland used amongst others for wastewater treatment. The idea behind the constructed wetlands is to use plants for the removal of nitrates and phosphate from polluted water. There are some parameters like the in ow of water, the status of the membrane used to prevent the water owing out of the basin, and the out ow. All these parameters in uence the water level. Moreover, also the weather conditions like rain, or a long period of heavy sunshine have an impact on the water level. On the other hand, the water level is important for ensuring the plant to survive. Is there is not enough water, the plant will nally die. Moreover, the concentration of nitrates and phosphates also impacts the health status of the plants. A healthy plant has a green color whereas a dying plant becomes brown. For more details about constructed wetlands as well as a discussion on the use of abductive reasoning versus decision trees we refer the interested reader to [20] and [19]. The latter discusses a di erent example from the wastewater treatment domain.
In order to construct a FMEA we rst have to identify the components and potential fault modes. A constructed wetland comprises the components in-valve, out-valve, membrane, and plants. In addition we have to consider also external components, which also impacts the behavior. Such external components represent parts of the environment of a system that impacts the behavior. For the constructed wetland these components are the weather condition and the nitrates and phosphate (NP) concentration of the water that ows into the constructed wetland. The fault modes are wrong settings of the valve, a leak in the membrane, a period of hot temperature and an unexpected NP concentration. It is worth noting that we are of course able to introduce more di erent fault modes like a lower in ow a higher in ow in order to distinguish di erent situations that are outside the operational settings of the constructed wetland. However, for simplicity of our example we only consider a few of them.
So, how can we construct a FMEA? A FMEA is a table, where each row describes the e ects of a fault constituting because of a failure of a certain component. Hence, for each component and fault mode we make one entry. For example, from the verbal description of the constructed wetland, we see that a leaking membrane impacts the water level negatively, which in turn causes a plant to die because of lack of water. Hence, the color of the plants become brown. We are able to make a similar entry for each possible component and fault mode nally leading to the FMEA. For the constructed wetland the FMEA is given in Table 1. It is worth noting that in a FMEA usually only single faults are considered. Component Fault mode E ect in-valve too low low in ow, wrong water level, brown plants out-valve too high high out ow, wrong water level, brown plants membrane leaking wrong water level, brown plants weather too hot long sunshine period, wrong water level, brown plants NP-conc. wrong brown plants
We now state a formal de nition of a FMEA. We assume that a FMEA is for systems comprising components COM P , that have corresponding fault modes M ODES. Moreover, we assume the existence of propositions P ROP S that belong to observations we obtained when running the system. If we observe a certain value, the proposition is said to be true, and false otherwise. We now de ne FMEAs as relation between components, a fault modes, and a set of e ects that has to be observed when the given component is in the given fault mode. Note that in our constructed wetland example, there is a one to one relationship between components and modes. This is usually not the case in practice where a component like a logic gate has many fault modes. A fault model of a logic gate may at least comprise the fault modes stuck at one and stuck at zero. De nition 1 (FMEA). A FMEA is a set of tuples (C; M; E) where C 2 COM P is a component, M 2 M ODES is a fault mode, and E P ROP S a set of e ects.
For our constructed wetland example, we have to map the verbal descriptions given in Table 1 to elements of COM P , M ODES, and P ROP S. For this purpose we set COM P = fin; out; membrane; weather; npg, M ODES = flow; high; leaking; hot; wrongg, and P ROP S = flow in; high out; wrong level; sunshine; browng and obtain the following FMEA for the constructed wetland example:
F M EACW = >>><>8 (ou(itn;h;liogwh;; fflhoiwghino;uwt;rwornognlgevleevl;eblr;obrwonwgn)g) >>>=>9
(membrane; leaking; fwrong level; browng) >> (weather; hot; fsunshine; wrong level; browng) >>> :>> (np; wrong; fbrowng) >;
In the next section, we brie y recapitulate the basic de nitions of abductive diagnosis. 3
In this section we discuss the basic de nitions of abductive reasoning and
abductive diagnosis in particular. For this purpose, we rst de ne a knowledge base
comprising horn clause rules (from HC) over propositional variables P ROP S.
The restriction of logical formula to be horn is not a limitation in the context of
physical systems since those models usually code the knowledge from causes to
their e ects. The used de nitions are close the ones introduced by Friedrich at
al. [
De nition 2 (Knowledge base (KB)). A knowledge base (KB) is a tuple (A; Hyp; T h) where A P ROP S denotes the set of propositional variables, Hyp A the set of hypothesis, and T h HC a set of horn clause sentences over A.
In the de nition of KB hypotheses corresponds directly to causes, such that for every cause there is a propositional variable that allows to hypothesize about the truth value of the cause. Hence, we use the terms hypotheses and causes in an interchangeable way.
Example 1. For example, the tuple (fwrong level; mode(in; low)g; fmode(in; low)g; fmode(in; low) ! wrong levelg) forms a knowledge base. In the tuple the set fwrong level; mode(in; low)g represents the used propositional variables, fmode(in; low)g the hypotheses, and fmode(in; low) ! wrong levelg the set of clauses.
De nition 3 (PHCAP). Given a knowledge base (A; Hyp; T h) and a set of observations Obs A, the tuple (A; Hyp; T h; Obs) forms a propositional horn clause abduction problem (PHCAP).
Example 2 (cont.). Assume that we observe a wrong water level, i.e., Obs = fwrong levelg we obtain a PHCAP.
Given a PHCAP we de ne a solution like in [
A solution of a PHCAP is an explanation for the given observations. Instead of solution we also say abductive diagnosis (or diagnosis for short). In De nition 4 diagnoses need not to be minimal or parsimonious. In most practical cases only minimal diagnoses or minimal explanations for given e ects are of interest. Hence, from here on we assume that all diagnoses are minimal diagnoses if not speci ed explicitly.
Example 3 (cont.). For our small example we obtain only one minimal diagnoses: = fmode(in; low)g for the observation wrong level.
It is well known that the problem of nding minimal diagnoses for a given
PHCAP is NP-complete. See for example Friedrich et al. [
For adding new observations in order to decrease the number of diagnoses, we introduce the notation of discriminating observations.
De nition 5 (Discriminating observation). Given a PHCAP (A; Hyp; T h; Obs) and two diagnoses 1 and 2. A new observation o 2 AnObs discriminates two diagnoses if and only if 1 is a diagnosis for (A; Hyp; T h; Obs [ fog) but 2 is not.
In order to compute discriminating additional observations it is possible adopt the approach by De Kleer and Williams [14] who introduced an algorithm for measurement selection. For more details about the use of measurement selection for abductive diagnosis and an algorithm we refer to [19]. The underlying idea is to rank potential observations accordingly to their power of discrimination, e.g., preferring the observation that is able to divide the search space into two halves.
We implemented an algorithm for solving the PHCAP as well as the nding discriminating observations problem. This implementation is based on De Kleer's Assumption-based Truth Maintenance System (ATMS) [12]. See for example [13] for an ATMS algorithm. An ATMS handles the consistency state of propositions that are connected via horn-clause rules. Moreover, an ATMS makes use of assumptions, which are assumed to be true unless a contradiction can be derived from the respective assumption. In ATMS terminology assumptions and propositions are said to be nodes, rules are justi cations, and the contradiction (?) is represented by the special node NOGOOD. Besides the truth status an ATMS also manages for each node all the di erent assumptions that are necessary for making that node true. This set of assumptions is called label, and its elements an environment. An ATMS environment in the context of non-monotonic logic can be seen as a possible world that makes the corresponding node true.
An ATMS makes sure that for each node all the stored environments are consistent and each of them allow for deriving the node. Moreover, the environments are also minimal, and complete. The latter is important to ensure that there is not a possible world missing. An ATMS can be easily used for abductive diagnosis. Given a PHCAP. Let us rst assume that all elements of A are mapped to nodes, all elements of Hyp are mapped to ATMS assumptions, and all rules in T h are mapped to ATMS justi cations. If we want to obtain an observation Obs = fog, then we only have to return the label l of the nodes that corresponds to o. All the elements of l are consistent and minimal. Moreover, from l [ T h we obtain o and there is no element missing in l. In general, the observations might contain more elements, i.e., Obs = fo1; : : : ; okg. In this case we generate a new proposition and add o1 ^ : : : ^ ok ! to the theory T h that is passed to the ATMS. The label of the corresponding node of is an abductive diagnosis for Obs.
It is worth noting that the ATMS has been used in consistency-based
diagnosis. The General Diagnostic Engine (GDE) [14] makes use of the ATMS for
computing con icts. A con ict in consistency-based diagnosis is a set of
correctness assumptions for components that lead together with the logical description
of a system and the given observations to a contradiction. When using an ATMS
all possible con icts are stored in the NOGOOD node. Reiter [18] proved that
the hitting sets of minimal con icts are the diagnoses. In his paper, Reiter also
provided an algorithm for computing the diagnoses from the con icts. Greiner
et al. [
In the next section, we discuss how to make use of a FMEA for obtaining a corresponding KB further used to construct a PHCAP. We also discuss some coding issues because of the restriction to horn-clause propositional logic.
In this section we discuss the mapping of FMEA to a corresponding (abductive) KB, which can be used for diagnosis purposes. Afterwards we discuss some properties of the knowledge base, which must hold in order to ensure the computability of a single diagnosis in case enough information (i.e., observations) are given. Furthermore, we show how FMEA can be revised in order to guarantee the computation of single diagnosis.
Let us rst start with the mapping of FMEAs to their corresponding knowledge base KB. This mapping is rather straightforward because FMEA already capture the cause-e ect relationship in tabular form. Formally, we use a function M : 2F MEA 7! HC for mapping a particular FMEA to a horn clause theory. In the following we de ne M in the following way iterating over all tuples stored in FMEA: De nition 6 (FMEA to HC; M). Given a FMEA, the function M is de ned as follows:
M(F M EA) =def
[ t2F MEA
M(t) where
M(C; M; E) =def fmode(C; M ) ! x jx 2 E g :
The causes, i.e., the components and their modes, stored in an FMEA, are mapped to proposition. Hence, we de ne the set of hypotheses as follows: Hyp =def
[ (C;M;E)2F MEA fmode(C; M )g:
What remains is the set of proposition. This set is equivalent to the union of all e ects stored in a FMEA, i.e.:
A =def
[ (C;M;E)2F MEA
E: Example 4. When using the F M EACW of the constructed wetland given at the end of Section 2 we obtain the following corresponding KBCW when applying the M function and the other de nitions for Hyp and A:
Hyp = mode(in; low); mode(out; high); mode(membrane; leaking);
mode(weather; hot); mode(np; wrong)
A = flow in; high out; sunshine; wrong level; brown; g T h = 8 > > > > > > > > < mode(in; low) ! low in; mode(in; low) ! wrong level; mode(in; low) ! brown; mode(out; high) ! high out; mode(out; high) ! wrong level; mode(out; high) ! brown;
mode(membrane; leaking) ! wrong level; >> mode(membrane; leaking) ! brown; mode(weather; hot) ! sunshine; >> >>>>>>: mode(weather; hot)m!odwe(rnopn;gwlervoenlg;m)!odeb(rwoweanther; hot) ! brown; >>>>>>; 9 > > > > > > > > =
When using KB together with the observation that the plants are brown, i.e., Obs = fbrowng, all the elements of Hyp are also a (single) diagnosis. Hence, someone is interested in reducing the number of diagnoses by adding new observations.
A reduction of diagnosis candidates can be done { as already discussed { using additional observations. For example, when adding the observation low in to Obs in Example 4, only the diagnosis fmode(in; low)g remains. In practice the observation low in would be obtained by inspecting the in-valve and comparing its ow with the expected ow. But what happens if the in ow is correct? In this case we have to add :low in to Obs and fmode(in; low)g would be removed from the list of diagnosis candidates because fmode(in; low)g [ T h 6j= fbrown; :low ing. However, also the other diagnosis candidates would be removed, because non of them lead to the derivation of :low in.
One way of overcoming this problem is to model also negated observations. However, a straightforward implementation would not be possible if we still rely on horn-clause logic. Hence, we would have to introduce special propositions, e.g., not low in, representing the fact :low in. In addition we would have to add inconsistency checking rules, stating that a proposition and its negation cannot be true at the same time, e.g., low in ^ not low in ! ?. Such a solution increases the size of the KB.
Another solution would be to state that a certain property does not longer hold. For example, if low in has not been observed, we are able to simple state that this property in the current world would lead to an inconsistency, e.g., low in ! ?. In this way, we rule out all diagnoses that derives an observation we are not able to establish in reality. In our system we follow this idea and represent negated observations o as additional rules of the form o ! ? in the KB's theory T h.
What is missing is to give an answer to the question whether the used model and in this case the underlying FMEA is good enough for diagnostic purposes. By 'good enough' we mean that the obtained results are correct and complete. This is ensured using abductive diagnosis where only correct, i.e., consistent, diagnoses are computed. Moreover, when searching for all diagnoses, we are sure that completeness is obtained with respect to the underlying model. Hence, we de ne 'good enough' for diagnosis here as the ability of the KB to nd one single fault diagnosis if all necessary information is given. We call this property one single fault diagnosis property and de ne it as follows: De nition 7 (One Single Fault Diagnosis Property (OSFDP)). Given a KB (A; Hyp; T h). KB ful lls the One Single Diagnosis Property (OSDP) if the following hold: 8m 2 Hyp : 9Obs A : fmg is a diagnosis of (A; Hyp; T h; Obs) and :9m0 2 Hyp : m0 6= m such that fm0g is a diagnosis for the same PHCAP: The OSFDP property allows us to ensure that with enough knowledge we are able to distinguish all single-fault diagnosis. If a KB does not ful ll OSFDP, then we cannot distinguish all diagnoses. Hence, in some cases we need to replace more components. Checking for OSFDP can be done in a simple but e ective way. We only have to go through all hypotheses and compute all proposition that follows from the current hypothesis and the theory T h. Afterwards we have to check for two hypotheses whether their derived propositions are the same. If yes, then the OSFDP can never be ful lled. If we do not nd such a pair, then the OSFDP has to hold because we can distinguish the two hypotheses with the non-intersecting parts of their propositions. In Algorithm 1 we summarize the checking procedure.
Algorithm 1 CHECK OSFDP(A; Hyp; T h) Input: A KB (A; Hyp; T h) comprising propositions A, hypothesis Hyp, and a horn-clause propositional logic.
Output: True if the KB ful lls the OSFDP, and false otherwise.
Algorithm 1 obviously terminates assuming Hyp to be nite (which is always the case in practice). The algorithm's time complexity is polynomial and in particular of order O(jHypj2). The runtime is mainly determined by the nested loops (line 5 to 10). Note also that the algorithm requires too many checks, which might be avoided. However, the time complexity would still remain the same considering the O(:) notation.
Example 5. The KB from Example 4 ful lls the OSFDP. Algorithm 1 would return true.
It is worth noting that { because of the construction of M { the check for OSFDP can also be easily checked on side of the FMEA. For this purpose only the e ects of the given causes have to be compared with each other. We will use this observation for the further elaboration on the question of how to deal with KBs not ful lling OSFDP. In principle, we have three possibilities: 1. We ignore that OSFDP is not ful lled. In this case we know that there are diagnoses, which we cannot distinguish regardless of the given observations. 2. If we know that there are two hypotheses h1 and h2 contradicting the OSFDP, then there is no way for distinguishing h1 from h2. Hence, we can treat both hypotheses the same. For this purpose, we introduce a new hypothesis h0 and replace both h1 and h2 with h. We proceed with this replacements until the OSFDP is ful lled. This method summarizes all hypotheses that cannot be distinguished and which should be treated as a single replaceable unit. 3. It is worth noting that there is another reason why an OSFDP is not fullled. There might be other observations of the system or internal values not observable from outside that are currently not considered in the given FMEA. By introducing these observables into the FMEA, we might be able to distinguish hypotheses. Hence, the third way of dealing with the problem is to ask the user for further observations to be used in the FMEA.
Hence, with the described methods the OSFDP can either be handled as it is, or treated in a way that allows for coming up with a FMEA (or the corresponding KB) where the OSFDP is ful lled. 5
In the paper we argued that abductive reasoning and in particular abductive diagnosis become more important for practical diagnostic applications. This is due to the fact of the growing importance of FMEAs used in industry for ensuring and also evaluating reliability and safety constraints. We discussed a method for mapping FMEAs directly to knowledge bases that code the knowledge in rules representing the cause-e ect relationship directly. Furthermore, we also discussed how this knowledge base can be used for diagnosis and also give some information on how to deal with observations. In particular, we discussed the problem of handling negated observations without changing the knowledge base substantially. We do this by adding a rule stating that the observation would lead to an inconsistency.
Finally, we introduced a property that has to hold for knowledge bases in order to allow for computing exactly one single-fault diagnosis if there is enough information provided. We also discussed what to do in case the knowledge base does not ful ll the property. There are two active ways of dealing with the problem: (1) handling non-distinguishable single-fault diagnosis as one component, and (2) asking the user for more observation and extensions for the FMEA. The former method generates a super-component that can be seen as a replaceable unit in case of failing. The latter might be interpreted in the way that the modeling has to be improved.
Future research will include an implementation of the proposed techniques and algorithms. Currently, the abductive diagnosis is implemented based on an ATMS implementation. Moreover, we want to use this method for diagnosis of technical systems. The rst application will be in the context of wind-turbines used to generate electricity, where the FMEA comes from our industrial partner. Using the application domain we want to clarify whether abductive reasoning is a good foundation for diagnosis or not. This includes computational aspects as well as usability concerns. With the automated conversion of FMEAs to KBs, we believe to have taken, an important step towards increased usability. Acknowledgements. The research presented in this paper has received funding from the Austrian Research Promotion Agency (FFG) under grant 842407 (Applied MOdel-based Reasoning (AMOR)). Many thanks also go to the anonymous reviewers for their very valuable comments helping to improve this paper. 11. Hawkins, P.G., Woollons, D.J.: Failure modes and e ects analysis of complex engineering systems using functional models. Arti cial Intelligence in Engineering 12, 375{397 (1998) 12. de Kleer, J.: An assumption-based TMS. Arti cial Intelligence 28, 127{162 (1986) 13. de Kleer, J.: A general labeling algorithm for assumption-based truth maintenance.
In: Proceedings of the National Conference on Arti cial Intelligence (AAAI). pp. 188{192. Morgan Kaufmann, Saint Paul, Minnesota (Aug 1988) 14. de Kleer, J., Williams, B.C.: Diagnosing multiple faults. Arti cial Intelligence 32(1), 97{130 (1987) 15. Malik, A., Struss, P., Sachenbacher, M.: Qualitative modeling is the key { a successful feasibility study in automated generation of diagnosis guidelines and failuer mode and e ects analysis for mechatronic car subsystems. In: Proceedings of the Sixth International Workshop on Principles of Diagnosis (1995) 16. Malik, A., Struss, P., Sachenbacher, M.: Case studies in model-based diagnosis and fault analysis of car-subsystems. In: Proceedings of the European Conference on Arti cial Intelligence (ECAI) (1996) 17. Price, C., Taylor, N.: Automated multiple failure fmea. Reliability Engineering &
System Safety 76, 1{10 (2002) 18. Reiter, R.: A theory of diagnosis from rst principles. Arti cial Intelligence 32(1), 57{95 (1987) 19. Wotawa, F., Rodriguez-Roda, I., Comas, J.: Environmental decision support systems based on models and model-based reasoning. Environmental Engineering and Management Journal 9(2), 189{195 (2010) 20. Wotawa, F.: On the use of abduction as an alternative to decision trees in environmental decision support systems. International journal of agricultural and environmental information systems 2(1), 63{82 (2011)