On the complexity of the constrained input selection problem for structural linear systems

• Tipo: Artigo em Revista Científica Internacional
• Data: 2015

Autores

Pequito, S (Autor) Outra; Kar, S (Autor) Outra; Aguiar, AP (Autor) FEUP

Revista

Título: Automatica

Vol. 62

Páginas: 193-199

ISSN: 0005-1098

Editora: Elsevier

Indexação

ISI Web of Knowledge - 39 Citações

Scopus - 39 Citações

Outras Informações

ID Authenticus: P-00G-WZS

DOI: 10.1016/j.automatica.2015.06.022

Abstract (EN): This paper studies the problem of, given the structure of a linear-time invariant system and a set of possible inputs, finding the smallest subset of input vectors that ensures system's structural controllability. We refer to this problem as the minimum constrained input selection (minCIS) problem, since the selection has to be performed on an initial given set of possible inputs. We prove that the minCIS problem is NP-hard, which addresses a recent open question of whether there exist polynomial algorithms (in the size of the system plant matrices) that solve the minCIS problem. To this end, we show that the associated decision problem, to be referred to as the CIS, of determining whether a subset (of a given collection of inputs) with a prescribed cardinality exists that ensures structural controllability, is NP-complete. Further, we explore in detail practically important subclasses of the minCIS obtained by introducing more specific assumptions either on the system dynamics or the input set instances for which systematic solution methods are provided by constructing explicit reductions to well known computational problems. The analytical findings are illustrated through examples in multi-agent leader-follower type control problems.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 7