DocumentCode
2066394
Title
How hard is it to control switched systems?
Author
Egerstedt, Magnus ; Blondel, Vincent D.
Author_Institution
Georgia Inst. of Technol., Atlanta, GA, USA
Volume
3
fYear
2002
fDate
2002
Firstpage
1869
Abstract
We show that the problem of deciding if there exists a control that drives a switched control system between two given states is undecidable. We furthermore investigate what happens if we search for a control that achieves this in a given number of steps, or with a given number of switches. These problems are shown to be respectively NP-complete and NP-hard. The results follow as a consequence of recent complexity results on matrix mortality.
Keywords
computational complexity; controllability; discrete time systems; matrix inversion; path planning; NP-complete problem; NP-hard problem; computational complexity; controllability; matrix algebra; path planning; polynomial time; switched systems; Artificial intelligence; Computational complexity; Control systems; Controllability; Drives; Legged locomotion; Stability; State-space methods; Switched systems; Switches;
fLanguage
English
Publisher
ieee
Conference_Titel
American Control Conference, 2002. Proceedings of the 2002
ISSN
0743-1619
Print_ISBN
0-7803-7298-0
Type
conf
DOI
10.1109/ACC.2002.1023905
Filename
1023905
Link To Document