Abstract
We address the problem of failure diagnosis in discrete event systems with decentralized information. We propose a coordinated decentralized architecture consisting of local sites communicating with a coordinator that is responsible for diagnosing the failures occurring in the system. We extend the notion of diagnosability, originally introduced in Sampath et al. (1995) for centralized systems, to the proposed coordinated decentralized architecture. We specify three protocols that realize the proposed architecture; each protocol is defined by the diagnostic information generated at the local sites, the communication rules used by the local sites, and the coordinator's decision rule. We analyze the diagnostic properties of each protocol. We also state and prove conditions for a language to be diagnosable under each protocol. These conditions are checkable off-line. The on-line diagnostic process is carried out using the diagnosers introduced in Sampath et al. (1995) or a slight variation of these diagnosers. The key features of the proposed protocols are: (i) they achieve, each under a set of assumptions, the same diagnostic performance as the centralized diagnoser; and (ii) they highlight the “performance vs. complexity” tradeoff that arises in coordinated decentralized architectures. The correctness of two of the protocols relies on some stringent global ordering assumptions on message reception at the coordinator's site, the relaxation of which is briefly discussed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aumann, R. J. 1976. Agreeing to disagree. The Annals of Statistics 4(6): 1236–1239.
Bavishi, S., and Chong, E. 1994. Automated fault diagnosis using a discrete event systems framework. Proc. 9th IEEE International Symposium on Intelligent Control, pp. 213-218.
Bertsekas, D., and Gallager, R. 1992. Data Networks. Englewood Cliffs, NJ: Prentice Hall.
Boubour, R., Jard, C., Aghasaryan, A., Fabre, E., and Benveniste, A. 1997. Petri net approach to fault detection and diagnosis in distributed systems: application to telecommunication networks, motivations, and modelling. Proc. 36th IEEE Conf. on Decision and Control. San Diego, CA.
Cassandras, C. G., and Lafortune, S. 1998. Discrete event systems: The state of the art and some recent trends. Applied and Computational Control, Signals and Circuits (Datta, B, ed.). Birkhäuser.
Castanon, D. A., and Teneketzis, D. 1985. Distributed estimation algorithms for nonlinear systems. IEEE Trans. Automat. Contr. 30(5): 418-425.
Davis, R., and Hamscher, W. 1992. Model based reasoning: Troubleshooting. Readings in Model Based Diagnosis (Hamscher, W., Console, L., and Kleer, J., eds.). Morgan Kaufman, pp. 3-24
Debouk, R. Failure Diagnosis of Discrete Event Systems with Distributed Information. PhD Thesis, Electrical Engineering and Computer Science Department, The University of Michigan. In preparation.
Frank, P. 1990. Fault diagnosis in dynamic systems using analytical and knowledge based redundancy. Automatica 26: 459-474.
Holloway, L., and Chand, S. 1994.Time templates for discrete event fault monitoring in manufacturing systems. Proc. 1994 American Control Conference, pp. 701-706.
Hopcroft, J., and Ullman, J. 1979. Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison Wesley.
Lapp, S., and Powers, G. 1977. Computer-aided synthesis of fault trees. IEEE Trans. Reliability Engineering 26(1): 2-13.
Lin, F. 1994. Diagnosability of discrete event systems and its application. Discrete Event Dynamic Systems: Theory and Applications 4(2): 197-212.
Pouliezos, A. D., and Stavrakakis, G. S. 1994. Real Time Fault Monitoring of Industrial Processes. Boston, MA: Kluwer Academic Publishers.
Ramadge, P. J., and Wonham, W. M. 1989. The control of discrete-event systems. Proc. IEEE 77(1): 81-98.
Sampath, M. 1993. The extended diagnoser. Unpublished memorandum.
Sampath, M. 1995. A discrete event systems approach to failure diagnosis. PhD thesis, The University of Michigan.
Sampath, M., Lafortune, S., and Teneketzis, D. 1998. Active diagnosis of discrete-event systems. IEEE Trans. Automat. Contr. 43(7).
Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K., and Teneketzis, D. 1995. Diagnosability of discrete-event systems. IEEE Trans. Automat. Contr. 40(9): 1555-1575.
Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K., and Teneketzis, D. 1996. Failure diagnosis using discrete-event models. IEEE Trans. Contr. Syst. Tech. 4(2): 105-124.
Scherer, W. T., and White, C. C. 1987. A survey of expert systems for equipment maintenance and diagnostics. In Fault Detection and Reliability: Knowledge Based & Other Approaches (Singh, M. G., Hindi, K. S., Schmidt, G., and Tzafestas, S., eds.). Pergamon Press.
Speyer, J. L. 1979. Computation and transmission requirements for a decentralized linear-quadratic-gaussian control problem. IEEE Trans. Automat. Contr. 24: 266-269.
Washburn, R. B., and Teneketzis, D. 1984. Asymptotic agreement among communicating decision makers. Stochastics 13(1-2): 103-129.
Willsky, A. 1976. A survey of design methods for failure detection in dynamic systems. Automatica 12: 601-611.
Willsky, A. S., Bello, M., Castanon, D. A., Levy, B. C., and Verghese, G. 1982. Combining and updating of local estimates and regional maps along sets of one-dimensional tracks. IEEE Trans. Automat. Contr. 27(4): 799-813.
Wong, K., and van Schuppen, J. H. 1996. Decentralized supervisory control of discrete event systems with communications. Proc. of WODES 1996, International Workshop on Discrete Event Systems. IEE, London, England, pp. 284-289.
Rights and permissions
About this article
Cite this article
Debouk, R., Lafortune, S. & Teneketzis, D. Coordinated Decentralized Protocols for Failure Diagnosis of Discrete Event Systems. Discrete Event Dynamic Systems 10, 33–86 (2000). https://doi.org/10.1023/A:1008335115538
Issue Date:
DOI: https://doi.org/10.1023/A:1008335115538