TY - JOUR
T1 - Approximating the minimal sensor selection for supervisory control
AU - Khuller, Samir
AU - Kortsarz, Guy
AU - Rohloff, Kurt R.
N1 - Funding Information:
1 This paper reports on work commenced while the third author was under the direction of Prof. Jan H. van Schuppen at C\-VI in Amsterdam. Financial support in part for the im'estigation was made avaiiable by the European Commission through the project Control and Computation (IST-2001-33520) of the Information Society Technologies Program and by ~SF grant CCR-0082184.
Publisher Copyright:
© 2004 IFAC.
PY - 2004
Y1 - 2004
N2 - This paper discusses the problem of selecting a set of sensors of minimum cardinality that can be used for the synthesis of a supervisory controller.We show how this sensor selection problem is related to a type of directed graph st-cut problem that has not been previously discussed in the literature. Approximation algorithms to solve the sensor selection problem can be used to solve the graph cut problem and vice-versa. Polynomial time algorithms to find good approximate solutions to either problem most likely do not exist (under certain complexity assumptions), but a time efficient approximation algorithm is shown that solves a special case of these problems.
AB - This paper discusses the problem of selecting a set of sensors of minimum cardinality that can be used for the synthesis of a supervisory controller.We show how this sensor selection problem is related to a type of directed graph st-cut problem that has not been previously discussed in the literature. Approximation algorithms to solve the sensor selection problem can be used to solve the graph cut problem and vice-versa. Polynomial time algorithms to find good approximate solutions to either problem most likely do not exist (under certain complexity assumptions), but a time efficient approximation algorithm is shown that solves a special case of these problems.
KW - Approximation algorithms
KW - Computer-aided control system design
KW - Discrete-event systems. supervisory control graph theory
KW - Observers
UR - http://www.scopus.com/inward/record.url?scp=85064566985&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85064566985&partnerID=8YFLogxK
U2 - 10.1016/S1474-6670(17)30727-9
DO - 10.1016/S1474-6670(17)30727-9
M3 - Conference article
AN - SCOPUS:85064566985
SN - 1474-6670
VL - 37
SP - 87
EP - 92
JO - IFAC Proceedings Volumes (IFAC-PapersOnline)
JF - IFAC Proceedings Volumes (IFAC-PapersOnline)
IS - 18
T2 - 7th International Workshop on Discrete Event Systems, WODES 2004
Y2 - 22 September 2004 through 24 September 2004
ER -