Two-Facet Scalable Cooperative Optimization of Multi-Agent Systems in the Networked Environment

Matthew Johnson-Roberson, Xiang Huo, Mingxi LiuIEEE Trans. Control. Syst. Technol 2022 · DOI

TL;DR

This paper introduces a novel decentralized optimization framework, SPMDS, designed to tackle the scalability challenges of coordinating a large number of agents (like electric vehicles) in a networked environment. By combining a systemic dimension reduction technique with a shrunken primal-multi-dual subgradient algorithm, SPMDS achieves significant computational savings and improved scalability with respect to both the number of agents and the network size.

What Problem Does This Paper Address?

Coordinating a vast number of agents, such as electric vehicles (EVs) charging in a power grid or vehicles in a traffic network, presents significant scalability challenges. Existing optimization methods often struggle with either the sheer number of agents or the complexity of the underlying network. This paper focuses on networked optimization problems (NOPs) where objective functions and constraints are coupled, making them difficult to decompose. Specifically, it addresses the issue of optimizing EV charging to flatten the power grid's demand curve while respecting local EV constraints and global network voltage constraints. The core problem is that as the number of agents and the network size grow, the computational burden on individual agents and central controllers becomes prohibitive, leading to memory overflow and exceeding processing capabilities.

Methods

The paper proposes a two-facet approach to overcome these scalability limitations:

  • Systemic Dimension Reduction via Virtual Agent Grouping: Instead of treating each agent individually, the authors group agents (EVs) into "virtual agent groups" using a K-means clustering algorithm. This grouping is based on how agents' actions impact specific voltage subsets within the network, effectively reducing the dimensionality of the problem. This is achieved by analyzing the sensitivity matrix of the network.
  • Shrunken Primal-Multi-Dual Subgradient (SPMDS) Algorithm: Building upon the dimension reduction, a novel decentralized optimization algorithm called SPMDS is developed. This algorithm utilizes shrunken primal and multi-dual gradients, which are derived from the reduced-dimension network model. SPMDS allows for parallel updates of dual variables and eliminates the need for direct agent-to-agent communication, relying on a central operator only for aggregating dual updates.

Datasets

The paper uses publicly available test feeders for simulations:

  • Modified IEEE 13-bus test feeder: Used for demonstrating EV charging control.
  • Modified IEEE 123-bus test feeder: Used to further verify the scalability of the proposed SPMDS algorithm.
  • A transportation network with 5 agents and 9 links: Used to illustrate the applicability of SPMDS to traffic congestion control.

Key Insights and Ideas

  • Two-Facet Scalability: The core innovation is achieving scalability in two dimensions: agent population and network dimension. This is crucial for real-world large-scale systems.
  • Virtual Agent Grouping: Grouping agents based on their impact on network voltage subsets, rather than just their physical location, is a novel way to reduce problem dimensionality.
  • SPMDS Algorithm: The SPMDS algorithm effectively integrates dimension reduction into a decentralized optimization framework, leading to significant computational savings.
  • Reduced Communication Overhead: The SPMDS framework minimizes communication by avoiding direct agent-to-agent interactions and centralizing only dual variable aggregation.
  • Robustness to K-means Sub-optimality: The convergence of SPMDS is guaranteed even if the K-means clustering yields a local optimum, making the approach practical.

Key Results

  • Significant Computational Reduction: Simulations on the modified IEEE 13-bus and 123-bus test feeders demonstrated substantial reductions in computational load. For the 13-bus feeder, primal update FLOPS were reduced by 57.22%, and dual update FLOPS by 80%. For the 123-bus feeder, these reductions were even more impressive at 73.4% and 89.41%, respectively.
  • Effective Valley-Filling: The EV charging control simulations successfully filled the overnight baseline load reduction, demonstrating the algorithm's ability to achieve the desired valley-filling objective.
  • Voltage Constraint Satisfaction: The simulations showed that nodal voltage magnitudes were maintained above the specified lower bound, indicating the effectiveness of the voltage control mechanism.
  • Comparable Convergence Speed: SPMDS exhibited a convergence speed comparable to existing methods like SPDS, while offering significantly lower computational costs.

Limitations and Future Work

  • Uniform Voltage Sub-vector Dimension: The current approach assumes that voltage sub-vectors for each EV group have the same dimension. The paper notes that nonuniform partitioning will be discussed in future work.
  • K-means Local Optima: While SPMDS is robust to local optima from K-means, the initial grouping quality can still influence performance.
  • Uncertainty Handling: The current model assumes perfect forecasting of baseline loads and does not explicitly address uncertainties in EV charging behavior or network conditions. Future work will investigate these aspects.
  • Vehicle-to-Grid (V2G) Integration: The current formulation primarily focuses on charging. Extending the framework to incorporate vehicle-to-grid capabilities is a potential future direction.

Summary updated

BibTeX
@article{johnsonroberson2022two,
  author = {Matthew Johnson-Roberson and Xiang Huo and Mingxi Liu},
  title = {{Two-Facet Scalable Cooperative Optimization of Multi-Agent Systems in the Networked Environment}},
  journal = {IEEE Trans. Control. Syst. Technol},
  year = {2022},
  doi = {10.1109/tcst.2022.3143115},
}
Figure