Structural Minimum Controllability Problem for Linear Continuous-Time Switching Systems

Sérgio Daniel Pequito, George J. PappasarXiv 2015 · OpenReview

TL;DR

This paper tackles the problem of finding the minimal set of actuators needed to make a switched linear system controllable, considering its underlying structure rather than specific parameter values. They introduce a novel condition combining graph-theoretic and algebraic properties, leading to an efficient algorithm for finding these minimal actuator configurations.

What Problem Does This Paper Address?

Controlling complex systems, especially those that switch between different operational modes (like a car's engine control or a power grid), is a significant challenge. A key aspect is ensuring that we can steer the system to any desired state from any initial state – a property known as controllability. For large-scale systems, it's often impractical or too expensive to control every single component. This paper focuses on "structural controllability," which means the system is controllable for some choice of parameters, making it robust to uncertainties. Specifically, they address the "structural minimum controllability problem" for switched linear continuous-time systems: finding the smallest set of "actuated" state variables (those we can directly influence) that guarantees structural controllability across all possible system modes. This is crucial for designing efficient and cost-effective control systems.

Methods

The authors propose a new necessary and sufficient condition for structural controllability of switched linear systems. This condition cleverly combines:

  • Graph-theoretic properties: Analyzing the structure of the system using directed graphs (digraphs) to understand how inputs can reach states. They leverage concepts like strongly connected components (SCCs) and non-top linked SCCs.
  • Algebraic properties: Using the concept of generic rank (g-rank) to assess controllability based on the structure of system matrices.

Based on this condition, they develop an algorithm (Algorithm 1) that efficiently determines a "dedicated solution" – where each actuator influences only one state variable. This algorithm involves constructing a weighted bipartite graph and finding a minimum weight maximum matching (MWMM), a technique often solved using algorithms like the Hungarian algorithm. They also characterize all possible minimal solutions and discuss the properties of switching signals that ensure controllability.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development for a general class of systems.

Key Insights and Ideas

  • Bridging Graph and Algebra: The core insight is that structural controllability in switched systems requires a unified approach, combining both the connectivity information from graph theory and the rank properties from linear algebra. This is a departure from some prior work that might lean more heavily on one aspect.
  • Dedicated Solutions are Key: The paper shows that finding a "dedicated solution" (where each actuator controls a single state) is a fundamental step towards solving the broader problem. This simplifies the design and analysis.
  • Switching Signal Complexity: While finding the minimal set of actuators is computationally tractable (polynomial time), determining the minimum number of modes a switching signal needs to ensure controllability is NP-hard. This highlights a trade-off: we can efficiently design what to control, but finding the optimal when to switch can be computationally challenging.
  • Structural Properties are Mode-Agnostic (Mostly): The paper notes that the order of modes in a switching signal doesn't affect structural controllability, as the underlying conditions are invariant to permutation. However, certain modes might be more "crucial" for controllability, influencing the choice of actuators.

Key Results

  • A new necessary and sufficient condition for structural controllability of switched linear continuous-time systems, combining graph-theoretic and algebraic properties.
  • An efficient (polynomial time) algorithm for finding a "dedicated solution" to the structural minimum controllability problem. The complexity is bounded by $O((mn+\beta)^\alpha)$, where $n$ is the number of states, $m$ is the number of modes, $\beta$ is related to non-top linked SCCs, and $\alpha < 2.373$ is the matrix multiplication exponent.
  • Characterization of all minimal solutions to the problem.
  • Demonstration that determining the minimum number of modes required for structural controllability is NP-hard.

Limitations and Future Work

  • Computational Complexity of Switching: The NP-hardness result for determining the minimum number of modes for controllability suggests that finding optimal switching sequences can be computationally prohibitive for large systems.
  • Future Research Directions: The authors suggest several avenues:
  • Considering different actuation costs for state variables and actuators.
  • Investigating possible switching sequences and their impact on controllability.
  • Exploring sparsest feedback patterns to ensure stabilizability (a related but distinct property from controllability).
  • Extending the analysis to more complex system types or control objectives.

Summary updated

Abstract

This paper addresses a structural design problem in control systems, and explicitly takes into consideration the possible application to large-scale systems. More precisely, we aim to determine and characterize the minimum number of manipulated state variables ensuring structural controllability of switched linear continuous-time systems. Towards this goal, we provide a new necessary and sufficient condition that leverages both graph-theoretic and algebraic properties required to ensure feasibility of the solutions. With this new condition, we show that a solution can be determined by an efficient procedure, i.e., polynomial in the number of state variables. In addition, we also discuss the switching signal properties that ensure structural controllability and the computational complexity of determining these sequences. In particular, we show that determining the minimum number of modes that a switching signal requires to ensure structural controllability is NP-hard.
BibTeX
@misc{pequito2015structural,
  author = {Sérgio Daniel Pequito and George J. Pappas},
  title = {{Structural Minimum Controllability Problem for Linear Continuous-Time Switching Systems}},
  year = {2015},
  eprint = {1507.07207},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1507.07207},
}

Loading related content...

Figure