Optimal Clustering of Substations for Topology Optimization Using the Louvain Algorithm

[BamunugeDR99]

Related Problem & Feature Request

Related Problem

In the official Grid2Op repo; a Multi-Agent Reinforcement Learning(MARL) example is currently being developed under the branch dev_multiagent .

In the current implementation, when creating the multi-agent environment a parameter called ACTION_DOMAINS is passed. This represents a dictionary that maps agent names to a list of substations they control. This approach aims to cluster the grid into smaller subgrids, each managed by an individual agent.

However, the primary issue with the current implementation is the lack of an optimal clustering methodology. Currently; as shown below, the agents and the substations they control are hard-coded (i.e. the substation ids are manually assigned by hand) for the l2rpn_case14_sandbox environment.

ACTION_DOMAINS = {
        'agent_0' : [0, 1, 2, 3, 4],
        'agent_1' : [5, 6, 7, 8, 9, 10, 11, 12, 13]
    }

This hardcoded clustering approach is not ideal because:

1. Lack of Flexibility: Hardcoding limits the adaptability of the solution to different environments and scenarios.

2. Suboptimal Clustering: Without a systematic method for clustering, the current setup may not effectively optimize the agents' performance.

Feature Request

Due to the limitations of the current hardcoded clustering, our team @rootcodelabs is exploring methods to perform this clustering more optimally. Currently, manually assigning IDs to agents and clustering the grid does not adequately consider factors such as connectivity and the inherent relationships between different sections of the grid. This can lead to sub-optimal performance of the agent. To address this, we are developing dynamic and adaptable clustering algorithms that can better partition the grid. These algorithms will ensure optimal clustering, with subgrids sharing more internal connectivity. This approach aims to improve overall performance and scalability by creating clusters that are more logically connected and efficient.

By addressing this issue, we aim to strengthen the current MARL approach implemented within Grid2Op.

Solution: Clustering Substations using the Louvain Algorithm

To improve substation clustering in the Grid2Op environment, our team explored various graph clustering algorithms. The basis for exploring these algorithms lies in their ability to analyze and partition the grid based on connectivity. Graph clustering algorithms help identify communities or clusters within a network, ensuring that closely connected substations are grouped together. This results in more cohesive subgrids and optimized performance. After evaluating multiple such algorithms, we selected the Louvain Algorithm for its superior performance in detecting community structures within large networks and its ability to maximize modularity. This ensures that the resulting clusters have dense internal connections and sparser connections between them, making it particularly suitable for our needs.

Results & Comparison

Figure 1

Figure 2

The first image displays the episode reward over time for the MARL implementation in Grid2op but with hardcoded substation clusters (the original method) instead of using the Louvain algorithm for clustering.

The second image shows the episode reward over time for the same MARL solution implementation; but with the substation clustering performed using the Louvain algorithm (the proposed method).

Comparing the two images, a few key differences can be observed:

1. The maximum episode reward (orange line) in the second image (with Louvain clustering) reaches significantly higher
   values, around 30,000, compared to the first image (with hardcoded clusters), where the maximum reward is around 4,000.

2. The mean episode reward (blue line) in the second image also tends to be higher, especially in the later episodes,
   suggesting better overall performance with the Louvain clustering approach.

3. The minimum episode reward (green line) in the second image exhibits more fluctuations and occasional dips to lower
   values compared to the first image, which may indicate greater variability or exploration in the learning process with
   Louvain clustering.

These differences suggest that the Louvain algorithm for substation clustering, by identifying relevant community structures in the power grid network may enable the MARL solution to learn more effective strategies and achieve higher rewards in the Grid2op environment compared to the hardcoded substation clustering approach.

Solution Implementation

from grid2op.Environment import Environment
import numpy as np
from sknetwork.clustering import Louvain
from scipy.sparse import csr_matrix

