Affiliations: CNRS/IRCCyN, 1 rue de la Noë, BP 92101,
44321 Nantes Cedex 3, France. franck.cassez@cnrs.irccyn.fr | Cadence Research Laboratories, 2150 Shattuck Avenue,
10th floor, Berkeley, CA, 94704, USA and CNRS, Verimag Laboratory, Centre
Equation, 2, avenue de Vignate, 38610 Gières, France.
tripakis@cadence.com
Note: [] Address for correspondence: CNRS/IRCCyN, 1 rue de la
Noë, BP 92101, 44321 Nantes Cedex 3, France
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 "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.
