Title :
How hard is it to control switched systems?
Author :
Egerstedt, Magnus ; Blondel, Vincent D.
Author_Institution :
Georgia Inst. of Technol., Atlanta, GA, USA
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;
Conference_Titel :
American Control Conference, 2002. Proceedings of the 2002
Print_ISBN :
0-7803-7298-0
DOI :
10.1109/ACC.2002.1023905
