Expand Observation + Action to check for game-ending topology changes

[DEUCE1957]

Expand Observation + Action to check for game-ending topology changes

I am playing around with the various options to simulate the environment. In the latest version there appear to be 4 ways:

1. Impact = Observation + Action: Fastest
2. obs.get_simulator().predict(): Fast
3. obs.simulate(action): Slow
4. Clone environment: Slowest

I wanted to do a quick topology check to see that my agent does not isolate any substations For this I wanted to use Observati

Ex. This is what i do:

env = grid2op.make("rte_case14_realistic", backend=lightsim2grid.LightSimBackend())
obs = env.reset()
action = env.action_space({})
action.line_set_status = [(18, -1)] # Causes game over
action.line_or_set_bus = [(14, 2)] # Changes topology, but not legally
action.line_ex_set_bus = [(9, 2)]
print(action)
plot_helper = PlotMatplot(env.observation_space)
sim_obs = obs + action
# sim_obs._is_done = False # Overriding this allows the bus_connectivity_matrix to be accessed
line_map = {line_no:(start,end) for line_no, (start, end) in enumerate(zip(sim_obs.line_or_to_subid, sim_obs.line_ex_to_subid)) if sim_obs.line_status[line_no] == True}
fig = plot_helper.plot_obs(sim_obs)
plt.show()

However, the Observation + Action method does not return a sensible bus_connectivity_matrix() nor get_energy_graph(): Since there are no power flows, the energy graph is naturally empty. The bus connectivity graph is also empty, however, which I would not expect. This appears to be because "(obs + action)._done" is always True.

While the comments on add_act() method state that this functionality is not intended to check for game over conditions, it does seem to me like it would be perfect for checking if a substation (and hence any connected elements) becomes disconnected.

An equality check between the elements matrix before and after the action can see if anything has been disconnected, but this will also return False for legal bus changes (such as the change from bus 1 to 2 on Substation 12 below):

Describe alternatives you've considered

Interestingly if I set "_done = False" on the sim_obs I can get access the bus_connectivity matrix. Not sure if this is intended behaviour, but seems to me it would be nicer to be able to access it since it is not actually a game over.

