Robust optimization in self-organizing power management
Dynamically evolving hierarchical structures offer robust, scalable and efficient power allocation in the presence of uncertainties.
In the future, energy systems will likely transition from classical few-suppliers-to-many-consumers scenarios to distributed systems involving highly stochastic generation from weather-dependent producers (e.g., photovoltaics and wind power plants). However, the ultimate goal of balancing supply and demand at all points in time becomes much harder to achieve in collective adaptive systems such as these. Effective organizational strategies are therefore required to enable the optimal dispatch of resources under uncertainties and thereby keep the power grid stable and economically attractive for both producers and consumers.
As a result of the increased interest in so-called smart grids, there are many research areas that focus on the problems that they impose. Representative studies are found in a variety of fields, including: computational economics investigating market-based distribution mechanisms; artificial intelligence and machine learning regarding the prediction and analysis of usage patterns; embedded and networked systems and their search for suitable protocols and hardware; and in control theory, regarding optimal controllers for distributed power plants. Many of these approaches involve so-called island networks (e.g., an isolated village), or are located at the level of a single household. In particular, many efforts are aimed at demand-response settings, wherein the demand is controlled according to the user’s goals. While all of these challenges and many more require attention, we believe that self-organizing principles excel in the problem of forming virtual power plants dynamically and enhancing existing optimization techniques for robust scheduling.
Factors involving uncertainty, volatility of participants and large scales require a mix and extension of various techniques that have so far been investigated mostly in isolation by different communities. Coalition structure games provide a formal framework for the analysis of partitions of agents, with the aim of maximizing social welfare. On the other hand, stochastic programming offers methods that enable decisions to be made under uncertainty while maintaining probabilistic success guarantees of the proposed solutions, or maximization of their expected utility. Game theorists have devised mechanisms that offer incentive schemes to agents, making truth telling their best strategy regarding the costs of production. Furthermore, literature offers some formalizations of optimal power-plant scheduling by means of mixed-integer models. We believe that these techniques must be coupled for an effective approach. For example, coalitions should be formed according to an observed runtime measure instead of a static characteristic cost function. Similarly, scheduling problems can be interleaved with structure formation to quickly obtain efficient and robust plant schedules.
Our approach revolves around the concept of autonomous virtual power plants (AVPPs). This technique partitions the whole system into balanced structures of trustworthy and untrustworthy units to make maximal use of all participants. We have devised self-organization algorithms to form and maintain adequate hierarchical structures of AVPPs at runtime. Such hierarchies provide benefits in terms of scalability and uncertainty compensation. We furthermore developed techniques for modelling heterogeneous suppliers and collectives. Additionally, trust-based methods allow AVPPs to anticipate deviations from predictions and calculate schedules for multiple scenarios of future energy that must be provided. We validated our techniques in a simulation based on a real-world model: see Figure 1.
The first important step is to find a suitable hierarchical structure of virtual and physical power plants. On the one hand, we aim for a structure that distributes untrustworthy agents evenly. This criterion ensures that each AVPP is able to compensate for uncertainties introduced by untrustworthy agents using their own subordinate trustworthy ones. On the other hand, we want a structure that reduces the discrepancies in terms of runtimes between different AVPPs by constraining their size and number. Usually, we cannot achieve both perfectly and need to find a suitable tradeoff. Because finding the optimal partitioning is an NP-hard problem, we have devised a discrete particle swarm optimizer (PSOPP) and a decentralized algorithm (SPADA) to help solve it.. These computational methods enable the problem to be solved sufficiently well for practical instances. As the environment and internal states of agents change at runtime, we want the hierarchy to adapt. After a suitable partitioning and hierarchy are obtained, control models for each AVPP must be created by means of a so-called supply automaton. This automaton represents the capabilities of its collective. Because power plants are subject to inertia regarding their controllability (e.g., ramp-up limits or minimal runtimes), we cannot arbitrarily change their output in a limited time frame. However, due to the self-organizing system structure, these models must be created at runtime. We generate optimization problems using these automata combined with additional constraints and objectives (e.g., cost-efficient distribution of the load). Collective control models are further abstracted using interval algebra and sampling, combined with active learning. These abstracted models are computationally more attractive than the mere composition of all underlying agents, and serve as a basis for coarse scheduling decisions made on higher levels of the hierarchy.
However, it is not just technical properties that matter in the system. Owners of power plants may have preferences regarding how they would like their system to be controlled. We have therefore devised a novel formalism that relies on a partial order over soft constraints to denote their relative importance, which each agent specifies to capture its preferences. This relieves us from making the soft constraints of different agents comparable, as would be required by a totally ordered scheme. Such a total ordering would require a common currency (e.g., weight 10 must mean the same priority level to each agent) that cannot be assumed, in general. If not all soft constraints can be satisfied, we aim to achieve as many as possible, respecting their relative importance.
We also devised a probabilistic model of deviation sequences to deal with stochastic influences (e.g., the weather-dependent production). These sequences, called trust-based scenarios, are acquired at runtime and used for proactive scheduling. Each scenario represents an expected development of the future demand or production and has a particular probability of occurrence. For solving the scheduling problem in large-scale open systems, we developed an auction-based mechanism called TruCAOS,, which deals with uncertainties by means of scenarios and trust values.
Our vision of a self-organizing hierarchy of autonomous (virtual) power plants shows promising initial results and has led to the development of techniques that can be applied to other large-scale multi-agent systems. The next stage of our research involves the integration of other resources besides energy (like gas or heat networks) and the investigation of how our principles can be gradually introduced into existing energy systems.
This research is sponsored by the German Research Foundation (DFG) via the “OC-Trust” (project FOR 1085).
Authors: Alexander Schiendorfer, Gerrit Anders, Hella Seebach and Wolfgang Reif
Institute for Software & Systems Engineering, University of Augsburg, Germany
- S. D. Ramchurn, P. Vytelingum, A. Rogers and N. R. Jennings, Putting the ‘smarts’ into the smart grid: a grand challenge for artificial intelligence, Commun. ACM 55, pp. 86–97, 2012.
- A. Hartmanns, H. Hermanns and P. Berrang, A comparative analysis of decentralized power grid stabilization strategies, Proc. WSC, pp. 1–13, 2012.
- J.-P. Steghöfer, G. Anders, F. Siefert and W. Reif, A system of systems approach to the evolutionary transformation of power management systems, Proc. INFORMATIK, 2013.
- G. Anders, F. Siefert and W. Reif, A heuristic for constrained set partitioning in the light of heterogeneous objectives, LNAI 9494, 2015.
- G. Anders, F. Siefert, J. P. Steghöfer and W. Reif, A decentralized multi-agent algorithm for the set partitioning problem, Proc. PRIMA 7455, pp. 107–121, 2012.
- A. Schiendorfer, G. Anders, J. P. Steghöfer and W. Reif, Abstraction of heterogeneous supplier models in hierarchical resource allocation, TCCI XX, 2015.
- A. Knapp, A. Schiendorfer and W. Reif, Quality over quantity in soft constraints, IEEE Proc. 26th ICTAI, pp. 453–460, 2014.
- A. Gerrit, F. Siefert, J.-P. Steghöfer and W. Reif, Trust-based scenarios -- predicting future agent behavior in open self-organizing systems, IWSOS, pp. 90–102, 2014.
- G. Anders, A. Schiendorfer, F. Siefert, J. P. Steghöfer and W. Reif, Cooperative resource allocation in open systems of systems, ACM TAAS 10, 2015.