PaperlayerView exact revision on arXiv

Source-linked AI summary

A Framework for Structural Input/Output and Control Configuration Selection in Large-Scale Systems

Sergio Pequito, Soummya Kar, A. Pedro Aguiar

arXiv:1309.5868v3math.OCeess.SY

TL;DR

The paper formulates structural input/output and feedback-configuration problems for large-scale systems. It develops graph-theoretic characterizations and a unified framework with polynomial-complexity algorithms for computing global solutions.

  • Problem

    The paper addresses structural design problems involving input/output selection and feedback configuration for large-scale systems.

  • Method

    The paper uses graph-theoretic characterizations and a unified framework to characterize possible solutions and construct control configurations.

  • Results

    Polynomial-complexity algorithms in the number of state variables systematically compute solutions to the addressed minimization problems.

  • Takeaways & Limitations

    The framework jointly addresses input/output selection for structural controllability and observability and feedback-edge selection for closed-loop systems without structurally fixed modes.

Abstract

from arXiv · show

This paper addresses problems on the structural design of control systems taking explicitly into consideration the possible application to large-scale systems. We provide an efficient and unified framework to solve the following major minimization problems: (i) selection of the minimum number of manipulated/measured variables to achieve structural controllability/observability of the system, and (ii) selection of the minimum number of feedback interconnections between measured and manipulated variables such that the closed-loop system has no structurally fixed modes. Contrary to what would be expected, we show that it is possible to obtain a global solution for each of the aforementioned minimization problems using polynomial complexity algorithms in the number of the state variables of the system. In addition, we provide several new graph-theoretic characterizations of structural systems concepts, which, in turn, enable us to characterize all possible solutions to the above problems.

I. INTRODUCTION

The paper formulates structural input/output and control-configuration selection for large-scale linear time-invariant systems. It develops a unified structural-systems framework to identify sparse configurations that ensure controllability, observability, and fixed-mode-free closed-loop behavior.

  • Structural design questions: The design problem asks which variables should be measured, manipulated, and interconnected in large-scale complex control systems.These choices affect control-system performance, complexity, and costs, while their combinatorial nature motivates systematic methods.
  • Problem classification: Problems 1–2 are input/output selection, while problem 3 is control-configuration selection for feedback links.Control-configuration selection is important in decentralized control because selected sensors and local controllers must be connected to preserve properties such as stability.
  • Structural-systems framework: Structural systems theory analyzes system-theoretic properties from the sparsity pattern of system matrices rather than accurately known numerical parameter values.The structural guarantees apply to almost all numerical instances, except on a manifold of zero Lebesgue measure.
  • Target properties: The framework targets structural controllability and observability for I/O selection and absence of structurally fixed modes for control-configuration selection.The latter property has implications for generic pole placement in decentralized control systems.
  • I/O selection: The paper seeks structural input and output matrices that ensure controllability and observability, including sparsest configurations with the minimum number of dedicated inputs and outputs.Dedicated inputs manipulate at most one state variable each, while dedicated outputs measure one state variable each.

1 Given ¯A associated with (1), find ( ¯B, ¯C) that solve

The paper formulates sparsest input/output and joint input/output–control-configuration selection under structural controllability, observability, and absence of structurally fixed modes. It develops globally optimal solutions and characterizes their relationship through mixed-pairing.

  • I/O selection: P1 seeks structural input and output patterns that minimize connections while ensuring structural controllability and observability.The corresponding constraints are stated as (Ā,B̄) structurally controllable and (Ā,C̄) structurally observable.
  • Scope and characterization: The framework addresses general information patterns rather than restricting K̄ to block-diagonal structure and characterizes all possible solutions to the design problems.The paper contrasts its setting with partitioning or pairing problems that impose block-diagonal information patterns.
  • Control configuration selection: P2 seeks B̄, K̄, and C̄ with no structurally fixed modes, allowing arbitrary pole placement for almost all compatible realizations.The information pattern K̄ specifies which outputs are available to each input.
  • Relationship between problems: The paper shows that some P1 solutions solve P2 optimally, while every P2 solution can be characterized using a P1 solution and mixed-pairing.Mixed-pairing is described as a pairing between inputs and outputs.
  • Complexity: The sparsest I/O selection problem is shown to be polynomially solvable in system size, unlike the cited numerical minimal controllability problem, which is NP-hard.The paper identifies problem (2a) as the structural counterpart and states polynomial complexity in the system size.

