Paper Info
Title
An online algorithm for minimal sensor activation in discrete event systems
Abstract
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.
Year
DOI
Venue
2009
10.1109/CDC.2009.5400888
CDC
Keywords
Field
DocType
observability,finite automata,finite automaton,discrete event systems,online algorithm,polynomial complexity algorithm,supervisory control,polynomial approximation,computational complexity,minimal sensor activation,sensors,online sensor activation,state estimate,satisfiability,polynomials,automata,data mining,trajectory,optimization
Online algorithm,Mathematical optimization,Observability,Polynomial,Computer science,Supervisory control,Automaton,Finite-state machine,Trajectory,Computational complexity theory
Conference
ISSN
ISBN
Citations 
0191-2216 E-ISBN : 978-1-4244-3872-3
978-1-4244-3872-3
8
PageRank 
References 
Authors
0.62
14
4
Name
Order
Citations
PageRank
Weilin Wang1627.29
StéPhane Lafortune21738181.23
Feng Lin342656.30
Anouck R. Girard413520.51