Computational complexity for state-feedback controllers with partial observation

Author

Kalyon, Gabriel ; Le Gall, Tristan ; Marchand, Hervé ; Massart, Thierry

Author_Institution

Univ. Libre de Bruxelles, Brussels, Belgium

fYear

2009

fDate

9-11 Dec. 2009

Firstpage

435

Lastpage

441

Abstract

We study the computational complexity of several decision and optimization control problems arising in partially observed discrete event systems. These problems are related to the state avoidance problem where one must compute a controller which prevents the system from accessing a set of bad states and which is maximal for a defined criterion, based on inclusion of the set of states remaining reachable after the control. We focus our study on memoryless controllers.

Keywords

computational complexity; control system synthesis; discrete systems; memoryless systems; state feedback; computational complexity; memoryless controllers; partially observed discrete event systems; state avoidance problem; state-feedback controllers; Automatic control; Automation; Computational complexity; Control system synthesis; Control systems; Discrete event systems; NP-hard problem; Optimal control; Polynomials; State-space methods; Computational Complexity; Controller Synthesis; Discrete Event Systems; Partial Observation;

fLanguage

English

Publisher

ieee

Conference_Titel

Control and Automation, 2009. ICCA 2009. IEEE International Conference on

Conference_Location

Christchurch

Print_ISBN

978-1-4244-4706-0

Electronic_ISBN

978-1-4244-4707-7

Type

conf

DOI

10.1109/ICCA.2009.5410356

Filename

5410356