On Most Permissive Observers in Dynamic Sensor Activation Problems

We consider the problem of dynamic sensor activation for fault diagnosis of discrete event systems modeled by finite state automata under the constraint that any fault must be diagnosed within no more than K + 1 events after its occurrence, a property called K-diagnosability. We begin by defining an appropriate notion of information state for the problem and defining dynamic versions of the projection operator and information state evolution. We continue by showing that the problem can be reduced to that of state disambiguation. Then we define the most permissive observer (MPO) structure that contains all the solutions to the problem, and we prove results showing that maintaining the K-diagnosability property is equivalent to satisfying the extended specification of the state disambiguation problem. We then prove a monotonicity property of the extended specification, and show that this allows us to reduce our information state, which in turn allows us to significantly reduce the complexity of our solution. Putting all of our results together, we obtain a MPO with a size complexity of O(2^|X|(K+2)^|X|2^|E|), compared with O(2^|X|2 ·K ·2^|E|) for the previous approach, where X and E are, respectively, the sets of states and events of the automaton to diagnose. Finally, we provide an algorithm for constructing the most permissive observer and demonstrate its scalability through simulation.