class ClusterUtils:
    """
    Outputs clustered substation based on the Louvain graph clustering method.
    """
    
    # Create connectivity matrix
    @staticmethod
    def create_connectivity_matrix(env:Environment):
        """
        Creates a connectivity matrix for the given grid environment.

        The connectivity matrix is a 2D NumPy array where the element at position (i, j) is 1 if there is a direct 
        connection between substation i and substation j, and 0 otherwise. The diagonal elements are set to 1
        to indicate self-connections.

        Args:
            env (grid2op.Environment): The grid environment for which the connectivity matrix is to be created.

        Returns:
            connectivity_matrix: A 2D Numpy array of dimension (env.n_sub, env.n_sub) representing the 
            substation connectivity of the grid environment.
        """
        connectivity_matrix = np.zeros((env.n_sub, env.n_sub))
        for line_id in range(env.n_line):
            orig_sub = env.line_or_to_subid[line_id]
            extrem_sub = env.line_ex_to_subid[line_id]
            connectivity_matrix[orig_sub, extrem_sub] = 1
            connectivity_matrix[extrem_sub, orig_sub] = 1
        return connectivity_matrix + np.eye(env.n_sub)

    
       
    # Cluster substations
    @staticmethod
    def cluster_substations(env:Environment):
        """
        Clusters substations in a power grid environment using the Louvain community detection algorithm.

       This function generates a connectivity matrix representing the connections between substations in the given
       environment; and applies the Louvain algorithm to cluster the substations into communities. The resulting 
       clusters are formatted into a dictionary where each key corresponds to an agent and the value is a list of 
       substations assigned to that agent.

        Args:
            env (grid2op.Environment): The grid environment for which the connectivity matrix is to be created.
            
        Returns:
                (MADict):
                    - keys : agents' names 
                    - values : list of substations' id under the control of the agent.
        """

        # Generate the connectivity matrix
        matrix = ClusterUtils.create_connectivity_matrix(env)

        # Perform clustering using Louvain algorithm
        louvain = Louvain()
        adjacency = csr_matrix(matrix)
        labels = louvain.fit_predict(adjacency)

        # Group substations into clusters
        clusters = {}
        for node, label in enumerate(labels):
            if label not in clusters:
                clusters[label] = []
            clusters[label].append(node)

        # Format the clusters
        formatted_clusters = {f'agent_{i}': nodes for i, nodes in enumerate(clusters.values())}
        
        return formatted_clusters

Sample Execution & Output

import grid2op
from lightsim2grid import LightSimBackend
from grid2op.multi_agent import ClusterUtils


ENV_NAME = "l2rpn_case14_sandbox"
env = grid2op.make(ENV_NAME, backend=LightSimBackend())

# Get ACTION_DOMAINS by clustering the substations
ACTION_DOMAINS = ClusterUtils.cluster_substations(env)

Output

{
'agent_0': [0, 1, 2, 3, 4],
'agent_1': [5, 11, 12], 
'agent_2': [6, 7, 8, 13], 
'agent_3': [9, 10]
}

Alternatives considered

Prior to finalizing the Clustering using the Louvain Algorithm, our team explored a couple of different alternatives.

1. Clustering substations using K-Means or DBSCAN algorithms - This was our initial approach and faced difficulties
   when creating a matrix with substation-specific information that will be fed to the algorithm; due to lacking expert
   domain knowledge in some power-grid properties. Although we managed to gather the required domain knowledge
   through resource persons the clusters formed using K-Means had poor performance.

2. Dynamic Clustering: In this approach, we brainstormed the possibility of performing a dynamic clustering (Clustering
   substations every time when agents deem it necessary to take an action) instead of static clustering at the initial stage.
   We realized that dynamic clustering does not provide any specific advantage and will actually be more computationally
   intensive.

Additional Context

Louvain Algorithm

Introduction

The Louvain Algorithm is a widely used method for detecting communities in large networks, renowned for its ability to identify high modularity communities efficiently. It is particularly useful for partitioning networks into clusters and is known for its scalability and rapid convergence. This algorithm is a type of greedy community detection algorithm and supports both weighted and unweighted graphs. One of its key features is the provision of hierarchical clustering, making it suitable for complex network analysis.

How the Louvain Algorithm Works

The Louvain Algorithm operates in an iterative manner, with each iteration consisting of two main phases aimed at maximizing modularity:

