On Submodularity and Controllability in Complex Dynamical Networks
arXiv:1404.7665 · doi:10.1109/TCNS.2015.2453711
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.
Original arXiv version of IEEE Transactions on Control of Network Systems paper (Volume 3, Issue 1), with a addendum (located in the ancillary documents) that explains an error in a proof of the original paper and provides a counterexample to the corresponding result
References in corpus (2)
Cited by in corpus (92)
- Control Principles of Complex Networks
- Spectrum of Controlling and Observing Complex Networks
- Data-Driven Control of Complex Networks
- Leading Cruise Control in Mixed Traffic Flow: System Modeling, Controllability, and String Stability
- Cooperative Formation of Autonomous Vehicles in Mixed Traffic Flow: Beyond Platooning
- Semidefinite Programming Approach to Gaussian Sequential Rate-Distortion Trade-offs
- Minimum energy control for complex networks
- Toward Stronger Robustness of Network Controllability: A Snapback Network Model
- Fast Greedy Optimization of Sensor Selection in Measurement with Correlated Noise
- On the Role of Network Centrality in the Controllability of Complex Networks
- Good Feature Matching: Towards Accurate, Robust VO/VSLAM with Low Latency
- State observation and sensor selection for nonlinear networks
- emgr - The Empirical Gramian Framework
- Effect of Objective Function on Data-Driven Greedy Sparse Sensor Optimization
- Proximal algorithms for large-scale statistical modeling and sensor/actuator selection
- Beyond Robustness: A Taxonomy of Approaches towards Resilient Multi-Robot Systems
- Irrelevance of linear controllability to nonlinear dynamical networks
- Approximate Supermodularity of Kalman Filter Sensor Selection
- Minimal Structural Perturbations for Network Controllability: Complexity Analysis
- On the Complexity and Approximability of Optimal Sensor Selection and Attack for Kalman Filtering
- Actuator Placement under Structural Controllability using Forward and Reverse Greedy Algorithms
- Centrality measures and the role of non-normality for network control energy reduction
- Observability Robustness under Sensor Failures: a Computational Perspective
- Computation-Communication Trade-offs and Sensor Selection in Real-time Estimation for Processing Networks
- Prevalence and scalable control of localized networks
- Minimal Inputs/Outputs for a Networked System
- Functional Observability, Structural Functional Observability and Optimal Sensor Placement
- Efficient Sensors Selection for Traffic Flow Monitoring: An Overview of Model-Based Techniques leveraging Network Observability
- Decentralized Data-Enabled Predictive Control for Power System Oscillation Damping
- Duality between controllability and observability for target control and estimation in networks
- Controllability scores for selecting control nodes of large-scale network systems
- Actuator Placement for Optimizing Network Performance under Controllability Constraints
- Structure Identifiability of an NDS with LFT Parametrized Subsystems
- Sparsity in Max-Plus Algebra and Systems
- Selecting Energy Efficient Inputs using Graph Structure
- Inadequacy of Linear Methods for Minimal Sensor Placement and Feature Selection in Nonlinear Systems; a New Approach Using Secants
- Generic Detectability and Isolability of Topology Failures in Networked Linear Systems
- Target Controllability and Target Observability of Structured Network Systems
- Controlling network ensembles
- Input Matrix Construction and Approximation Using a Graphic Approach
- Approximate Submodular Functions and Performance Guarantees
- Approximate Supermodularity Bounds for Experimental Design
- Structural Invertibility and Optimal Sensor Node Placement for Error and Input Reconstruction in Dynamic Systems
- Optimal Formation of Autonomous Vehicles in Mixed Traffic Flow
- Particle filtering of dynamical networks: Highlighting observability issues
- Total Unimodularity and Strongly Polynomial Solvability of Constrained Minimum Input Selections for Structural Controllability: an LP-based Method
- Fast Data-driven Greedy Sensor Selection for Ridge Regression
- Probabilistic state transfer, estimation and measures for optimal actuator/sensor placement for linear systems with packet dropouts
- Joint Centrality Distinguishes Optimal Leaders in Noisy Networks
- Resilient Monotone Submodular Function Maximization
- Distributed Submodular Minimization And Motion Coordination Over Discrete State Space
- Submodular Observation Selection and Information Gathering for Quadratic Models
- Uniqueness Analysis of Controllability Scores and Their Application to Brain Networks
- Sensor Selection via Randomized Sampling
- From Sensor to Processing Networks: Optimal Estimation with Computation and Communication Latency
- Minimal Actuator Placement with Bounds on Control Effort
- Greedy-Based Feature Selection for Efficient LiDAR SLAM
- Trust-based user-interface design for human-automation systems
- Sensor placement minimizing the state estimation mean square error: Performance guarantees of greedy solutions
- The Impact of Message Passing in Agent-Based Submodular Maximization
- Edge Selection in Bilinear Dynamical Networks
- Herding Positive, Complex Networks
- Maximizing the Number of Spanning Trees in a Connected Graph
- Observability and Generalized Sensor Placement for Nonlinear Quality Models in Drinking Water Networks
- Sensor Selection and Optimal Precision in Estimation Framework: Theory and Algorithms
- Performance analysis and optimization of power systems with spatially correlated noise
- Efficient constrained sensor placement for observability of linear systems
- On the Equivalence among Three Controllability Problems for a Networked System
- Abstraction of Linear Consensus Networks with Guaranteed Systemic Performance Measures
- Sensor Assignment Algorithms to Improve Observability while Tracking Targets
- Growing Linear Consensus Networks Endowed by Spectral Systemic Performance Measures
- Scaling Submodular Optimization Approaches for Control Applications in Networked Systems
- Minimal Input Selection for Robust Control
- Self-Tuning Network Control Architectures
- PySensors: A Python Package for Sparse Sensor Placement
- Minimal controllability problems on linear structural descriptor systems
- Controllability Metrics on Networks with Linear Decision Process-type Interactions and Multiplicative Noise
- Distributed control and game design: From strategic agents to programmable machines
- Optimal Input Placement in Lattice Graphs
- Structural Control Analysis of System Dynamics Models
- Demarcating Endogenous and Exogenous Opinion Dynamics: An Experimental Design Approach
- Joint Actuator-sensor Design for Stochastic Linear Systems
- Data-Driven Minimum-Energy Controls for Linear Systems
- Comparison of Bounds for Optimal PMU Placement for State Estimation in Distribution Grids
- Controllability maximization of large-scale systems using projected gradient method
- On the Complexity and Approximability of Optimal Sensor Selection for Kalman Filtering
- Multiple sparsity constrained control node scheduling with application to rebalancing of mobility networks
- Parameter Estimation in Epidemic Spread Networks Using Limited Measurements
- Good Feature Selection for Least Squares Pose Optimization in VO/VSLAM
- Distributed Submodular Minimization over Networks: a Greedy Column Generation Approach
- Minimal Inputs/Outputs for Subsystems in a Networked System
- Submodularity in Input Node Selection for Networked Systems