Diagnosability Analysis of a Class of Hierarchical State Machines

This paper addresses the problem of fault detection and isolation for a particular class of discrete event dynamical systems called hierarchical finite state machines (HFSMs). A new version of the property of diagnosability for discrete event systems tailored to HFSMs is introduced. This notion, called L₁-diagnosability, captures the possibility of detecting an unobservable fault event using only high level observations of the behavior of an HFSM. Algorithms for testing L₁-diagnosability are presented. In addition, new methodologies are presented for studying the diagnosability properties of HFSMs that are not L₁-diagnosable. These methodologies avoid the complete expansion of an HFSM into its corresponding flat automaton by focusing the expansion on problematic indeterminate cycles only in the associated extended diagnoser.

Stéphane LafortuneEmail:

---

Andrea Paoli   received the master degree in Computer Science Engineering and the Ph.D. in Automatic Control and Operational Research from the University of Bologna in 2000 and 2003 respectively. He currently holds a Post Doc position at the Department of Electronics, Computer Science and Systems (DEIS) at the University of Bologna, Italy. He is a member of the Center for Research on Complex Automated Systems (CASY) Giuseppe Evangelisti. From August to January 2002, and in March 2005 he held visiting positions at the Department of Electrical Engineering and Computer Science at The University of Michigan, Ann Arbor. In July 2005 he won the prize IFAC Outstanding AUTOMATICA application paper award for years 2002-2005 for the article by Claudio Bonivento, Alberto Isidori, Lorenzo Marconi, Andrea Paoli titled Implicit fault-tolerant control: application to induction motors appeared on AUTOMATICA issue 30(4). Since 2006 he is a member of the IFAC Technical Committee on Fault Detection, Supervision and Safety of Technical Processes (IFAC SAFEPROCESS TC). His current research interests focus on Fault Tolerant Control and Fault Diagnosis in distributed systems and in discrete event systems and on industrial automation software architectures following an agent based approach. His theoretical background includes also nonlinear control and output regulation using geometric approach. Stéphane Lafortune   received the B. Eng degree from Ecole Polytechnique de Montréal in 1980, the M. Eng. degree from McGill University in 1982, and the Ph.D. degree from the University of California at Berkeley in 1986, all in electrical engineering. Since September 1986, he has been with the University of Michigan, Ann Arbor, where he is a Professor of Electrical Engineering and Computer Science. Dr. Lafortune is a Fellow of the IEEE (1999). He received the Presidential Young Investigator Award from the National Science Foundation in 1990 and the George S. Axelby Outstanding Paper Award from the Control Systems Society of the IEEE in 1994 (for a paper co-authored with S. L. Chung and F. Lin) and in 2001 (for a paper co-authored with G. Barrett). At the University of Michigan, he received the EECS Department Research Excellence Award in 1994–1995, the EECS Department Teaching Excellence Award in 1997–1998, and the EECS Outstanding Achievement Award in 2003–2004. Dr. Lafortune is a member of the editorial boards of the Journal of Discrete Event Dynamic Systems: Theory and Applications and of the International Journal of Control. His research interests are in discrete event systems modeling, diagnosis, control, and optimization. He is co-developer of the software packages DESUMA and UMDES. He co-authored, with C. Cassandras, the textbook Introduction to Discrete Event Systems—Second Edition (Springer, 2007). Recent publications and software tools are available at the Web site .