1. Phase 1: Change Community Memberships of Nodes (Partitioning)

   • In this phase, each node is assigned to different communities in a greedy manner. The objective is to maximize the
     modularity gain, which measures the density of links inside communities compared to links between communities.

   • Nodes are moved between communities to find the configuration that results in the highest increase in modularity.
     This process is repeated until no further improvement can be achieved.

2. Phase 2: Aggregate Identified Communities into Super-Nodes (Restructuring)

   • Once the optimal community structure is identified in Phase 1, these communities are aggregated into super-nodes,
     effectively reducing the network's size.

   • The resulting network, with super-nodes, is then used as the input for the next iteration, where the algorithm repeats
     the process of community assignment and aggregation.

This two-phase process continues iteratively, with each iteration refining the community structure until maximum modularity is achieved, and no further changes occur.

Advantages of the Louvain Algorithm

• High Modularity Communities: Effectively identifies communities with high modularity, ensuring dense connections
  within communities and sparse connections between them.

• Scalable: Handles large networks efficiently, making it suitable for extensive datasets.

• Greedy Community Detection: Uses a greedy approach for community assignment, ensuring rapid convergence.

• Hierarchical Clustering: Provides a hierarchical clustering of the network, allowing for multi-level analysis.

Suitability of the Louvain algorithm for clustering substations

The Louvain algorithm is suitable for clustering substations in a power grid environment like grid2op for the following reasons:

1. Power Grid as a Network: A power grid can be represented as a network or graph, where substations are nodes, and
   the transmission lines connecting them are edges. The Louvain algorithm is designed to identify communities or clusters
   within such networks.

2. Electrical Connectivity: Substations that are electrically connected and have a high degree of interaction are more
   likely to belong to the same cluster or community. The Louvain algorithm aims to maximize the modularity of the
   network, which measures the density of connections within clusters compared to connections between clusters.

3. Hierarchical Clustering: The Louvain algorithm can detect hierarchical community structures, which is beneficial in
   power grids where substations may be organized into different voltage levels or operational zones.

4. Scalability: The Louvain algorithm is known for its efficiency and scalability, making it suitable for clustering large-
   scale power grids with numerous substations and transmission lines.

[BDonnot]

Hello,

Thanks for this detailed description.

First, let me start by saying that the examples code are simple examples, sufficient to get started and focus on the usage of ray / rllib.

Also, the "dev_multiagent" branch is, as its name suggest still a development version and as such missing a whole lot of core features (required to make grid2op fully "multi agent").

TL;DR

First, create another script that come up (with the method of your choice) with the ACTION_DOMAINS and OBSERVATION_DOMAINS.

This script can be what you have made already. And save its output in your preferred format: csv, json, yaml, pickle etc.

Once you have that, copy paste the example script, remove the "ACTION_DOMAINS" and "OBSERVATION_DOMAINS" definition (remove these global variable). And read back the "responsibility area" of each agent from the file that you saved (csv, json, yaml, pickle etc.)

Long answer

Let me then try to answer to some of your point (and maybe suggest a few solutions when I can think of some)

In the current implementation, when creating the multi-agent environment a parameter called ACTION_DOMAINS is passed. This represents a dictionary that maps agent names to a list of substations they control. This approach aims to cluster the grid into smaller subgrids, each managed by an individual agent.

Yes, exactly. And this will always be the case in the current implementation. It's at the environment creation that you need to define what are the area operated by each agent.

We have no solution right now to change dynamically the area operated by each agent after the environment is created.

However, the primary issue with the current implementation is the lack of an optimal clustering methodology. Currently; as shown below, the agents and the substations they control are hard-coded (i.e. the substation ids are manually assigned by hand) for the l2rpn_case14_sandbox environment.

I don't see why. I mean, of course there exists lots of grid clustering algorithms. But for me the process would be:

1. use any available clustering algorithm to come up with an "action domains" and an "observation domain"
2. use grid2op (and the example of this branch) to train agents operating on each subgrid.

Following this process, if someone come up with a brilliant new way to cluster the grid, only the "step 1" above needs to be changed. And you can still use step 2 without anything.

On the other hand, if you put inside grid2op some clustering algorithms you:

1. need to add / remove new methods following the state of the art
2. need to re implement every method using only grid2op code
3. fix every possible bugs in the method you have developed

