Approximating the minimal sensor selection for supervisory control

Samir Khuller, Guy Kortsarz, Kurt R. Rohloff

Research output: Contribution to journalConference article

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)87-92
Number of pages6
JournalIFAC Proceedings Volumes (IFAC-PapersOnline)
Volume37
Issue number18
DOIs
StatePublished - Jan 1 2004
Event7th International Workshop on Discrete Event Systems, WODES 2004 - Reims, France
Duration: Sep 22 2004Sep 24 2004

Keywords

  • Approximation algorithms
  • Computer-aided control system design
  • Discrete-event systems. supervisory control graph theory
  • Observers

ASJC Scopus subject areas

  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Approximating the minimal sensor selection for supervisory control'. Together they form a unique fingerprint.

  • Cite this