Fault Diagnosis with Static and Dynamic Observers

• Autorzy: Cassez F. , Tripakis S.
• Języki publikacji: EN

Abstrakty

EN

We study sensor minimization problems in the context of fault diagnosis. Fault diagnosis consists in synthesizing a diagnoser that observes a given plant and identifies faults in the plant as soon as possible after their occurrence. Existing literature on this problem has considered the case of fixed static observers, where the set of observable events is fixed and does not change during execution of the system. In this paper, we consider static observers where the set of observable events is not fixed, but needs to be optimized (e.g., minimized in size). We also consider dynamic observers, where the observer can “switch” sensors on or off, thus dynamically changing the set of events it wishes to observe. It is known that checking diagnosability (i.e., whether a given observer is capable of identifying faults) can be solved in polynomial time for static observers, and we show that the same is true for dynamic ones. On the other hand, minimizing the number of (static) observable events required to achieve diagnosability is NP-complete. We show that this is true also in the case of mask-based observation, where some events are observable but not distinguishable. For dynamic observers’ synthesis, we prove that amost permissive finite-state observer can be computed in doubly exponential time, using a game-theoretic approach. We further investigate optimization problems for dynamic observers and define a notion of cost of an observer. We show how to compute an optimal observer using results on mean-payoff games by Zwick and Paterson.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 88, nr 4
• Strony: 497--540
• Opis fizyczny: bibliogr. 24 poz., tab., wykr.

Twórcy

autor

Cassez F.

autor

Tripakis S.

• CNRS/IRCCyN 1 rue de la Noë, BP 92101, 44321 Nantes Cedex 3, France,

Bibliografia

• [1] Cassez, F., Tripakis, S., Altisen, K.: Sensor Minimization Problems with Static or Dynamic Observers for Fault Diagnosis, 7th Int. Conf. on Application of Concurrency to System Design (ACSD'07), IEEE Computer Society, 2007.
• [2] Cassez, F., Tripakis, S., Altisen, K.: Synthesis Of Optimal Dynamic Observers for Fault Diagnosis of Discrete-Event Systems, 1st IEEE & IFIP Int. Symp. on Theoretical Aspects of Soft. Engineering (TASE'07), IEEE Computer Society, 2007.
• [3] Cieslak, R., Desclaux, C., Fawaz, A., Varaiya, P.: Supervisory control of discrete-event processes with partial observations, IEEE Transactions on Automatic Control, 33, 1988, 249-260.
• [4] Courcoubetis, C., Vardi, M., Wolper, P., Yannakakis, M.: Memory Efficient Algorithms for the Verification of Temporal Properties, Formal Methods in System Design, 1, 1992, 275-288.
• [5] Dasdan, A., Irani, S., Gupta, R.: Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems, Annual ACM IEEE Design Automation Conference, ACM Press New York, NY, USA, New Orleans, Louisiana, United States, 1999, ISBN:1-58133-109-7.
• [6] Debouk, R., Lafortune, S., Teneketzis, D.: On an Optimization Problem in Sensor Selection, Discrete Event Dynamic Systems, 4(12), November 2004.
• [7] Doyen, L., Chatterjee, K., Henzinger, T., Raskin, J.-F.: Algorithms for omega-regular games with imperfect information, in: Computer Science Logic (CSL), Lecture Notes in Computer Science 4207, Springer, 2006, 287-302.
• [8] Holzmann, G., Peled, D., Yannakakis, M.: On nested depth-first search, Proc. of the 2nd Spin Workshop, American Mathematical Society, 1996.
• [9] Holzmann, G. J.: Software model checking with SPIN, Advances in Computers, 65, 2005, 78-109.
• [10] Jiang, S., Huang, Z., Chandra, V., Kumar, R.: A Polynomial Algorithmfor Testing Diagnosability of Discrete Event Systems, IEEE Transactions on Automatic Control, 46(8), August 2001.
• [11] Jiang, S., Kumar, R., Garcia, H.: Optimal Sensor Selection for Discrete Event Systems with Partial Observation, IEEE Transactions on Automatic Control, 48(3),March 2003, 369-381.
• [12] Karp, R.: A characterization of the minimum mean cycle in a digraph, Discrete Mathematics, 23, 1978, 309-311.
• [13] Kupferman,O., Vardi,M.: Synthesis with Incomplete Informatio, 2nd International Conference on Temporal Logic, Manchester, July 1997.
• [14] Lamouchi, H., Thistle, J.: Effective Control Synthesis for DES Under Partial Observations, IEEE Conference on Decision and Control, 2000.
• [15] Ramadge, P., Wonham, W.: Supervisory control of a class of discrete event processes, SIAM J. Control Optim., 25(1), January 1987.
• [16] Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K., Teneketzis, D.: Diagnosability of Discrete Event Systems, IEEE Transactions on Automatic Control, 40(9), September 1995.
• [17] Thomas,W.: On the Synthesis of Strategies in Infinite Games, Proc. 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS'95), 900, Springer, 1995, Invited talk.
• [18] Thorsley, D., Teneketzis, D.: Active Acquisition of Information for Diagnosis and Supervisory Control of Discrete Event Systems, Discrete Event Dynamic Systems, 4(17), December 2007, 531-583.
• [19] Tsitsiklis, J.: On the Control of Discrete Event Dynamical Systems, Mathematics of Control, Signals and Systems, 2(2), 1989.
• [20] Yoo, T.-S., Garcia, H.: Computation of Fault Detection Delay in Discrete-Event Systems, 14th International Workshop on Principles of Diagnosis, DX'03,Washington, D.C., June 2003.
• [21] Yoo, T.-S., Lafortune, S.: On the computational complexity of some problems arising in partially-observed discrete event systems, American Control Conference (ACC'01), 2001, Arlington, VA.
• [22] Yoo, T.-S., Lafortune, S.: NP-completeness of sensor selection problems arising in partially observed discrete-event systems, IEEE Transactions on Automatic Control, 47(9), September 2002, 1495-1499.
• [23] Yoo, T.-S., Lafortune, S.: Polynomial-Time Verification of Diagnosability of Partially-Observed Discrete-Event Systems, IEEE Transactions on Automatic Control, 47(9), September 2002, 1491-1495.
• [24] Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs, Theoretical Computer Science, 158(1-2), 1996, 343-359.