OPTIMAL SENSOR SELECTION FOR STRUCTURAL OBSERVABILITY IN DISCRETE EVENT SYSTEMS MODELED BY PETRI NETS

This paper studies sensor selection problems in Discrete Event Systems modeled by Petri nets with outputs (i.e., Petri nets with both transition sensors and place sensors). The goal is to place sensors so as to maintain the property of structural observability, i.e., the ability to uniquely determine the system state based on sensor information and knowledge of the initial state of the system. The paper establishes that the place sensor selection problem (given a fixed labeling function) is NP-complete; but the transition sensor selection problem (given a fixed set of place sensors) can be solved efficiently in time that is polynomial in the number of places and transitions.