Minimal Controllability Problems

DOI10.1109/TCNS.2014.2337974MaRDI QIDQ5358422zbMATH OpenFDO

Authors Alex Olshevsky

Publication date 21 September 2017

Published in IEEE Transactions on Control of Network Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.3071

Mathematics Subject Classification ID

Controllability (93B05)

Abstract: Given a linear system, we consider the problem of finding a small set of variables to affect with an input so that the resulting system is controllable. We show that this problem is NP-hard; indeed, we show that even approximating the minimum number of variables that need to be affected within a multiplicative factor of $clogn$ is NP-hard for some positive $c$. On the positive side, we show it is possible to find sets of variables matching this inapproximability barrier in polynomial time. This can be done by a simple greedy heuristic which sequentially picks variables to maximize the rank increase of the controllability matrix. Experiments on Erdos-Renyi random graphs demonstrate this heuristic almost always succeeds at findings the minimum number of variables.

Cited in

(59)

• Minimum structural controllability problems of complex networks
• Spectral coarse grained controllability of complex networks
• Minimal controllability of conjunctive Boolean networks is NP-complete
• On structural behavioural controllability of linear discrete time systems with delays
• Networks with diagonal controllability Gramian: analysis, graphical conditions, and design algorithms
• Minimal inputs/outputs for subsystems in a networked system
• Regularity/controllability/observability of an NDS with descriptor form subsystems and generalized LFTs
• Resource-aware time-optimal control with multiple sparsity measures
• Optimizing network topology for average controllability
• Observability-blocking control using sparser and regional feedback for network synchronization processes
• An overview of structural systems theory
• On the control of psychological networks
• 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
• An integrative model for the identification of key players of cancer networks
• On the fixed controllable subspace in linear structured systems
• The robust minimal controllability problem
• A randomized approach to sensor placement with observability assurance
• Complexity of constrained sensor placement problems for optimal observability
• Lyapunov modal analysis and participation factors applied to small-signal stability of power systems
• Resilience to denial-of-service and integrity attacks: a structured systems approach
• Minimum cost input/output design for large-scale linear structural systems
• Controllability as minimality
• On a Conjecture of Godsil Concerning Controllable Random Graphs
• Controllability improvement for multi-agent systems: leader selection and weight adjustment
• scientific article; zbMATH DE number 4181206 (Why is no real title available?)
• Controllability of the multi-agent system modeled by the threshold graph with one repeated degree
• Key-nodes selection problem for minimum cost control of directed networks
• Existence of (cheap) minimal norm controllers
• Input matrix construction and approximation using a graphic approach
• Sensor selection for Kalman filtering of linear dynamical systems: complexity, limitations and greedy algorithms
• Structural minimum controllability problem for switched linear continuous-time systems
• Dynamics over signed networks
• 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
• Selecting energy efficient inputs using graph structure
• CONTROL ENERGY AND CONTROLLABILITY OF MULTILAYER NETWORKS
• THE ACTUATION SPECTRUM OF SPATIOTEMPORAL NETWORKS WITH POWER-LAW TIME DEPENDENCIES
• Sparse control for continuous‐time systems
• Optimal resilient sensor placement problem for secure state estimation
• A survey on compressed sensing approach to systems and control
• Controllability of networked multiagent systems based on linearized Turing's model
• Design of controllable leader-follower networks via memetic algorithms
• Real-time sensor selection for time-varying networks with guaranteed performance
• Sufficient control of complex networks
• Minimum jointly structural input and output selection
• Group controllability of discrete-time second-order multi-agent systems with two-time-scale feature
• Structural controllability of networked systems with general heterogeneous subsystems
• Output null controllability for linear time-invariant structured discrete-time systems: a graph theoretic condition
• Spectrum computation and optimization for controllability Gramian of networked Laplacian systems with limited control placement
• A distributed framework for the minimum cost problem based on graph decomposition
• Merging rules for strong structural controllability and minimum input problem in undirected networks
• Generic diagonalizability, structural functional observability and output controllability
• Generalising Laplacian controllability of paths
• Tracking controllability of linear difference equations
• Minimal realizations under controllability
• The single-input minimal controllability problem for structured systems

This page was built for publication: Minimal Controllability Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5358422)