{'fraction_non_alphanumeric': 0.031079317511721206, 'fraction_numerical': 0.006186862583981826, 'mean_word_length': 4.83803611738149, 'pattern_counts': {'":': 1, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robust and Deterministic Scheduling of Power Grid Actors

Modern power grids need to cope with increasingly decentralized, volatile energy sources as well as new business models such as virtual power plants constituted from battery swarms. This warrants both, day-ahead planning of larger schedules for power plants, as well as short-term contracting to counter forecast deviations or to accommodate dynamics of the intra-day markets. In addition, the geographic distribution of renewable energy sources forces scheduling algorithms with a hugely different communication link qualities. In this paper, we present an extension to the Lightweight Power Exchange Protocol (LPEP), dubbed LPEP++. It draws on the strength of the LPEP to find the optimal solution of the combinatorial power demand-supply problem with string guarantees in acceptable time and extends it with facilities for long-term planning, parallel negotiations and reduces its memory footprint. We furthermore show its robustness towards volatile communication link quality.


I. INTRODUCTION
Globally, there has been a huge shift set in motion to provide a decarbonized energy supply. These goals have been widely propagated through many agreements in different countries; the European Union's goal to be climate-neutral by 2050 might serve as an example to this claim [1]. The reduction of CO 2 emissions is, in many countries, achieved by increasing the share of volatile, i.e., weather-dependant renewable energy sources such as wind and Photovoltaic (PV).
The shift from a centrally managed, hierarchically-structured power grid towards with power plants feeding into the transmission grid towards decentralized power generation using renewables was one of the reasons that has given rise to the concept of the smart grid, as it requires the introduction of extensive Information and Communication Technology (ICT) infrastructure to coordinate demand and supply. Arguably, this decentralized power generation also calls for a decentralized, divide-et-impera-style approach [2]. This means that a Multi Agent System (MAS) is used to manage power demand and supply-or other aspects of power grid operations, such as the provision of reactive power-, integrating a huge share of renewable-energy-based generators.
This new design of the power grid needs ICT connectivity to deliver on its promise of an efficient power supply. However, wind parks and PV plants are usually erected at locations that are sensible from the perspective of harvesting the wind's or sun's power, but not with regards to an seamless inclusion into the grid's ICT network. In addition, newer prosumer and market concepts, such as Virtual Power Plants (VPPs) and battery swarm storage, are increasingly constituted from MAS [3]- [7].
Many of these approaches abstract from the communication medium, assuming losless link quality with negligible delay. The research project LarGo! considers as one of the first research projects the complex interaction between the power grid and its ICT infrastructure. Mainly focused on software rollouts, a resilient power grid scheduling is one of the research questions of the project [8].
In the scope of the research question, this paper describes an extension to the Lightweight Power Exchange Protocol (LPEP). We show the resiliency of the LPEP with regards to an impaired communication medium, i.e., specifically to (intermittently) high delays. The procotol's and the underlying demand-supply solver's ability to draft a new schedule for power provisioning or consumption in non-optimal ICT situations is shown. We also present an extension to the protocol, named LPEP++ that allows a more efficient convergence towards complete schedules.
The remainder of this paper is structured as follows: We will introduce related work in Section II. As an extension, we provide a description of the current state of the LPEP in Section III. Based on this, Section IV details the modifications and forms the main contribution of this paper. In Section VI, we provide experimental results to substantiate our claims towards LPEP improvement with results obtained from simulation. We conclude in Section VII, where we also provide an outlook for future work.

II. RELATED WORK
One of the ancestral behavioral protocols for MAS is the Contract Net Protcol by Smith [9]. Here, agents announce tasks using broadcast messages for other agents to bid on. The announcement also contains the ranking process, i.e., bids delivered by other agents are ranked according to metrics such as estimated time to task completion. The announcer, or task manager, then awards the task to a specific node, informing all other nodes in the process. The awarded node can then additionally choose to break the task up into smaller subtasks and sub-contract them through a similar procedure.
The general broadcast-bidding-awarding structure of behavior laid down in the Contract Net Procol has influenced many (negotiation) protocols for distributed computation. In many cases, additional ideas are brought in to add efficiency, to speed up the negotiation, or to reduce the amount of messages or data being sent. The LPEP [2], [10] specifies initial messages (requests for or offers of power) as broadcasts, but models the overlay networks the agents use on the power grid in which the agents' physical entities represent, imposing rules on message routing that limit message propagation, introducing the concept of dynamic neighborhoods where supply and demand have as little physical line meter between them as possible, reducing the line loss. Responses are routed directly through a dynamic routing table on each node that is being built during the request stage.
Additionally, Shen and Norrie [11] worked towards eschewing the initial broadcast stage. They employ multicasting-i.e., the network protocol concept [12]-for the task announcement messages, creating interest groups to which agents can subscribe. Wanyama and Homayoun Far [13] reduce the number of negotiation rounds until consensus is reached, limiting the scope of agent coalitions to a group-choice problem and basing their negotiation approach on game theory, replacing explicit knowledge through message exchanges by implicit knowledge coming from a game-theoretic model of the negotiation process. Garcia, Cao, and Casbeer [14] have reduced the number of messages per negotiation, assuming a control theory problem behind the agents' communication and implementing an asynchronous, event-based protocol based on a discretized model that is decoupled from the state of the agent's neighbors.
The aforementioned publication by Olfati-Saber, Fax, and Murray [15] also emphasizes the effectiveness of neighborhood concepts, based on small-world networks by Watts and Strogatz [16]-being one of the hallmark works on overlay topologies for distributed computing-, and referring to the weightings introduced by Xiao and Boyd [17]. The two works heavily influenced the later, much-celebrated small-world model for MAS by Olfati-Saber [18]. The Combinatorial Optimization Heuristic for Distributed Agents (COHDA) protocol by Hinrichs, Lehnhoff, and Sonnenschein [19]-the key competitor to LPEP++-builds on the small-world model; Nieße, Bremer, and Lehnhoff [20] also note that fast convergence or the quantitative guarantee of convergence do not necessarily mean that the optimal solution to a problem is found, but that the ICT overlay network topology influences the search for a solution with certain MAS protocols.
In the context of a cyber-physical system (CPS), fully decentralized MAS approaches to a problem can be viewed with suspicion. After all, there is no way to control or "look into" the process as it happens. The statement of the convergence problem by Hanachi and Sibertin-Blanc [21] mentioned above is approached by the authors through a protocol moderator, i.e., an explicit middleman. Similarly, for COHDA, Nieße and Tröschel [22] propose an observer-controller architecture for the in its core completely decentralized protocol. The questions these approaches rise is whether how certain behavior can be formulated as being expected, rather than just exhibited. It is expressed in the move from specifications to contracts in component design.
The LPEP features a different approach towards contracting. It leverages the power of Ternary Vector Lists (TVLs) to model demand and supply. Thus, it is guaranteed to arrive at the optimal solution for a given set of input data [23]. Its current shortcoming is its granularity: The LPEP starts negotiation for every timestep anew. This allows for a maximum of flexibility, but has high costs in terms of efficiency, especially if a complete schedule needs to be reconsidered due to intraday flexibilities.

A. Communication Protocol
The LPEP as it exists now [2] has, at its core, the so-called Four-Way Handshake. Agents initiate a negotiation with either a Demand Notication or Offer Notification, depending on whether they request additional power or offer it. To understand both cases, one most take the concept of the power equilibrium into account. This constitutes the state in which power demand and supply match. Whenever an agent detects a deviation from the state of equilibrium, e.g., based on a node-local forecast, it initiates the negotiation. When the disequilibrium is caused by a surplus of power, a Offer Notification starts the negotiation; consequently, the Demand Notification expresses the agent's request for power from other nodes.
These initial messages are then routed through an overlay network modelled according to the underlying power grid infrastructure. The rules governing the message exchange let message propagation boundaries form, depending on the contribution of neighboring node (called "match-or-forward" rule). This favors power equilibria. During this stage of the negotiation that essentially employs broadcasting, the ad-hoc routing table for the directly-routed answers is built. The routing metric is the impedance of the local power line, i.e., the goal is to reduce line loss.
When other agents answer, they send the matching Offer Notification to an initial Demand Notification, and vice versa. The difference is the presence of an explicit message ID in the answer, which is the ID of the initial request. When the initiating agent receives answers, it can start its internal solver to match its request with the replies it received; this is discussed in Section III-B. When the solver finds a solution, all agents whose offer are taken receive an Acceptance Notification and, in turn, reply with an Acceptance Acknowledgement Notification. This fourth step allows agents to withdraw replies, e.g., when forecasts deviate.
The Four-Way Handshake is depicted in Figure 1. For a more detailed, extensive discussion, please refer to [2].

B. Solver
Any demand or offer is mathematically described as a mappingt → P , wheret = [t 1 ; t 2 ] is a time interval for which P is valid. The vector of all absolute power values is P = (|P 0 |, |P 1 |, |P 2 |, . . .); the vector of all time interval lengths ist = (t 0,2 − t 0,1 , t 1,2 − t 1,1 , t 2,2 − t 2,1 , . . .).  To convert this multi-valued optimization problem into a Boolean-valued one, we use the greatest common divisor to formulate each demand and offer in terms of atoms sized each representing one part of it: 1 if the agent i influences the power grid in the time subintervalt with power from the power subintervalP , 0 otherwise.
Using these atoms, the requirements function for each demand or offer expresses complete, potentially partial acceptance, or decline: 1 if x i,t,P denotes a valid interval for accepting the requirement from agent i, 0 otherwise.
The simplest case that is always present is "accept fully, or do not accept at all": Next, symmetric functions for each time subinterval are used to model all possible arrangements of the atoms: with k = 1, 2, . . . , |t| ∆t . In order to arrive at an solution, the agent must determine the exact cover: A representation using TVLs, implemented using the XBOOLE system, enables an efficient calculation of this cover [2], [24].

IV. PROTOCOL EXTENSION
In the originial LPEP, with every new input, the agent with the disequilibrium tries to solve it. In the LPEP++, if not the complete disequilibrium could be solved, the agent after a certain time determines the power which can be afforded. This might be relevant for use cases like trading on energy markets, where agents negotiate about trades which cannot be fulfilled anymore. Therefore, as much power as possible needs to be afforded in order to keep overstretching of existing commitments as low as possible. Since the agent with the disequilibrium does not have knowledge of all agents of the network, it may not wait until it received every offer or demand. A timeout was implemented for the conversion. The inquiring agent then starts a timer when sending out the initial Offer orRequest Notification. The timer being expired, the agent determines the power which could be afforded based on the available. After solving the disequilibrium as best as possible, it sends out Acceptance Notifications and the agents follow the Four-Way Handshake of the LPEP. The number of seconds the timer expires depends on the size of the network. It needs to be high enough so that the Offer or Demand Notifications of as many agents as possible have already arrived in order to not exclude any power. In a network of six agents, the timer was set to 0.02 seconds.
Another possible extension is considering a total replanning of schedules with the LPEP. If an imbalance occurs in more than one interval of the schedule, it is required to replan every relevant interval of the schedule. Therefore, the agent determining the disequilibrium sends out an Offer or Demand Notification with the missing power and time mapping for the whole timeframe which is concerned.
Agents receiving the call for supply may answer with a time-power-mapping in any kind of time interval length. If supplying power is for example only possible in parts of the requested time, the agent only replies with power for this time and sends its reply as time-power-mapping for the possible time.
The agent with the disequilibrium receiving the answers, divides them by building atoms for each time interval given by the other agents. Since the solver describes demands or offers mathematically as a mapping from time to powert → P , wherẽ t = [t 1 ; t 2 ] is a time interval for which power value P is valid, multiple time intervals may be considered. Figure 2 shows an example of the power balance state after the discretization. In the example, the acceptance function is shown from eq. (10).  Figure 2. Boolean demand and supply The LPEP++ then does not intitiate a new negotiation or each timestep, but it allows to consider several timesteps in one negotiation and so consider entire schedules in one negotiation. Thus, the LPEP++ keeps the maximum of the flexibility and furthermore improves effiency.

V. SOLVER MODIFICATION
Due to heterogenous power offers, sizing each atom of the power of the agents by using the greatest common divisor leads to many different variables. As an alternative [2] states using an interval partioning algorithm to lower the number of variables. Therefore, the solvers way to divide the Offer or Demand Notification and the disequilibrium needs to be modificated. It determines interval margins of the power values and uses these interval margins to convert the problem into the boolean domain. Each entry in the TVL for each offer or demand is an atom which states whether the agent influences the power grid for the given power subinterval. The dividing of the notifications into subintervals here is depending on the offers and demands of all other agents and the disequilibrium. Considering power intervals P = (|P 0 |, |P 1 |, |P 2 |, . . .) formed by all power values available for the solver, atoms are represented as: 1 if the power value of agent i is within current power subintervalP and influences power grid at time subinterval x i,t,P , 0 otherwise. (14) Taking the power values P = (5, 51, 150) as an example, thus according to eq. (1) ∆(5, 51, 150) = gcd(5, 51, 150) (15) results in atoms sized gcd(5, 51, 150) = 1 (16) To determine the number of atoms N gcd for the sizing of the atoms with the gcd, divide the maximal power value by the size of atoms.
The example shows the reduction of the number of variables by using the interval paritioning algorithm.

VI. SIMULATION-BASED TESTING A. LPEP++ compared to COHDA
The LPEP guarantees the optimal solution to be found [23]. COHDA, on the other hand, does not give this guarantee. In order to contrast further behaviours of the two systems, a setting was implemented in which both may be compared.
For reactive scheduling, a modified version of Particon's ISAAC was used. ISAAC is a software, used for energy unit aggregation and planning, based on the principles of controlled self-organization and regulated autonomy [25]. Here, ISAAC is used to coordinate the negotiations of the agents.
Within ISAAC, COHDA is used to optimize DER scheduling to a given target. Agents exchange information regarding their independently working algorithms to determine the optimal.
The LPEP++ was additionally integrated into ISAAC, which allows to start negotiations with both systems.
In the scenario, six agents are considered. For each MAS, 100 negotiations were computed. The comparison includes the number of messages exchanged, the size of the messages and the duration of the negotiation until the convergence. Results are collected in Table I.
The standard deviation of the message size in cohda is due to the fact that the agents send along the system state. This contains the current solution candidate. As the negotiation progresses, the number of agents included in the solution candidate increases, since the agent only knows part of the network at the beginning of the negotiation. Furthermore, the standard deviation of the negotiation period of the LPEP is due to the implementation of the timer. The LPEP meets the advantages such as fast convergence provided by COHDA, while still guaranteeing the optimal solution to be found.

B. LPEP++ with communication delays
To state the robustness of the LPEP, a communication scenario in the Python Library NetworkX was implemented. NetworkX provides functionality for analysing networks and graphs. A wireless Network was created, each of the six agents was placed at a single node. Between the nodes, three access points were placed. The scenario was used to determine communication delays between two agents. The delay between each agent and its closest access point was chosen randomly between 0.01 and 0.1 seconds. To determine the delay between certain agents, the shortest path according to Dijkstra's algorithm was calculated. When exchaning information, the agent's messages are delayed by the computed time according to the ICT scenario. Results show that with different possible topologies of the agent, the LPEP always finds the problems solution.

VII. CONCLUSION AND FUTURE WORK
The protocol extension includes the additional calculation of the applicable power as soon as the disequilibrium cannot be completely dissolved. In addition, the possibility of rescheduling longer-term planning intervals such as entire schedule was demonstrated. The modifications and extensions of the protocol lead to advantages in certain use cases and also enable its use in other cases such as the replanning of an entire schedule table, e.g. during intraday planning.
The solver modification includes the division of the atoms by using the interval boundaries instead of the gcd. This results in a lower number of variables which provides more effiency.
The results show that the protocol finds a solution under acceptable time with acceptable message sizes and can keep up with the heuristic COHDA in aspects such as fast convergence, but beyond that it even provides the guarantee of solution completeness which COHDA does not.
To simulate the communication infrastructure, delays were determined using a wireless network scenario. It was shown that the protocol extension performs robustly even under nonoptimal ICT simulations. The solution is guaranteed to be found even with these communication delays.
To underpin the robustness of the protocol under poor communication conditions, a communication scenario is to be implemented in OMNET++, which will be linked to the agent implementation. This allows the protocol to be tested under high traffic and packet losses.