Approximating optimal place sensor selection for structural observability in discrete event systems modeled by Petri Nets

In this paper, we study place sensor selection problems in discrete event systems modeled by Petri nets with outputs (i.e., Petri nets with transition and place sensors). Our goal is to place a minimal number of 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 system model and initial state). The place sensor selection problem has been shown to be NP-complete and this paper proposes two efficient algorithms to approximate its solution. Simulations suggest that the two methods run faster and can find reasonably good solutions compared to methods that are based on linear integer programming solvers.