Submodularity of energy related controllability metrics

The quantification of controllability and observability has recently received new interest in the context of large, complex networks of dynamical systems. A fundamental but computationally difficult problem is the placement or selection of actuators and sensors that optimize real-valued controllability and observability metrics of the network. We show that several classes of energy related metrics associated with the controllability Gramian in linear dynamical systems have a strong structural property, called submodularity, which allows for an approximation guarantee by using a simple greedy heuristic for their maximization. The results are illustrated for randomly generated systems and placement of power electronic actuators in a model of the European power grid.

• Publication year

  2014

• Venue

  IEEE Conference on Decision and Control

• Publication date

  2014-03-25

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1109/CDC.2014.7039832arXiv 1403.6351
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Submodular Function Maximization

  2014cited by this paper
• Minimal Controllability Problems

  2013cited by this paper
• Controllability Metrics and Algorithms for Complex Networks

  2013cited by this paper
• Direct numerical solution of algebraic Lyapunov equations for large-scale systems using Quantized Tensor Trains

  2013cited by this paper
• Actuator performance evaluation using LMIs for optimal HVDC placement

  2013cited by this paper
• Optimal Sensor and Actuator Placement in Complex Dynamical Networks

  2013influential reference
• The Minimal Controllability Problem

  2013cited by this paper
• Placement of HVDC links for power grid stabilization during transients

  2013cited by this paper
• Controllability of complex networks

  2011cited by this paper
• Grid stabilization through VSC-HVDC using wide area measurements

  2011cited by this paper
• SFO: A Toolbox for Submodular Function Optimization

  2010cited by this paper
• Contagion in financial networks

  2010cited by this paper
• The Role of FACTS and HVDC in the future Pan-European Transmission System Development

  2010cited by this paper
• Tractability: Practical Approaches to Hard Problems

  2009cited by this paper
• Power System Dynamics: Stability and Control

  2008cited by this paper
• Near-optimal Observation Selection using Submodular Functions

  2007cited by this paper
• Submodular function minimization

  2007cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003cited by this paper
• A review of methods for input/output selection

  2001cited by this paper
• Balanced realization and model reduction for unstable systems

  1999cited by this paper
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• Submodular functions and optimization

  1991cited by this paper
• Numerical Solution of the Stable, Non-negative Definite Lyapunov Equation

  1982influential reference
• Submodular functions and convexity

  1982cited by this paper
• An analysis of approximations for maximizing submodular set functions—I

  1978cited by this paper
• Structural controllability

  1974cited by this paper
• Analysis and optimization of certain qualities of controllability and observability for linear dynamical systems

  1972cited by this paper
• On the general theory of control systems

  1959cited by this paper

• Which information metric is the best, CRLB, FIM or EMGR for optimal mobile sensing of a diffusing source?

  2025cites this paper
• Enhancing Vehicle Platooning Safety via Control Node Placement and Sizing under State and Input Bounds

  2025cites this paper
• Network Topology Optimization for Energy-Efficient Control

  2025cites this paper
• Sample-based almost-sure quasi-optimal approximation in reproducing kernel Hilbert spaces

  2024cites this paper
• Dynamic Sensor Selection for Biomarker Discovery

  2024cites this paper
• Matrix full rank, Controllability and Observability: Revisit Basic Concepts

  2024influential citation
• Bespoke Mitigation Framework for False Data Injection Attack-Induced Contingency Events

  2023cites this paper
• Maximum diffusion reinforcement learning

  2023cites this paper
• Design of a Decentralized Strategy for Layered Self-Assembly of 3D Structures Using Robotic Blocks

  2023cites this paper
• Submodularity of optimal sensor placement for traffic networks

  2023cites this paper
• Actuator Selection for Dynamical Networks with Multiplicative Noise

  2023cites this paper
• Overleaf Example

  2022cites this paper
• Controllability of Coarsely Measured Networked Linear Dynamical Systems (Extended Version)

  2022cites this paper
• Measures of Modal Controllability for Network Dynamical Systems

  2022cites this paper
• Performance bounds for robust estimation using the H∞ filter

  2021cites this paper
• Observability‐Based Sensor Placement Improves Contaminant Tracing in River Networks

  2021influential citation
• Concurrent Morphology-Optimization and Behavior-Learning: Co-Designing Intelligent Quadcopters

  2020cites this paper