1. Next, inspired by the solution

The paper introduces new graph-theoretic characterizations for structural controllability and observability, then uses them to derive solution descriptions and polynomial-complexity procedures for the selection problems. It also characterizes all possible designs and illustrates the results with an example.

  • Structural characterizations: A new necessary-and-sufficient graph-theoretic condition for structural controllability also yields structural observability by duality.The condition is presented before the paper develops solutions to the selection problems.
  • Algorithmic framework: The graph representation supports computation and characterization of solutions for the dedicated, sparsest, and joint I/O and control-configuration problems.The procedures use the original system digraph, its directed acyclic graph representation, and bipartite graph representations.
  • Solution characterization: The paper describes all possible solutions to the respective design problems rather than only constructing one feasible design.This includes solution descriptions for the I/O and control-configuration problems.
  • Complexity: Polynomial-complexity procedures compute solutions to the dedicated I/O, I/O, and control-configuration selection problems.The paper states that these procedures are developed for the number of state variables as the relevant system-size measure.
  • Illustration: An illustrative example explores the solutions to the different problems addressed in the paper.The example appears after the algorithmic procedures and before the conclusion.

II. PRELIMINARIES AND TERMINOLOGY

The preliminaries represent structural LTI systems with digraphs and bipartite graphs. They define effective inputs and outputs, SCC-based DAG structure, reachability, and matching terminology used in the subsequent analysis.

  • Graph representations: The structural patterns Ā, B̄, and C̄ encode nonzero relationships among state, input, and output variables.Their associated digraphs include state transitions, input-to-state edges, and state-to-output edges; K̄ adds output-to-input feedback edges.
  • Effective I/O: Effective inputs are the nonzero columns of B̄ connected to at least one state vertex, with an analogous interpretation for outputs.Zero columns correspond to isolated input vertices in the system digraph.
  • SCCs and DAGs: A strongly connected component is a maximal subgraph with mutual reachability, and collapsing SCCs produces an acyclic directed graph.The resulting DAG can be generated with complexity O(|V| + |E|).
  • SCC classifications: Non-top-linked SCCs have no incoming edges from other SCCs, whereas non-bottom-linked SCCs have no outgoing edges to other SCCs.These classifications are defined on the SCC condensation structure.
  • Bipartite matchings: A matching is a set of bipartite edges sharing no vertices, and a maximum matching has the largest possible number of edges.Matched and unmatched vertices are defined relative to a particular matching, which need not be unique.
  • Bipartite matchings: Weighted maximum matching selects a maximum matching with minimum or maximum total edge weight and can be solved using the Hungarian algorithm in O(max{|S1|,|S2|}^3).The complexity is stated for bipartite vertex sets S1 and S2.

A. Structural Controllability and Observability

The paper characterizes structural controllability and observability using graph decompositions into input, output, and state cacti. These characterizations connect controllability and observability to spanning cactus structures in system digraphs.

  • An input stem links an input vertex to the root of a state stem, while an output stem links a state-stem tip to an output vertex.
  • Input cacti extend input stems by attaching state-only cycles, and output cacti analogously extend output stems with cycles.
  • An input-output cactus combines an input-output stem with cycles connected to or from its vertices.
  • Structural controllability is equivalent to the state-input digraph being spanned by a disjoint union of input cacti.
  • Structural observability holds exactly when the transposed system is structurally controllable, equivalently when the system digraph is spanned by output cacti.

B. Structural Fixed Modes 

