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.
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.
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.
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
- [1]:
Marie-Odile Cordier and Alban Grastien. Exploiting independence in a decentralised and incremental approach of diagnosis. In International Workshop on Principles of Diagnosis (DX-06), 2006.
- [2]:
Marie-Odile Cordier and Alban Grastien. Exploiting independence in a decentralised and incremental approach of diagnosis. In International Joint Conference on Artificial Intelligence (IJCAI-07), 2007.
- [3]:
Priscilla Kan John and Alban Grastien. Local consistency and junction tree for diagnosis of discrete-event systems. In European Conference on Artificial Intelligence (ECAI-08), 2008.
- [4]:
Alban Grastien and Gianluca Torta. A theory of abstraction for diagnosis of dicrete-event systems. In Symposium on Abstraction, Reformulation and Approximation (SARA-11), pages 50-57, 2011.
- [5]:
Alban Grastien and Gianluca Torta. Reformulation for the diagnosis of discrete-event systems. In Symposium on Abstraction, Reformulation and Approximation (SARA-11), pages 42-49, 2011.
- [6]:
Jussi Rintanen and Alban Grastien. Diagnosability testing with satisfiability algorithms. In International Joint Conference on Artificial Intelligence (IJCAI-07), 2007.
- [7]:
Alban Grastien. Symbolic testing of diagnosability. In International Workshop on Principles of Diagnosis (DX-09), pages 131-138, 2009.
- [8]:
Alban Grastien and Anbulagan. Incremental diagnosis of DES with a non-exhaustive diagnosis engine. In International Workshop on Principles of Diagnosis (DX-09), pages 345-352, 2009.
- [9]:
Alban Grastien. Diagnosis properties by design. In International Workshop on Principles of Diagnosis (DX-11), pages 155-158, 2011.
- [10]:
Alban Grastien, Patrik Haslum, and Sylvie Thiébaux. Exhaustive diagnosis of discrete event systems through exploration of the hypothesis space. In International Workshop on Principles of Diagnosis (DX-11), pages 60-67, 2011.
- [11]:
Alban Grastien, Patrik Haslum, and Sylvie Thiébaux. Conflict-based diagnosis of discrete event systems: theory and practice. In International Conference on the Principles of Knowledge Representation and Reasoning (KR-12), 2012.
< Back to main page