Student research opportunities
Diagnosis properties as a game
Project Code: CECS_154
This project is available at the following levels:
PhD
Please note that this project is only for higher degree (postgraduate) applicants.
Keywords:
Diagnosis, Discrete event systems, Game theory
Supervisor:
Dr Alban GrastienOutline:
Diagnosis is the problem of determining whether a given system behaves
normally or whether a fault occurred and, if so, to determine
precisely what wrong happened in the system. Model-based diagnosis of
discrete event systems (DES; basically, systems modeled -- i.e.
described -- as automata) is well-defined as finding paths on the
system model.
The existing work mostly concentrates on improving diagnosis
techniques, either by compiling the model in a deterministic form
(Sampath et al. 1995), by using decentralised/distributed techniques
(Aghasaryan et al. 1998; Su and Wonham, Pencolé and Cordier 2005;
Cordier and Grastien 2007, Kan John and Grastien 2008), or by using
symbolic techniques (Schumann et al. 2004; Benveniste et al. 2005;
Grastien et al. 2007). These approaches allow to stretch the
complexity boundaries and consider the diagnosis of larger systems;
however, the size of the systems handled is still limited as these
approaches all have an exponential factor.
More recently, other approaches have been proposed. First steps were
taken towards determining how to abstract the system to reduce
complexity yet maintain precision (Pencolé et al. 2006; Kan John et
al, Unpublished). Similarly, in order to reduce the flow of
observations (both to relieve the diagnoser but also the system),
control of observations was proposed (Thorsley and Teneketzis 2007;
Cassez and Tripakis 2008). This relates to the issue of active
diagnosis where the diagnoser deliberately modifies the inputs of the
system to obtain information (Sampath et al. 1998, Sachenbacher and
Schwoon, Kuhn et al. 2008); active diagnosis was not well studied so
far. It also relates to the problem of choosing an optimal (minimum)
set of sensors that makes a fault diagnosable (Brandán Briones et
al. 2008).
Studying these properties is essential to apply diagnosis techniques
to large networks. Techniques developed in the game theory can be
used for this purpose. An agent of the game tries to diagnose
correctly the problem, while the opponent tries to fool the diagnoser.
When there are several diagnosis agents monitoring different parts of
the system, they can collaborate (form a coalition) to help each
others.
Goals of this project
The purpose of the thesis is threefold:
* Express diagnosis-related problems in the game theory framework and
use techniques and tools from this field to solve these problems.
* Develop the game theory field by looking at diagnosis-related
problems. We strongly believe that the results the student will
obtain in game theory, although originally applied to diagnosis, can
be generalize to the framework of game theory.
* Work in the game theory field in general.
Requirements/Prerequisites
A good knowledge on either discrete event systems or game theory.
Background Literature
* Meera Sampath, Raja Sengupta, Stéphane Lafortune, Kasim Sinnamohideen, and Demosthenis Teneketzis. Diagnosability of discrete-event systems. IEEE Transactions on Automatic Control (TAC). 1995.
* Armen Aghasaryan, Éric Fabre, Albert Benveniste, Renée Boubour, and Claude Jard. Fault detection and diagnosis in distributed systems: an approach by partially stochastic Petri Nets. Journal of Discrete Event Dynamical Systems (JDEDS). 1998.
* Meera Sampath, Stéphane Lafortune, and Demosthenis Teneketzis. Active diagnosis of discrete-event systems. IEEE Transactions on Automatic Control (TAC). 1998.
* Anika Schumann, Yannick Pencolé, and Sylvie Thiébaux. Symbolic models for diagnosing discrete-event systems. European Conference on Artificial Intelligence (ECAI-04). 2004.
* Albert Benveniste, Stefan Haar, Éric Fabre, and Claude Jard. Distributed monitoring of concurrent and asynchronous systems. Journal of Discrete Event Dynamical Systems (JDEDS). 2005.
* Rong Su and W Wonham. Global and local consistencies in distributed fault diagnosis for discrete-event systems. IEEE Transactions on Automatic Control (TAC). 2005.
* Yannick Pencolé and Marie-Odile Cordier. A formal framework for the decentralised diagnosis of large scale discrete event systems and its application to telecommunication networks. Artificial Intelligence (AIJ). 2005
* Yannick Pencolé, Dmitri Kamenetsky, and Anika Schumann. Towards low-cost diagnosis of component-based systems. IFAC Symposium on Fault Detection, Supervision and Safety of Technical Processes (SafeProcess-06). 2006
* Marie-Odile Cordier and Alban Grastien. Exploiting independence in a decentralised and incremental approach of diagnosis. International Joint Conference on Artificial Intelligence (IJCAI-07). 2007.
* Alban Grastien, Anbulagan, Jussi Rintanen, and Elena Kelareva. Diagnosis of discrete-event systems using satisfiability algorithms. Conference on Artificial Intelligence (AAAI-07). 2007.
* David Thorsley and Demosthenis Teneketzis. Active acquisition of information for diagnosis and supervisory control of discrete event systems. Journal of Discrete Event Dynamical Systems (JDEDS). 2007
* Priscilla Kan John and Alban Grastien. Local consistency and junction tree for diagnosis of discrete-event systems. European Conference on Artificial Intelligence (ECAI-08). 2008.
* Franck Cassez and Stavros Tripakis. Fault diagnosis with static or dynamic diagnosers. Fundamenta Informaticae (FI). 2008.
* Martin Sachenbacher and Stefan Schwoon. Model-based test generation using quantified CSPs. International Workshop on Principles of Diagnosis (DX-08). 2008.
* Lukas Kuhn, Bob Price, Johan de Kleer, Minh Do, and Rong Zhou. Pervasive diagnosis: integration of active diagnosis into production plans. International Workshop on Principles of Diagnosis (DX-08). 2008.
* Laura Brandán Briones, Alexander Lazovik, and Philippe Dague. Optimal observability for diagnosability. International Workshop on Principles of Diagnosis (DX-08). 2008.
* Priscilla Kan John, Alban Grastien, and Yannick Pencolé. Synthesis of a distributed and accurate diagnoser. Unpublished. Interested students can ask for a copy.
