Fault Diagnosis with Static and Dynamic Diagnosers

Fault Diagnosis with Static and Dynamic Diagnosers. Cassez, F. & Tripakis, S. Fundamenta Informaticae, 88(4):497–540, November, 2008.

Paper abstract bibtex

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 ``switc'' 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 a most 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.

@article{cassez-fi-08,
  AUTHOR = {Franck Cassez and Tripakis, Stavros},
  TITLE = {Fault Diagnosis with Static and Dynamic Diagnosers},
  JOURNAL = {Fundamenta Informaticae},
  YEAR = {2008},
    Type = {A - Journal},

  VOLUME = {88},
  NUMBER = {4},
  PAGES = {497--540},
  keywords = {fault diagnosis, automata},
  MONTH = NOV,
  ABSTRACT = {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 ``switc'' 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 a most 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.  },
  urlpaper = {papers/diag-fi-08.pdf},
}

Downloads: 0

{"_id":"km5KeWXHoQm6czrB2","bibbaseid":"cassez-tripakis-faultdiagnosiswithstaticanddynamicdiagnosers-2008","author_short":["Cassez, F.","Tripakis, S."],"bibdata":{"bibtype":"article","type":"A - Journal","author":[{"firstnames":["Franck"],"propositions":[],"lastnames":["Cassez"],"suffixes":[]},{"propositions":[],"lastnames":["Tripakis"],"firstnames":["Stavros"],"suffixes":[]}],"title":"Fault Diagnosis with Static and Dynamic Diagnosers","journal":"Fundamenta Informaticae","year":"2008","volume":"88","number":"4","pages":"497–540","keywords":"fault diagnosis, automata","month":"November","abstract":"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 ``switc'' 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 a most 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. ","urlpaper":"papers/diag-fi-08.pdf","bibtex":"@article{cassez-fi-08,\n AUTHOR = {Franck Cassez and Tripakis, Stavros},\n TITLE = {Fault Diagnosis with Static and Dynamic Diagnosers},\n JOURNAL = {Fundamenta Informaticae},\n YEAR = {2008},\n Type = {A - Journal},\n\n VOLUME = {88},\n NUMBER = {4},\n PAGES = {497--540},\n keywords = {fault diagnosis, automata},\n MONTH = NOV,\n ABSTRACT = {We study sensor minimization problems in the context of\n fault diagnosis. Fault diagnosis consists in\n synthesizing a diagnoser that observes a given plant\n and identifies faults in the plant as soon as\n possible after their occurrence. Existing literature\n on this problem has considered the case of fixed\n static observers, where the set of observable events\n is fixed and does not change during execution of the\n system. In this paper, we consider static observers\n where the set of observable events is not fixed, but\n needs to be optimized (e.g., minimized in size). We\n also consider dynamic observers, where the observer\n can ``switc'' sensors on or off, thus dynamically\n changing the set of events it wishes to observe. It\n is known that checking diagnosability (i.e., whether\n a given observer is capable of identifying faults)\n can be solved in polynomial time for static\n observers, and we show that the same is true for\n dynamic ones. On the other hand, minimizing the\n number of (static) observable events required to\n achieve diagnosability is NP-complete. We show that\n this is true also in the case of mask-based\n observation, where some events are observable but\n not distinguishable. For dynamic observers'\n synthesis, we prove that a most permissive\n finite-state observer can be computed in doubly\n exponential time, using a game-theoretic\n approach. We further investigate optimization\n problems for dynamic observers and define a notion of\n cost of an observer. We show how to compute an\n optimal observer using results on mean-payoff games\n by Zwick and Paterson. },\n urlpaper = {papers/diag-fi-08.pdf},\n}\n\n","author_short":["Cassez, F.","Tripakis, S."],"key":"cassez-fi-08","id":"cassez-fi-08","bibbaseid":"cassez-tripakis-faultdiagnosiswithstaticanddynamicdiagnosers-2008","role":"author","urls":{"Paper":"http://science.mq.edu.au/~fcassez/bib/papers/diag-fi-08.pdf"},"keyword":["fault diagnosis","automata"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"http://science.mq.edu.au/~fcassez/bib/franck-bib.bib","dataSources":["8742EsvjQfyP2fYBW","qbqYFWskmoonRB43F","yYF8uwWqay28JyxZC"],"keywords":["fault diagnosis","automata"],"search_terms":["fault","diagnosis","static","dynamic","diagnosers","cassez","tripakis"],"title":"Fault Diagnosis with Static and Dynamic Diagnosers","year":2008}