The paper defines structurally fixed modes and states graph-theoretic conditions for eliminating them through output feedback. Absence of structurally fixed modes supports almost arbitrary pole placement within the structural sparsity class.

  • Structurally fixed modes are eigenvalues that remain fixed across all numerical realizations and allowable feedback matrices in an information pattern.
  • A structural system has no structurally fixed modes when at least one compatible realization has no fixed modes.
  • When no structurally fixed modes exist, almost all systems in the sparsity class permit pole placement arbitrarily close to prescribed eigenvalues.
  • The graph characterization requires every state vertex to lie in an SCC containing an output-feedback edge.
  • It also requires a finite disjoint union of cycles in the closed-loop system digraph.

III. SOLUTION TO PROBLEM Pd

This section develops graph-theoretic characterizations of feasible dedicated input and output configurations. Maximum matchings, unmatched vertices, and assignable strongly connected components determine minimum configurations and all corresponding solutions.

  • A maximum matching decomposes the state digraph into disjoint cycles and state stems spanning the system, with roots at right-unmatched vertices and tips at left-unmatched vertices.
  • A dedicated input configuration is feasible exactly when it includes right-unmatched vertices from some maximum matching and one state variable from each non-top linked SCC.
  • The minimum number of dedicated inputs is determined by the number of right-unmatched vertices and the maximum top assignability index.
  • For strongly connected systems, the minimum input count simplifies to p = max(m, 1).
  • Minimal feasible configurations use right-unmatched vertices from a maximum-top-assignability matching and one variable from every remaining non-top linked SCC.
  • Polynomial-complexity procedures construct minimal feasible dedicated configurations and thereby solve the associated structural input-output design problem.

IV. SOLUTION TO PROBLEM P1

This section characterizes and constructs minimum-input structural controllability designs, then extends them by duality to output design and joint input-output configuration selection. The framework identifies both minimum effective inputs and sparsest link patterns.

  • The minimum number of links between inputs and states is m + β − α, and all sparsest input configurations are explicitly characterized.
  • By duality, the same characterizations extend to output design and jointly yield solutions to problem P1.
  • Structural controllability holds when inputs cover right-unmatched vertices of a maximum matching and include one state variable from each non-top linked SCC.
  • Inputs assigned to distinct right-unmatched states must be distinct, whereas inputs assigned to additional SCC states may be shared.
  • The effective-input lower bound is max(m, 1), where m is the number of right-unmatched vertices in a maximum matching.
  • A structural input matrix solves problem (2a) exactly when it belongs to I(M) for a maximum matching M with maximum top assignability.

V. SOLUTION TO PROBLEM P2

The paper characterizes all feasible solutions to P2 by combining minimal input/output configurations with feedback patterns derived from maximum matchings and mix-pairings. It shows that the minimum feedback-link bound is achievable while satisfying the structural conditions of Theorem 2.

  • Characterization of P2 solutions: Theorem 10 states that a solution to P2 consists of a minimal P1 configuration together with a feedback pattern meeting the characterized pairing conditions.The result characterizes all such solutions rather than only one construction.
  • Graph-theoretic characterization: A common maximum matching M* combines separate input and output matchings and decomposes the joint digraph into cycles and input-output stems.This separation principle supports the feedback-design characterization.
  • Special case: When the state bipartite graph has a perfect matching, one effective input and output suffice, and a single feedback link can produce one SCC containing a feedback edge.In this case, the optimal information pattern has one nonzero entry.
  • Minimality: Exactly m input-output stems arise from the common matching, and appropriately pairing their endpoints makes max(m, 1) feedback edges sufficient.The resulting pairing can also satisfy the remaining Theorem 2 condition, establishing achievability of the lower bound.
  • Mix-pairings: For a maximum matching, disjoint subsets S_i of matched edges define mix-pairings that satisfy Theorem 2 conditions under specified constructions.One construction uses all matched edges in a particular subset, yielding both conditions.
  • Minimality: The sparsest feasible feedback pattern uses max(m, 1) links, where m is the number of right- or left-unmatched vertices.Fewer effective inputs or outputs would violate structural controllability or observability, while fewer feedback links cannot satisfy the required condition.

