On Submodularity and Controllability in Complex Dynamical Networks

DOI10.1109/TCNS.2015.2453711zbMATH Open1370.93055arXiv1404.7665OpenAlexW1938602245MaRDI QIDQ5358487FDOQ5358487

Authors: Tyler H. Summers, Fabrizio Luca Cortesi, John Lygeros 

Publication date: 21 September 2017

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

Abstract: Controllability and observability have long been recognized as fundamental structural properties of dynamical systems, but have recently seen renewed interest in the context of large, complex networks of dynamical systems. A basic problem is sensor and actuator placement: choose a subset from a finite set of possible placements to optimize some real-valued controllability and observability metrics of the network. Surprisingly little is known about the structure of such combinatorial optimization problems. In this paper, we show that several important classes of metrics based on the controllability and observability Gramians have a strong structural property that allows for either efficient global optimization or an approximation guarantee by using a simple greedy heuristic for their maximization. In particular, the mapping from possible placements to several scalar functions of the associated Gramian is either a modular or submodular set function. The results are illustrated on randomly generated systems and on a problem of power electronic actuator placement in a model of the European power grid.

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Controllability (93B05) Observability (93B07) Design techniques (robust design, computer-aided design, etc.) (93B51) Linear systems in control theory (93C05)

Cited In (45)

• Sufficient control of complex networks
• Observability-blocking control using sparser and regional feedback for network synchronization processes
• A study on \(\langle(\mathcal{Q,S,R})-\gamma\rangle\)-dissipative synchronisation of coupled reaction-diffusion neural networks with time-varying delays
• Strong structural controllability of networks: comparison of bounds using distances and zero forcing
• Novel Gramians for linear semistable systems
• \texttt{emgr} -- the empirical Gramian framework
• Security-aware optimal actuator placement in vehicle platooning
• Strategic sensor placement on graphs
• Networks with diagonal controllability Gramian: analysis, graphical conditions, and design algorithms
• Optimal resilient sensor placement problem for secure state estimation
• Parameter estimation in epidemic spread networks using limited measurements
• Key-nodes selection problem for minimum cost control of directed networks
• Submodular containment is hard, even for networks
• Particle filtering of dynamical networks: highlighting observability issues
• Maximizing the smallest eigenvalue of a symmetric matrix: a submodular optimization approach
• Measure of quality of finite-dimensional linear systems: a frame-theoretic view
• On polynomially solvable constrained input selections for fixed and switched linear structured systems
• Distributed strategy selection: a submodular set function maximization approach
• Input matrix construction and approximation using a graphic approach
• Controllability-Gramian submatrices for a network consensus model
• On verification and design of input matrix for robust linear systems: complexity and polynomially solvable cases
• Control‐channel interactions in diffusive dynamical networks: A graph‐theoretic perspective
• Key node selection in minimum-cost control of complex networks
• Eigenvalue clustering, control energy, and logarithmic capacity
• A randomized approach to sensor placement with observability assurance
• Inadequacy of linear methods for minimal sensor placement and feature selection in nonlinear systems: a new approach using secants
• A sub-modular receding horizon solution for mobile multi-agent persistent monitoring
• Complexity of constrained sensor placement problems for optimal observability
• Minimal inputs/outputs for subsystems in a networked system
• The controllability Gramian of lattice graphs
• Optimizing network topology for average controllability
• Selecting energy efficient inputs using graph structure
• Spectrum computation and optimization for controllability Gramian of networked Laplacian systems with limited control placement
• Closed-loop control of nonlinear neural networks: the estimate of control time and energy cost
• Sparsity in max-plus algebra and systems
• Design of controllable leader-follower networks via memetic algorithms
• Controllability metrics on networks with linear decision process-type interactions and multiplicative noise
• Robust controllability assessment and optimal actuator placement in dynamic networks
• Learning-based actuator selection for increased attack resilience of uncertain systems
• Graph-theoretic approaches for analyzing the resilience of distributed control systems: a tutorial and survey
• Sensor selection for Kalman filtering of linear dynamical systems: complexity, limitations and greedy algorithms
• On the control of psychological networks
• Real-time sensor selection for time-varying networks with guaranteed performance
• A separation theorem for joint sensor and actuator scheduling with guaranteed performance bounds
• Numerical interpretation of controllability coefficients in nonlinear dynamics

This page was built for publication: On Submodularity and Controllability in Complex Dynamical Networks

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