MSIM Project: Verification and Diagnosis of Discrete Event Systems with Modular Structure

Verification and Diagnosis of Discrete Event Systems with Modular Structure

Project Title: Verification and Diagnosis of Discrete Event Systems with Modular Structure

Co-PI Involved: Stéphane Lafortune,
Professor, Electrical Engineering & Computer Science, University of Michigan

Collaborator: Dr. Andrea Paoli,
Professor, University of Bologna, Italy

Students:
Olivier Contant Ph.D. (2005),
Sahika Genc, Ph.D. (2006),
Patricia Pena, visiting scholar
Kurt Rohloff, Ph.D. (2004), all of Electrical Engineering & Computer Science, University of Michigan

Project Description

The past decade has witnessed the development of novel theories, with associated applications, for control and diagnosis of dynamic systems that can be modeled in a discrete event systems framework. A crucial issue in the implementation of these theories is their scalability to systems composed of several interacting components, often referred to as “modular systems.” Many of the algorithmic techniques developed to-date for diagnosis and control suffer from the problem of state space explosion as the number of system components grow. In order to tackle the problem of network monitoring and control for anomaly detection, it is imperative to develop new algorithmic techniques that exploit the modular structure of the system and thus achieve the goal of scalability. This project attacks this problem from a variety of angles, using different classes of modeling formalisms for discrete event systems (automata, Petri nets, statecharts) and considering relevant classes of diagnosis (centralized, modular and distributed diagnosis, pattern diagnosis, predictability) and control problems (modular control, verification of nonconflictingness, control of systems with symmetries). Specific details are available in the publications below.

References

1. O. Contant, S. Lafortune, and D. Teneketzis (2006), “Diagnosis of Discrete Event Systems with Modular Structure”, Discrete Event Dynamic Systems: Theory and Applications, Vol. 16, No. 1, January 2006, pp. 9-37

2. S. Genc (Lafortune advisor), “On Diagnosis and Predictability of Partially-Observed Discrete-Event Systems”, PhD. thesis, Dept. EECS, University of Michigan, May 2006

3. S. Genc and S. Lafortune (2005), “A Distributed Algorithm for On-line Diagnosis of Place-bordered Petri Nets”, in Proc. 16th International Federation of Automatic Control (IFAC) World Congress, Prague, Czech Republic, July 2005

4. S. Genc and S. Lafortune, “Distributed Diagnosis of Place-Bordered Petri Nets”, in IEEE Transactions on Automation Science and Engineering, Vol. 4, No. 2, April 2007, pp. 206-219.

5. S. Genc and S. Lafortune (2006), “Predictability in Discrete-Event Systems under Partial Observation”, in Proceedings of the 6th IFAC Symposium on Fault Detection, Supervision and Safety of Technical Processes - SAFEPROCESS'06, Beijing, China, August 2006

6. A. Paoli and S. Lafortune (2006), “On the Diagnosability of a Class of Hierarchical State Machines”, in Proceedings of the 6th IFAC Symposium on Fault Detection, Supervision and Safety of Technical Processes - SAFEPROCESS'06, Beijing, China, August 2006

7. P. Pena, J. Cury, and S. Lafortune (2006), “Testing Modularity of Local Supervisors: An Approach Based on Abstractions”, in Proceedings of the 8th International Workshop on Discrete Event Systems, Ann Arbor, Michigan, USA, July 2006

8. L. Ricker, S. Lafortune, and S. Genc, “DESUMA: A Tool Integrating GIDDES and UMDES”, in Proceedings of the 8th International Workshop on Discrete Event Systems, Arbor, Michigan, USA, July 2006. (2 pages)

9. K. Rohloff and S. Lafortune, “The Verification and Control of Interacting Similar Discrete-Event Systems”, in SIAM Journal on Control and Optimization, Vol. 45, No. 2, pp. 634-667, 2006.

10. S. Genc and S. Lafortune, "Predictability of Event Occurrences in Partially-Observed Discrete-Event Systems", to appear.

11. T. Jeron, H. Marchand, S. Genc, and S. Lafortune, "Predictability of Sequence Patterns in Discrete Event Systems", in Proceedings of the 17th IFAC World Congress, Seoul, Korea, 2008.

12. A. Paoli and A. Lafortune, "Diagnosability Analysis of a Class of Hierarchical State Machines", in Discrete Event Systems: Theory and Applicaitons, Vol. 18, No. 3, September 2008. pp. 385-413

13. S. Genc and S. Lafortune, "Diagnosis of Patterns in Partially-Observed Discrete-Event Systems", in Proceedings of the 45th IEEE Conference on Decision and Control, December 2006.

Links

UM Discrete-Event Systems Group Website