VI. ALGORITHMIC PROCEDURE AND COMPLEXITY ANALYSIS

The paper gives a polynomial-time algorithm for computing a minimal feasible dedicated input configuration using SCC structure and weighted maximum matching. The algorithm is correct, has complexity O(|X|^3), and returns the minimum number of dedicated inputs as |S_u|.

  • Algorithm 1: Algorithm 1 computes a minimal feasible dedicated input configuration by identifying non-top linked SCCs and solving a weighted bipartite matching problem with slack variables.Edges receive infinite, unit, or two-unit costs depending on whether they are unavailable, state-graph edges, or slack-variable edges.
  • Correctness and complexity: Theorem 11 proves Algorithm 1 correct and gives it complexity O(|X|^3), where |X| is the number of state vertices.The output is a minimal feasible dedicated input configuration S_u.
  • Correctness and complexity: The minimum number of dedicated inputs required for structural controllability is |S_u|, computed by the algorithm.The construction is especially useful because the underlying selection problem is combinatorial while the proposed procedure has polynomial complexity.
  • Illustrative example: In the worked example, m = 2, β = 2, and α = 2, yielding p = m + β − α = 2 dedicated inputs.The resulting minimal feasible input configuration is {x2, x4}.
  • Illustrative example: The example's only minimal feasible input configuration is {x2, x4}, whose two input-state edges produce a structurally controllable system.The input labels may be permuted across the two selected state variables.

VIII. CONCLUSIONS AND FURTHER RESEARCH

The paper presents a unified framework for sparse I/O and feedback configuration selection in structural systems, with polynomial-complexity procedures and graph-theoretic characterizations of solutions.

  • VIII. CONCLUSIONS AND FURTHER RESEARCH: The paper provides graph-theoretic characterizations of all possible solutions to the addressed structural design problems.These characterizations complement the algorithmic procedures for selecting sparse configurations.
  • VIII. CONCLUSIONS AND FURTHER RESEARCH: The framework jointly addresses sparse input/output configurations for structural controllability and observability and sparse feedback patterns preventing structurally fixed modes.It considers dedicated or non-dedicated inputs and outputs, as well as minimum feedback-edge configurations.
  • VIII. CONCLUSIONS AND FURTHER RESEARCH: The proposed algorithms compute solutions to the structural design problems in polynomial complexity in the number of state variables.The procedures apply to the I/O and control-configuration selection problems.
  • VIII. CONCLUSIONS AND FURTHER RESEARCH: A future research direction is extending the framework to heterogeneous actuation, measurement, and communication costs.The extension would allow costs to vary across state variables and input-output feedback pairs.

APPENDIX A

The appendix develops matching- and digraph-based constructions to prove minimality and characterize feasible dedicated configurations and feedback information patterns.

  • APPENDIX A: A matching in the state bipartite graph corresponds to a spanning decomposition into disjoint state stems and cycles.This correspondence supports decomposition-based proofs of structural design properties.
  • APPENDIX A: The decomposition induced by a maximum matching is shown to use the minimum possible number of state stems.The proof proceeds by contradiction against any decomposition with fewer stems.
  • APPENDIX A: Dedicated input feasibility requires reaching every non-top linked strongly connected component from selected state vertices.Otherwise, an uncovered component cannot belong to a state-cacti decomposition rooted in the selected inputs.
  • APPENDIX A: Reachability partitions the digraph into subgraphs that can be spanned by disjoint state cacti rooted in the selected unmatched and additional input vertices.The construction separates the reachable region from its complement and builds cactus decompositions for both.
  • APPENDIX A: The appendix characterizes feedback information patterns through constructions based on matchings and input-output stems.A suitable pattern can produce a single strongly connected closed-loop digraph containing feedback links, while the construction includes patterns with fewer links.
  • APPENDIX A: Solutions to the main selection problems can be computed with polynomial complexity once minimal feasible dedicated input/output configurations are available.The appendix connects the construction procedures for the earlier problems to the polynomial-complexity result.
Loading 1309.5868v3…