def is_sub_disconnected(obs):
    """
    Checks if any substation (and its associated elements) has become disconnected
    due to a topology-change in the Environment or due to the agent. Isolated elements
    are a game over condition.

    Args:
        obs (BaseObservation): Observation + Action

    Returns:
        bool: True if 1 or more substations have become disconnected
    """
    # line_map = [(s_, e_) for i, (s_, e_) in enumerate(zip(obs.line_or_to_subid, obs.line_ex_to_subid)) if obs.line_status[i] == True]
    subs = set(elt for i, (elt) in enumerate(roundrobin(obs.line_or_to_subid, obs.line_ex_to_subid)) if obs.line_status[i // 2] == True)
    sub_is_disconnected = len(subs) < obs.n_sub
    return sub_is_disconnected

Additional context

Working on extending this into a topology-check PR.

[BDonnot]

Hello,

Sorry for the late reply. This sounds like a super interesting idea.

I am not sure the current implementation you propose is correct though. To check this we need to run an algorithm to check if the graph is connected or not. For example you could have one part of the graph with substation 0, 1 and 4 and all the substations connected together (for example by disconnecting lines 4->5, 4->3, 1->3 and 1-> 2). And if my understanding of your algorithm is correct, this would be ok (but maybe I read it too fast, sorry if I'm wrong here)

One solution would be to convert the action to a networkx graph and then run a connected_components() and check that the results has length 1 (which takes lots of time, probably around the same time as an obs.simulate I would guess). Of course it would be possible to implement the "check connected component" which would make it faster but requires some coding time which I don't have :-( (i'm open for a PR though :-) )

I'll try to work on it ASAP but it will probably not be in grid2op 1.10.2 release unfortunately

[DEUCE1957]

Have tested this algorithm again just now, you are correct that it misidentifies the case you suggest as having no disconnected substations:

For the next attempts I will proceed with 4 scenarios:

1. InitObs: The initial observation (should return False, no islanded substations)
2. ValidObs: The obs + act of disabling line 0-> 1 (should return False, no islanded substations)
3. GameOverObs: The obs + act of disabling line 6 -> 7 (should return True, since sub 7 becomes islanded)
4. DisjointObs: The obs + act of the above example where the bottom left 3 substations become islanded (should return True) Which are defined as follows:

   env.parameters.MAX_LINE_STATUS_CHANGED = env.n_line
   init_obs = env.reset()
   valid_obs = init_obs + env.action_space({"set_line_status":[('0_1_0', -1)]})
   game_over_obs = init_obs + env.action_space({"set_line_status":[('6_7_18', -1)]})
   disjoint_obs = init_obs + env.action_space({"set_line_status":[('4_5_17', -1), ('3_4_6', -1), ('1_3_3', -1), ('1_2_2', -1)]}) 

   Attempt 1: Using line_or_to_subid / line_ex_to_sub_id

   Returns (False, False, True, False). Incorrectly identified 'disjoint_obs' as False since it does not capture multi-substation islands.

Attempt 2: Using networkx.connected_components()

Using the elements graph we can write:

import networkx as nx
def is_sub_disconnected_nx(obs):
    G = obs.get_elements_graph()
    return len([network for network in nx.connected_components(G.to_undirected())]) > 1

is_sub_disconnected_nx(init_obs), is_sub_disconnected_nx(valid_obs), is_sub_disconnected_nx(game_over_obs), is_sub_disconnected_nx(disjoint_obs)

This returns (False, True, True, True). So it incorrectly identifies 'valid_obs' as False. This is because the elements graph includes all elements, in this case the disconnected line ends from line 0->1 are seen as islands.

Attempt 3: Hybrid Approach

In the specific case of power line status changes, we know if the bus_connectivity_matrix shrinks after the powerline status change that is must be because a single bus become isolated. Like before, however, this does not capture the disjoint islanding scenario. The bus connectivity matrices for our 4 scenarios look as follows, if you look carefully at the disjoint case you can see that buses 0, 1, and 4 form an island (they are not connected to any other buses).

Assuming the disjoint cases are rare, we can first compare the matrix sizes (which should be v. fast) and only then check if there are islands:

from scipy.sparse.csgraph import connected_components
from grid2op.Action import PowerlineSetAction

def get_sub_disconnected(obs:BaseObservation, powerline_act:PowerlineSetAction):
    """
    Determines if one or more substations will become disconnected (typical game
    over condition) as a result of a change in Powerline status. This will not
    work for actions that modify the substation topology.

    Args:
        obs (BaseObservation): Observation before action is taken
        powerline_act (PowerlineSetAction): Desired setting of powerline status 

    Returns:
        _type_: _description_
    """
    # Assume: Only available action is powerline status change
    new_obs = obs + powerline_act
    new_obs._is_done = False # Ensures BCM is available
    BCM = new_obs.bus_connectivity_matrix()
    # Check if single substation was disconnected
    if BCM.size < obs.bus_connectivity_matrix().size:
        return True
    # Check if multiple islands exist
    n_islands = connected_components(BCM, directed=False, return_labels=False)
    if n_islands > 1:
        return True
    return False

Returns (False, False, True, True) which is correct. This takes about 593ns / iteration for non-disjoint cases. It takes 293 microseconds for disjoint cases (which are hopefully rare).

Future Work

Ideally we would have a obs.sub_connectivity_matrix(), won't necessarily speedup the above case but would allow us to generalize to none-PowerlineSetAction cases. It might also be possible to speed up the connected_components check by exiting as soon as more than 1 island is detected (since we are not actually interested in the no. of islands in this case).

[BDonnot]

Wahou, awesome work thank you :-)

Let me know if something can be done on my end.

Best

Benjamin

[DEUCE1957]

Not sure, we are currently using it to check whether a maintenance action is safe. Since it only works for power line status changes (won't generalize to substation topology changes) its utility is somewhat limited. Can make a pull request but not sure where it would belong? / Xavier