• On the Observability and Controllability of Large-Scale IoT Networks: Reducing Number of Unmatched Nodes via Link Addition

  2020cites this paper
• Revisiting the Water Quality Sensor Placement Problem: Optimizing Network Observability and State Estimation Metrics

  2020cites this paper
• Target Control of Networked Systems

  2020cites this paper
• Sensor Selection With Cost Constraints for Dynamically Relevant Bases

  2020cites this paper
• Topology Effects on Sparse Control of Complex Networks with Laplacian Dynamics

  2019cites this paper
• Energy Cost for target control of Complex Networks

  2019cites this paper
• Key Nodes Selection in Controlling Complex Networks via Convex Optimization

  2019cites this paper
• A Security Index for Actuators Based on Perfect Undetectability: Properties and Approximation

  2018cites this paper
• The Structured Controllability Radius of Symmetric (Brain) Networks

  2018cites this paper
• Control Energy of Lattice Graphs

  2018cites this paper
• A Submodular Approach for Optimal Sensor Placement in Traffic Networks

  2018cites this paper
• Minimum-cost control of directed complex networks

  2018influential citation
• Greedy Sensor Placement With Cost Constraints

  2018cites this paper
• Information-based Analysis and Control of Recurrent Linear Networks and Recurrent Networks with Sigmoidal Nonlinearities

  2018cites this paper
• Determination of Design of Optimal Actuator Location Based on Control Energy

  2018cites this paper
• Resilient Submodular Maximization for Control and Sensing

  2018cites this paper
• Actuator Security Indices Based on Perfect Undetectability: Computation, Robustness, and Sensor Placement

  2018cites this paper
• Discrete-Time Dynamical Networks with Diagonal Controllability Gramian

  2017cites this paper
• A submodular optimization approach to leader-follower consensus in networks with negative edges

  2017cites this paper
• Bispectral analysis for measuring energy-orientation tradeoffs in the control of linear systems

  2017cites this paper
• Toward Synchronization in Networks With Nonlinear Dynamics: A Submodular Optimization Framework

  2017cites this paper
• Key node selection in minimum-cost control of complex networks

  2017cites this paper
• On the Control of Consensus Networks: Theory and Applications

  2017cites this paper
• Distributed Protocols, Nonlinear State-Dependent Networks, and Human-Swarm Interactions

  2017cites this paper
• Maximizing the Smallest Eigenvalue of a Symmetric Matrix: A Submodular Optimization Approach

  2017cites this paper
• Optimal control of weighted networks based on node connection strength

  2017cites this paper
• On the number of strongly structurally controllable networks

  2017cites this paper
• Convex relaxations and Gramian rank constraints for sensor and actuator selection in networks

  2016cites this paper
• H∞-optimal actuator placement with a class of nonlinear constraints

  2016cites this paper
• The Observability Radius of Networks

  2016cites this paper
• The observability radius of network systems

  2016cites this paper
• Joint Performance and Controllability of Networked Systems

  2016cites this paper
• Sensor and actuator placement for zero-shaping in dynamical networks

  2016cites this paper
• Abnormal overheating detectability analysis based on cross Gramian for a supercapacitors string

  2016cites this paper
• Growing controllable networks via whiskering and submodular optimization

  2016cites this paper
• Actuator placement in networks using optimal control performance metrics

  2016cites this paper
• Scheduling of control nodes for improved network controllability

  2016cites this paper
• Rigid Network Design Via Submodular Set Function Optimization

  2015cites this paper
• Efficient leader selection for translation and scale of a bearing-compass formation

  2015cites this paper
• Estimation of control Energy and control Strategies for Complex Networks

  2015cites this paper
• On the Role of Network Centrality in the Controllability of Complex Networks

  2015cites this paper
• Control Principles of Complex Networks

  2015cites this paper
• On Submodularity and Controllability in Complex Dynamical Networks

  2014cites this paper
• Controlling linear networks with minimally novel inputs

  2014cites this paper
• Input Novelty as a Control Metric for Time Varying Linear Systems

  2014cites this paper
• Observability-Based Guidance and Sensor Placement

  2014cites this paper
• Minimal Actuator Placement With Bounds on Control Effort

  2014influential citation
• Topology design for optimal network coherence

  2014cites this paper
• Optimal Sensor and Actuator Placement in Complex Dynamical Networks

  2013cites this paper