This consumes much more "man power" that to have an independant (of grid2op) process to come up with "action domains" and "observation domains"

And this is clearly suboptimal (you might not have implemented the right clustering algorithms) and not flexible (you have to recode everything every time)

[BDonnot]

So basically, I recommend something like this:

1. make a detached script, say "make_clustering" that would compute something like that:

import grid2op
from lightsim2grid import LightSimBackend
from grid2op.multi_agent import ClusterUtils


ENV_NAME = "l2rpn_case14_sandbox"
env = grid2op.make(ENV_NAME, backend=LightSimBackend())

# Get ACTION_DOMAINS by clustering the substations
action_domains = ClusterUtils.cluster_substations(env)

# save it somewhere
action_domains.save("action_domain_{env_name}_{method_name}.json")

Then get rid of all global variable ACTION_DOMAINS in the example script. And replace it with something like:

some code here

ENV_NAME = "l2rpn_case14_sandbox"
DO_NOTHING_EPISODES = -1  # 200

ACTION_DOMAINS = {
        'agent_0' : [0, 1, 2, 3, 4],
        'agent_1' : [5, 6, 7, 8, 9, 10, 11, 12, 13]
    }

OBSERVATION_DOMAINS = {"agent_0": [0, 1, 2, 3, 4, 5, 8, 6],
                        "agent_1": [5, 6, 7, 8, 9, 10, 11, 12, 13, 4, 3]}
    
env_for_cls = grid2op.make(ENV_NAME,
                           action_class=PlayableAction,
                           backend=LightSimBackend())

# wrapper for gym env
class MAEnvWrapper(MAEnv):
    def __init__(self, env_config=None):
        super().__init__()
        if env_config is None:
            env_config = {}

        env = grid2op.make(ENV_NAME,
                           action_class=PlayableAction,
                           backend=LightSimBackend())  

        action_domains = copy.deepcopy(ACTION_DOMAINS]
        if "action_domains" in env_config:
            action_domains = env_config["action_domains"]
        observation_domains = copy.deepcopy(OBSERVATION_DOMAINS)
        if "observation_domains" in env_config:
            observation_domains = env_config["observation_domains"]
        self.ma_env = MultiAgentEnv(env,
                                    action_domains,
                                    observation_domains)

  some other code there too

if __name__ == "__main__":

    again, some other code...

   # load back your clustering
   action_domain = json.load("action_domain_{env_name}_{method_name}.json")
   observation_domain = json.load("observation_domain_{env_name}_{method_name}.json")

  ray_ma_env = MAEnvWrapper(env_config={"action_domain": action_domain, "observation_domain": observation_domain})

   again lots of other code

This is somewhat what is done in the second example.

[BDonnot]

And about clustering algorithm, I know (and I have worked a bit with him) that Nourredine Henka is working on grid clustering.

He made some article with reproducible code available here https://github.com/rte-france/grid2op-milp-agent

Nourredine now tries to come up with a clustering technique that scales (to real grid) and that is able to cluster "changing grid" so that you don't have to cluster the grid multiple times (ideally). The outcome should be a "robust" clustering.

One of the core algorithm is infomap https://github.com/mapequation/infomap (not sure if this is the right repo). I'll see if Nourredine can add some precisions :-)

[BDonnot]

Finally (now that I reached your implementation) you have tons of methods in grid2op to retrieve more or less information with a graph structure. You can have an example in the documentation, available here: https://grid2op.readthedocs.io/en/latest/grid_graph.html especially https://grid2op.readthedocs.io/en/latest/grid_graph.html#how-to-retrieve-the-graph-in-grid2op

[BamunugeDR99]

Hi @BDonnot ,
Thank you for your detailed feedback.

I have noted down our responses to each of your comments and concerns below. Looking forward to hearing your thoughts on this too.

I don't see why. I mean, of course, there exists lots of grid clustering algorithms. But for me, the process would be:

1. use any available clustering algorithm to come up with an "action domains" and an "observation domain"
2. use grid2op (and the example of this branch) to train agents operating on each subgrid.

