Student research opportunities

Diagnosis of Discrete Event Systems by Petri Nets and Integer Linear Programming

Project Code: CECS_857

This project is available at the following levels:
Masters, PhD
Please note that this project is only for higher degree (postgraduate) applicants.

Keywords:

Diagnosis Discrete event systems Petri nets Integer linear programming

Supervisor:

Dr Alban Grastien

Outline:

Integer Linear Programming (ILP) has recently been proposed to diagnose Petri nets.
Essentially, the set of possible ``explanations'' of the observations
is represented by a set of integers, each integer representing
the number of unobservable transitions of a certain type
in a period of time defined as the interval between two observations.
This defines a big ILP problem
on top of which questions can be asked such as ``did fault f1 occur possibly/certainly''.

The purpose of this project is to explore extensions of this work.

Goals of this project

• The work by Basile et al. reduces drastically the number of integer variables
  necessary for diagnosis, but at the price of precision:
  in certain cases, faults can be diagnosed by Dotoli et al.
  while Basile et al. will not diagnose them.
  It would be interesting to characterise the class of systems (Petri nets)
  for which Basile et al. always returns the precise diagnosis.
  


• This method requiers a strong assumption on the Petri net,
  which is that its unobservable part should be free of cycles.
  An extension would be to lift this restriction as much as possible.
  


• The output of the diagnosis algorithm is restricted to detecting single events.
  It would be interesting to extend this work for patterns of faults.
  Another topic of interest would be to deal with partially ordered observations.
  


• The method proposed by Dotoli et al. requiers many variables,
  some of which are clearly unnecessary.
  This reduces the efficiency of this approach
  as the full power of Petri nets is wasted.
  It would be interesting to determine if certain variables could be merged.
  


• The incremental aspect of the diagnosis means that the same knowledge
  could be inferred over and over again.
  We would like to explore how such information (or an ambiguity that can not be settled)
  can be extracted and reused.
  

Requirements/Prerequisites

Knowledge in either Petri nets or ILP.

Background Literature

• Francesco Basile, Pasquale Chiacchio, and Gianmaria De Tommasi. An efficient approach for online diagnosis of discrete event systems. IEEE Transactions on Automatic Control (TAC), 54(4):748-759, 2009.
  


• Francesco Basile, Pasquale Chiacchio, and Gianmaria De Tommasi. On K-diagnosability of Petri nets via integer linear programming. Automatica (Automatica), 482047-2058, 2012.
  


• Mariagrazia Dotoli, Maria Pia Fanti, Agostino Marcello Mangini, and Walter Ukovich. On-line detection in discrete event systems by Petri nets and integer linear programming. Automatica (Automatica), 452665-2672, 2009.
  


• Alban Grastien. Diagnosis properties by design. In International Workshop on Principles of Diagnosis (DX-11), pages 155-158, 2011.
  [Open problems track]
  


• 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.
  

Contact: