An online algorithm for minimal sensor activation in discrete event systems

To observe occurrences of an event in a discrete event system, a sensor must be placed and activated. Both placement and activation incur costs. Assuming sensors have been placed, to minimize costs, one would like to minimize the activation of the sensors. In this paper, an online algorithm is developed to minimize sensor activation. The discrete event system under consideration is modeled by a finite automaton. The objective of observation is to distinguish certain pairs of states in the automaton, which are called a specification. This specification is extended to account for future evolution of the system under partial observation. Using the extended specification, the online algorithm presented needs only to look one step ahead and requires only to remember the current state estimate. The algorithm is of polynomial complexity at each step. The activation policy generated by the online algorithm is proved to be feasible, minimal, and to satisfy the specification. An example is presented to illustrate the results.