Diagnosis

The diagnostic task is to determine why a correctly designed system is not functioning as it was intended, using observations of the system. My work focusses on model-based diagnosis where the diagnosis is performed by using a description (the model) of how the system of interest is supposed to or can behave.

I mostly considered discrete-event systems (DES), which is a class of model for dynamic systems where the states and the evolution are represented at a discrete abstraction level. A voltage or a temperature for instance would be described as low, normal, or high, rather than with a precise continuous value. I also started working on circuits (static systems) and hybrid systems (dynamic systems with a discrete and a continuous compounds).

There are four main research topics associated with diagnosis: complexity, diagnosability, and information.

Complexity

Model-based diagnosis works by finding ``explanations'' to the system observation that are compatible with the system model. Finding these explanations (sometimes, even all explanations) is often computationally demanding: we are talking here about NP-hard problems. Being able to cope with the complexity is essential.

I have explored several directions to handle complexity of diagnosis of DES; the idea is to exploit symmetries that exist in the diagnosis problem in order to speed up the resolution.

The first approach was to use a temporal decomposition to allow for spatial decomposition [1,2]. Spatial decomposition is quite powerful: if two subsystems behave independently for a moment, you can consider them separately, which transforms a large problem in two smaller problems. However, all components in a system eventually interact with one-another, and no useful spatial decomposition can be found. Now, if you do a temporal decomposition, i.e., you slice the diagnosis window in smaller time frames, then you can identify temporary spatial independencies and exploit them.

A second approach I worked on was Junction Trees [3]. It is well known that many hard network problems become tractable when applied to trees (or forests); what then defines the complexity of the problem is the size of each node . The system (= network) that diagnosis is performed on is usually not a tree. However, it can be reshaped in a tree and, although the size of node may be very large (it could be the whole system), it is often much smaller than the system. We have shown that junction trees don't provide any guarantee for diagnosis of DES, but this approach is still the state-in-the-art in exhaustive diagnosis of DES.

I have started considering abstraction for diagnosis [4]. The idea is to ignore certain aspects of the model, while still maintaining a certain diagnosis precision (cf. the dedicated section). This has been applied to decide whether certain connections between components can be ignored for diagnosis; the reason you want to ignore connections is that the junction tree diagnosis approach is then more powerful.

Finally, a last approach I am working on extensively at the moment is the reformulation of the diagnosis problem in simple diagnostic questions [5], which enables to use powerful tools as SAT, model-checker, theorem provers, classical planners, etc. More about it in the section about diagnosis and information.

Diagnosability and Precision

When you build a system or its diagnoser, you may want to know what this diagnoser is able to do. I will now discuss this type of properties.

The most commonly question asked is whether the diagnoser will always be able to identify a fault if it occurs; this property is known as diagnosability. Diagnosability is important because it tells whether you should add more sensors on your system, or whether your model is precise enough. I have worked a bit on diagnosability, proposing a SAT-based method to test non-diagnosability [6]. I proposed an approach using model-checking and BDDs to solve this problem [7]; now, the reason I found this work interesting is that it was the first approach that used a backward approach to solve the problem. Diagnosability of DES is checked by determining if there exists two indistinguisable infinite sequences of events, one that is exhibits a certain fault and the other one that does not; the reason I wanted to build such a pair of sequences from the end is that I hope that the faulty behaviour will significantly differ from the nominal behaviour, which will allow a very quick answer. In the same piece of work, I looked at the problem of finding minimal subsets of sensors for diagnosability.

I started looking at other similar properties. I discussed a property which states that you need only look at the last observations if you want to compute a diagnosis as precisely as possible [8]. I also studied how diagnosability allows you to translate diagnosis in simpler questions [5] (cf. section Diagnosis and Information for this topic).

Finally, I presented an interesting idea of Property by Design [9]. The problem is the following: I want to define design constraints that, when they are followed by the system designer, will make the system exhibit certain properties. For instance, putting a sensor on every second transformer might allow to diagnose precisely any faulty transformer.

Diagnosis and Information

There are some very interesting questions on how diagnosis and information are related. A diagnosis is an explicit formulation of some information that already exists in the diagnosis problem. To attack the complexity problem of diagnosis, implicit information is sometimes returned and it is not always clear what is called a diagnosis. For instance, in discrete event systems, the output of the diagnosis engine is sometimes the set of behaviours that explain the observations; it is assumed the diagnosis can be easily extracted from this representation. To make things worst, the set of behaviours can even be spatially or temporally decomposed.

What is the most useful diagnostic representation is not clear. If the diagnosis is ``components A and B, or components A and C, are faulty'', would not the following formulation be more clear: ``component A and, either component B or component C, are faulty''. The second representation is a set of conflicts, and it is well-known that diagnosis is the set of hitting sets of conflicts.

In the last years, I spent some time working on the problem of reformulating diagnosis as a set of diagnostic questions [10,11]. A diagnostic question is a simple problem that asks whether a specific type of behaviour is consistent with the observations. For instance, is it possible that the system is working in nominal mode? or can it be that the component A failed before component B, while component C did not fail, if it ever did, before component B?.

References

< Back to main page