• Yes, this is exactly the approach we are following as well. In our proposed feature we are not going to cluster the grid multiple times after the environment is created. Instead, we are performing a static clustering during initialization of the agents (Same as in the original implementation at the dev_multiagent). The primary contribution here is the integration of the Louvain algorithm to create an effective initial set of substation clusters (step-1) and allocate those clusters to agents.

• Our proposed contribution solely focuses on proposing an improvement for the 1st step of the process (by introducing an optimal way to do the substation clustering). Like you have mentioned it absolutely makes sense to perform the clustering and substation allocation to agents before initiating the environment, and that is the approach we wanted to focus on too.

First, create another script that come up (with the method of your choice) with the ACTION_DOMAINS and
OBSERVATION_DOMAINS.

This script can be what you have made already. And save its output in your preferred format: csv, json, yaml, pickle etc.

• We have added the functionality as a utility method inside the util.py file which then can be conveniently called when needed (so that we do not have to perform I/O file operations within the code). But if you think it’s best for the script to generate file with the substation clusters and agent allocations, we can make that update too. What are your thoughts on this?

• Also we have included the complete solution implementation and added a sample execution in the “ray_example_3.py” file.

• We have added a PR (Optimal Clustering of Substations for Topology Optimization Using the Louvain Algorithm #620) so you can have a clear view and understanding of the proposed contribution.

And about clustering algorithm, I know (and I have worked a bit with him) that Nourredine Henka is working on grid
clustering.
He made some article with reproducible code available here https://github.com/rte-france/grid2op-milp-agent
Nourredine now tries to come up with a clustering technique that scales (to real grid) and that is able to cluster "changing
grid" so that you don't have to cluster the grid multiple times (ideally). The outcome should be a "robust" clustering.

• Thank you for this resource. We tried out multiple clustering algorithms and compared their performances and found that the Louvain algorithm provides better performance and also good scalability. We tried out the substation clustering using the Louvain algorithm for rte_case5_example , l2rpn_case14_sandbox, and l2rpn_wcci_2022 environments and the results were good relative to other clustering algorithms. And if it’s useful we are planning to make additional contributions with other clustering algorithms as out-of-the box functions as well, so that users can experiment and benchmark different multi-agent clustering methods without having to develop the implementation on their own.

Finally (now that I reached your implementation) you have tons of methods in grid2op to retrieve more or less information with a graph structure. You can have an example in the documentation, available here: https://grid2op.readthedocs.io/en/latest/grid_graph.html especially https://grid2op.readthedocs.io/en/latest/grid_graph.html#how-to-retrieve-the-graph-in-grid2op

• Thanks again for this as well. Yes, there is a magnitude of information that we could retrieve from the graph structure in the Grid2Op. We have created a substation-specific matrix that considers substation connectivity as a factor for creating clusters as we felt this was the best way to represent the substations in an adjacency matrix, as required by the Louvain algorithm.

[BDonnot]

Hello :-)

Thanks for this super interesting work. I am working on a new grid2op release at the moment (for the "main" branch) and I will get back to you ASAP concerning this.

I also saw the PR which is awesome, thanks :-)

Again, I will try to have a look asap. As you mentioned it's super interesting to have a good default clustering. Which is of course way better than the "random" clustering proposed in the notebook.

I'll keep you posted as soon as I have some time to work on it :-)

[BamunugeDR99]

Hi Benjamin, Thank you for the feedback and glad to know that you think it's useful. We are eagerly looking forward to your feedback on the PR and making the contribution

…

On Thu, Jul 4, 2024 at 7:20 PM Benjamin DONNOT ***@***.***> wrote: Hello :-) Thanks for this super interesting work. I am working on a new grid2op release at the moment (for the "main" branch) and I will get back to you ASAP concerning this. I also saw the PR which is awesome, thanks :-) Again, I will try to have a look asap. As you mentioned it's super interesting to have a good default clustering. Which is of course way better than the "random" clustering proposed in the notebook. I'll keep you posted as soon as I have some time to work on it :-) — Reply to this email directly, view it on GitHub <#613 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AVEO3ZUSW4OPVKZMGMCX72TZKVHKHAVCNFSM6AAAAABJIULS2WVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDEMBZGA2TAMBYHA> . You are receiving this because you authored the thread.Message ID: ***@***.***>