The robust minimal controllability problem
From MaRDI portal
Publication:2409157
Abstract: In this paper, we address two minimal controllability problems, where the goal is to determine a minimal subset of state variables in a linear time-invariant system to be actuated to ensure controllability under additional constraints. First, we study the problem of characterizing the sparsest input matrices that assure controllability when the autonomous dynamics' matrix is simple. Secondly, we build upon these results to describe the solutions to the robust minimal controllability problem, where the goal is to determine the sparsest input matrix ensuring controllability when specified number of inputs fail. Both problems are NP-hard, but under the assumption that the dynamics' matrix is simple, we show that it is possible to reduce these two problems to set multi-covering problems. Consequently, these problems share the same computational complexity, i.e., they are NP-complete, but polynomial algorithms to approximate the solutions of a set multi-covering problem can be leveraged to obtain close-to-optimal solutions to either of the minimal controllability problems.
Recommendations
- The single-input minimal controllability problem for structured systems
- Structural minimum controllability problem for switched linear continuous-time systems
- On the complexity of the constrained input selection problem for structural linear systems
- Minimal controllability of conjunctive Boolean networks is NP-complete
- Input matrix construction and approximation using a graphic approach
Cites work
- A Framework for Structural Input/Output and Control Configuration Selection in Large-Scale Systems
- A review of methods for input/output selection
- Almost optimal set covers in finite VC-dimension
- Controllability and Observability of Grid Graphs via Reduction and Symmetries
- Controllability Metrics, Limitations and Algorithms for Complex Networks
- Controllability of multi-agent systems from a graph-theoretic perspective
- Dynamic Attack Detection in Cyber-Physical Systems With Side Initial State Information
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- Exact algorithms for set multicover and multiset multicover problems
- Generic properties and control of linear structured systems: A survey
- Graph Controllability Classes for the Laplacian Leader-Follower Dynamics
- scientific article; zbMATH DE number 1667424 (Why is no real title available?)
- scientific article; zbMATH DE number 3987117 (Why is no real title available?)
- scientific article; zbMATH DE number 3594998 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Interacting with Networks: How Does Structure Relate to Controllability in Single-Leader, Consensus Networks?
- Large-scale dynamic systems. Stability and structure
- Linear systems theory.
- Minimal Controllability Problems
- Number and placement of control system components considering possible failures
- Observability in Connected Strongly Regular Graphs and Distance Regular Graphs
- On the Controllability Properties of Circulant Networks
- On the Reachability and Observability of Path and Cycle Graphs
- On the set multicover problem in geometric settings
- Random matrices have simple spectrum
- Secure Estimation and Control for Cyber-Physical Systems Under Adversarial Attacks
- Templates for the Solution of Algebraic Eigenvalue Problems
- The complexity of the matrix eigenproblem
- The robust minimal controllability problem
Cited in
(36)- Minimum structural controllability problems of complex networks
- Minimal controllability of conjunctive Boolean networks is NP-complete
- Networks with diagonal controllability Gramian: analysis, graphical conditions, and design algorithms
- Robustness of minimax controllers to nonlinear perturbations
- Key node selection in minimum-cost control of complex networks
- The controllability Gramian of lattice graphs
- A separation theorem for joint sensor and actuator scheduling with guaranteed performance bounds
- Feedback robustness in structured closed-loop system
- Strategic sensor placement on graphs
- Structurally quotient fixed modes
- The robust minimal controllability problem
- Minimum cost input/output design for large-scale linear structural systems
- On the Robustness of Nominal Nonlinear Minimum-Time Control and Extension to Non-Robustly Controllable Target Sets
- Robust control of large-scale systems: efficient selection of inputs and outputs
- scientific article; zbMATH DE number 4181206 (Why is no real title available?)
- Robustness of a minimal controller synthesis algorithm
- Nonlinear robust control and minimax team problems
- On three puzzles in robust control
- Input matrix construction and approximation using a graphic approach
- Structural minimum controllability problem for switched linear continuous-time systems
- Minimal structural perturbations for controllability of a networked system: complexities and approximations
- General resilient consensus algorithms
- A Survey of Determinacy of Infinite Games in Second Order Arithmetic
- The robust minimal controllability and observability problem
- Graph-theoretic approaches for analyzing the resilience of distributed control systems: a tutorial and survey
- On polynomially solvable constrained input selections for fixed and switched linear structured systems
- THE ACTUATION SPECTRUM OF SPATIOTEMPORAL NETWORKS WITH POWER-LAW TIME DEPENDENCIES
- Optimal resilient sensor placement problem for secure state estimation
- Matrix Pontryagin principle approach to controllability metrics maximization under sparsity constraints
- Minimum jointly structural input and output selection
- Output null controllability for linear time-invariant structured discrete-time systems: a graph theoretic condition
- On verification and design of input matrix for robust linear systems: complexity and polynomially solvable cases
- Rank resilience of pattern matrices against structured perturbations with applications
- Minimal realizations under controllability
- The single-input minimal controllability problem for structured systems
- On the complexity of the constrained input selection problem for structural linear systems
This page was built for publication: The robust minimal controllability problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409157)
