Coalitional model predictive control for systems of systems

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA Universidad de Sevilla Filiberto Fele Coalitional model predictive control for systems of systems DOCTORAL THESIS Sevilla, 2016 ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA Universidad de Sevilla Filiberto Fele Coalitional model predictive control for systems of systems DOCTORAL THESIS Supervisors: Professor Eduardo F. Camacho Dr. José María Maestre Sevilla, 2016 This Doctoral thesis has been made at Escuela Técnica Superior de Ingeniería de Sevilla, University of Seville, Department of Systems and Automation Engineering Supervisors: Professor Eduardo F. Camacho Dr. José María Maestre This Doctoral thesis contains 159 pages Abstract Coalitional model predictive control for systems of systems An aspect so far rarely contemplated in distributed control problems is the explicit consideration of individual (local) interests of the components of a complex system. Indeed, the focus of the majority of the literature about distributed control has been the overall system performance. While on one hand this permitted to address fundamental properties of centralized control, such as system-wide optimality and stability, one the other hand it implied assuming unrestricted cooperation across local controllers. However, when dealing with multi-agent systems with a strong heterogeneous character, cooperation between the agents cannot be taken for granted (due to, for example, logistics, market competition), and selfish interests may not be neglected. Another critical point that must be kept into consideration is the diversity characterizing systems of systems (SoS), yielding very complex interactions between the agents involved (one example of such system is the smart grid). In order to tackle such inherent aspects of SoS, the research presented in this thesis has been concerned with the development of a novel framework, the coalitional control, that extends the scope of advanced control methods (in particular MPC) by drawing concepts from cooperative game theory that are suited for the inherent heterogeneity of SoS, providing as well an economical interpretation useful to explicitly take into account local selfish interests. Thus, coalitional control aims at governing the association/dissociation dynamics of the agents controlling the system, according to the expected benefits of their possible cooperation. From a control theoretical perspective, this framework is founded on the theory of switched systems and variable structure/topology networked systems, topics that are recently experiencing a renewed interest within the community. The main concepts and challenges in coalitional control, and the links with cooperative network game theory are presented in this document, tracing a path from model partitioning to the control schemes whose principles deliniii iv eate the idea of coalitional control. This thesis focuses on two basic architectures: (i) a hierarchically supervised evolution of the coalitional structure, and (ii) a protocol for autonomous negotiation between the agents, with specific mechanisms for benefit redistribution, leading to the emergence of cooperating clusters. Keywords: model predictive control, cooperative MPC control, cooperative game theory, multi-agent systems, systems of systems, microgrid, smart grid, irrigation canals Contents 1 Introduction 1 1.1 Controlling large-scale systems: the path to coalitional control . . . . . 3 1.1.1 Model partitioning . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Cooperative control . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.3 Dynamic neighborhoods and coalitional control . . . . . . . . . 9 1.2 Coalitional MPC control . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Objective of coalitional control . . . . . . . . . . . . . . . . . . 12 1.2.2 Cost of cooperation . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.3 Global control problem . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.4 A game theoretical perspective . . . . . . . . . . . . . . . . . . 15 1.3 Contributions of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.4 Thesisoutline................................ 21 2 Supervised coalition structure generation 23 2.1 Introduction................................. 23 2.2 Systemdescription ............................. 25 2.2.1 Model ................................ 25 2.2.2 Exchange of information . . . . . . . . . . . . . . . . . . . . . . 25 2.2.3 Coalition dynamics . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Controlobjective .............................. 26 2.4 Thecontrolalgorithm ........................... 27 2.5 Illustrative case I: Coalitional MPC control of an irrigation canal . . . . 30 2.5.1 Modeling the canal . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5.2 Coalition dynamics . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5.3 Controlobjective .......................... 34 2.5.4 The control algorithm . . . . . . . . . . . . . . . . . . . . . . . 36 2.5.5 Simulationmodel.......................... 40 2.5.6 Identification of the control model . . . . . . . . . . . . . . . . . 41 2.5.7 Results................................ 41 i 4Chapter 1. Introduction Once the global model has been partitioned, each resulting subsystem i∈ N is assigned to a local control agent that has partial knowledge of the overall system, such that its behavior can be described by x+ i=fi(xi, ui) + wi, yi=gi(xi) + $i,(1.2) where xi∈Rniand ui∈Rqiare respectively the local state and input vectors, constrained in the sets Xiand Uirespectively, and yi∈Rpiis the local output vector. The vector wi∈Rnirepresents the measurable state disturbances resulting from the coupling with other subsystems, wi=X j∈Mi fij(xj, uj),(1.3) where Mi,{j∈ N \ {i}:∃(xj, uj)∈ Xj× Uj|fij(xj, uj)6=0}is referred to as the neighborhood of subsystem i. Similarly, $i∈Rpiexpresses the measurable disturbances on the local output. Notice that neither the external state and inputs xjand ujnor their relation fij with the local ones are known a priori by the local agent, eventually inducing some modeling error due to possibly neglected state–state, input–state, or input–output interactions. In the search for the optimal structure of the control system, an important limiting factor comes from the available computation and communication resources. For instance, the excessive partitioning of the system may reduce the model size and hence the computational requirements at each node, yet at the expense of an increased communication load—which in turn limits the possibilities of a parallel implementation of the control algorithm. Similarly, while a small sampling time allows to obtain a model that reflects the actual structure of the system, it will result in high communication rates between nodes, as well as in a shorter time available for computation [1]. Besides, more often than not, large-scale systems are characterized by multi-scale dynamics—typically slower overall dynamics arising out of a group of subsystems with fast dynamics. With specific attention towards the strong relationship between model decomposition and sampling time, a structural analysis for decomposition is presented in [1], oriented to the implementation of a hierarchical multi-rate estimation and control architecture. In [18], the coupling structure of the plant is analyzed prior to the design of feedback laws in order to decompose the model into hierarchically coupled clusters. A two-layer multi-rate control for such hierarchical decomposition is proposed in [19], 1.1. Controlling large-scale systems: the path to coalitional control 5 where information is exchanged at each time step within clusters of strongly coupled subsystems, while a slower communication rate is required between different clusters. The interaction among subsystems can be as well viewed as multiplicative output uncertainty. In [20], the selection of best model partition within a given set of candidates is based on their associated (open loop) uncertainty bounds. The implications of system decomposition on robustness are investigated in [21]. The robustness of distributed MPC schemes characterized by different levels of knowledge of the non-local dynamics of the system is evaluated by means of an H∞index. The formulation of a multi-objective mixed-integer nonlinear programming problem (MINLP) based on this index allows to seek a tradeoff between global robust performance and the degree of connectivity among agents (translated in terms of local interaction model coverage). Given Nsubsystems, the MINLP considers N(N−1) binary variables to choose the structure of the controller over all possible connections among the subsystems. Simulation results show how controllers characterized by dense connectivity are more sensitive to errors in the interaction models. When these are affected by significant uncertainty, a fully decentralized structure can provide higher robustness. Several other methods have been proposed in the literature. In [22], the most relevant variables of the system are controlled by a central coordinator MPC, and a set of decentralized controllers complete the control action by responding to the inputs of the coordinator. The work of [23] addresses the assignment of actuators to a given set of controllers on the basis of two criteria, in order to achieve submodels of manageable size for MPC control. The first is an open-loop criterion based on maximizing the connectivity of the weighted graph representing the system, as an expression of the Hankel norm resulting by the controllability and observability Grammians. The second is a closed-loop criterion that aims at minimizing the performance degradation due to model partitioning, measured through the MPC’s cost function. A method for the derivation of a distributed model is suggested in [24], based on the Kalman canonical form of the linear state-space model for each input-output pair [25]. An exhaustive study of the issues related to model partitioning for the decentralized control of large-scale systems can be found in [6]. One contribution of [6] is that of showing how graph theory methods are well suited to gain an insight about the structural controllability and observability of large-scale systems, and employ these as a basis for model decomposition. Graph theory methods have been as well employed for the analysis of the impact of system topology on controllability and observability in [26, 27]. Based on graph partitioning is the work of [28], where a decomposition method providing a set of non-overlapping subgraphs, with balanced number of vertices and 6Chapter 1. Introduction minimal number of interconnecting edges, was developed. More recently, a threshold on the Shapley value [29] of the potential communication links between the controllers was proposed in [30] as a criterion for partitioning. 1.1.2 Cooperative control We assume in the following that the objective of each local controller is to drive the subsystem’s state towards the origin of the state space. The cost of subsystem iat any given time step kis expressed by the stage cost `i(xi, ui). At time k, a control sequence is derived by the solution of the MPC problem min uiJi= Np−1 X t=0 `i(xi(t|k), ui(t|k)) + Vi(xi(Np|k)) (1.4a) s.t. xi(t+ 1|k) = fi(xi(t|k), ui(t|k)) + ˆwi(t|k),(1.4b) hin i(xi(t|k), ui(t|k)) ≤0, t = 0, . . . , Np,(1.4c) heq i(xi(t|k), ui(t|k)) = 0, t = 0, . . . , Np−1,(1.4d) xi(0|k) = xi(k).(1.4e) The first element of the minimizer u∗ i,[ui(0|k)∗, ui(1|k)∗, . . . , ui(Np−1|k)∗]is applied as input to the subsystem, and the problem is solved again at subsequent time steps in a receding horizon fashion. Notice that, in absence of measures from the rest of the system, an estimate of the disturbance term (1.3) is employed in the solution of (1.4). For this reason, decentralized schemes generally require either assuming a priori bounds on the coupling between subsystems, or considering worst-case interactions, resulting in a loss of performance [1]. Communication between local controllers allows to achieve a visible enhancement in the overall control performance; however, it is difficult to synthesize a general result, due to the dependence on the particular scheme used [31, 32]. It is essential that the communication serves as a means to reach a shared consensus—an improvement over the decision that each agent would be able to make by relying merely on locally available information. Once the model partitioning is given, the control by means of a cooperative scheme requires to answer fundamental questions. We analyze some of them in the following. 1.1. Controlling large-scale systems: the path to coalitional control 7 How communication improves performance? According to the degree of selfishness of the objective function employed, two categories of controllers emerge in the distributed MPC literature: noncooperative, where the agents pursue a local objective, and cooperative, where the influence on the rest of the system, including how nonlocal objectives are affected, is taken into account in the choice of the inputs locally applied by each agent. More specifically, a global objective—consisting of a given (weighted) combination of individual objectives—is optimized over local inputs ui,i∈ N, min uiJ= Np−1 X t=0 `(xi(t|k), ui(t|k), x−i(t|k), u−i(t|k)) + V(xi(Np|k), x−i(Np|k)),(1.5) subject to (1.4b)–(1.4e) (subscript ‘−i’ designates all subsystems j∈ N \{i}). Several techniques can be applied to obtain feedback about the values of nonlocal variables in (1.5): typically, controllers update these values over intermediate iterations, by direct exchange or through Lagrangian multipliers. The importance of cooperation among MPC control agents is underlined in [8]: the exchange of information among subsystems provided with mutual interaction models does not constitute a sufficient guarantee for closed-loop stability, due to the competition arising from the pursuit of conflicting objectives. Similar conclusions are given by [33], showing that increased cooperation not always translates to a gain in performance; indeed, in some cases it may even lead to a performance loss. This emphasizes the importance of the criteria upon which the cooperation is based. In case that the interests of local controllers diverge from the global benefit, a reward scheme may be implemented at the supervisory layer in order to bring these interests as much in line as possible [13]. Who should communicate with whom? The control agents communicate through a data network whose topology can be described by means of the undirected graph G= (N,E), where to each subsystem in Nis assigned a node. Dependence of the optimal topology E ⊆ N × N of the communication graph on the coupling between the local control problems is expected. The answer can be derived from a case-oriented evaluation of the performance deterioration due to the absence of communication between a given pair of local controllers. Control architectures for large-scale systems typically include a supervisory level, which may act as a coordinator to set the necessary information flows [13]. The sharing of information in a networked system can be represented through a knowledge graph, where each node stands for the model of a given subsystem, and the edges 8Chapter 1. Introduction indicate that the information about the models is available to the agents controlling the pointed nodes. The connectivity and the degree distribution of such graph can be interpreted in quantitative terms [34]. In [33], a graph representing the coupling between subsystems is updated at each time step by identifying the constraints that were active at the previous time step. Then, the cooperating sets are formed by those subsystems that are connected by a path in the graph. Further control-related studies, such as [35, 36], focus on the PageRank index, a variant of the eigenvector centrality measure, used to quantify the relevance of nodes from a coalition formation viewpoint. What information should be available to each local agent? The answer to this problem depends on the coupling source and the type of distributed control strategy that is implemented. In general, the need for information exchange is inversely proportional to the coverage of the locally available information. In [37], the control is performed by means of a (global) linear feedback law. A continuous exchange of information is avoided by providing models of the coupled subsystems to each agent. In the interval between broadcasts, these models are used to predict a local estimate of the evolution of the neighbors’ state. In [10] the effect of input coupling is viewed—on the grounds of the slow dynamics of the plant under study—as a constant disturbance along the prediction horizon, which is then estimated with a Kalman filter. Usual choices are the expected state and/or input sequences [38, 39], or auxiliary coordination variables such as prices [40] or sensitivities [41]. See also [42] for further details regarding the information exchange in different schemes. Regardless of the knowledge of the global dynamics that may be available to each agent, the closed-loop behavior can range from stable and almost optimal, to unstable Nash equilibria if conflicting objectives are pursued. This sensible difference in performance is likely to be detected when dealing with strongly coupled subsystems [8]. How to deal with constrained communications? The system dynamics impose limits on the time available to make agreements over cooperative decisions. Limitations in bandwidth or in energy consumption, as well as communication delays or packet losses concerning the data link infrastructure, need to be taken into account. Some algorithms are more flexible than others in this regard, providing superior robustness to delays or failures in communication. For example, the strategy presented in [24] admits the injection of suboptimal control actions in order to relax the heavy communicational requirement typical of iterative distributed schemes. Through a hierarchical design, 1.1. Controlling large-scale systems: the path to coalitional control 9 this same strategy has been later extended to allow the asynchronous update among different neighborhoods [5]. Another example of algorithms showing such properties can be found in [39], where the robust tube feedback formulation admits steps with no updates (by employing shifted input sequences). 1.1.3 Dynamic neighborhoods and coalitional control The coupling among subsystems can be categorized over three classes. In presence of dynamical coupling, a subsystem’s behavior may be influenced by the value of the state and/or input of some other subsystems. Output coupling is a particular case of state coupling. This class of coupling can be described as in (1.2)–(1.3). When the system is characterized by constraints involving multiple subsystems, the coupling is seen through the constraints. This wide class includes constraints on input and/or state variables (such as physical limits of the plant or common-pool resources), and constraints not involving physical limits but related with the objective functions of the subsystems (for example, limited benefit within a free market with limited demand). Such problems may be analyzed under a zero-sum games perspective. Notice that constraint-coupled subsystems are not necessarily dynamically coupled. In this case, constraints (1.4c)–(1.4e) take the form: hin(x, u)≤0, heq(x, u) = 0,(1.6) where hin and heq cannot be fully decomposed into independent equations hin i(xi, ui), heq i(xi, ui),i∈ N. Lastly, coupling can appear through the objective function: subsystems are part of a larger interacting environment and, therefore, it is likely that external variables exert some influence on their performance. These variables are usually related with the state of other subsystems, and often express economic indices. Notice that this category may overlap with the previous ones. Broadly speaking, a neighborhood designates a group of agents whose control problems show appreciable coupling that can be sensed within a limited time delay. Although the coupling structure may be fixed for a given system, in most cases the effect of coupling fluctuates. At this point, a natural question is what to do when coupling varies with time? Is it reasonable to consider time-varying neighborhoods? Some distributed control schemes in the literature have already moved in this direction. The notion of cooperating sets is employed in [33, 39]. Within any given cooperating set, one subsystem at each time step locally computes optimal control ac- 10 Chapter 1. Introduction tions for all the subsystems involved in the set, even if only the results relative to that subsystem are broadcast. The rationale behind computing such “hypothetical” nonlocal control inputs is to optimize the individual strategy considering what others may be able to achieve, so that cooperation is indirectly promoted among the agents. The composition of such sets is updated according to a graph representing the active coupling constraints. Interestingly, the results of [33] show that the optimal cooperating set is not necessarily restricted to directly coupled subsystems. In the distributed MPC scheme of [43], the cost incurred by each local controller is dynamically adjusted to fulfill minimum local requirements, on the basis of situational altruism criteria. On a similar line is the work of [44], where a flexible hierarchical MPC scheme is proposed for a hydro-power valley, where the priority of the agents in optimizing their control actions can be rearranged according to the different operational conditions. The work of [10] investigates the design of a hierarchical control scheme characterized by some flexibility over the employ of the data network through which the local control agents exchange information. The application on an irrigation canal is considered as a case study. The design of an optimal communication topology and its associated set of decentralized feedback control laws can be posed as a mixed-integer problem. However, such formulation generally suffers from high computational complexity as the number of control nodes and the possible communication links between them grow. This issue is addressed through a two-layer greedy approach in [10], with the aim of optimizing the data links usage and decomposing the global MPC problem in small sized subproblems whenever possible. The goal of the supervisory layer is to find the best compromise between control performance and communication costs by actively modifying the network topology. The actions taken at the supervisory layer alter the control agents’ knowledge of the complete system, and the set of agents with which they can communicate. Each group of linked subsystems constitutes a coalition, independently controlled on the basis of a decentralized MPC scheme managed at the bottom layer. This feature is particularly interesting for communication infrastructures based on battery-powered wireless communication devices. The properties of a multi-agent control scheme based on this same idea are discussed in [9], where the time-variant relevance of the communication within a set of dynamically coupled linear systems is analyzed using tools from cooperative game theory. A different approach is found in [45], where the distributed MPC problem for dynamically-coupled subsystems is analyzed under a dynamic bargaining game perspective. The formulation follows a few recent proposals in which the classic (static) 1.2. Coalitional MPC control 11 bargaining theory has been extended to dynamic decision environments (see references in [45]). These works focus on the coalition as the objective of the bargaining, as a means of implementing a coalition-wide solution (the same for all members). However, the application of the same control input by all the agents in a coalition is likely to provide poor performances—if not an infeasible strategy—in a controlled system. Filling this gap, the work of [45] provides a distributed MPC formulation where cooperation is subject to bargaining: an agent accepts to be part of a coalition only if a benefit is foreseen over the performance expected by acting independently. Guarantees for the satisfaction of a minimum individual performance are imposed by means of a disagreement point, defined as the threshold of maximum allowed loss of performance in case of cooperation. An agent’s disagreement point is decreased whenever it decides to cooperate, and increased otherwise such as to foster a later participation; in this way, the disagreement point tends to the optimal expected value of the objective function. The recent advances on ICT, particularly the spread of wireless networks and cloudbased applications, simplify the deployment of a communication infrastructure between local controllers. The use of a distributed database of systemwide measures to achieve a globally optimal, yet scalable, control is a promising line of research yet to be explored [1]. Nonetheless, when non-local information is critical for adequate global feedback, issues derived by privacy-concerned subsystems not inclined to share local models and/or state information need to be specifically addressed. 1.2 Coalitional MPC control The distinct feature of such adaptive schemes, namely the rerouting of information flows among changing sets of controllers, can be schematized by the dynamical graph G(k) = (N,E(k)), where the time dependence of E(k)⊆ N × N reflects the possibility to activate or shut down data links at any given time step k. A coalition is constituted by establishing flows of information—a broadened control feedback—within a given set of agents. The cooperation of the agents within a coalition can be carried out in different ways: the agents can exchange whichever information is required to enhance their performance by jointly solving the control problem—commonly state or output trajectories, or planned input sequences. The flow of such information from agent ito agent jis enabled by the activation of the associated link lij ={i, j}∈E. The description provided by G(k)delineates a partition P(N,G(k)) = {C1,...,CNc} of the set of controllers into Ncconnected components, referred to as coalitions [46]. 12 Chapter 1. Introduction Coalitions are disjoint sets such that [47] Ci⊆ N,for all i∈ {1, . . . , Nc},and Nc [ i=1 Ci=N. The number of coalitions Ncpertains to the interval [1,|N|], whose extremes correspond to the centralized control case (all the |N | subsystems connected) and the case where each subsystem “forms a coalition” on its own (all links disabled). The dynamics (1.2) of all subsystems relative to a given connected component i∈ {1, . . . , Nc}can be aggregated as ξ+ i=Fi(ξi, νi) + ωi,(1.7) with ξi,(xj)j∈Ci,νi,(uj)j∈Cithe aggregate state and input vectors, and Fi(ξi, νi) the relative state transition function, describing the state and input coupling between members of the same coalition. Finally, the vector ωi= (w0 j)j∈Ci(1.8a) gathers the disturbances due to the coupling with subsystems external to Ci. Following (1.3) it holds that w0 j=X r fjr(xr, ur),with r∈ Mj\ Ci,(1.8b) pointing out how, for each j∈ Ci, the set of unknown coupling from neighboring subsystems is reduced to the neighbors left out of the coalition. That is, from the coalition standpoint, the uncertainty comes from any subsystems r∈(Sj∈CiMj)\ Ci. Notice that in case of singleton coalition, i.e., Ci≡ {i}, the description given by (1.7) coincides with (1.2). 1.2.1 Objective of coalitional control In the remainder, we refer to the stage cost extended to Ci⊆ N as `i(ξi, νi). Although the most straightforward example would be `i≡Pj∈Ci`j, the coalitional stage cost can be formulated differently to exploit the added knowledge provided by cooperation. One such example is provided in 3.6. Local controllers aggregate into a coalition with the aim of coordinating the effort and achieving a better overall performance. At time k, a control sequence for all subsystems j∈ Ciis derived by the joint solution of the 1.2. Coalitional MPC control 13 MPC problem min νi Ji= Np−1 X t=0 `i(ξi(t|k), νi(t|k)) + Vi(ξi(Np|k)) (1.9a) s.t. ξi(t+ 1|k) = Fi(ξi(t|k), νi(t|k)) + ˆωi(t|k),(1.9b) Hin i(ξi(t|k), ν(t|k)) ≤0, t = 0, . . . , Np,(1.9c) Heq i(ξ(t|k), ν(t|k)) = 0, t = 0, . . . , Np−1,(1.9d) ξi(0|k) = ξi(k),(1.9e) Problem (1.9) is solved independently for each coalition Ci∈P(N,G(k)). At time kthe first element of νi(k)∗is applied to every subsystem involved in the coalition. Given (3.1b) and (1.8b) we have   w0 j  ≤ kwjkfor j∈ Ci; in words, since the effect of unmodeled interactions on the dynamics of any subsystem is reduced by its participation in a coalition, an improvement of the associated performance index is expected. Broadly speaking, provided the agents cost functions are linked, a prerequisite of cooperation is that the aggregate cost of the agents participating in a coalition outperforms the cost that the agents would have achieved through noncooperative optimization, that is, J∗ i<Pj∈CiJ∗ jmust hold. In case the cost function expresses economical quantities, this translates in the availability of a surplus that can be split among the members of the coalition. 1.2.2 Cost of cooperation Cooperation may not come for free. First, as previously discussed, communication may be constrained: a clear example is given by wireless networks, where the use of the links can be restricted in bandwidth/duration to reduce the energy consumption. In order to stimulate an optimal use of the network, it is reasonable to associate a cost to any communication (including those performed for the obtainment of measures). In some contexts, where privacy concerns are preponderant, the cost may also depend on the identities of the transmitter and the receiver: some agents may be less prone to exchange information than others. Besides, the coordination of a large number of agents can become a problem itself because the computation and communication requirements grow with the number of cooperating controllers involved. Therefore, costs required for the cooperation of a given set of agents can be taken into account by means of ad hoc indices related with the composition of the coalition or the data links needed 20 Chapter 1. Introduction munication between the various control stations is impractical. Considering all these factors, the study focused on the design of an MPC control scheme featuring flexible structure. The approach relied on partitioning the global control law amongst a number of local control agents, a common starting point in distributed architectures. The aim was to adapt the partitioning to the varying coupling conditions between different parts of the system, in an online fashion, promoting cooperation among clusters of control nodes when clear benefits in the performance were foreseen. A two-layer architecture was developed, where the information flow is manipulated by disconnecting data links that do not yield a significant improvement of the control performance, compared with their relative cost of use. This feature is particularly interesting, for example, whenever battery-powered devices are used for decentralized sensing and control, or when such tasks are delegated to human-in-the-loop interventions. As a result, the system is partitioned into coalitions working in a decentralized fashion. The work was validated on a detailed model of a 45 km section of the Dez irrigation canal, implemented on the hydrodynamic simulator SOBEK [10]. While in [10] the cooperation in the achievement of the global objective is not questioned, in [65, 62] it is assumed instead that the agents controlling the system base their cooperation on the individual rationality criterion: they will be willing to cooperate only if the expected individual benefit derived through cooperation exceeds the one achieved through noncooperative control. Such individual rationality concerns have been addressed in an autonomous coalition formation framework, where coalitions are the outcome of an pairwise bargaining procedure, through which the structure of each agent’s controller is adapted to the time-variant coupling conditions. Furthermore, the distribution of the value of a given coalition among its components is addressed in [62] by means of an iterative utility transfer scheme that compensates the dissatisfaction of subset of members with respect to their currently assigned payoff. Such method guarantees coalition-wise stability, provided that the set of stable allocations of the associated transferable-utility (TU) game is nonempty. The last part of the thesis shows the application of coalitional control for the management of fast charging stations for plug-in electric vehicles (EV). Pricing strategies have been studied considering an open market scenario (analogous to common gas stations), with offers by several competing parties (charging managers). In such a scenario, the prices serve as incentive for EV drivers to deviate from their ideal route and seek for the best battery recharging alternative. The coalitional control framework has been employed to improve the performance of the charging managers on the market, by joint strategy planning and subsequent benefit redistribution [66]. 1.4. Thesis outline 21 1.4 Thesis outline The thesis is organized in five chapters. After the introductory research outline presented before, chapters are described as follows. •Chapter 2 addresses the hierarchical supervision of the cooperation structure among the agents of the system. A two-layer coalitional control architecture is presented: the cooperation structure is manipulated at the top layer according to given collective objectives, whereas the bottom layer handles the real-time control tasks, decentralized into the coalitions arising from the chosen cooperation structure. The discussion is directed on two case studies. The first regards the management of water distribution infrastructures, where the objectives of the local control agents align with those of the whole system. Coalitions are implemented as a means to change the cooperation topology to best fulfill an overall efficiency objective. The second illustrates a smart grid scenario involving a set of prosumers connected to the main grid and equipped with local generation and storage devices. Prosumers can establish a local energy market running in accordance to the coalitional control scheme, pursuing the minimization of the cost of buying energy from the main grid while minimizing losses due to transfers over the distribution lines. In this case, the prosumers are decoupled agents with autonomous objectives: therefore, the cooperation here aims at the energy loss reduction (collective goal) and at the maximization of individual economic objectives. •In Chapter 3, the assumption of the availability of an omniscient supervisor is dropped. A protocol for autonomous negotiation between the agents is introduced, based on pairwise bargaining over coalition formation. This protocol provides a specific method for benefit redistribution, to specifically address individual rationality (agents cooperate only if the expected individual benefit derived through cooperation exceeds the one achieved through noncooperative control). This method consists in an iterative utility transfer scheme that compensates the dissatisfaction of subset of members with respect to their assigned payoff. Coalition-wise stability is subject to the nonemptiness of the set of stable allocations of the associated transferable-utility (TU) game. A wide-area control application for power grid, with the objective of minimizing frequency deviations and undesired inter-area power transfers, has been considered to demonstrate this second architecture. 22 Chapter 1. Introduction •Chapter 4 shows the application of coalitional control for the management of fast charging stations for plug-in electric vehicles (EV). The use of coalitional control as a means to improve the performance of the charging managers on the market is shown. By modeling the interaction of charging managers in an open market scenario as a coalitional game, joint strategy planning and subsequent benefit redistribution are evaluated. Pricing strategies are optimized in order to incentivize EV drivers to deviate from their ideal route and seek for the best battery recharging alternative. •The thesis is finally concluded in Chapter 5 by an overview of the results with last remarks about future developments and reserch challenges. Chapter 2 Supervised coalition structure generation 2.1 Introduction Often different parts of a networked system are owned and managed by independent entities (think about infrastructures), unwilling to coordinate their action unless strictly necessary. In addition, permanent communication across the entire system network can be impractical. Consequently, even when the whole system is owned and managed by a single entity, the use of a traditional centralized control approach is hampered. This motivates the two-layer hierarchical control scheme presented in this chapter. The basic setting, introduced in Chapter 1.1, is reported here for the linearized case specifically employed for the controller design. The proposed algorithm is an approximation of the global problem (1.10) formulated in Section 1.2.3, for the generation of the optimal coalitional structure according to (1.12). The main goal of the supervisory layer is to find the best compromise between control performance and coordination effort by actively modifying the cooperation topology. The actions taken at the supervisory layer alter the control agents’ knowledge of the complete system, and the set of agents with which each one of them can communicate. Each group of linked subsystems—a coalition—is independently controlled following a decentralized MPC scheme, constituting the bottom layer of the architecture [10]. The basic idea is to partition the centralized problem over a given number of local controllers or agents (see, e.g., [6]). The presence of a supervisor makes possible the global design of a feedback control law, that may be structured in accordance to any 23 24 Chapter 2. Supervised coalition structure generation given partition. By a global design, the satisfaction of certain global properties can be guaranteed. Given such a feedback law, the cooperation of the agents can be realized in two ways: (i) it can turn into an explicit exchange of local information (such as interaction models, state measures, etc.) for the joint optimization of future input sequences, or (ii) it can remain at the implicit level dictated by the globally-designed control law. A multi-agent control scheme based on the same basic idea is discussed in [9], where a design method with closed-loop stability guarantees is provided. The optimization of the data network topology, through which the agents establish cooperation links, is regarded as a cooperative game in order to study the relevance of the different links and agents (in view, e.g., of fault-tolerant policies) From this game-theoretical perspective, the sequence of optimal network topologies is interpreted as a set of coalitions of links that evolve in order to optimize the trajectory of the closed-loop system. Among other related works is [33], addressing the formation of groups of cooperative agents according to the coupling constraints that are active at a given time. [19] describes a hierarchical framework where information is exchanged at each time step within clusters of strongly dynamically coupled subsystems, while a slower communication rate is required between different clusters. In [67], the complexity of the MPC control problem of the Barcelona drinking water network is reduced by means of a partitioning algorithm, controlling the resulting subnetworks in a hierarchical-distributed manner. In [44] a flexible hierarchical MPC scheme is proposed for a hydro-power valley, where the priority of the agents in optimizing their control actions can be rearranged according to the different operational conditions. The scheme presented here focuses on how the coupling between subsystems varies with time [10, 61]. A cost on the coordination effort is considered according to several possible criteria, such as the data link usage, the total number of agents involved in the coalition, the number of decision variables and/or constraints of the aggregate problem, reflecting the computational requirements [65], etc. In this way, the overall structure of the controller evolves by trading off performance for savings on coordination costs. As a result, coordination between agents is promoted whenever the undesired effect of dynamic interaction between coupled subsystems (or the benefit of cooperative trajectory planning in case of uncoupled systems) exceeds the threshold dictated by the allowed cooperation costs. 2.2. System description 25 2.2 System description 2.2.1 Model Consider a set N={1, . . . , N}of interconnected systems. The dynamics of any subsystem i∈ N are described by the linear model: xi(k+ 1) = Aiixi(k) + Biiui(k) + Diwi(k),(2.1a) wi(k) = X j∈Mi Aijxj(k) + Bijuj(k),(2.1b) where xi∈Rniand ui∈Rqiare the state and input vectors respectively, and wi∈Rmi describes the influence on xiof the neighbors’ states and inputs. In (2.1b), xj∈Rnj and uj∈Rqjare the state and input vectors of each neighbor j∈ Miof subsystem i. The neighborhood set Miis defined as: Mi={j∈ N|Aij 6=0∨Bij 6=0, j 6=i},(2.2) i.e., it contains all the subsystems j6=iwhose state and/or input produce some effect on the dynamics of subsystem i. 2.2.2 Exchange of information The set of controllers can communicate through a network infrastructure described by the undirected graph G(k) = (N,E(k)), where to each subsystem in Nis assigned a node, and E(k)⊆ N × N is the set of edges. The time dependency of E(k)reflects the possibility to establish cooperation links at any given time step k. The description provided by G(k)delineates a partition P(N,G(k)) = {C1,...,CNc}of the the set of control agents into Ncconnected components. As agents within the same communication component will benefit from cooperation—sharing information in order to aggregate their control tasks—we will refer to such components as coalitions, and the partition resulting by a given network topology E(k)will be denoted as P(N,G(k)) = {C1,C2,...,CNc}. The set of indices SP={1, . . . , Nc}is defined as well. 2.2.3 Coalition dynamics In order to describe the dynamics of each coalition Ci∈P, the following extension of (2.1a) holds: ξi(k+ 1) = Aiiξi(k) + Biiνi(k) + Diωi(k),(2.3) 26 Chapter 2. Supervised coalition structure generation where ξiand νiare respectively the state and input vectors of coalition Ci, composed by stacking the vectors of all the subsystems in the coalition: ξi= (xj)j∈Ci, υi= (js)j∈Ci, i ∈ SP, As an extension of (2.1b), ωiexpresses the influence on ξiof subsystems external to the coalition Ci: ωi= (w0 j)j∈Ci,(2.4c) where (2.4d) replaces (2.1b), since, for each j∈ Ci, the unknown coupling is that relative to the neighbors left out of the coalition: w0 j=X r Ajrxr(k) + Bjrur(k),with r∈ Mj\(Ci∩ Mj).(2.4d) That is, from the coalition standpoint, the uncertainty comes from any subsystems r∈(Sj∈CiMj)\ Ci. Matrices Aii,Aij,Bii,Bij and Diare arranged in order to match the composition of the state and input vectors.1 2.3 Control objective We assume in the remainder that the objective of the controller is to drive the system’s state toward the origin of the state space. The performance of the controller in this task is measured by the MPC cost function J= Np−1 X t=0 X i∈SPξ| i(t|k)Qiξi(t|k) + ν| i(t|k)Riνi(t|k) + ξ| i(Np|k)Piξi(Np|k),(2.5) where Qi≥0,Ri>0and Pi=P| i>0are constant weighting matrices. Costs required for the cooperation of the coalition members are taken into account by means of ad hoc indices related with the composition of the coalition or the number of data links needed to share the feedback information. For coalition Ci, cooperation costs are expressed as a function χi(Ci,Ei), where Ei⊆ E is the subset of edges of the graph G= (N,E)connecting the nodes in Ci. Such cooperation costs are assumed comparable with the cost (2.5). Hence, the optimal cooperation structure for the system at a given time step k, together with its associated global input, is obtained by the supervisor as 1In case of singleton coalition, i.e., C ≡ {i}, the description given by (2.3) coincides with (2.1). 2.4. The control algorithm 27 the solution of the following problem: min ν,EJ= Np−1 X t=0 X i∈SPξ| i(t|k)Qiξi(t|k) + ν| i(t|k)Riνi(t|k) +ξ| i(Np|k)Piξi(Np|k)+χi(Ci,Ei(k)) (2.6a) s.t. ξi(t+ 1|k) = Aiiξi(t|k) + Biiνi(t|k) + Diωi(t|k),(2.6b) ξi(t|k)∈Ξi, t = 0, . . . , Np,(2.6c) νi(t|k)∈Ψi, t = 0, . . . , Np−1,(2.6d) ξi(0|k) = ξi(k),(2.6e) ωi(t|k) = ˆωi(k+t), t = 0, . . . , Np−1,(2.6f) E(t)⊆ N × N, t = 0, . . . , Np,(2.6g) where Ξi=X1× X2×. . . XNiis the Cartesian product of the local state constraints relative to each member of the coalition (an analogous definition holds for the input constraint set Ψi). Since any topology corresponds to a partition of the global system, the composition of the resulting coalitions’ state and input vectors and matrices will implicitly depend on E. The choice of the network topology is made within a discrete set whose size grows exponentially with the number of subsystems. As already mentioned in Section 1.2.3, Problem (2.6) constitutes a dynamic optimization problem with mixed integer variables (MINQP). Moreover, the predition model (2.6b) requires the knowledge of (2.4c), describing the effect of possible coupling between subsystems belonging to different coalitions. As previously motivated, one of the goals here is to avoid such communication requirement. Next, we present a hierarchical multiagent control algorithm with lower computational and communicational requirements, though a suboptimal solution is provided. 2.4 The control algorithm The architecture of the proposed approximation of Problem (2.6) is organized over two layers: the top layer takes charge of the choice of the network mode, whereas the bottom layer handles the estimation and the real-time control tasks. At the bottom layer, the control is decentralized into the coalitions arising from the optimal—according to (2.6)—partition S∗ P. With the term decentralized we designate the absence of communication among different coalitions; agents within a coalition share their information 28 Chapter 2. Supervised coalition structure generation at each sample time. Coalitions still communicate with the supervisor whenever required for the choice of a new topology. As a consequence, the term ωiin (2.6b), modeling the effect of neighboring coalitions, cannot be computed through (2.4c) and (2.4d), and coalitions may need to use an estimate ˆωi. Issues related with such estimation are case-related. For instance, as shown in the example in Section 2.5, inter-coalition coupling can be viewed as a constant perturbation (so that suitable estimation techniques can be used) if it shows relatively slow dynamics and transient phenomena can be neglected. Next, details are given about the operation of the top layer. The discrete part of Problem (2.6) regards the choice of the optimal controller topology. This constitutes the most computationally demanding part of the problem. For this reason it is handled at the top layer, and its solution can be computed on a coarser time frame (w.r.t. the sample time Tsrequired for the low-level control of the system), maintaining the resulting topology during the subsequent interval TE≥Ts. In order to select the most appropriate global control structure, several network topologies are compared. Let E+={E1,E2,...,ENE}be the set of candidate topologies. These are evaluated through the function J:Rn×(N × N )7→ Rdefined as follows [9]: J(ξ, E) = X i∈SP ξ| iPiξi+TEχi(Ci),(2.7) for each E ∈ E+.Pi=P| i>0, derived as the solution of (2.8) described in the following, and χi(coali)expresses the cost of coordinating the members of Ci, considered over the interval TE. In the following, It is not pragmatic to see E+as the set containing every possible configuration of links. Because the number of all possible topologies grows exponentially with the number of subsystems, the set E+should be defined as a reasonably sized set of relevant topologies for the system to be controlled. The composition of E+may either be static or evolving in relation with, e.g., the current state of the system, the network constraints, or the willingness to cooperate among the agents. Of all the configurations considered at a given moment, the one providing the minimum value of (2.7), denoted as E∗∈E+, is applied during the subsequent interval TE. According to any given topology E, the set of agents is partitioned into a given set of coalitions P(N,G(k)) = {C1,C2,...,CNc}. To attain the optimal performance objective (2.5), a feedback gain Kfor the whole system is computed at the top layer. In conformity with the partition P(N,G(k)),Kwill be composed of a set of decentralized feedback gains, each one associated to a coalition, i.e., K= diag(K1,...,KNc).2Given 2For the grand coalition, the feedback law Kwill coincide with the LQR gain. 2.4. The control algorithm 29 the block-diagonal matrix P= diag(P1,...,PNc)>0, consider the Lyapunov function V(ξ) = ξ|Pξ, where ξ,(ξi)i∈SPis the global state vector, permuted according to the partition P.V(ξ)will constitute an upper bound of the infinite-horizon performance objective if the constraints of the following LMI problem are satisfied (see, e.g., [68]): max K,PTr P−1(2.8a) s.t. P=P|>0,(2.8b) (A+BK)|P(A+BK)−P≤ −Q−K|RK,(2.8c) where Aand Bare respectively the global state and input matrices, rearranged to match ξand ν,(νi)i∈SP. Similarly, Q= diag(Qi)i∈SP≥0and R= diag(Ri)i∈SP>0 are the global weighting matrices. By the solution of (2.8), a set of feedback control laws νi=Kiξithat minimize V(ξ)is obtained for all Ci∈P, along with the set of associated matrices {Pi}i∈SP. These matrices are then used at the bottom layer in the formulation of the “local” MPC controller associated to each coalition. The set of matrices {Pi}i∈SPis used to determine the cost-to-go associated to a given topology in the computation of (2.7). Remark 2.1. The evaluation of different network topologies is independent and can be executed in parallel on a multi-processor platform. Also, the set of control laws associated with any network topology can be stored and reused whenever the same topology is considered again, without the need of solving more than once the relative LMI problem. Next, two study cases are used to illustrate the deployment of a top-down coalitional architecture. The first one is an irrigation canal application (Section 2.5), where the objective is to keep at a minimum the need for information exchange between sensors and actuators located at different reaches. The second case study regards the formation of coalitions among prosumers in a power microgrid (Section 2.6): there the objective is to enable local energy transfers, allowing the grid users to access energy at more competitive prices. From the grid operator’s standpoint, such a scheme allows to prioritize the satisfaction of demand with locally available resources, thus reducing long-distance transfer losses over the distribution lines. 36 Chapter 2. Supervised coalition structure generation s.t. ξi(t+ 1|k) = Aiiξi(t|k) + Biiυi(t|k) + Dp iρi(k) + Dw iˆωi(k),(2.14b) and (2.6c)–(2.6g). Since coalition Cihas no knowledge of the states and inputs of external subsystems, an estimate ˆωiof the perturbation they cause on ξiis performed at each time step k, and its value is assumed constant along the prediction horizon in (2.14b). Details are given in Section 2.5.4. Remark 2.2. In typical canal operation, the offtake planning is typically made in advance, and the perturbation ρi(k+t)can be known for the entire prediction horizon. In this example, however, forecasts are not considered, so as to simulate an “on-demand” operation. Therefore, a constant value of the offtake flow, corresponding to the current measure, is maintained along the horizon. 2.5.4 The control algorithm The hierarchical multi-agent architecture introduced in this chapter is proposed as an approximation of problem (2.14), with the intent of reducing the computational and communicational requirements of (2.14). Hence, problem (2.14) is split into two layers: a top layer, taking charge of the choice of the network mode (see Section 2.4), and a bottom layer handling the estimation and the real-time control tasks. A conceptual diagram of the resulting coalitional MPC strategy is shown in Figure 2.3. Figure 2.3: Functional diagram of the hierarchical coalitional MPC architecture applied to the irrigation canal case. 2.5. Illustrative case I: Coalitional MPC control of an irrigation canal 37 Top layer The discrete part of Problem (2.14), namely the topology optimization, is computed on a coarse time scale at the top layer. A set E+={E1,E2,...,ENE}of candidate network topologies are compared, by defining their value as J:Rn× N × N 7→ R(see also [82]): J(ξ,E) = X i∈SP ζ| iPiζi+cl|E|TE,E ∈ E+,(2.15) where Pi=P| i>0,|E| is the number of enabled links and clis the cost of use of one link, considered over the interval TE. In this particular case, at a given time k, the set of topologies candidate for the interval [k+Ts, k +TE]is formed by considering the topologies derived by switching the current state of (at most) one of the links.4 To compute the value of (2.15), Problem (2.8) is solved and the block-diagonal matrix P= diag(Pi)i∈SP, defining a global Lyapunov function V(ξ,E∗) = ξ|Pξfor the (unconstrained) system is obtained. Of all the topologies considered, the one giving the minimum value of (2.15), denoted as E∗∈E+, will be applied during the next interval TE. As a consequence of the chosen cooperation graph G(k)=(N,E∗), the set of agents is partitioned into a specific set of coalitions P(E∗) = {C1,C2,...,C|Nc|}. To each coalition is associated the feedback law υi=Kiξi, obtained as the minimizer of V(ξ,E∗)by the solution of Problem (2.8). Bottom layer As schematized in Figure 2.3, the control is decentralized at the bottom layer into the coalitions arising from the partition P(E∗), whose choice is carried out at the top layer. Agents within the same coalition share their information at each sample time k. The term ωiis related with the water demand in neighboring coalitions. Every coalition gets an estimate ˆωiby a local Kalman filter, based on the available measures of water level errors and current offtake flows. Given the slow dynamics of the system and the steady nature of the offtake flows, transient dynamics can be neglected. Remark 2.3. In general, inter-pool transient dynamics are not negligible. However, (i) the system examined in the case study is inherently stable, and (ii) local flow controllers are present at each gate. If the response of these local control loops is sufficiently fast, the interaction between two adjacent pools reduces to a one-way perturbation [76]. Therefore, ˆωiis viewed as a constant integrating disturbance, included in the model by an augmented state vector. Then, implementing a standard offset-free scheme for 4The new topology will be active starting from the next sample time. 38 Chapter 2. Supervised coalition structure generation regulation [83], the agents steer their subsystems to an appropriate setpoint in order to compensate for both the estimated disturbance and the offset caused by the measurable offtake flows. Notice that any offset due to mismatches between the linear model and the actual system will be also included in ˆωi. The Kalman filter also serves as an observer for the values of water flows. For any coalition Ci, the setpoint (¯ ξi,¯υi)is obtained by the solution of the linear system:   I−Aii −Bii Γi0   ¯ ξi ¯υi =  Dp iρi(k) + Dw iˆωi(k) 0 (2.16) where Γiis an output matrix defined such that Γiξi= (ej)j∈Ci, i.e., the water level deviations of all the subsystems in coalition Ci. Because of the estimation of ˆωi, the setpoint computed through (2.16) is expected to change at each time step. Note that when the topology is changed the Kalman filters structure changes as well, according to the composition of the new set of coalitions. To avoid undesired drifts on the computed value of the setpoint, a good initial guess of the state and the covariance matrix is needed for each new coalition’s local filter. Past data, communicated by the members of the coalition, can be used to initialize the Kalman filter. The setpoint obtained by (2.16) may not satisfy the constraints. Therefore, Problem (2.17)—featuring the slack variable σiin the equality constraint—is solved to obtain the nearest feasible setpoint (ξs i, υs i)to (¯ ξi,¯υi) min ξs i,υs i,σi (υs i−¯υi)|Ri(υs i−¯υi) + ξs i |Qiξs i+σ| iGiσi(2.17a) s.t. (I−Aii)ξs i−Biiυs i−σi=Dp iρi(k) + Dw iˆωi(k)(2.17b) Hiξs i>0(2.17c) Ki(ξi(k)−ξs i) + υs i∈ Ui.(2.17d) In (2.17), the input reference ¯υiis the one obtained from (2.16); Qiand Riare the submatrices relative to coalition Ci(the same used for the optimal performance specification in the top layer); Gi>0is a constant weighting matrix, whose value has been chosen such that the magnitude of the term σ| iGiσiin (2.17) is comparable with the rest of the cost function. Hard constraints are imposed on the water flows with (2.17c): the product Hiξs iis the vector composed of the flow values at each section of any reach controlled by coalition Ci. From the solution of Problem (2.8) (top layer) and Problem (2.17), the follow- 2.5. Illustrative case I: Coalitional MPC control of an irrigation canal 39 ing controller is available for each coalition to regulate the subsystems to the desired setpoint: υi(k) = Kiζi(k) + υs i(k),(2.18) where the shifted state is redefined as ζi=ξi−ξs i. However, feasibility cannot be guaranteed with (2.18). Thus, the value given by (2.18) is “rectified” through the solution of MPC problem (2.21), obtaining an additional input term: υi(k) = Kiζi(k) + υs i(k) + υ0 i(k).(2.19) Possible issues related with the loss of feasibility are dealt with by considering physical limits on the water flows as soft constraints. Restrictions on the input change rate are formulated as hard constraints. By redefining the shifted input as νi=υi−υs i, the cost function of the MPC problem solved at the bottom layer is derived from (2.13a) as follows: J0 i= Np−1 X t=0 ζ| i(t|k)Qiζi(t|k) + ν| i(t|k)Riνi(t|k) +ζ| i(Np|k)Piζi(Np|k) + Np X t=1 | i(t)Sii(t)(2.20) where Si>0is a constant weighting matrix for the slack variable i, used to relax the constraints on the flows. The optimization problem to be solved by coalition Ciat each time step kis: min υ0 i,i J0 i(ζi(k), νi)(2.21a) s.t. ζi(t+ 1|k)=(Aii +BiiKi)ζi(t|k) + Biiυ0 i(t|k)(2.21b) Hiζi(t|k) + ξs i(k)+i(t)>0,∀t∈[0, Np](2.21c) Kiζi(t|k) + υ0 i(t|k) + υs i(k)∈ Ui,∀t∈[0, Np](2.21d) ζi(0|k) = ξi(k)−ξs i(k)(2.21e) where the product Hi(ζi+ξs i) = Hiξigives the vector composed of the stacked water flows at each section of any reach considered within coalition Ci. A description of the proposed algorithm is provided below. Algorithm 2.1. Coalitional MPC 40 Chapter 2. Supervised coalition structure generation Step 1. Prepare a set E+of suitable network topologies to be evaluated for their use during the next interval TE, defined as a multiple of the sampling time at the bottom layer. Step 2. For each E ∈ E+compute K(E)and P(E). Step 3. For each E ∈ E+, estimate the steady-state effect due to neighbor coalitions as: ˆωi(k) = X j∈Mi Aij ˆ ξs j+Bij ˆυs j,∀i∈ SP, where each pair (ˆ ξs j,ˆυs j)is the most updated setpoint available from coalition Cj. Step 4. For each E ∈ E+, solve (2.16) to obtain the setpoints (¯ ξi(k),¯υi(k)),∀i∈ SP, using the value of ˆωi(k)computed at Step 3. Step 5. Compute an estimate of the global cost with (2.7) and pick the network mode E∗that would give the minimum cost. Step 6. Communicate each local feedback law Ki(E∗)and Pi(E∗)to the corresponding coalition. Step 7. Each coalition computes a setpoint (ξs i(k), υs i(k)) by solving (2.16) and (2.17). Step 8. Each coalition solves (2.21) for υ0 i(k), and the control action (2.19) is applied to the subsystems in coalition Ci. Step 9. By means of the local Kalman filter, each coalition obtains the estimate ˆωi(k+ 1) ≡ˆωi(k+ 1|k)to be used during the following time step. Step 10. Repeat Steps 7–9 during the interval TE, then go to Step 1. 2.5.5 Simulation model A detailed simulation of the physics of the west main canal of the Dez irrigation network has been performed using the SOBEK modeling suite for water systems. Based on the WL|Delft Hydraulics implicit finite difference scheme [75], this software package is currently developed at the Deltares research institute in the Netherlands. Design parameters have been specified in order to accurately reproduce the canal dynamics: path, cross-sections, layout of the canal network, type and width of gate, crest levels 2.5. Illustrative case I: Coalitional MPC control of an irrigation canal 41 and discharge coefficients, upstream and downstream boundary conditions. All the necessary information about the geometry of the canal and the hydraulic structures has been obtained from the water authority of Khuzestan province. The boundary condition at the head gate is a constant water level at its upstream side, while its maximum discharge capacity is 157 m3/s. The model has been calibrated and validated using real data relative to six months of operation [84], and has been further employed in [79, 85]. 2.5.6 Identification of the control model The parameters of the ID model for the 13 reaches have been identified through simulations on the SOBEK validated model, and are given in Table 2.1. The transport delay and the average storage area have been characterized while considering the canal at steady state with an input amounting to 80% of the maximum inflow, and all the offtakes at 80% of the maximum discharge capacity. The values in Table 2.1 refer to the canal in this operational conditions. An additional identification of the model parameters has been carried out for a medium discharge setting, namely 50% of the maximum inflow and 50% of the maximum offtake. Since the parameters have demonstrated little sensitivity to the change in the discharge regime, the dependence of the parameters on the flow has been neglected. Furthermore, the implementation of an offset-free method, together with the inherent robustness of the MPC, contributes to the compensation of model-plant mismatches. The values in Table 2.1 have been used throughout the scenarios presented in the next section. 2.5.7 Results Two scenarios are analyzed in the following, reflecting the canal operation at medium– high discharge regimes. In the first one, the water levels and flows are initially settled for the supply of constant nonzero offtakes along the canal until four of the reaches undergo a step decrease in their offtake flows, 360 minutes past the beginning of the simulation (k= 72). The same situation is considered in the second scenario, with the addition of a second step change—360 minutes after the first one (k= 144)—restoring the offtakes to their former values. The variation of the offtake flows amounts to 10 m3/s at reaches 4 and 13, and to 5 m3/s at reaches 9 and 10, ranging from 20% to 100% of their initial magnitude. The simulation is meant to test the performance of the proposed control scheme in rejecting the simultaneous changes in the offtakes, keeping the water level at each reach around its corresponding reference. The exchange 42 Chapter 2. Supervised coalition structure generation Reach Length [m] Width (bottom) [m] Backwater surface (·105) [m2] Delay steps 16219 12 0.9318 3 21933 12 1.0952 1 33718 10 0.8554 2 43906 10 3.7060 2 52934 5 1.7095 2 64670 5 0.7786 3 73110 5 0.6661 2 82240 5 0.8904 1 93405 5 0.8671 2 10 3820 5 0.4897 2 11 2520 4 0.4032 2 12 2874 4 0.3820 2 13 2468 5 0.3884 2 Table 2.1: Parameters of the first 13 reaches of the west main Dez canal, identified at 80% of the maximum discharge rate. Symbol Description Value NpPrediction horizon 10 NcControl horizon 3 QiWeight on the errors 250 RiWeight on the flow increments 2800 SiWeight on flows <0(soft constr.) 104 c`Cost of an active link 0.6 TcSampling time [s] 300 Table 2.2: Parameters of the controller. of information between different agents is enabled by the chosen network topology, according to how the dynamic coupling between the reaches evolves with time (see Section 2.5.4). In the simulations, the state of only one of the links is allowed to change between any two subsequent choices of topology. Hard constraints are imposed on the water flow increment at each gate, |∆qi(k)| ≤ 1m3/s. Constraints on the direction of the water flows, i.e., qi(k)>0, are imposed as soft constraints. Table 2.2 lists the values of the controller’s parameters used for both scenarios. These values have been tuned by trial and error, balancing the performance improvement with the computational requirements (an initial guess for matrices Qiand Rihas been obtained following the inverse-variance weighting method). The plots in Figure 2.4 refer to Scenario 1. In the upper plot, the evolution of water level errors is shown. It can be 2.5. Illustrative case I: Coalitional MPC control of an irrigation canal 43 seen how the sudden decrease in the offtake flows at time k= 72 causes the water levels to rise above the desired setpoint, reaching in some pools a peak of 0.5 m. In the bottom plot of Figure 2.4, bold segments indicate active links between the corresponding agents. The agents in charge of the first four upstream reaches act jointly when the disturbance occurs. This coordination allow to minimize the perturbation on reach 3 (and consequently on reach 2 and 1) due to the recovery maneuver of the agent in charge of reach 4. During the transient response of the local flow controllers, the sudden variation of the offtake flows produces an immediate perturbation in downstream direction. Therefore, in order to improve the performance of the overall system, the agents are organized into bigger coalitions while the effect of the offtakes’ variation is perceived. As the disturbance is rejected, the data links are disabled and most of the agents continue to control their reaches in a decentralized way. It can be seen that the coalition among upstream agents is profitable and thus does not eventually disappear. One reason to this might be the fact that, in the system under study, an accurate decentralized estimation of neighbor’s state is not possible, and water levels at upstream reaches tend to deviate from the setpoint as soon as their agents stop to communicate. This may suggest that in an optimal partition of the overall system the upstream agents would be part of the same coalition. Figure 2.5 shows the inflows qi(k)to the reaches. Starting from time k= 72, the flows are reduced in response to the decreased offtakes in order to bring the water levels back to their setpoints. The results relative to Scenario 2 are shown in Figure 2.6. Before the offtakes variation at time k= 72, the network topology changes to a decentralized configuration while the water levels are kept at their setpoints. When the decrease in the offtakes occurs, the system reacts by reducing the inflows (Fig. 2.7), while data links are enabled in order to coordinate the operations along the canal. At time k= 144 the offtake flows are restored, which is matched with an increase in the input flows. As the error in the water levels is attenuated, downstream data links are disabled. Notice in the last part of the simulation the persistence of the coalition among the upstream agents, and also the coalition formed by agents 5 and 6, since the water level in reach 5 does not converge to its setpoint. It can be seen in Figures 2.5 and 2.7 that the constraints on the water flows are satisfied in both scenarios. Moreover, even without taking into account any offtake forecast, the results achieved with the proposed distributed control scheme are within the admitted range of canal operation. For comparison, the performance of a centralized MPC controller in the same scenarios is shown in Figures 2.8 and 2.9. The centralized control law is computed as 44 Chapter 2. Supervised coalition structure generation Coal. (·103)Centr. (·103) Scn. 1 c`= 0 5.62 2.06 c`= 0.610.44 14.06 Scn. 2 c`= 0 9.36 3.89 c`= 0.614.80 15.89 Table 2.3: Comparison of the average costs of the proposed coalitional scheme and centralized MPC for the two scenarios. n◦dec. var. n◦coal. Scn. 1 5.6 8.2 Scn. 2 6.3 7.6 Centr. MPC 39 1 Table 2.4: Average number of decision variables for the decentralized MPC controllers at the bottom layer, relative to both scenarios. in (2.19), using the same parameters of Table 2.2 (except for the cost of active links, which is null). The centralized controller can coordinate the response of the entire canal to provide a faster reaction to the disturbance, which yields about 30% reduction in the level error peaks.5As expected, due to the absence of network topology switching with centralized control, a smoother response of the system is obtained. Table 2.3 displays a comparison of the average control costs of the coalitional and centralized MPC schemes, for both scenarios. In Figure 2.10 the accumulated costs relative to Scenario 1 are represented, evidencing the impact of communication-related costs in a centralized framework. The average number of decision variables for the decentralized MPC problems solved by the coalitions at the bottom layer is shown in Table 2.4, along with the average number of coalitions. 5An exception to this is the water level in reach 13, as no further downstream reaches can be employed to improve its response (the water discharge at the downstream gate in reach 13 cannot be manipulated by the controller). 2.5. Illustrative case I: Coalitional MPC control of an irrigation canal 45 0 50 100 150 200 250 −0.2 0 0.2 0.4 0.6 Water level errors [m] Time steps Reach 1 Reach 2 Reach 3 Reach 4 Reach 5 Reach 6 Reach 7 Reach 8 Reach 9 Reach 10 Reach 11 Reach 12 Reach 13 0 50 100 150 200 250 1 2 3 4 5 6 7 8 9 10 11 12 13 Time steps Agents Figure 2.4: Scenario 1: At k= 72 reaches 4, 9, 10 and 13 undergo a step decrease in the offtake flows. The upper plot shows how the controller regulates the water level errors along the canal. Each bold segment in the bottom plot represents an active data link between two control agents. Starting from a centralized configuration, links are deactivated one at a time until the variation in the offtakes is sensed. Then links are enabled to form coalitions among the most concerned control agents, until the disturbance is eventually rejected. 52 Chapter 2. Supervised coalition structure generation Figure 2.11: We consider a set of nodes connected to the main grid, equipped as well with local generation and storage devices. These prosumers can establish a local energy market by aggregating into coalitions, so as to minimize the cost of buying energy from the main grid. Power losses over the distribution lines are added to the incurred costs. As a result of the application of the coalitional control algorithm, nodes associate according to variations in the local demand and supply, as well as to changes in the energy prices. The figure shows the energy balance at each node. Figure 2.12: Reciprocal location of the 8 prosumers considered in the example: the distance between rows of houses is 0.5 km. This distance is taken into account for the losses in the distribution lines resulting from the local energy transfer. 2.6. Illustrative case II: Microgrid 53 Table 2.5: List of symbols employed in the description of the example. Symbol Description Unit ¯ dDemand [kWh] ¯pGeneration output [kWh] dgrid Energy bought from the grid [kWh] pgrid Energy sold to the grid [kWh] cgrid Grid spot price [CU] vgrid Feed-in tariff [CU] dcoal Energy bought from the coalition [kWh] pcoal Energy sold to the coalition [kWh] ccoal Coalition spot price [CU] vcoal Coalition feed-in tariff [CU] sState of charge of the storage [kWh] ∆sIncrement in the storage level [kWh] local demand and production, as well as to the changes in the energy prices. Let us consider first the case in which the consumer nodes only rely on the main grid. For any node i∈ N , the energy exchange with the main grid is quantified by the variable xgrid i, representing the difference ¯ di−¯pibetween local demand and generation. Whenever xgrid i>0, node ibuys energy dgrid i=xgrid ifrom the grid—to fulfill the residual demand that cannot be matched by its local production—at the spot price cgrid i. In case of local energy surplus instead, that is xgrid i<0, node ican sell energy pgrid ito the grid at the feed-in tariff vgrid i. We assume that both generation and demand profiles are deterministic, known beforehand within a 5-hour horizon. We also assume that the tariff scheme implemented by utility companies is always such that cgrid i(k)> vgrid i(k). The local availability of a storage device allows the agent some flexibility when facing the spot prices imposed by the grid: the purchase and the sale of energy can be shifted in order to benefit from more convenient prices. At this point, the control problem individually addressed by each node would be (symbols are defined in Table 2.5) min ui Np−1 X t=0 cgrid i(t|k)dgrid i(t|k)−vgrid i(t|k)pgrid i(t|k),(2.22a) s.t. si(t+ 1|k) = si(t|k)+∆si(t|k),(2.22b) ¯ di(t|k)+∆si(t|k) + pgrid i(t|k) = ¯pi(t|k) + dgrid i(t|k),(2.22c) dgrid i(t|k), pgrid i(t|k)≥0,(2.22d) si(t|k)∈[0, si,max], t = 0, . . . , Np,(2.22e) 54 Chapter 2. Supervised coalition structure generation si(0|k) = si(k).(2.22f) The manipulable inputs are ui,[∆s| i,d| i,p| i]|, where the bold notation indicates a vector containing the values along the prediction horizon. The monetary amount expressed by (2.22a) is the local balance of the energy exchange with the grid. Since the problem is formulated as a minimization, a positive balance indicates the expense required to buy energy from the grid, whereas a negative balance is the revenue from feeding energy to the grid. Constraints (2.22b)–(2.22f) represent, respectively, the dynamics of the storage, the energy balance at the node, the admitted values of inputs and storage level, and the initial state of charge. Problem (2.22) is now modified taking into account the possibility for two or more nodes to agree over mutual exchange of energy, establishing a common pool of resources. The local variable xcoal i,dcoal i−pcoal i, whose components are the demand of energy to the coalition and the energy transferred to its members, describes such exchange. The objective function of the coalitional problem involves a component for the minimization of the costs of energy exchange with the main grid, and an additional component concerning the minimization of power losses due to transfers between members of the coalition. min ν,Cρcoal X i,j∈C Np−1 X t=0 rij xcoal ij (t|k) 2!2 +X i∈C Np−1 X t=0 cgrid i(t|k)dgrid i(t|k)−vgrid i(t|k)pgrid i(t|k), (2.23a) s.t. si(t+ 1|k) = si(t|k)+∆si(t|k), i ∈ C (2.23b) ¯ di(t|k)+∆si(t|k) + pgrid i(t|k) + pcoal i(t|k) = ¯pi(t|k) + dgrid i(t|k) + dcoal i(t|k), i ∈ C, (2.23c) X i∈C pcoal i(t|k) = X i∈C dcoal i(t|k),(2.23d) dgrid i(t|k), pgrid i(t|k)≥0, i ∈ C,(2.23e) si(t|k)∈[0, si,max], t = 0, . . . , Np, i ∈ C (2.23f) si(0|k) = si(k), i ∈ C,(2.23g) C ⊆ N ,(2.23h) where xcoal ij is the interchange of energy among the pair of agents i, j ∈ C, and rij is their relative Euclidean distance. The coalitional energy transfer dcoal i−pcoal iis taken into account in the balance constraints (2.23c). Constraint (2.23d) expresses the zero 2.6. Illustrative case II: Microgrid 55 sum energy balance of the coalition. Given its complexity, problem (2.23) is approximated here by splitting it in two subproblems, each one concerning one of the two components of the objective function. So, for any C ⊆ N , the first subproblem is formulated as: min νJ=X i∈C Np−1 X t=0 cgrid i(t|k)dgrid i(t|k)−vgrid i(t|k)pgrid i(t|k),(2.24) subject to (2.23b)–(2.23g). The resulting energy transfers are accompanied by energy losses over the distribution lines. An approximation of their value is added to Jas Jχ=ρcoalˆrX i∈C (dcoal i)2,(2.25) where ˆris a representative mean distance between every pair of coalition members, and dcoal iis the energy demanded to the coalition by agent i. Finally, the value v(C) of any given coalition C ⊆ N (recall that v: 2N7→ Ris the function mapping any possible coalition of agents into a real value) is defined as v(C),J+Jχ, where (2.25) represents the cost of forming the coalition. Now, the second subproblem consists in finding the partition P={C1,...,CNc}of Nsuch that the preference of every agent is satisfied according to the Pareto order. In order to do this, individual payoffs within each possible subset of agents S ⊆ N are first calculated as those defined by the Shapley value φS:R2|S| 7→ R|S|. Thus, for i∈ S: φS i(v) = X C⊆S\{i} |C|!(|S| − |C| − 1)! |S|![v(C ∪ {i})−v(C)].(2.26) Note how the marginal contribution v(C ∪{i})−v(C)is weighted by the probability for any agent iof joining the coalition C ⊆ S \ {i}, in case the agents form the coalition S in a random order: in this way, the value assigned by Shapley’s criterion corresponds to the individual expected marginal contribution. Once this step is accomplished, a mapping Φ : N ×2N7→ Rof the individual payoff for each possible coalition the agent i∈ N can participate in is available. At time step k,Φ(i, C, k)defines the cost (or the benefit) incurred by agent iby participating in the coalition C ⊆ N . Note that such payoff will coincide with the cost of energy exchange with the main grid (Φ(i, {i}, k)≡cgrid i(k)dgrid i(k)−vgrid i(k)pgrid i(k)) in case the agent does not participate in any coalition. On the other hand, if the agent is member of a coalition, the equivalent price payed/earned on the coalition’s internal market can be 56 Chapter 2. Supervised coalition structure generation Time [h] 8 10 12 14 16 18 20 22 24 Demand [kW] 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5Node 1 Node 2 Node 3 Node 4 Node 5 Node 6 Node 7 Node 8 Figure 2.13: Daily demand patterns considered in the simulations for the 8 nodes. derived as: ceq i(k),Φ(i, C, k) xgrid i(k) + xcoal i(k)"CU kWh#,(2.27) where CU stands for currency unit. Such mapping provides each agent with a preference order over the coalitions he wishes to join. Since any agent can be in one coalition at a time (coalitions do not overlap), the agents will organize themselves into a partition P∗following the preference order dictated by Φ. 2.6.2 Results The demand and generation patterns considered in the simulation are depicted in Figures 2.13 and 2.14. Grid spot prices are shown in Figure 2.15, relative to the purchase (top) and feed-in (bottom). The interval 7 a.m.–24 p.m. is considered in the simulations. A time step of 1 h and a prediction horizon Np= 5 h are employed in the optimization problem. We assume the possibility for each node to access the grid with different prices, to emulate the presence of multiple utility companies. Notice that this means that coalitions do not merely consist of a combination of nodes with a surplus of power and nodes that are in need of additional power to meet their demand. 2.6. Illustrative case II: Microgrid 57 Time [h] 8 10 12 14 16 18 20 22 24 Production [kW] 0 0.2 0.4 0.6 0.8 1 1.2 1.4 Node 1 Node 2 Node 3 Node 4 Node 5 Node 6 Node 7 Node 8 Figure 2.14: Generation profiles considered in the simulations for the 8 nodes. Time [h] 8 10 12 14 16 18 20 22 24 Grid pricing [CU/kWh] 0.03 0.04 0.05 0.06 0.07 0.08 0.09 Node 1 Node 2 Node 3 Node 4 Node 5 Node 6 Node 7 Node 8 Figure 2.15: Grid spot prices relative to the energy purchase (top) and excess of production sale (bottom). 58 Chapter 2. Supervised coalition structure generation Agent 12345678 Cost [CU] 0 1 2 3 4 Grid only Grid w/ storage ρ = 5e-3 ρ = 5e-4 ρ = 1e-4 ρ = 1e-5 Figure 2.16: Comparison of the accumulated costs incurred by each agent during the entire simulated interval, over different scenarios: Grid only no coalitions, no storage; Grid w/ storage local storage available; 10−5≤ρcoal ≤5·10−3coalitions with different costs for power losses. The choice over which coalition to form is made on performances predicted over an horizon Npof several time steps. In particular, the aggregate performance is evaluated, and predictions are not required to be favorable at all time steps. However, nodes can change their affiliation at each time step. This may lead to the accumulation of monetary losses. This phenomenon becomes more visible as the penalty for energy losses ρcoal increases, since it implies less stability of coalitions in time. Indeed, nodes can make agreements to get access to the main grid through the more advantageous tariff of another node. The evolution of the coalitions, under different penalties ρcoal for energy losses, is shown in Figure 2.17. By recomputing the mapping Φ(i, ·, k), agents can reconsider their affiliation at each time step. When costs for local energy transfers are significant, coalitions typically involve a restricted number of neighboring agents. On the other hand, big cooperating clusters form when penalties for power losses are low. The costs incurred by the agents for the whole simulated interval are shown in Figure 2.16. As expected, internal transfers’ power losses affects the final result. The high costs for agents 6 and 8 with ρcoal = 10−5can be ascribed to the fact that they are mostly left out of coalitions, as can be seen in Figure 2.17d. Furthermore, recall that the payoff mapping, and thus the decision whether to join a coalition, is based on a forecast along the horizon Np= 5 h (see (2.24)). However, since agents are allowed to join/leave coalitions every time step, possible monetary losses taking place in the short term may accumulate (this issue is pointed out in [49] as well). The realizations of the equivalent prices during the simulations are shown in 2.6. Illustrative case II: Microgrid 59 Time [h] 8 10 12 14 16 18 20 22 24 Agents 1 2 3 4 5 6 7 8 (a) ρcoal = 5 ·10−3 Time [h] 8 10 12 14 16 18 20 22 24 Agents 1 2 3 4 5 6 7 8 (b) ρcoal = 5 ·10−4 Time [h] 8 10 12 14 16 18 20 22 24 Agents 1 2 3 4 5 6 7 8 (c) ρcoal = 10−4 Time [h] 8 10 12 14 16 18 20 22 24 Agents 1 2 3 4 5 6 7 8 (d) ρcoal = 10−5 Figure 2.17: Evolution of the coalitions among the nodes, under different penalties ρcoal for energy losses. Nodes marked with the same color belong to the same coalition. Agents are allowed to reevaluate their affiliation at each time step, by updating the preference mapping Φ(i, ·, k). When costs for local energy transfers are significant, coalitions typically involve a restricted number of neighboring agents. Conversely, big cooperating clusters form when penalties for power losses are low. 60 Chapter 2. Supervised coalition structure generation Table 2.6: Comparison of the average prices (in [CU/kWh]) paid by each agent. The figures in the third column are the equivalent average prices relative to the coalitions’ internal market. See how, in reference to the tariffs in Figure 2.15, both buyers and sellers are benefited by the local energy market. Demand can be satisfied at prices lower than those offered by the main grid, and supply gets better value on the local market. Agent Grid only Grid only Coalitions no storage w/ storage (ρ= 10−5) 1 0.0817 0.0787 0.0784 2 0.0813 0.0795 0.0603 3 0.0810 0.0782 0.0653 4 0.0812 0.0784 0.0620 5 0.0822 0.0797 0.0714 6 0.0805 0.0784 0.0745 7 0.0810 0.0776 0.0620 8 0.0810 0.0786 0.0798 Table 2.6. Comparing the average prices resulting by the coalitions’ internal market with the grid tariffs in Figure 2.15, it is clear that the Shapley allocation benefits both buyers and sellers. Buyers can access energy at prices more affordable than those offered by the main grid, while sellers can achieve a higher profit on the local market. In conclusion, local energy trade has been induced among consumers within a small geographical areas through the implementation of a coalitional control scheme. Power losses over the distribution lines can be taken into account in the coalition formation mechanism. Naturally, the larger the number of agents participating in such scheme, the higher the chance to match demand and supply among them, resulting in a higher profitability of the coalitions. Chapter 3 Autonomous coalition formation 3.1 Introduction Major challenges in control are in dealing with the increasing heterogeneity of networked systems—possibly characterized by decentralized management, a certain degree of autonomy of the parts and dynamic structure reconfiguration possibilities [88]. In such setting selfish interests may assume a dominant role, significantly influencing the way systems are managed, and their resulting performance. This issue is especially evident in public infrastructures, often co-owned by independent entities, and whose management requires a trade-off among sectors in direct competition [2, 15]. This constitutes an impulse to new approaches to distributed control problems, where the cooperation between networked controllers is actively fostered and adapted in real-time to the state of the system, by characterizing the improvement provided by a broader feedback information [89, 90]. Methods for the analysis of the relevance of the agents and data links involved in the distributed control of a complex network system have been recently studied by [91, 27, 26]. The structural information about the system provided by these methods allows the available control resources to be efficiently allocated, promoting sparsity in order to minimize computational and communicational requirements [92]. A step further is the online identification of the optimal controller structure: besides accommodating the controller requirements in real-time [93], such flexibility grants the possibility of reconfiguring the system for improving robustness or fault-tolerance [94], or even for featuring plug-and-play capabilities [95]. The notion of cooperating sets of 61 68 Chapter 3. Autonomous coalition formation coalitional structure. From now on, the term player may refer to either a single control agent or a group of agents that, as a consequence of their participation in the same coalition, act as a single entity. In order to keep the notation simple, indices {1,2}will be used to designate the parties of the bargaining process for the formation of a (bigger) coalition;3 furthermore, the notation {1∪2}will refer to their merger. The subsystems involved in either part of a given bargaining process are identified by the sets P1∈P(N,G(k)) and P2∈P(N,G(k)) \ P1. The set of merging subsystems will be designated as P1∪2,P1∪ P2. Following the notation introduced in Section 3.2.2, the states and inputs of every subsystem taking part in the bargaining process are gathered into the player’s state and input vectors, defined as ξi,(xi)j∈Pi,νi,(uj)j∈Pi, where ξi∈Rni,ni=Pj∈Pinj and υi∈Rqi,qi=Pj∈Piqj,i∈ {1,2}. Finally, the merger state and input vectors are composed as ξ1∪2= (ξ1, ξ2),ν1∪2= (ν1, ν2). Next, the objective is to establish a possible criterion for endogenous coalition formation, oriented at dynamically-coupled networks of systems, featuring the redistribution of the benefits derived from cooperation. Starting from a discussion of the performance improvement offered by cooperative control, viewed as coalitional benefit, we point out the issues of the absence of redistribution of such benefit from the individual control agent’s standpoint. Then, we propose a solution based on the equal division of the benefit between the players. 3.3.1 Evaluation of coalitional benefit As mentioned earlier, the structure of each agent’s MPC controller is allowed to evolve according to the time-variant coupling conditions of the system. Such evolution is the outcome of a bargaining procedure over the formation of a coalition between any two players. The bargaining is based on an index accounting for both control performance and cooperation-related costs: Ji= Nb X t=0 `i(t|k) + Nbχi(k), i ∈ {1,2,1∪2}.(3.9) The first term evaluates the stage cost (3.7) associated with either the merger or the individual players’ over a bargaining horizon of length Nb. Since we assume the agents free to switch their membership between coalitions at any given time step (coalition is 3The case of split will be considered later in this document. 3.3. Coalitional control 69 not binding for the entire horizon length Np), the possible outcomes of the bargaining procedure can be evaluated over a shorter time slot, i.e., Nb≤Np. In the second term, χi(k) = f(|Pi|,|Ei(k)|)expresses the cooperation costs for coalition Pi—assumed comparable with the stage cost (3.7)—where Ei(k)⊆ E(k)is the subset of edges of the graph G(N,E(k)) connecting the nodes in Pi. Notice that for i∈ {1,2}the costs expressed by χiinvolve only player iinternal connections. The predicted state and input sequences used in the computation of (3.9) are obtained as solution of the MPC problem (1.9) for the three possible cost functions associated to i∈ {1,2,1∪2}, where `i(t|k)is the stage cost (see Section 3.2.3) predicted on the basis of the knowledge available within either set of agents Piif i∈ {1,2}or, in case of merger, the joint knowledge provided by P1∪ P2. 3.3.2 Joint benefit through cooperation A necessary condition for the coalition P1∪ P2to form is that its predicted cost (3.9) outperforms the aggregate cost resulting from unilateral strategies: J1∪2≤J1+J2.(3.10) Remark 3.2. Any new coalition will be product of the union of two players, and thus of all agents they involve. The present approach is based on the performance of the player as a whole and not on that of its individual components. This approximation avoids the combinatorial explosion of the possible configurations that would arise otherwise. Local performance concerns are addressed later in this document. Example 3.1. The procedure presented so far is illustrated on a simple example, which will be utilized to set the point for further discussion as well. Consider a pair of agents controlling two input-coupled unidimensional linear systems whose dynamics conform to (3.1). In particular, the state trajectory xi∈Rof the ith system responds to xi(k+ 1) = Aiixi(k) + Biiui(k) + Bijuj(k),(3.11) for i, j ∈ {1,2},i6=j.A11 =A22 = 0.99,B11 = 0.2,B12 = 0.4,B21 = 0.15 and B22 = 0.3; weights are chosen as Qi= 1 and Ri= 10,i∈ {1,2}. Inputs are constrained to the interval Ui= [−0.2,0.2]. The matrices relative to the merger correspond to A1∪2= diag(A11, A22),B1∪2= [Bij]i,j∈{1,2}, and Q1∪2= diag({Qi}), R1∪2= diag({Ri}),i∈ {1,2}. Cooperation costs are considered null. We assume that both agents base their decisions over the unilateral strategies on 70 Chapter 3. Autonomous coalition formation Table 3.1: Example 3.1. Expected and actual costs. J1J2J1+J2J1∪2 ˆuj←minmax 25.200 24.579 49.779 48.975 ˆuj= 0 24.405 24.284 48.689 48.975 actual 24.992 24.432 49.424 48.975 the worst-case MPC cost, with prediction horizon Np= 1. Hence, the performance of the merger (i= 1∪2) is evaluated through the solution of (1.9), whereas the following problem is solved for i∈ {1,2}in order to evaluate the expected performance of the unilateral strategies. min uimax uj Np−1 X t=0 `i(t|k) + `f i(Np|k), j ∈ {1,2}\{i},(3.12a) s.t. xi(t+ 1|k) = Aiixi(t|k) + Biiui(t|k) + Bijuj(t|k),(3.12b) ui(t|k)∈ Ui, t = 0, . . . , Np−1,(3.12c) uj(t|k)∈ Uj, t = 0, . . . , Np−1,(3.12d) xi(0|k) = xi(k).(3.12e) The figures in Table 3.1 are obtained from an initial condition x0= (5,−5). The first row reports the expected values, whereas the last row the costs actually achieved by implementing the control inputs relative to each strategy. Since condition (3.10) is fulfilled for the values in the first row of Table 3.1, the merger is formed. Neglecting other players’ actions is generally not a reasonable option in such coupled systems, since it means completely ignoring their effect—either beneficial or detrimental— on the actual performance of the unilateral strategies. This may lead to mistakenly considering these as the most profitable to implement. For instance, the second row of Table 3.1 shows that condition (3.10) is not verified and the merger is rejected. At this point, it is clear that useful predictions can only be achieved if some knowledge about the unilateral strategies is available to both parties. Different techniques can be applied for their estimation (e.g., worst-case predictions, as in the example above): this point, however, goes beyond the scope of the present work. Here, we propose exploiting the knowledge of the interaction model—communicated by the players in order to perform the evaluation of their merger—in the optimization of unilateral 3.3. Coalitional control 71 strategies.4Thus, unilateral strategies (νi,i∈ {1,2}) are evaluated by assuming that the tails of previously obtained input sequences will be applied by the other player. This means solving (1.9) over νi, for i∈ {1,2}, by replacing constraints (3.8b) with ˆ ξ1∪2(t+ 1|k) = A1∪2ˆ ξ1∪2(t|k) + B1∪2,iνi(t|k) +B1∪2,j ˜νj(t|k) + $1∪2(t|k),(3.13a) ˜νj(t|k),ν∗ j(t+ 1|k−1),(3.13b) ˜νj(Np−1|k),0,(3.13c) with j∈ {1,2}\{i}. Then, recalling that ξ1∪2,(ξ1, ξ2), the predicted evolution can be separated into the components corresponding to either player. 3.3.3 Individual rationality So far we have assumed that if an agreement is beneficial for the coalition then it is beneficial for its members too. However, the premise here is that agents are rational and selfish. Let J(j) 1∪2, k+Nb X t=k `(j) 1∪2(t) + Nbχ(j) 1∪2, j ∈ {1,2},(3.14) be the quota relative to player jin the merger cost J1∪2. The stage cost `(j) 1∪2(t)in (3.14) is the component of (3.7) relative to player jwithin the merger (i.e., relative to the state and input trajectories obtained by solving the MPC problem (1.9) for i= 1∪2). The value of χ(j) 1∪2is a proper share of the cooperation costs. Notice that J1∪2=J(1) 1∪2+J(2) 1∪2. It can be verified (by assuming, for simplicity, χ= 0) that J1∪2≤J1+J26=⇒J(j) 1∪2≤Jj,∀j∈ {1,2},(3.15) which can be shown by referring again to the same couple of systems considered in Example 3.1. The components of the merger costs therein are: J(1) 1∪2= 24.271 < J1, J(2) 1∪2= 24.704 J2. Indeed, condition (3.10) is not sufficient to guarantee lower individual costs to both players. On the grounds of individual rationality, a new coalition is formed if and only if a secure benefit can be granted to their future members. In other words, the 4An analogous problem has to be addressed for the correct evaluation of the performance derived from leaving a coalition. This issue is further discussed in Section 3.4.2. 72 Chapter 3. Autonomous coalition formation individual player’s payoff in the merger has to be at least equal to the one obtained through a unilateral strategy. In particular, player jwill accept participating in the merger P1∪P2if and only if the following individual rationality requirement is fulfilled: J(j) 1∪2≤Jj, j ∈ {1,2}.(3.16) Notice that (3.15) can be extended to the individual members of any coalition. Thus, even if cooperation allows the aggregate cost to be decreased, it can indeed be unfavorable for some agents from the point of view of the locally incurred costs. Hence, there is not a straightforward relationship between cooperation and individual rationality—unless some means of transferring the value between (sets of) agents is provided. In Section 3.3.4, starting from the assumption of transferable utility (TU), specific criteria for the bargaining are given to provide the possibility of coalition formation whenever individual rationality does not directly follow condition (3.10) for both players. In Sections 3.4 and 3.5 we get at the individual agent’s level, addressing the redistribution of the value of a coalition among its members. 3.3.4 Transferable utility In the remainder we assume that (3.9) is defined so as to express an economic index. Then, we consider the possibilities opened whenever a value equivalent to the surplus achieved through the merger, i.e., Π = J1+J2−J1∪2,(3.17) can be transferred between the players. The surplus expressed by (3.17) is defined as a positive quantity, representing savings on control-associated costs. Essentially, the recompense has to be valuable for the players, so its nature may vary. For example, it may consist of a monetary amount, or a flow of (shared) resources across the system. In such a scenario it is possible to fulfill condition (3.16) for both players by means of a proper a posteriori redistribution of the utility between the players. We refer to this as a transferable utility (TU) scenario. Here we take a more abstract approach, and aim at reallocating the individual control costs. It is worth emphasizing that such compensation is an a posteriori procedure: first, the bargaining players agree on a given reallocation—based on the expected performance—before incurring the actual control-associated costs; then, these actual 3.3. Coalitional control 73 costs are balanced out on the basis of the prior agreement.5 Remark 3.3. Only a prediction of the quantity expressed by (3.17) can be computed in practice: following the outcome of the bargaining, either the realization of the merger performance or that of the unilateral strategies can be measured. Value transfers calculated over expected costs will be eventually converted into feasible ones, based on the actual merger performance. Let pj∈Rdesignate the payoff assigned to agent j∈ Pi,i∈ {1,2}, and pi= Pj∈Pipjdenote the aggregate payoff for a given player. If rational players come to an agreement, they will agree on achieving the largest possible payoff, subject to Pipi= J1∪2. Such joint agreement—referred to as cooperative strategy—will belong to the Pareto front (where no allocation can make a player better off without making another player worse off) [51, 106]. The values achieved with unilateral strategies, i.e., (J1, J2), constitute the disagreement point: players would not accept an aggregate payoff pi= Pj∈Pipjworse than their own disagreement point. It is worth to point out that the following discussion addresses the problem at the level of the pair of bargaining players. The final problem is to find a vector p∈R|P1∪P2|,(pj)j∈P1∪P2,Pjpj=J1∪2, i.e., a reallocation of the control costs such that all agents in the merger are satisfied w.r.t. individual and group (i.e., taking into account the outcome of possible subcoalitions) rationalities. A natural and straightforward solution for the allocation of the surplus between two cooperating entities is the egalitarian redistribution. In particular, we assign to each player an equal share of the surplus Πobtained by the merger, w.r.t. the disagreement point, i.e., pi=Ji−1 2Π.(3.18) Geometrically, the allocation (p∗ 1,p∗ 2)corresponds to the midpoint of the line segment connecting (J1, J1∪2−J1)and (J1∪2−J2, J2): pi=1 2(J1∪2+Ji−Jj),(3.19) for i∈ {1,2}and j∈ {1,2}\{i}.6Since the formation of any coalition is conditional on the subadditivity requirement (3.10), an efficient and individually rational allocation is guaranteed to exist for the two-player case: Π>0if (3.10) is strictly satisfied, and 5Analogous to an a priori compensation can be considered, e.g., the distributed MPC scheme proposed in [43] where, on the basis of situational altruism criteria, the cost incurred by each controller is dynamically adjusted so as to fulfill minimum local requirements. 6Notice that (3.19) coincides with the Shapley value formula for a two-player game. 74 Chapter 3. Autonomous coalition formation the allocation computed through (3.19) always fulfills the following condition p∗ i< J∗ i,∀i∈ {1,2},(3.20) which corresponds to the individual rationality property for the player.7It is easy to see that the cost allocated over each player depends on the difference between the expected performances of unilateral strategies (centered about a half of the merger cost), and Ji> Jj=⇒pi>pj, i, j ∈ {1,2}, j 6=i. Finally, consider the situation prior to the utility transfer. Let ˇ J(i) 1∪2be the cost actually incurred by player i∈ {1,2}within the merger. Note that Piˇ J(i) 1∪2=ˇ J1∪2. The expected payoff (4.6) is used to derive the quota of each player in the realization of the compound cost J1∪2: once the merger performance is measured, feasible payoffs are defined by assigning to each player a share pi/J1∪2of ˇ J1∪2 pi=pi J1∪2 ˇ J1∪2, i ∈ {1,2}.(3.21) Now consider the quantity pi−ˇ J(i) 1∪2, i.e., the gap between the feasible payoff (3.21) and the cost the player actually incurs. Recall that by efficiency of the allocation, we have Ppi=J1∪2. Also, by definition Piˇ J(i) 1∪2=ˇ J1∪2. By subtracting these two equalities we have pi−ˇ J(i) 1∪2=−hpj−ˇ J(j) 1∪2i, i, j ∈ {1,2}, j 6=i(3.22) revealing that one of the players is excessively benefited—according to the surplus distribution dictated by (4.6)—following its participation in the coalition, whereas the other player experiences the opposite situation. Thus, we can define a unique value for the gap ,|pi−ˇ J(i) 1∪2|. By the transferable utility assumption, we aim at compensating this gap in order to incentivize the formation of a coalition between individually rational players. The cost distribution dictated by (3.21) can be established by transferring a value τTU = from one player to the other, i.e., J(1) 1∪2±τTU =p1and J(2) 1∪2∓τTU =p2. Example 3.2. Consider the system defined in Example 3.1. The payoffs obtained by applying (4.6) are displayed in Table 3.2. The costs incurred by the players are shown in the first column of Table 3.2. The gap amounts to = 0.496 (predicted 0.527), meaning that player 2 is penalized—prior to any value transfer—by participating in the coalition 7Recall that here we refer the term individual to the entire player coalition. 3.4. Bargaining procedure 75 Table 3.2: Example 3.2. Individual costs with merging and unilateral strategies. J(i) 1∪2piJi P1 predicted 24.271 24.798 25.200 actual 24.271 24.767 24.992 P2 predicted 24.704 24.177 24.579 actual 24.704 24.208 24.432 with player 1. Therefore, player 1 compensates player 2 by a transfer τTU =. Final perceived costs are shown in the second column of Table 3.2. Costs incurred through unilateral strategies are shown for comparison in the last column. So far, we have presented the TU framework for two-player bargaining, without explicitly dealing with the case |Pi|>1, i.e., with the redistribution of a player’s payoff over the multiple agents composing its corresponding coalition. Next, we address the coalition structure evolution due to the autonomous coalition formation within the whole set of agents whenever |N| >2. 3.4 Bargaining procedure All players in pairs will perform, at given time intervals, a one-shot bargaining whose outcome will decide the generation of new coalitions. At each round, all players available for bargaining have to be paired. It is worth to remark that the way the pairs are selected may influence the final outcome of the coalition formation process [107]. 3.4.1 Coalition formation At time k, let the global set of agents N={1, . . . , N}be partitioned into Nc∈ {2, . . . , N}coalitions as defined by P(N,G(k)) = {C1,...,CNc}. A pair of coalitions P1,P2∈P(N,G(k)) is randomly selected. This procedure is performed over the remaining coalitions until all possible pairs of players are selected.8It may occur that the total number of coalitions Ncavailable for bargaining is not even: in this case, the unpaired coalition will not participate in the bargaining (i.e., it will skip the round). Assumption 3.2. The bargaining is carried on simultaneously by all players. Each pair of bargaining players assumes that no further coalitions are being formed or disrupted among the rest of players. 8Different methods can be employed, e.g., favoring big (or small) coalitions. 76 Chapter 3. Autonomous coalition formation Therefore, when evaluating the possible formation of coalition P1∪ P2, each pair assumes that the rest of agents remain organized as they were at the previous time step. Each pair of players verifies (3.10) before stipulating the agreement, following Assumption 3.2 in the computation of (1.9). This means that potential changes of configuration concerning subsystems external to P1∪ P2are not taken into account on the estimate of the unknown coupling ˆωi. As pointed out at the end of Section 3.3.2, in order to correctly ponder the outcome of unilateral strategies, tails of previous input sequence are used in the bargaining. In case the merger yielding (p1,p2)is approved, an initial payoff is assigned to each agent j∈ Pi,i∈ {1,2}, by equally splitting pj: pj=1 |Pi|J1∪2, j ∈ Pi,(3.23) Notice that the payoff allocation given by (3.23) is not necessarily stable in the coalitional sense: some agents may estimate more profitable to leave (or modify) the current agreement. Requests for utility transfer within P1∪ P2are checked over a number Ns of randomly sampled subsets Cr⊂ P1∪P2,r∈ {1, . . . , Ns}. If some subset Crof agents is dissatisfied with the initial allocation, the iterative utility transfer scheme described in Section 3.5 is performed in order to adjust (if possible) the allocation according to their request. 3.4.2 Coalition disruption While any coalition is formed through a bilateral agreement, an agent can leave it unilaterally. If for a given pair the bargaining does not result into a merger, the possibility of some subset of agents wanting to leave coalition Pi,i={1,2}, is checked. The same is done when the current configuration corresponds to the grand coalition as well, in that case the only (unpaired) player available. Remark 3.4. In cooperative game theory, the coalition is viewed as a binding agreement. In this work, the agreement is not binding over the prediction horizon. In order to adapt to the time-varying system state, agents are free to change their affiliation at any time step. More specifically, over each one of the selected players, (i)a subset of agents C ⊂ Pi is randomly chosen and (ii)the conditions for the unilateral exit of either Cor its complementary subset Pi\ C are checked. Keeping the same notation as before, we refer to the above subsets of Piby the indices {1,2}. In particular, we define S1=C, 3.4. Bargaining procedure 77 and S2=Pi\ C. The whole coalition Piwill be designated by {1∪2}. Either of the above subsets will want to leave the coalition if condition (3.20) is not fulfilled. Consider, for instance, the case where J1<p1: in order to reestablish the individual rationality of p1, it may be possible to reallocate part of the benefit from S2. However, since the agents in S2have the option of leaving the coalition and achieve an expected payoff p2=J2, they will not accept to get past this value (the disagreement point, as defined in Section 3.3.4). Hence, if J(1) 1∪2−J1>−(J(2) 1∪2−J2),Piwill split into two coalitions S1and S2. As with merging, the process is simultaneous over all players, so it is assumed that the exit of one or more members of a coalition does not affect the decisions of other agents. The split of Piwould result in a modification of the coalition structure (and of the associated communication graph) such that Piis replaced in P(N,G(k+ 1)) by S1and S2. Once the new coalitions are formed, the payoff allocation among the members of Si,i∈ {1,2}is updated so that Pj∈Sipj=pi=Ji. This is done as in (3.23). After the initial allocation is set, requests for utility transfer within Si,i∈ {1,2}are checked over a random sample of subsets Cr⊂ Si,r∈ {1, . . . , Ns}. If some subset Cris found dissatisfied with the initial allocation, the iterative utility transfer scheme described in Section 3.5 is performed on the player Si⊃ Cr. In contrast, if J(1) 1∪2−J1≤ −(J(2) 1∪2−J2),(3.24) it is possible for S2to compensate the dissatisfaction while maintaining some benefit in participating in the coalition Pi=S1∪ S2. The utility transfer protocol aimed at achieving a stable allocation of the coalitional benefit is discussed in the following section. Remark 3.5. Notice that either the randomly chosen Cor Pi\C might not be included among the allowed coalitions (for instance, they might not be significant due to the topology of the system9). Given a feasible C, then the complementary subset may consist of several feasible coalitions. If this is the case, the procedure described in this section does not change, except the above conditions are verified for each of these coalitions. Remark 3.6. As for coalition formation, the veracity of the unilateral strategies used to evaluate the possible exit from a coalition is critically important. However, in this case previous input sequence result from a joint optimization. For this reason, they are not useful for correctly pondering the outcome of coalition split as done in (3.13). Therefore, problem (1.9) is solved over several iterations—with constraints (3.13) re- 9One such example is considered in Section 3.6. 84 Chapter 3. Autonomous coalition formation where xi,[∆θi,∆ωi,∆Pmi,∆Pvi]∈R4,ui= ∆ ¯ Pi∈R, and ∆di∈Ris the variation in the demand (symbols are defined in Table 3.3).12 The last term in (3.37) describes the influence of coupled areas, identified in the set Mi={j∈ N \ {i}| Aij 6=0}. Matrices are composed as Aii =          0 1 0 0 −Pj∈MiP0 ij 2Hi−ρfi 2Hi 1 2Hi0 0 0 −1 τti 1 τti 0−1 rviτgi0−1 τgi          Bi=          0 0 0 1 τgi          Aij =          0 0 0 0 P0 ij 2Hi0 0 0 0 0 0 0 0 0 0 0          Di=        0 −1 2Hi 0 0         . (3.38) For reasons of space, the values of the parameters are not reported here (the reader is referred to [109]). The coupling of the generation frequency between areas connected through transmission lines appears in the second row of Aii and Aij. Inter-area power transfers are modeled as ∆Pij =P0 ij(∆θi−∆θj), i, j ∈ N ,(3.39) where positive values indicate a transfer from area ito area j. Classic discretization yields non-sparse structures, unless very small sampling steps are employed [1]. In order to preserve the topology of the system in the discrete-time model’s structure, avoiding the dependence on the sampling time, the continuoustime model (3.37) is discretized following the method of [110], with Ts= 1s. More specifically, by treating uias an exogenous input along with ∆diand xj, the inputdecoupled structure of the continuous-time model is replicated in discrete time. Notice that the use of such a method is reasonable in this kind of framework, where one basic assumption is that system-wide knowledge of the model is not likely to be achieved (besides communication constraints, one further reason is the dependence of the time constants characterizing the linear model on the current setpoints [90]). From now on, any mention of the above matrices will refer to the discrete-time model. 12The load is assumed not sensitive to frequency variation. 3.6. Illustrative case III: wide-area control of power grid 85 Time [s] 0 10 20 30 40 50 60 - ∆P -- ∆p [p.u.] -0.3 -0.25 -0.2 -0.15 -0.1 -0.05 0 0.05 0.1 0.15 Area 1 Area 2 Area 3 Area 4 Area 5 ccoal = 1e-3 Time [s] 0 10 20 30 40 50 60 - ∆P -- ∆p [p.u.] -0.25 -0.2 -0.15 -0.1 -0.05 0 0.05 0.1 0.15 Area 1 Area 2 Area 3 Area 4 Area 5 ccoal = 5e-4 Figure 3.2: Scenario 2: the capacity of local generation is impaired, making energy transfers from neighboring areas necessary for demand satisfaction. Variation of the demand (dashed lines) and local power generation in the 5 areas. In the left plot, relative to ccoal = 10−3, the lack of supply in Area 3 due to a 10% capacity drop w.r.t the demand value, is supplemented with energy transfers from Areas 4 and 5. Similarly, the right plot, corresponding to ccoal = 5·10−4, shows that Area 3 receives additional supply from Areas 2 and 5 (see Fig. 3.4). Power setpoints are computed with the RTO (3.41). 3.6.2 Controller design It can be inferred from (3.39) that large energy transfers are caused by large differences in the angle deviation. The minimization of the energy transferred between connected areas can be implicitly addressed by penalizing large values of ∆θi; additionally, measures available from cooperating nodes can be exploited by penalizing the angle difference between the members of a given coalition. Therefore, the state weighting matrices in the objective function are chosen as Qii = diag(qθ ii +X j∈Mi qθ ij +qθ ji, qω ii, qPm ii , qPv ii ), Qij = diag(−X j∈Mi qθ ij +qθ ji,0,0,0),(3.40) where Qij ∈Rni×njis the submatrix of Q∈Rn×nrelative to the coupling between nodes iand j. For noncooperative control, qij =qji = 0; the rest of the values are defined as in [109], i.e., Qii = diag(500,0.01,0.01,10) and Ri= 10,∀i∈ N. In case of cooperation, we set qij =qji = 1000. 86 Chapter 3. Autonomous coalition formation Table 3.4: Constraints on local generation. ku1k∞≤ ku2k∞≤ ku3k∞≤ ku4k∞≤ ku5k∞≤ S1 0.2310 0.1680 0.1050 0.0840 0.1050 S2 0.3465 0.1512 0.0945 0.1260 0.0945 We test the capability of the coalitional controller based on autonomous coalition formation in achieving ∆ωi→0,∀i∈ N in presence of step variations in the load ∆di at any i∈ N. Two scenarios are considered: in the first, local production capacity is sufficient for locally matching any demand, and the objective is to track the reference (¯x, ¯u), computed as a function of the change in the grid load. Since each area’s load must be matched with the local production, the components of the setpoint vector are defined as ¯xi= [0,0,∆di,∆di],¯ui= ∆di, corresponding to the increment in the energy generation required to balance an increase in the demand. In the second scenario the capacity of local generation is impaired, making energy transfers from neighboring areas necessary for demand satisfaction (see Table 3.4). These transfers are described by the coalitional setpoints optimized by an RTO layer min νr i,ξr i Np−1 X t=0 kνr i(t|k)−¯νi(t|k)k2 Ri +  ξr i(t+ 1|k)−¯ ξi(t+ 1|k)   2 Qi (3.41a) s.t. ξi(t+ 1|k)(I−Aii)−Biiνi(t|k) = Diδi(t|k),(3.41b) 1|νi(t|k) = 1|δi(t|k),(3.41c) νi(t|k)∈Ψi, t = 0, . . . , Np−1,(3.41d) X r Prj(∆θr−∆θj) = (∆dj−umax j)+, j∈ Ci,∀r∈ Mj∩ Ci,(3.41e) δ(t|k) = ˆ δi(k+t), t = 0, . . . , Np−1,(3.41f) where νr i,[νr i(k), . . . , νr i(k+Np−1)] is the input setpoint along the horizon Npfor Ci, and ξr i,[ξr i(k+1), . . . , ξr i(k+Np)] is the associated state reference. In the steadystate condition (3.41b), δi,(∆dj)j∈Ciis the demand vector relative to all members of the coalition; (3.41c) defines the demand-supply equilibrium within a coalition, i.e., it is equivalent to Pj∈Ci∆¯ Pj=Pj∈Ci∆dj. Weighting matrices in (3.41a) are defined as Qi= diag(Qii)and Ri= diag(Rii), with Qii = (10,0,100,100) and Rii = 100. The setpoint (νr i, ξr i)≡(¯xi,¯ui)is assigned to singleton coalitions, since power transfers 3.6. Illustrative case III: wide-area control of power grid 87 cannot be arranged for them. At each time step, the procedure described in Section 3.4 is followed to evaluate the possible formation of coalitions, and then Problem (1.9) is solved independently by each resulting coalition to derive the control inputs ν∗ i(k)allowing the generation side of the grid to follow the reference (ur, xr). Cooperation costs are assumed increasing with the coalition size, χ=ccoal|C|2, for |C| ≥ 2. The prediction and bargaining (see (3.9)) horizons length is set to Np=Nb= 5. Following [111], the terminal cost in (3.8a) is chosen as `f i(Np|k) = (ξi(k)−¯ ξi)|Qf i(ξi(k)−¯ ξi),(3.42) where Qf i= 20Qi. 3.6.3 Results In order to evaluate the variation of the controller performance over different degrees of cooperation, two indices are defined. The first is the average overall frequency deviation, η(ω) = 1 Tsim Tsim X t=1 X i∈N ∆ω2 i,(3.43) and the second reflects the energy transferred between areas, ψ(θ) = Tsim X t=1 X i∈N X j∈Mi k∆Pij(t)Tsk2,(3.44) where ∆Pij is defined in (3.39), and Tsis the sampling time. These indices provide a measure of the global performance not dependent of the particular evolution of the coalition structure. One instance of the evolving coalitional structure in Scenario 1 is represented in Fig. 3.3: notice that following the grid topology, coalitions are allowed only between interconnected areas. Similarly, results with the second scenario are shown in Fig. 3.4. One example of the energy supply provided by coalitional control in the second scenario is shown in Fig. 3.2. In this case, the supply capacity in Area 3 is not always sufficient to fulfill the local demand; meanwhile, generators in Area 5 cannot decrease their production to match the lowest local demand level, so the excess of production is transferred to other areas. As can be seen in Figure 3.2, the lack of supply capacity is covered by neighboring generators. Figures 3.5 and 3.6 gather the results of a set of 200 simulations for the two scenarios, showing the performance for different values of ccoal. Coalition formation is 88 Chapter 3. Autonomous coalition formation Time [s] 5 10 15 20 25 30 35 40 45 50 55 60 Agents 1 2 3 4 5 [1e-3] Time [s] 5 10 15 20 25 30 35 40 45 50 55 60 Agents 1 2 3 4 5 [5e-4] Time [s] 5 10 15 20 25 30 35 40 45 50 55 60 Agents 1 2 3 4 5 [1e-4] Time [s] 5 10 15 20 25 30 35 40 45 50 55 60 Agents 1 2 3 4 5 [1e-5] Figure 3.3: Scenario 1: production capacity is sufficient for locally matching any demand. Formation of coalitions for different values of ccoal. Costs of cooperation are increasing with the coalition size, i.e., χ=ccoal|C|2, for |C| ≥ 2. 3.6. Illustrative case III: wide-area control of power grid 89 Time [s] 5 10 15 20 25 30 35 40 45 50 55 60 Agents 1 2 3 4 5 [1e-3] Time [s] 5 10 15 20 25 30 35 40 45 50 55 60 Agents 1 2 3 4 5 [5e-4] Time [s] 5 10 15 20 25 30 35 40 45 50 55 60 Agents 1 2 3 4 5 [1e-4] Time [s] 5 10 15 20 25 30 35 40 45 50 55 60 Agents 1 2 3 4 5 [1e-5] Figure 3.4: Scenario 2: the capacity of local generation is impaired, making energy transfers from neighboring areas necessary for demand satisfaction (see Fig. 3.2). The plots show the evolution of coalitions for different values of ccoal. Costs of cooperation increase with the coalition size, i.e., χ=ccoal|C|2, for |C| ≥ 2. The cooperation in this case follows a more stable pattern. 90 Chapter 3. Autonomous coalition formation η(ω) ×10-6 0.9 1 1.1 1.2 1.3 1.4 1.5 1.6 S1 ccoal 1e-5 1e-4 5e-4 1e-3 S2 1e-5 1e-4 5e-4 1e-3 ψ(θ) ×10-4 2 3 4 5 6 7 8 9 S1 ccoal 1e-5 1e-4 5e-4 1e-3 S2 1e-5 1e-4 5e-4 1e-3 Figure 3.5: Performance index η(ω)(left) and ψ(θ)(right), respectively regarding the minimization of the frequency deviation and of inter-area energy transfers, for increasing values of ccoal. Plots marked with S1 are relative to Scenario 1, while S2 refers to the case in which areas 2, 3 and 5 experience limitations in their power generation. The dotted line marks the performance of the strictly cooperative strategy (centralized MPC), whereas the dashed-dotted line refers to the strictly noncooperative one. See Fig. 3.7 for details on the box representation. Even with scarce cooperation (ccoal = 10−3), the performance improvement over noncooperative control is sensible: indices η(ω)and ψ(θ)are enhanced in Scenario 1 by about 18% and 31%, respectively. In Scenario 2, η(ω)is improved by about 18%; however, power transfers cannot be avoided in this scenario, and the low coordination between areas results in an increase of ψ(θ)by 5%. coal. size 1 1.5 2 2.5 3 3.5 S1 ccoal 1e-5 1e-4 5e-4 1e-3 S2 1e-5 1e-4 5e-4 1e-3 coal. lifetime [time steps] 2 4 6 8 10 12 S1 ccoal 1e-5 1e-4 5e-4 1e-3 S2 1e-5 1e-4 5e-4 1e-3 Figure 3.6: Average size of coalitions (left) and coalition lifetimes (right), for different values of ccoal (costs of cooperation are increasing with the coalition size, i.e., χ=ccoal|C|2). Plots marked with S1 are relative to Scenario 1, while S2 refers to the case in which areas 2, 3 and 5 experience limits on the power generation. See Fig. 3.7 for details on the box representation. 3.6. Illustrative case III: wide-area control of power grid 91 Table 3.5: TU scheme allocation for the grand coalition. Dec. MPC Centr. MPC TU alg. Shapley Area 1 0.424 0.433 0.359 0.353 Area 2 0.365 0.268 0.329 0.333 Area 3 0.136 0.080 0.085 0.085 Area 4 0.057 0.052 0.054 0.052 Area 5 0.143 0.101 0.110 0.112 disincentivized as ccoal is increased, deteriorating the achievable performance. Roughly speaking, the performances of coalitional control fall between those obtained through fully-cooperative (centralized) and noncooperative MPC control. It is interesting to see how, even with a reduced cooperation effort, the performance improvement over the noncooperative control is sensible: with ccoal = 10−3(see top plot in Fig. 3.3), yielding an average coalition size of 1.2, indices η(ω)and ψ(θ)are enhanced by about 18% and 31%, respectively. In Scenario 2, η(ω)is improved by about 18%; however, power transfers cannot be avoided in this scenario, and the low coordination between areas results in an increase of ψ(θ)by 5%. Table 3.5 shows the accumulated control costs for each area, in Scenario 1 (cooperation costs are not included). The allocation produced by the proposed iterative utility transfer algorithm is compared to the Shapley value. In order to better evaluate these two outputs, the agents were not allowed to leave the grand coalition in the simulations relative to Table 3.5. The first two columns show the control costs associated to centralized (fully cooperative) and noncooperative MPC: notice how for Area 1 cooperation implies an increase of the local cost. Individual rationality is achieved for all areas with both allocation methods. The results relative to the iterative transfer algorithm have been obtained with 10 iterations, i.e., the dissatisfaction w.r.t. the assigned allocation has been checked for 10 randomly selected subcoalitions (see Sections 3.4 and 3.5). Instead, the Shapley value required at each time step the evaluation of all possible subcoalitions, in this case 25= 32. These calculations are carried out by the procedure described in Sections 3.3.1 and 3.3.2. Figures 3.7 and 3.8 show the accumulated control costs for the 5 areas, and their corresponding online reallocation, resulting over 200 simulations for the two scenarios. Notice how—particularly in Scenario 1—individual rationality is not always fulfilled when cooperation costs become appreciable. Online reallocation mitigates this issue and provides an incentive for the cooperation (see especially the case of Area 1). 92 Chapter 3. Autonomous coalition formation local cost (Area 1) 0.32 0.34 0.36 0.38 0.4 0.42 0.44 0.46 0.48 0.5 0.52 ccoal 1e-5 1e-4 5e-4 1e-3 TU 1e-5 1e-4 5e-4 1e-3 local cost (Area 2) 0.25 0.3 0.35 0.4 0.45 ccoal 1e-5 1e-4 5e-4 1e-3 TU 1e-5 1e-4 5e-4 1e-3 local cost (Area 3) 0.08 0.1 0.12 0.14 0.16 0.18 ccoal 1e-5 1e-4 5e-4 1e-3 TU 1e-5 1e-4 5e-4 1e-3 local cost (Area 4) 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.11 ccoal 1e-5 1e-4 5e-4 1e-3 TU 1e-5 1e-4 5e-4 1e-3 local cost (Area 5) 0.08 0.1 0.12 0.14 0.16 0.18 0.2 0.22 ccoal 1e-5 1e-4 5e-4 1e-3 TU 1e-5 1e-4 5e-4 1e-3 Figure 3.7: Scenario 1: production capacity is sufficient for locally matching any demand. Cost—involving both control and cooperation—locally incurred by agents, accumulated along the simulated interval. Plots marked with TU show the result of the online reallocation with the proposed algorithm. Box plots gather the results of 200 simulations, for different values of ccoal (costs of cooperation are increasing with the coalition size, i.e., χ=ccoal|C|2, for |C| ≥ 2). As a reference, the costs corresponding to the fully cooperative strategy are denoted by the dotted line, showing the influence of cooperation costs. These—initially equally supported by the agents—are reallocated online with the proposed algorithm, as shown by the dotted line in ‘TU’ plots. The dashed-dotted line refers to the local cost with the noncooperative strategy. Boxes cover the range between the 25th and the 75th percentiles (the central mark is the median), and outliers (data exceeding a distance from the box extremes of 1.5 times the difference between the 25th and the 75th percentiles) are plotted separately. 3.6. Illustrative case III: wide-area control of power grid 93 local cost (Area 1) 0.32 0.34 0.36 0.38 0.4 0.42 0.44 0.46 0.48 ccoal 1e-5 1e-4 5e-4 1e-3 TU 1e-5 1e-4 5e-4 1e-3 local cost (Area 2) 0.2 0.25 0.3 0.35 0.4 0.45 0.5 ccoal 1e-5 1e-4 5e-4 1e-3 TU 1e-5 1e-4 5e-4 1e-3 local cost (Area 3) 0.05 0.1 0.15 0.2 0.25 0.3 ccoal 1e-5 1e-4 5e-4 1e-3 TU 1e-5 1e-4 5e-4 1e-3 local cost (Area 4) 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.11 0.12 0.13 ccoal 1e-5 1e-4 5e-4 1e-3 TU 1e-5 1e-4 5e-4 1e-3 local cost (Area 5) 0.08 0.1 0.12 0.14 0.16 0.18 0.2 ccoal 1e-5 1e-4 5e-4 1e-3 TU 1e-5 1e-4 5e-4 1e-3 Figure 3.8: Scenario 2: the capacity of local generation is impaired, making energy transfers from neighboring areas necessary for demand satisfaction. Control cost locally incurred by agents, accumulated along the simulated interval. Plots marked with TU show the result of the online cost reallocation with the proposed algorithm. As a reference, the costs corresponding to the fully cooperative strategy are denoted by the dotted line, showing the influence of cooperation costs. These—initially equally supported by the agents—are reallocated online with the proposed algorithm, as shown by the dotted line in ‘TU’ plots. The dashed-dotted line refers to the local cost with the noncooperative strategy. See Fig. 3.7 for details on the box representation. 100 Chapter 4. Coalition formation of fast EV charging stations Table 4.1: Table of symbols EEV max,i EV ibattery capacity [kWh] SoCfSoC after the recharge % SoCocurrent SoC % SoC(i,j)drop in EV iSoC for reaching CS j% pjprice of recharge at CS j[CU/kWh] t(i,j)time for reaching CS j[h] tw jwaiting time at CS j[h] ttol itolerable waiting time for EV i[h] ψicost of time for user i[CU/h] nEV jvehicles in line at CS jnplug jplugs available at CS j- Pmax,j power at CS jplugs [kWh] ¯ EEV average recharge [kWh] on the other, both want to properly allocate the EVs to charging stations according to their interests. The first scenario presented in this study considers four charging stations located in the urban area of Seville, Spain, each owned by a different charging manager. The objective is to study how different pricing strategies affect the economic benefit that each CS can achieve, and how coalitions between CMs influence their performance. The strategy of each CM is optimized on the basis of a simplified model of the behavior of EV drivers looking for fast recharging facilities in response to spot price variations: Ei(k+ 1) = Ei(k) + B∆p(k+ 1) + D¯p(k+ 1) −palt palt Ei(k),(4.3) where ∆p∈R|NCS |×1is defined as ∆p(k+ 1) ,[pi(k+ 1) −pi(k)]i∈NCS , Eiis the total recharged energy supplied at CS i,piis the price per kWh applied for the recharge, palt is the alternative price taken as reference. The parameters of the model are identified over different simulations on the developed microsimulation platform. Two terms compose the model: the first, taking into account the price differences between stations, evaluates the redistribution of the energy over the different CSs; the second expresses the tendency of the demand at decreasing when facing an overall rise of the perceived price, in presence of more competitive alternatives (the opposite holds when perceived price decrease). The manipulated variables are the daily prices (in 4.1. Problem formulation of the case study 101 CU/kWh) applied at the stations for battery recharge, simultaneously made available by all charging managers. The utility of the charging stations owner consists in maximizing its profit, which broadly speaking translates in serving as much EVs as possible while fulfilling the most restrictive constraint between the maximum power deliverable by the stations and the eventual limitations imposed by the grid operator. The next sections describe the formulation of the optimization problem. 4.1.2 Control objective The objective of the control consists in maximizing the station’s revenue derived by the recharging service. The revenue is formulated as Eipi, where Eiis the overall energy supplied by CS i, and piis the applied price per kWh. Notice that not all the revenue will constitute benefits for the CS. In this work, we model general costs for the use of infrastructures—that can be addressed to different aspects related with the energy provision and recharging operations—as a quadratic term depending on the delivered energy volume. Also, recall that each CS has a limited number of available charging plugs: as a byproduct of the optimization, such term will avoid to attract with low prices an excessive number of customers, since the station will not be able to satisfy the demand within a reasonable time slot. Hence, the CS utility is expressed by Ui=Eipi−ciE2 i,(4.4) where ciis a constant parameter associated with the infrastructural availability and supply-associated costs of CS i. Then the objective to maximize for CS iis defined as: Ji(k) = k+Np X t=k Ei(t)pi(t)−ciE2 i(t),(4.5) over the prediction horizon Np. For each station, the value of ciis assumed to be in the order of 10−5CU/kWh2. Prices are considered in the range 0.275 – 0.325 CU/kWh. The steady-state demand distribution across the stations, when all four CSs apply the same price of 0.300 CU/kWh, is E0= (296.63,323.25,264.75,289.88) kWh. Predictions employed for the solution of the problem of profit maximizing are based on the model (4.3), identified over a microsimulated traffic scenario. 102 Chapter 4. Coalition formation of fast EV charging stations 4.2 Description of the applied management strategies 4.2.1 Coalition formation The above setting is expanded by considering the possibility of coalition formation among CMs. The problem consists in deciding with whom to cooperate and under which conditions (namely, the allocation of the payoffs among the members of a coalition). We model such situation as a coalitional game in characteristic form. A coalitional game is uniquely defined by the pair (N, v), where Nis the set of players and vis the value of a given coalition. More specifically, a value is assigned to any possible coalition through a function v: 2N→R. The real value v(C)associated with coalition Ccan be divided and transferred among its members (e.g., side-payments used to attract other players). The payoff φiis defined as the utility received by each agent i∈ C by the division of v(C). The vector of payoffs assigned to all the agents is referred to as the allocation. Notice that such model cannot accurately reproduce the vast majority of real life scenarios. It is natural in engineering applications to encounter problems in which the value of a given coalition cannot be determined regardless of how the rest of the agents are organized. Games in partition form better fit to such type of problems: given a partition of the set of agents N, i.e., a set of disjoint coalitions C={C1,...,Cl}, the value of a coalition Ci∈Cis expressed as v(Ci,C)[54]. Since it is not possible to derive a closed-form allocation in such setting, we approximate the partition function game with a characteristic function game by assigning values to coalitions following a minmax approach. The value of a given coalition will thus take into account the most unfavorable externalities given by any coalitional setup of the rest of agents. Shapley Value In order to compute a division of the coalition value across the coalition members, we consider here the closed-form expression provided by the Shapley value. Shapley defined the conditions to obtain a unique payoff mapping of the game (N, v)[29]. The Shapley value φ(v)satisfies the following three axioms:2 2Further axioms characterize the Shapley value. We mention here the ones related with our purpose. 4.2. Description of the applied management strategies 103 1. Efficiency: X i∈N φi(v) = v(N). 2. Symmetry: given two players iand j, if v(C ∪ {i}) = v(C ∪ {j}),∀C|C ∩ {i, j}=∅, then φi(v) = φj(v). 3. Dummy: if, for any player i, it holds that v(C) = v(C ∪ {i}),∀C|C ∩ {i}=∅, then φi(v) = 0. The symmetry axiom assigns the same payoff to players that equally improve a given coalition, while the dummy axiom assigns a null payoff to a player which does not contribute when joining a coalition. The formulation of the individual payoff assigned to player iaccording to the Shapley value’s mapping is: φi(v) = X C⊆N \{i} |C|!(|N| − |C| − 1)! |N|![v(C ∪ {i})−v(C)] (4.6) In words, the Shapley value expresses the individual expected marginal contribution of agent ito the coalition. Despite the advantage of its closed form, the computational complexity of (4.6) increases significantly with the number of agents: some efficient techniques for its computation can be found in the literature (see, e.g., [128]). The sampling time of 12 h employed in this scenario leaves enough room for the computation; nevertheless, combinatorial explosion needs to be addressed when the number of independent charging stations grows. 4.2.2 Coalitional approach to the EV case study The aim here is to explore the benefit brought in by the cooperative management of the set of CMs. Such benefit can be directly translated into economic units, and then possibly transferred (as recompense) from one agent to another in order to overcome what constrained the emergence of cooperation in the first place. This type of situations is designated in the game theory literature as transferable utility (TU) [51]. 104 Chapter 4. Coalition formation of fast EV charging stations The following mechanism is implemented here for coalition formation. At each round (every 12 h in the simulations), all possible coalitions among CMs are evaluated, and the organization into a given coalitional structure will be decided as the outcome of a best matching algorithm. This operation is carried out on the basis of an increase of individual economic benefit for each agent, derived from the Shapley allocation of the value of the coalition the agent is affiliate with. Remark 4.1. For simplicity of presentation, we assume in the remainder that every CS belonging to a given CM will be involved in the coalition in which the CM participates. Nonetheless, a CM may in general choose to consider within a given coalition the management of only a subset of the CSs he owns. Given the above assumption, any set of CMs C ⊆ NCM straightforwardly maps into a set of CSs C0⊆ NCS, where C0contains all the CSs belonging to the CMs in C. The value of a coalition C ⊆ NCS are computed as the aggregate estimated revenue of the members v(C) = X i∈C Eipi−ciE2 i,(4.7) where the second term models usage and maintenance costs (see (4.4)). As mentioned in Section 4.2.1, the problem is approximated to a characteristic form game by assigning the value resulting by the worst-case scenario for any given coalition. Let pi,(pj)j∈C, and p−i,(pj)j∈NCS \Ci. Both vectors are formed by subsets of components of the global vector p,(pj)j∈NCS . The revenue prediction for CS iresults by the solution of the minmax problem max pimin p−iJi(4.8a) s.t. E(t+ 1) = E(t) + B(p(t+ 1) −p(t)) + D¯ p(t+ 1) −palt palt E(t),(4.8b) E(0) = E(k),(4.8c) X t Ei(t)≤12PCS max,i,(4.8d) p(t+ 1) ∈ U,(4.8e) t={0, . . . , Np −1}, where (4.8b) is the global energy prediction model relating all CS. Note that no limitations by the grid operator are considered in this problem. Once the 2|NCM |−1values for the possible coalitions among the CMs are available, the corresponding members’ 4.3. Technical description of the implementation 105 payoffs can be computed by means of the Shapley value. Notice that for the grand coalition, i.e., C ≡ NCS,p−iis not defined, and the problem reverts to mere minimization. At this point, payoffs are used as input to a best matching algorithm in order to derive the best coalition(s) according to individually rational preference order. Since CMs will accept to form a coalition if and only if it implies a rise in their individual payoff, the algorithm matches CMs such that no player is left unsatisfied. However (due to the nonconvexity of this specific game) a conflict may arise between a pair of CMs when the respective preference orders are misaligned. This conflict are solved by assigning players to coalitions according to the lexicographical order. Let CM 1 and CM 2be two players of the game, and {C(i) A,C(i) B}, with i={1,2}, the possible coalitions that can be joined by CM i. Consider the case where the formation of C(i) A and C(i) Bis mutually exclusive. Then, the following order reflects the preference of CMs {C(1) A,C(2) A}  {C(1) B,C(2) B}iff    φ1(C(1) A)> φ1(C(1) B) or φ1(C(1) A) = φ1(C(1) B) and φ2(C(2) A)≥φ2(C(2) B),(4.9) where φi(C)is the payoff defined by the Shapley value for the participation of player i in coalition C, and is the lexicographical preference operator. Finally, the prices relative to the chosen coalitional structure are applied to the system. The profits derived by the energy sale at CS facilities are shared among all members of the corresponding coalition, according to the Shapley values previously computed. Note that since the Shapley values are based on estimated values, they cannot be directly applied to the realization of the profits. Instead, the ratios dictated by the Shapley’s payoffs over the predicted coalition value are used for the division of the actual profits. 4.3 Technical description of the implementation 4.3.1 Microsimulations The microsimulation platform employed for the macroscopic model identification and validation of coalitional strategies among CMs consists of two interdependent layers): the first layer is implemented on the open source microscopic traffic simulator SUMO [127], the second is implemented in Matlab. The two layers communicate via socket, employing the library TraCI4MATLAB [129] (Figure 4.1). The characterization of urban traffic (vehicle displacements, traffic congestion, velocities in each lane, 106 Chapter 4. Coalition formation of fast EV charging stations Figure 4.1: Implementation of the EV microsimulation platform over two software layers. Vehicle displacement, traffic congestion is modeled in SUMO. Energy management operations and CS choice is performed in the Matlab layer. etc.) is performed in the first layer. Detailed street maps of the urban areas of Seville and Malaga (Spain) have been prepared for the purpose. A population of nv= 10000 vehicles has been considered, including both electrical and conventional automobiles, of which nEV = 400 (Seville) and nEV = 1000 (Malaga) are possible customers of fast charging facilities. The second layer is responsible for the specific management of electric vehicles. Each driver’s decision of when, where and how much energy to recharge is defined at this layer. Other tasks are the modeling of the charging process and the battery discharge along each vehicle’s route. For this, information extracted from the historical data (available from project Zem2All) about battery consumption as a function of the velocity has been employed. The data are relative to a specific brand and model, the Mitsubishi i-MiEV, featuring a 16 kWh battery. A charging curve has also been extracted from the database. Four independent CMs are considered, each characterized by different maintenance/usage cost factors ci. For the Seville scenario, each CM owns one CS equipped with one charging post, capable of providing 50 kW output power. The Malaga scenario contemplates the availability of 60 CSs across the whole urban area, also equipped with a single 50 kW charging post. Remark 4.2. Although 50 kW can be viewed as the “entry level” power capacity for a level 3 charging post, the i-MiEV battery capacity of 16 kWh is fairly small if compared with the capacity of newer EV models. Therefore, the results of the microsimulation presented in the remainder also scale to higher CS power and larger battery capacities. The CS distribution for the two maps is shown in Figures 4.2 and 4.3. 4.4. Validation of the management strategies for the case study 107 X coordinate [m] -2000 0 2000 4000 6000 8000 10000 12000 Y coordinate [m] 0 2000 4000 6000 8000 10000 1 23 4 Figure 4.2: Location of CSs in Seville urban area. Colors show the different CM affiliation. 4.4 Validation of the management strategies for the case study 4.4.1 Scenario parameters Values for the initial battery levels of the vehicles, the discharge rates as a function of the velocity as well as the locations of CSs are provided as initial data for the simulation. Any demand for recharge is triggered when the EV battery reaches a given (low) battery threshold. This threshold is expected to vary from one user to another: in this study, trigger values have been extracted from a probability distribution obtained over the Zem2All benchmark database. Similarly, the final battery level of each charging operation is inferred by real usage data. The first vehicle in line is served at the maximum power of the station Pmax,j = 50 kW. No limits are imposed on the size of the waiting queue. In contrast with common non-electric or hybrid vehicles, the route length is limited by the autonomy of the batteries. Indeed, it is possible for an EV to run a distance greater than that allowed by its autonomy—without long charging stops—if a fast recharge is performed along the route. This is the usage pattern that we aim to 108 Chapter 4. Coalition formation of fast EV charging stations X coordinate [m] ×104 0 0.5 1 1.5 2 Y coordinate [m] 0 2000 4000 6000 8000 10000 12000 14000 16000 1 2 3 4 5 67 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3334 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 Figure 4.3: Location of the 60 CSs in Malaga urban area. Colors show their affiliation to the four CMs. 4.5. Results 109 Figure 4.4: Malaga scenario: charging demand at five CSs sampled at different prices applied at CS 1 (all xaxes refer to CS 1 price). simulate in this study. Studies such as [126] estimate that about 30% of the EV routes will generate fast charging demand (see also [130]). To model this aspect, routes of proper length (25 km in average, according to [130], see deliverable D5.3 for further details) have been defined over the two urban areas, such that most of the nEV drivers need to stop and recharge at least once along their route.3 4.4.2 Macroscopic model identification The sensitivity matrices Band Dhave been identified through a series of simulations capturing the change in the aggregate daily demand to variation of the spot prices applied at CSs. In this particular study, a linearized response has been adjusted over the sampled space by least-square approach. Figure 4.4, relative to the Malaga scenario, shows an example of how the charging demand at five CSs is affected by the variation of the price applied at CS 1 (all xaxes refer to CS 1 price). Notice that the coupling between demands at different CSs is a function of the routes followed by EVs and of the (relative) location of CSs, besides the prices and waiting times. 4.5 Results 4.5.1 Seville Two scenarios are studied for the urban area of Seville, characterized by different maintenance/use costs. We have for scenario (i) c= [20 25 26 2] ·10−5CU/kWh2;(4.10) scenario (ii) is identical except the coefficients for CS1 and CS2 are swapped. 3Since the synthesis of the routes and the initial battery level are extracted from a probability distribution, some EVs can travel their entire route without having to stop. 116 Chapter 4. Coalition formation of fast EV charging stations Figure 4.13: Redistribution of recharges ([MWh]) resulting by the grand coalition of CMs. The values in the yaxis refer to the aggregate demand at all CSs owned by a given CM, over a timespan of 10 days. The plot shows a comparison between the demand resulting by maintaining a fixed price of 0.3 CU/kWh at all CSs (ref. case), and the strategy resulting by the grand coalition. Prices are slightly raised in order to take advantage of the monopoly, so demand is reduced in CSs characterized by high cost-of-use. The outcome is not consistent with CM 4 incurred costs, mainly due to prediction errors resulting by the linearized model: however, revenue redistribution through the Shapley value covers this issue, as shown in Figure 4.16. as shown in Figure 4.16. For the case where no coalition is formed (Figure 4.14) and the case relative to the coalition structure {{1,4},{2,3}} (Figure 4.15), worst-case approach implemented to derive prices leads to competitive strategies, resulting in the same minimal price sequence applied over the considered timespan. Overall demand increases due to the low prices, while the distribution over the CMs facilities remains constant. Interestingly, over the same pricing strategy, the Shapley value provides a reallocation of the revenues towards the CM incurring the highest cost (here CM 4, see Figure 4.16). Finally, Figure 4.17 shows the average profit (total revenue −cost-of-use) over 9 simulated days. The grand coalition provides a net improvement of the profit of CMs, whereas strictly competitive strategies yield a poor economic performance. In average, a daily average profit of 1947.55 CU is achieved with the grand coalition, versus the 1542.46 CU of the strictly competitive strategy. As can be seen in Figure 4.18, this is due to the poor efficiency of the strategy in adapting to the different infrastructural limitations of the CMs. 4.5. Results 117 Figure 4.14: Redistribution of recharges ([MWh]) resulting by the grand coalition of CMs. The values in the yaxis refer to the aggregate demand at all CSs owned by a given CM, over a timespan of 10 days. The worst-case approach implemented yields competitive strategies, resulting in the minimal price sequence possible. Overall demand increases due to the low prices, while the distribution over CMs facilities remains constant. Figure 4.15: Redistribution of recharges ([MWh]) relative to the CM coalition structure {{1,4},{2,3}}. The values in the yaxis refer to the aggregate demand at all CSs owned by a given CM, over a timespan of 10 days. The worst-case approach leads to competitive strategies, resulting in the same minimal price sequence of the no coalition case. Interestingly here, over this same pricing strategy, the Shapley value provides a reallocation of the revenues towards the CM incurring the highest cost (CM 4), as can be seen in Figure 4.16. 118 Chapter 4. Coalition formation of fast EV charging stations (a) Grand coalition (b) {{1,4},{2,3}} Figure 4.16: Benefit redistribution (Shapley value) for the grand coalition and the coalition structure {{1,4},{2,3}}, relative to the Malaga scenario. The plot shows how the revenue is reallocated towards the owners of facilities characterized by the highest costs. Figure 4.17: Average profit over 9 days of simulation (total revenue −cost-of-use). The grand coalition (GC) provides a net improvement of the profit of CMs, whereas strictly competitive strategies (“No GC”) yield a poor economic performance. In average, 1947.55 CU are earned in average with the GC, versus the 1542.46 CU of the strictly competitive strategy. As can be seen in Figure 4.18, this is due to the poor efficiency of the strategy, associated with high costs-of-use w.r.t. the achievable revenue. Notice that the reference case should be viewed just as an initial condition, since the competition between CMs would not allow to keep its associated prices. 4.6. Conclusion 119 Figure 4.18: Ratio of the costs of use over the total revenue. The pricing strategy optimized by the grand coalition (GC) provides a uniform distribution of the costs of use w.r.t. the energy supplied. Moreover, the GC achieves sensible overall reduction of the ratio: 31% in average, versus 38% resulting from the competitive strategies. 4.6 Conclusion The work presented in this chapter is a study of a near future scenario regarding plugin electric vehicles population. Considering the standpoint of the owners of battery recharge infrastructures, the problem of the energy refill pricing is analyzed, involving possible cooperative strategies. The price sensitivity of EV fast charging facilities users has been modeled over a microsimulated scenario representing a finite population of EVs and four independent and selfish CMs. Then, following an approach to incentive coalition formation based on the Shapley value’s allocation, the possibilities offered by the coalitional management of CSs are studied. Results from simulations have shown that a joint planning of pricing strategies allows to increase the profit (about 25%) and the quality of service for the users. Interestingly, the increase in the profit can be mainly attributed to a better management of the charging infrastructure, allowed by the possibility of demand reshaping offered by coalitional strategies. Naturally, for such a framework to be feasible, a more transparent management of charging infrastructures is required. In this work, only on-the-fly recharge operations have been considered. Ongoing work is concerned with the possibility of booking recharge slots in advance. The case study admits further analysis of competition issues (oligopoly), that need to be specifically addressed through computationally-viable tools. Finally, as an important byproduct of this work, the prediction model object of this study could be employed for decentralized routing mechanism that can enhance the quality of service provided 120 Chapter 4. Coalition formation of fast EV charging stations to EV drivers, fulfill grid capacity constraints, or optimize some other specific charging facility’s owner objective function. This currently constitutes a large body of research in the intelligent transportation systems field. 4.7 Acknowledgments The study presented in this chapter has been carried out in collaboration with Ezequiel González Debada and David Cerero Tejero. Chapter 5 Conclusion and outlook As the architecture of multiagent systems becomes more complex—featuring reconfigurable topologies [10, 9, 94, 11], misaligned individual interests [12, 131, 132, 15], human-in-the-loop control [133], plug and play capabilities [58]—the relationship between possible restrictions on the global availability of information and the system performance is increasingly unclear [134]. Some of the challenges and open issues for coalitional control are summarized in the remainder. Criteria for coalition formation How to determine the most appropriate coalitional structure for the overall system is a problem that shows fundamental analogies with model partitioning. Two different perspectives on coalition formation can be considered. The first is a top-down approach, where the global coalitional structure is optimized at a supervisory layer. Of fundamental importance is the criterion used to break the overall system into coalitions. Some possibilities have been already explored, such as the minimization of an index that combines optimal control performance and communication costs [10], or an H∞robustness index—reflecting model-plant mismatches due to nonlinearities or inaccurate identification—as proposed in [21]. To address individual rationality as well, the second consists of a bottom-up approach: here the formation of coalitions is produced as the outcome of an autonomous bargaining procedure. While the first approach may offer some advantages in view of global system stability guarantees, the second appeals as a more appropriate scheme for real-world (plug and play) applications. Information exchange Information plays a fundamental role in the coordination of multiagent systems. Either attained through direct sensing or communication, in- 121 122 Chapter 5. Conclusion and outlook formation is the basis for the local decisions of agents and, as such, decisive to the emergent global behavior [134]. Despite the huge effort dedicated to the development of distributed controllers for large-scale systems, communication has been mainly studied from a transmission perspective, covering issues such as bandwith limitations, data loss, or the effects of noisy channels [135]. The very nature of the information exchange has received little attention. Indeed, in order to allow fundamental properties of centralized control, such as system-wide optimality and stability, the majority of the literature about distributed control overlooked privacy-related issues in order to focus on the overall system performance. Does providing agents with additional information always lead to improvements in the performance? On the other hand, can the excess of information be detrimental under some given system-wide perspectives? These questions have been partially addressed in works such as [134, 34]. In [134], a graph-coloring problem is used as a simple platform for studying the effect of information on multiagent collaboration. Results demonstrate that an increased amount of information is able to improve the efficiency of the Nash equilibria; on the other hand, it degrades the convergence rate of the distributed algorithm, where the agents seek to maximize their utility. Constraints on coalition formation Bigger coalitions provide better control performance at the cost of increasing cooperation requirements. The enforcement of limitations on the composition of coalitions may be necessary. Some limitations can be of direct application (as for example size constraints), whereas others can implicitly derive by the penalization of specific metrics (use of the network infrastructure, identity of the participants, optimization variables, time expected to solve the control problem). In either case, this is a problem that requires attention. See [136] for a detailed analysis about constraints in the coalition formation process. Partial cooperation and information When dealing with systems characterized by a strong heterogeneity, selfish interests may hinder the sharing of knowledge relevant for control purposes and cooperation as well. It is possible that only a subset of the control agents is willing to exchange information about their subsystems. It is therefore necessary to explore the performance bounds of the control loop possibly achievable with partial system information. Similar issues have been already studied in the field of Economics, using tools provided by the game theory. The authors of [34] extend a performance metric introduced by [137]—the competitive ratio—for the purpose of quantifying the distance from the optimum of the distributed solution of an LP problem 123 when the information is locally segmented. From the coalitional control standpoint, it is arguably critical to characterize the improvement provided by a broader knowledge of the system, and promote the formation of coalitions accordingly. Notice that the previous question can be reversed: what is the minimal partition of the system model information necessary to guarantee some performance goal? In order to address this question, the authors of [34] point out that additional metrics need to be formulated in order to allow the characterization of the different partitioning possibilities and the relative minimality notion. Again, possible candidate for such task are already available in the game theory literature about multi-agent decision making under partial information. Performance metrics The development of the coalitional control field requires the definition of key performance indicators, especially those capable of capturing the tradeoff between the information exchanged by the control agents and the performance of the system. For example, in [34] the connection between closed-loop performance and the amount of exchanged information is characterized for distributed linear quadratic controllers. Bounds are provided on the minimal information exchange needed to achieve an improvement over the performance of the best decentralized (communication-less) scheme. By addressing a networked resource allocation problem, the work of [138] identifies how a measure of locality in the individual control laws can be translated into a bound on the overall achievable efficiency. The relationship between the redundancy of information in the control laws implemented by agents and the achievable efficiency of the overall behavior is then characterized, providing bounds on the efficiency of the stable solutions. When full information regarding the mission space is available to the agents, the efficiency of the resulting stable solutions is guaranteed to lie within 50% of the optimal. However, as the reach of the information becomes more limited, the efficiency of the stable solutions may be as low as 1/N of the optimal, where Ndesignates the number of agents. Commitment between cooperating agents Depending on the type of information exchanged and its purpose, it is possible to classify the cooperation in decreasing degrees of subsystems’ integration, ranging from full information (the coalition is formally equivalent to a unique subsystem) to binding to a prearranged output interval, or sharing planned trajectories, interaction models, objectives. Data for different degrees of cooperation can be computed offline and retrieved during system operation, 124 Chapter 5. Conclusion and outlook in order to implement control schemes with varying requirements (from completely decentralized to centralized) on top of the same control infrastructure [8, 10]. This includes the possibility of reserving some backup strategies for the case of communication failure [94]. Theoretical guarantees Classical theoretical properties such as stability or robustness for the closed-loop system are more challenging in this context, specially in the case of bottom-up approaches, where little global information may be available at the individual subsystem level. Coalitional guarantees Research on the novel properties specific of this type of control systems is needed. An example would be the degree of robustness of the coalitions with respect to the external incentives that their members may have for leaving. Combinatorial explosion Another issue is linked with the number of possible structures of the controller under a given data network. Approaching the problem of finding the optimal coalitional structure with exhaustive search can become unviable even for relatively small number of agents, due to the exponential growth of the number of possible coalitions. Constraints on the communication topology and the number of agents in a coalition might help to relieve this issue, since the realization of some configurations would be denied. Alternatively, limitations on the number of links that can be switched during a certain period would reduce the search space and ease the on-line implementation of coalitional control schemes. At this point, the coalitional control framework reveals itself as a wide open field for novel and diverse investigation. In the complex networked systems falling within its scope, information about the relevance of the agents and data links involved in the distributed control problem is of critical importance [27, 26]. Game theory can be useful in this sense. The role of cooperation costs on the outcome of the coalition formation, as well as its relation with control optimality, constitutes an interesting topic for future research. Allocation criteria from game theory may be employed to redistribute the control effort over the agents participating in cooperative tasks [139], or for dynamic model partitioning in a distributed control architecture. Reconfiguration capabilities provided to the controlled system through the evolving coalitional structure are suited for fault-tolerance needs or plug-and-play settings [140]. When only a subset of the control agents is able/willing to exchange information 125 about their subsystems, it might be interesting to investigate the performance bounds of the overall control loop. These questions have been already addressed in fields such as economics and computer science, but remain an open challenge in the framework of dynamical systems control. Privacy-related issues—inherent in SoS—have been generally overlooked in order to focus on the overall system performance or on specific data transmission problems (e.g., limited bandwith, channel noise, data loss). The impact of (partially) restricted knowledge of the global system by local control agents has received relatively little attention [141]. Conversely, by exploiting available real-time data exchange infrastructures, it can be interesting to characterize the improvement provided by a broader knowledge of the system [90], and promote the formation of coalitions accordingly. Incentive mechanisms from game theory can be applied in intelligent transportation systems, for traffic or service demand reshaping [99], also in competing markets like EV charging [119, 100]. Finally, there is still room for the analysis of the coalitions stability (average coalition lifetime), and the associated conditions on benefit redistribution among cooperating controllers [98] (especially if the objective function has an economical meaning), as well as the sufficient conditions for the stability of the system in control theoretic sense, i.e., guarantees of reaching the desired setpoint. 132 Appendix A. Coalitional control and game theory A.4 Bayesian games The Bayesian games framework can be used to model scenarios in which the set of agents may be characterized by several behavior profiles (e.g., some agents might favor cooperation, while others may want to cheat). In particular, an agent does not know in advance the exact behavior that the other agents will apply to a certain situation, although it may know the whole set of possible behaviors. The uncertainty about the characteristics of other players is modeled by introducing a set of possible states, called player’s types, with their associated (guessed) probability of occurrence. Example A.1. In a bargaining situation for the allocation of a given payoff, the information disclosed by the agents (e.g., about the costs of operating their systems) may or may not be truthful, in order to take advantage and receive a greater share of the payoff; in such a case, Bayesian game model can be used to extract a profile of the other agents’ actions.  When choosing the strategy to be implemented next, a player should take into account the probability of occurrence of each of the other players’ types, and thus their possible actions. A.5 Multi-agent learning An important line of research related with game theory is the development of learning algorithms in order to achieve a desired cooperative equilibrium. A learning algorithm is typically composed of three steps: (i) observation of the state of the environment; (ii) estimation of the prospective utility;(iii) update of the strategy [14]. The best response represents the simplest form of such algorithms: at each iteration, every agent applies the strategy which maximizes its utility. However, the outcome of such a scheme is very sensitive to the initial condition. Convergence to an equilibrium is only guaranteed with particular types of utility functions, and the convergence to an efficient equilibrium cannot be ensured [14]. In [14] some relevant categories of advanced learning algorithms are introduced: •Fictitious play: algorithms in this category are based on the estimation of the frequency with which other agents implement a given strategy. On the basis of its estimate, each agent can choose the best strategy. For some type of games (e.g., zero-sum games) this scheme converges to a Nash equilibrium. •Regret matching: this class of algorithms is based on the minimization of the A.6. Coalitional game theory 133 regret from applying a certain strategy, i.e., the difference between the utility of always applying that strategy and the utility achieved by implementing the current strategy. •Reinforcement learning. •Stochastic learning. In order to overcome instability issues due to possible errors (i.e., nonrational strategies) during the learning procedure, these algorithms are commonly designed so that the agents are allowed to choose unintended strategies, so as to perturb the reached equilibrium and seek for any opportunity of improvement. This kind of approach, called learning by experimentation, is receiving significant attention in game theory and multiagent learning, and has shown good performances in communication applications [14]. A.6 Coalitional game theory Cooperative game theory provides means of analyzing the behavior of self-organizing agents that can communicate and decide to cooperate in order to achieve some benefit. Also, cooperative game theory focuses on the design of mechanisms for the cooperation so to guarantee fairness and efficiency. However, since most research has been focused on noncooperative games so far, specialized tools are still needed for the design of such mechanisms, in particular those suited for the dynamical environments naturally encountered in engineering applications. Under cooperative game theory, coalitional games and Nash bargaining provide tools for the analysis of situations in which the agents have to decide with whom to cooperate and under which conditions [14]. Nash bargaining focuses on the negotiation of the conditions for the cooperation within a given coalition (e.g., allocation of the payoffs among the members of a coalition). A coalitional game is uniquely defined by the pair (N, v), where Nis the set of players, and v(C)is the value of a given coalition C ⊆ N in the game. The definition of this value determines the form and the type of the game [48]. The basic category of coalitional games is represented by games in characteristic form, where the value of Cdepends only on the members that compose it, with no regard to how the rest of the agents are organized. In games with transferable utility (TU), a value is assigned to any possible coalition through a function v: 2N→R. The 134 Appendix A. Coalitional control and game theory real value v(C)associated with coalition Ccan be divided and transferred among its members (e.g., side-payments used to attract other players). The payoff piis defined as the utility received by each agent i∈ C after the division of v(C). The vector of payoffs assigned to all the agents is referred to as the allocation. For the members of any given coalition, an allocation is said to be efficient when it is obtained by splitting the entire value of the coalition, i.e., when the following condition holds: Definition A.1 (Efficiency). X i∈C pi=v(C)(A.2) Furthermore, an allocation is said to be individually rational when it satisfies: Definition A.2 (Individual rationality). pi≥v({i}),∀i∈ C (A.3) In other words, individual rationality implies that the payoff offered to any member of a coalition has to be at least equivalent to the payoff that can be achieved by playing independently. An allocation satisfying both (A.2) and (A.3) is designated as imputation [49]. In different cases, the payoff is assigned directly to the members of a coalition, according to given rules (or possible constraints on the division of the utility). The individual payoffs cannot be redistributed (transferred) among the players. Such situations are modeled by coalitional games with nontransferable utility (NTU). Hence, the value of a coalition Cis not expressed by a single real value; instead, v(C)⊆R|C| is aset of allocations, each one relative to a given coalition’s strategy.1 Games in characteristic form allow to model a wide spectrum of scenarios. In engineering applications, however, it is natural to encounter problems in which the value of a given coalition cannot be determined regardless of how the rest of the agents are organized. Games in partition form model such type of problems. Given a partition of the set of agents N, i.e., a set of disjoint coalitions C={C1,...,Cl}, the value of a coalition Ci∈Cis expressed as v(Ci,C)(this value can be either TU or NTU). The two game forms introduced so far do not consider any underlying communication infrastructure among the agents. Indeed, either in characteristic or in partition form, the value of a coalition does not depend on how the agents are connected. Coalitional games in graph form have been introduced to model situations in which the 1The notation |·|denotes the cardinality of a set. A.7. Canonical coalitional games 135 connections between the agents influence the utility that they can achieve. As the name suggests, these connections are modeled by means of a graph (either directed or undirected) whose nodes represent the agents. The value of a coalition v(GC)is thus expressed on the basis of the topology of the edges connecting the agents of C; depending on the scenario, the value v(GC,GN \C)can be a function of how the rest of the agents are connected [48]. A.7 Canonical coalitional games Canonical coalitional games are in characteristic form (TU or NTU). The main feature of games belonging to this category is that cooperation is always beneficial. More specifically, the superadditivity property always holds: v(C1∪ C2)≥v(C1) + v(C2)(A.4) which implies that the members of two disjoint coalitions C1and C2are able to achieve at least the same payoff allocation if participating in the coalition produced by the union C1∪ C2. This, in turn, leads to the formation of the grand coalition, since the payoff allocation that can be obtained from v(N)is at least as good as those obtained through the coalition of any possible subset of agents. Hence, the theory on canonical coalitional games focuses on two main problems: •stability: how to find a payoff allocation guaranteeing that no agent would prefer to leave the grand coalition; •fairness: it can be interpreted as a notion allowing to model the influence of “global goals” on the agents’ behavior. The members of a coalition may care about receiving a payoff that is balanced with the individual contributions (thus, each agent care about both its own payoff and the payoff assigned to the others) [144]. A.8 The core The set of payoff allocations able to guarantee that no agent has an incentive to leave the grand coalition Nto form a coalition C ⊂ N is called the core. In particular, a payoff allocation p≡ {pi}i∈N belonging to the core satisfies the following two conditions2: 2The examples refer to a TU game. For NTU games the definition of the core is similar, although based on the individual payoff instead of their sum. 136 Appendix A. Coalitional control and game theory •Efficiency (budget rationality): P i∈N pi=v(N), i.e., the entire value of the grand coalition has to be shared among its members. •Group rationality:P i∈C pi≥v(C),∀C ⊆ N , i.e., the payoff piobtained by each member of the grand coalition has to be greater (or equal) to the one obtained by acting alone or within a smaller coalition. A payoff allocation pbelonging to the core is said to be stabilizing [49]. The core is not guaranteed to exist for all canonical games. When the core is empty, the grand coalition cannot be stabilized. The existence of the core in a TU game is related to the feasibility of the following LP problem: min pX i∈N pi s.t. X i∈C pi≥v(C),∀C ⊆ N (A.5) Since the growth of the number of constraints in (A.5) is exponential in the number of agents, finding the existence of the core is an NP-complete problem. In practice, however, the search of imputations can be narrowed by considering those of most interest (possibly already known to be fair) in a given scenario. Nonemptiness of the core is assured in convex games. Definition A.3 (Convex game).A TU canonical game is convex if the following condition holds:3 v(C1) + v(C2)≤v(C1∪ C2) + v(C1∩ C2),∀C1,C2⊆ N (A.6) or alternatively, for all i∈ N and any pair of coalitions C1⊆ C2⊆ N such that C1∩ {i}=C2∩ {i}=∅, v(C1∪ {i})−v(C1)≤v(C2∪ {i})−v(C2)(A.7) Definition (A.7) relates the convexity of the game to the marginal contribution of each agent i: in a convex game, the marginal contribution of any agent iis nondecreasing w.r.t. set inclusion (i.e., the size of the coalition it joins). In other words, a game is convex if an agent’s marginal contribution increases if it joins a larger coalition [145]. However, convexity is a strong condition, hard to find in real-world scenarios. Balanced- 3The definition can be extended to NTU games as well. A.9. Shapley Value 137 ness of a game is a weaker condition—which holds for a wide class of problems—that also guarantees a nonempty core, as stated by the Bondareva-Shapley theorem [49]. Definition A.4 (Balanced map).Let α: 2N→[0,1] be a function that assigns a weight to each possible coalition in a set Nof agents. The function αis said to be a balanced map if X C∈2N α(C)1{i∈ C} = 1,∀i∈ N (A.8) i.e., αis a balanced map if, for any agent i, the sum of the weights assigned by α to every coalition containing iequals 1.4 Definition A.5 (Balanced game).A game (N, v)is said to be balanced if for any balanced map αit holds that X C∈2N α(C)v(C)≤v(N) Theorem A.1 (Bondareva-Shapley).A coalitional game has a nonempty core iff it is balanced. A.9 Shapley Value As mentioned in Section A.7, it is not uncommon to find the core to be an empty set or, vice versa, to be so large to make the choice of a suitable imputation a hard task. Furthermore, an allocation belonging to the core does not necessarily guarantee fairness to every agent (e.g., Bird’s allocation rule). Shapley tackled these issues by defining the conditions to obtain a unique payoff mapping, i.e., the Shapley value of the game (N, v). Any Shapley allocation φmust satisfy the following four axioms:5 1. Efficiency:Pi∈N φi(v) = v(N). 2. Symmetry: given two players iand j, if v(C∪{i}) = v(C ∪{j}),∀C|C∩{i, j}=∅, then φi(v) = φj(v). 3. Dummy: if, for any player i,v(C) = v(C ∪ {i})holds ∀C|C ∩ {i}=∅, then φi(v) = 0. 4The notation 1{·} :N → {0,1}designates the indicator function, which takes the value 1if i∈ C, or 0if i /∈ C [146]. 5The definition is given here for TU games. Definitions of the Shapley value for NTU games are also available. 138 Appendix A. Coalitional control and game theory 4. Additivity: let uand vbe characteristic functions. Then φ(u+v) = φ(u) + φ(v). The symmetry axiom assigns the same payoff to players that equally improve a given coalition, while the dummy axiom assigns a null payoff to a player which does not contribute when joining a coalition. The additivity axiom states the uniqueness of the mapping φover the space of all coalitional games, relating the Shapley values of two different games characterized by uand v[48]. The formulation of the individual payoff assigned to player iaccording to the Shapley value’s mapping is: φi(v) = X C⊆N \{i} |C|!(|N| − |C| − 1)! |N|![v(C ∪ {i})−v(C)] (A.9) The weight factor of the marginal contribution v(C∪{i})−v(C)expresses the probability —for any agent i— of joining a given coalition C ⊆ N \ {i}, assuming that the agents form the grand coalition in a random order. Thus, the value assigned by Shapley’s criterion corresponds to the individual expected marginal contribution. A Shapley allocation that also belongs to the core of a game combines the fairness properties of the Shapley value with the stability of the core. Note that for convex games, the Shapley value provides a closed-form expression of an imputation belonging to the core. However, in nonconvex games the Shapley value is generally not related to the core [49]. Despite the advantage of its closed form, the computational complexity of (A.9) increases significantly with the number of agents: alternative techniques for its computation can be found in the literature (the interested reader is referred to [48] and references therein). A.10 The nucleolus Another important allocation criterion for canonical games is the nucleolus. It consists in the allocation p= (pi)i∈N (for the grand coalition) able to minimize the dissatisfaction of all the agents for all the possible coalitions in N. The dissatisfaction is defined for each coalition C ⊆ N as the excess e(p,C) = v(C)−X i∈C pi(A.10) Consider the vector θ(p)∈R2Ncontaining the excess values for every coalition in the set of agents, arranged in nonincreasing order, relative to an imputation p. Then, the A.11. Power indices 139 nucleolus is the imputation p∗providing the minimum dissatisfaction according to the lexicographic order, i.e.: θ(p∗)<lex θ(p) where the <lex operator designates the lexicographic order, defined as: (e1, . . . , e2|N | )<lex (e0 1, . . . , e0 2|N | ) iff ∃i≤2|N| |ei< e0 i∧ej=e0 j,∀j < i Definition A.6 (Nucleolus [49]).The nucleolus of a game (N, v)is the lexicographically minimal imputation. As a consequence of the efficiency and group rationality conditions, only imputations with negative or null dissatisfaction belong to the core. If the core of a game is not empty then the nucleolus is in the core; following Theorem A.1 this condition is surely verified in balanced games (which include convex games). The nucleolus of a canonical coalitional game always exists and is unique. It is group and individually rational, and satisfies the symmetry and dummy Shapley’s axioms. Moreover, it always belongs to the kernel of a game.6The nucleolus has so far been defined only for TU games, and its computation requires the solution of O(2N)linear programs, each with |N| + 1 decision variables [49].7 A.11 Power indices Power indices express the influence of players on the formation of coalitions and on the outcome of the game [142]. A fair allocation rule can be based on (normalized) power indices. Widely used power indices are the one proposed by Shapley and Shubik (also known as Shapley value, see Section A.9), the Banzhaf index, and the Holler-Packel index. The Shapley value assumes an equal distribution of the probability of the order in which any agent joins all possible coalition. The Banzhaf power index assumes instead that all possible coalitions containing agent iare equally probable. The measure of the 6Given two players iand j, the kernel of a game is the set of allocations such that the maximum dissatisfaction of a player ibelonging to any coalition not including player jis equal to the maximum dissatisfaction of player jbelonging to any coalition without i. 7One decision variables corresponding to the payoff of each agent, plus an additional slack variable representing the excess for that coalition. 140 Appendix A. Coalitional control and game theory power of agent iaccording to the Banzhaf index is defined as: BPIi=1 2|N|−1X S⊆N |i∈S (v(S)−v(S \ {i})). The Holler-Packel index is based as well on the marginal contribution of agent i, but it focuses on the coalitions whose allocations are in the core:8 HPIi=X S∈C(N,v) (v(S)−v(S \ {i})), where C(N, v)denotes the set of coalitions whose payoff allocations constitute the core of the game (i.e., the best that can be achieved by the members of these coalitions, such that no one of them has an incentive to leave in search of a greater payoff). Depending on the situation, some indices may be more suited than others. In particular, the Shapley value is based on the assumption that the agent commits to stay in the coalition it joins. On the other hand, the Banzhaf value is based on the idea that agents are free to join and leave any coalition. A.12 Dynamic coalition formation In this class of games the focus is directed on the evolution of the coalitional structure due to variations in the nature of the game (e.g., variations in the degree of coupling among different parts of the system, players that enter or leave the game in a plug & play setting). The purpose of the coalition formation process is to maximize the total utility (social welfare) in TU games, or to achieve a Pareto optimal payoff allocation in NTU games. In general, the optimization of the composition of coalitions is an NP-complete problem, since it requires the evaluation of all the possible partitions of the set N of agents, whose number—known as the Bell number—grows exponentially with the number of agents. Let Ksdenote the set of possible coalitional structures (that is, partitions of N) composed by scoalitions. The cardinality of this set is expressed by the Stirling number of the second kind [147]: |Ks|=1 s! s−1 X j=0 (−1)j s j!(s−j)n(A.11) 8See Section A.8 for a definition of the core. A.12. Dynamic coalition formation 141 Then |K| =P|N| s=1 |Ks|is the number of possible coalitional structures given a set Nof agents [103]. For example, a set of 10 agents originates 115975 possible partitions. As a consequence, a centralized approach for the optimization of the coalitional structure is impractical. In many cases the properties of the game (e.g., the way its value vis defined) can be used as a guide for reducing the computational complexity. Nevertheless, since coalition formation naturally involves several autonomous agents, a distributed approach is generally desired for the solution of such problem. Several techniques have been proposed so far, based on heuristic methods, Markov chains, set theory, bargaining and other negotiation algorithms from economics (the interested reader is referred to [48] and references therein). The work of Apt and Witzel [57] focuses on the outcome of a coalition formation process resulting from the application of two rules, namely merge and split. The aim is to identify the conditions under which the outcome of the process is a unique coalitional structure, irrespective of the initial condition. The rules proposed in [57] are based on the comparison of different partitions of the set of players involved in a given merge or split operation, according to preference criteria such as Nash, utilitarian or leximin order (these ordering criteria provide advantageous properties, namely irreflexivity, transitivity, and monotonicity). Definition A.7 (Merge [57]). {C1,...,Ck} ∪ P → { k [ i=1 Ci}∪P iff { k [ i=1 Ci}.{C1,...,Ck} Definition A.8 (Split [57]). { k [ i=1 Ci} ∪ P → {C1,...,Ck}∪P iff {C1,...,Ck}.{ k [ i=1 Ci} In definitions A.7 and A.8, the symbol .denotes the local preference operator. The rest of the agents not concerned with the transformation is denoted as P ≡ N \Sk i=1 Ci. The application of supplementary basic rules can be studied to improve the convergence of the coalition formation process. For example, transfers (moving a subset of agents from one coalition to another) and swaps (exchanging subsets of agents between two coalitions) are considered in [148].