A Game Theoretical Randomized Method for Large-Scale Systems Partitioning

Received June 5, 2018, accepted June 25, 2018, date of publication July 10, 2018, date of current version August 20, 2018. Digital Object Identifier 10.1109/ACCESS.2018.2854783 A Game Theoretical Randomized Method for Large-Scale Systems Partitioning FRANCISCO JAVIER MUROS 1, JOSÉ MARÍA MAESTRE 1, (Senior Member, IEEE), CARLOS OCAMPO-MARTINEZ 2, (Senior Member, IEEE), ENCARNACIÓN ALGABA 3, AND EDUARDO F. CAMACHO 1, (Fellow, IEEE) 1Department of Systems and Automation Engineering, University of Seville, 41092 Seville, Spain 2Automatic Control Department, Universitat Politècnica de Catalunya, Institut de Robòtica i Informàtica Industrial (CSIC-UPC), 08028 Barcelona, Spain 3Department of Applied Mathematics II, University of Seville, 41092 Seville, Spain Corresponding author: Francisco Javier Muros ([email protected]) This work was supported in part by the European Union Project FP7-ICT-ICT-2013.3.4-611281 (DYMASOS) and in part by the MINECO-Spain Projects DPI2016-78338-R (CONFIGURA), DPI2017-86918-R, ECO2015-68856-P, and DPI2016-76493-C3-3-R (DEOCS). ABSTRACT In this paper, a game theory-based partitioning algorithm for large-scale systems (LSS) is proposed. More specifically, a game over nodes is introduced in a model predictive control framework. The Shapley value of this game is used to rank the communication links of the control network based on their impact on the overall system performance. A randomized method to estimate the Shapley value of each node and also an efficient redistribution of the resulting value to the links involved are considered to relieve the combinatorial explosion issues related to LSS. Once the partitioning solution is obtained, a sensitivity analysis is proposed to give a measure of its performance. Likewise, a greedy fine tuning procedure is considered to increase the optimality of the partitioning results. The full Barcelona drinking water network is analyzed as a real LSS case study, showing the effectiveness of the proposed approach in comparison with other partitioning schemes available in the literature. INDEX TERMS Coalitional control, cooperative game theory, system partitioning, randomized methods, Shapley value, large-scale systems (LSS), drinking water networks (DWN). I. INTRODUCTION Model predictive control (MPC) has evolved considerably over the last decades. It designates an ample range of control methods that make explicit use of a model of the process to obtain the control signal by minimizing an objective function [1]. Its flexibility – for any type of model can be used – and the ease of dealing with constraints and dead times are well-known advantages of this methodology. In particular, this paper focuses on distributed MPC (DMPC) schemes, where the overall control problem is divided into smaller pieces assigned to local controllers or agents, which are able to communicate among them. Typical features of these approaches, such as scalability, modularity, and the capacity of controlling large-scale systems (LSS) [2], will be very welcome in this work. Each agent involved in a distributed scheme has partial system information and communicates with neighbors for the sake of coordination [3]. Typically, the partition of the overall system is assumed to be given before the DMPC strategy is applied, and it is calculated during the system modeling, based on physical insight, experience or intuition, and other methods available in the literature, where the starting point is commonly associated with the seminal work of Siljak [4]. Recently, many partitioning schemes have appeared, based on graph theory [5]–[8], states and inputs estimation [9], social network algorithms [10], genetic algorithms [11], or PageRank [12]. In any case, no single partitioning strategy is the best fit for all situations. This way, specific partitioning techniques have been applied to real LSS case studies, e.g., in water systems [10], [13]–[15], power networks [16], [17], biological systems [18], integrated circuits [19], and urban traffic networks [20]. In fact, LSS might involve a big communication network implying the handling of large amount of data, which could yield in high computational costs. Therefore, performing the partition of the problem into smaller pieces is a natural solution for managing these networks. In this work, the coalitional control framework, which can be summarized as a set of dynamic partitioning methods for VOLUME 6, 2018 2169-3536 2018 IEEE. Translations and content mining are permitted for academic research only. Personal use is also permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information. 42245 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning networked control systems that seek for a trade-off between communication burden and control performance [21]–[26], is used to determine static neighborhoods that define the partitioning of an LSS. That is, despite its dynamic scope, the coalitional framework can be used to obtain offline system information, i.e., independent from the implementation of the control scheme. In this coalitional context, the well-known Shapley value, a cooperative game solution concept presented originally in [27], is used here to provide information regarding the relevance of the agents and the links involved in a communication network, following the ideas described in [21]–[23]. The specific contributions of this article with respect these earlier works are the following: a) A game defined in the set of agents is proposed here, where the closed-loop stage cost of the system is accumulated along the simulation scenario. This is a difference with respect to previous works, were openloop costs where used at each time step. This game is associated with the cost function of a coalitional MPC scheme, in the line of [23]. Note that the viewpoint is changed with respect to [21] and [22], where a game with the players being the links was related to the cost function of a coalitional control approach based on linear feedback gains. b) The Shapley value, which gives an averaged contribution of each player into the game, is calculated here by using randomized methods [28], [29] satisfying a minimum bounded error requirement. The relevance of the links is obtained by an index, introduced in [23], which redistributes the Shapley value from the agents to the links. c) In [21] and [23], a very preliminar partitioning that uses few thresholds to classify the links as a function of the control performance is proposed. Here, the partitioning algorithm is drastically improved by introducing new parameters that balance the size of the communication components. Additionally, a new set that refers to expensive links among components is also introduced here to provide a proper definition of the network configuration after applying the partitioning method. d) A sensitivity analysis that gives a measure of the partitioning control performance is included in this paper. Through this analysis, the proposed partitioning solution is compared with other schemes available in [10] and [13], and also with the centralized and decentralized configurations. Moreover, this analysis is recursively implemented in a greedy fashion [30], [31] to make a fine tuning of the partitioning approach. Notice that the results reported in previous works were only suitable for academic small networks. Nevertheless, through the combination of a) and b) the computational and combinatorial explosion issues related to LSS are mitigated and it is possible to implement the new partitioning algorithm introduced in c) and d) in such networks. Moreover, the full Barcelona drinking water network (DWN), modeled in [13] and [14], is chosen as a real LSS case study to assess the effectiveness of the proposed partitioning approach, which represents an additional contribution of this paper. The remainder of this paper is organized as follows. In Section II, the problem setting is stated in a coalitional control framework. Next, in Section III, a game over nodes is considered, being the Shapley value utilized as a means of distributing the cost of the game among the agents. Likewise, a randomized method to estimate the Shapley value and a redistribution of this value to the set of links are proposed to deal with combinatorial explosion issues. In Section IV, a Shapley value-based partitioning algorithm is introduced. The partitioning performance is evaluated by means of a sensitivity analysis, whose information is also recursively used for a fine tuning of the proposed approach. In Section V, the Barcelona DWN is presented as the case study, with the corresponding partitioning results and comparisons with other approaches being presented in Section VI. Finally, conclusions are drawn in Section VII. II. FOUNDATIONS OF COALITIONAL CONTROL Consider the class of distributed linear systems composed of N= {1,2,...,|N|} interconnected subsystems or agents. The dynamics of agent i∈Ncan be mathematically described, with k∈Z+, as xi(k+1) =Aiixi(k)+Biiui(k)+wi(k), wi(k)=X j6=iAijxj(k)+Bijuj(k)+Bpidi(k),(1) where xi(k)∈Rnxiis the state vector of agent i,ui(k)∈Rnui its corresponding input vector, and wi(k)∈Rnxithe related disturbances, which can be either external to the whole system, denoted by di(k)∈Rndi, or be caused by the neighbors as well. Likewise, Aii ∈Rnxi×nxi,Bii ∈Rnxi×nui,Aij ∈ Rnxi×nxj,Bij ∈Rnxi×nujand Bpi∈Rnxi×ndiare system matrices of suitable dimensions. Both states and inputs are constrained into independent sets defined by a collection of linear inequalities, i.e., xi(k)∈Xi,Xi⊆Rnxi,ui(k)∈Ui,Ui⊆Rnui.(2) A. NETWORKED COALITIONAL STRUCTURE In standard coalitional control, the agents are merged at each time instant into several disjoint neighborhoods or communication components C1,C2,...,Cnc, verifying Snc s=1Cs=N. Conversely, the goal in this paper is to use coalitional control to find a time-independent set denoted as NC= {C1,C2,...,Cnc}, i.e., nc= |NC|, assuming that agents in Nare initially connected by a network described by an undirected graph (N,E), where E=EN=N×Nis the set of links corresponding to all feasible communication connections among the agents. Hence, the number of elements in both sets is, in the worst case, connected by [21], [23] |E| = |N|(|N| − 1) 2,(3) 42246 VOLUME 6, 2018 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning which corresponds to the number of links of a complete network. This case, which is the most demanding in terms of problem size, will be assumed throughout the paper. Note that, under this premise, any group or coalition C⊆Nof agents is internally connected. Each link l∈Ecan be classified according to its relevance from a control viewpoint. This way, it can be more profitable for the overall system performance to fix/disconnect some links permanently. In this work, the partitioning objective will focus on finding out those links. When a specific coalition C is formed, a model analogous to (1) is calculated at a coalition level, i.e., xC(k+1) =ACCxC(k)+BCCuC(k)+wC(k), wC(k)=X j/∈CACjxj(k)+BCjuj(k)+BpCdC(k),(4) with xC(k)=[xi(k)]i∈C∈RnxC,uC(k)=[ui(k)]i∈C∈RnuC and wC(k)=[wi(k)]i∈C∈RnwC,dC(k)=[di(k)]i∈C∈ RndCbeing respectively the coalitional states, inputs, overall disturbances and external disturbances that aggregate the corresponding vectors, and ACC ∈RnxC×nxC,BCC ∈RnxC×nuC, ACj∈RnxC×nxj,BCj∈RnxC×nujand BpC∈RnxC×ndC are obtained by aggregating the corresponding individual matrices. The coalitional constraints become xC(k)∈XC⊆RnxC,XC=Y i∈C Xi, uC(k)∈UC⊆RnuC,UC=Y i∈C Ui.(5) Finally, from an overall centralized viewpoint, the system is described by xN(k+1) =ANxN(k)+BNuN(k)+BpNdN(k),(6) with xN(k)∈RnxN,uN(k)∈RnuN,dN(k)∈RndNbeing, respectively, the overall state, input and disturbance vectors. Note that from a centralized viewpoint, wN(k) is only composed of external disturbances BpNdN(k). The centralized constraints have the form xN(k)∈XN⊆RnxN,XN=Y i∈N Xi, uN(k)∈UN⊆RnuN,UN=Y i∈N Ui.(7) B. CONTROL OBJECTIVE Under an MPC framework, the goal of each coalitional controller C⊆Nis to drive a sequence of future states over a prediction horizon Np, that is, XC(k+1:k+Np)= {xC(k+1),...,xC(k+Np)}, by using the most appropriate control sequence. To this end, the controller solves the following open-loop finite-horizon optimization problem at each time instant k: U∗ C(k:k+Np−1) =arg min UC(k:k+Np−1) Np−1 X r=0 `CxC(k+r+1),uC(k+r), (8) subject to (4), (5), the aggregate forecast of the expected local disturbances ˆ WC(k:k+Np−1) = { ˆ wC(k),..., ˆ wC (k+Np−1)}, and a measured coalitional initial state ˆ xc(k). Likewise, `CxC(k),uC(k)is a certain convex coalitional stage cost that is minimized along the prediction horizon. As a result, the sequence of the coalitional optimal control inputs over Np, that is, U∗ C(k:k+Np−1) = {u∗ C(k),...,u∗ C (k+Np−1)}is obtained. Only the first control input u∗ C(k) is actually applied, and the rest of elements are discarded. At the next time instant, (8) is solved again in a receding horizon fashion. Notice that a coalition can be a singleton. In this case, each local controller i∈Nsolves an optimization problem analogous to (8) by taking C=i. Likewise, to compute a centralized MPC scheme implemented in a distributed fashion it is enough to calculate the optimal input sequence by taking C=Nand solving (8). III. COOPERATIVE GAMES AND THE SHAPLEY VALUE In [21] and [22], the set of links Ewas interpreted as the set of players of a cooperative game whose characteristic function assigned a value to each of the different configurations of links or network topologies. As commented before, in the approach proposed this paper it is assumed that the number of links is related to the agents by (3). Hence, to mitigate combinatorial explosion issues associated to LSS, the perspective of the aforementioned works is changed here, as done in [23], to working directly with a cooperative game (N,v) defined over set of agents N. To this end, a cost function vthat assigns a cost to each coalition of players C⊆Nis defined by v(C,xN)= Tsim−1 X k=0"`CxC(k+1),u∗ C(k) +X i/∈C `ixi(k+1),u∗ i(k)#,(9) with `ixi(k),ui(k)and `CxC(k),uC(k)being the stage costs, which will be defined for the case study in Section V-B, and where Tsim is the number of simulation steps used to accumulate the closed-loop stage cost of the system over the simulation time. This function vis computed by applying at each time step the first element of the control sequence of coalition C, i.e., u∗ C(k), which is obtained by solving (8). The rest of the agents calculate their input sequences u∗ i(k) by solving (8), with C=i, independently. Remark 1: Equation (9) is evaluated with input information from all agents, independently whether they are either in or out the coalition C. Each coalition Csolves its own optimization problem, which is decoupled from the rest of the network. Hence, 2|N|values are needed to fully characterize function vusing the standard approach, which is not the case in this work, as it will be shown in the next subsection by considering randomized methods. Once the game is defined, the Shapley value [27] is considered here to get the corresponding cost that each player expects from the game. This value assigns to game (N,v) VOLUME 6, 2018 42247 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning vector φ(N,v), defined ∀i∈Nas φi(N,v) =X C⊆N,i/∈C |C|!(|N|−|C| − 1)! |N|! [v(C∪{i},xN)−v(C,xN)], (10) i.e., the marginal contribution of each agent i∈Nis averaged for all possible coalition permutations it can be part of. Remark 2: Equation (10) was originally defined in the context of transferable utility (TU) games. Given that agents out of Cwork independently, an univocal v(C)is obtained for each C, and (9) could be interpreted as a TU-game by simply assuming a redefined game v0(C,xN)=v(C,xN)−v(∅,xN). This way, the Shapley value of this redefined game, which trivially coincides with the Shapley value of the original game (see [22]), will be considered here. Given that the partitioning procedure proposed in this paper will be performed by fixing/disconnecting some communication links among the different agents, a measure of the relevance of the links is required. Given a link l= {i,j} ∈ E, it is possible to redistribute the Shapley value of the agents that are the end-points of this link, i.e., iand j, by means of the following expression [23]: ξl(N,v)=1 |Ei|φi(N,v)+1 |Ej|φj(N,v),(11) with Eiand Ejbeing, respectively, the set of links connected to agents iand j. Notice that values ξl(N,v) satisfy efficiency as the original Shapley value, i.e., X l∈E ξl(N,v)=X i∈N φi(N,v)=v(N,xN).(12) Note that (11) provides a way to arrange and compare the links according to their relevance from a control-performance perspective, which can be interpreted as a LinkRank, in the line of [32]. This way, the lower this value is, the more useful the link becomes. This is consistent with the Shapley value, which associates useful players to lower values. Remark 3: Equation (11) provides information from all links l ∈Eby means of the Shapley value of agent-based game (9), which is obtained by evaluating the corresponding 2|N|coalitions. This fact mitigates the combinatorial explosion of the method proposed in [21], which depends on a linkgame that requires to evaluate 2|E|coalitions per game, with |E| = f(|N|2)as shown in (3). A. ESTIMATION OF THE SHAPLEY VALUE In networks with a large number of agents it is not computationally feasible to compute (9) for every coalition. This issue can be solved by using randomized methods such as [28] and [29]. In particular, the method in [28] is used here to provide an estimation of the Shapley value of each agent calculated in polynomial time provided that (9) can also be calculated in polynomial time, which will be shown in Section V-B. To this end, the following alternative definition of the Shapley value, expressed in terms of all possible orderings of players in Ncoming into coalition, i.e., |N|!, is used in the sampling method given in [28]: φi(N,v)=1 |N|! X π∈5(N) mπ i(N,v),∀i∈N,(13) where the orderings are assumed to be equiprobable, with 5(N) being the collection of all permutations π, and where mπ i(N,v)=v({j∈N:π(j)≤π(i)}) −v({j∈N:π(j)< π(i)}),(14) is the marginal contribution of player ito the players that are ranked before it in permutation π. The basics of the method in [28] consist in choosing a given number of random orderings from set 5(N) for estimating the Shapley value of each player. To this end, a set Qthat contains a sample of qdifferent permutations π, which are taken with replacement and with equal probability from set 5(N), is considered. This way, an estimation of the Shapley value is given by the average of the marginal contributions over set Q, i.e., e φi(N,v)=1 qX π∈Q mπ i(N,v),∀i∈N.(15) Equation (15) provides an approximation of the Shapley value with desirable properties. In particular, as the Shapley value, the estimator satisfies efficiency. Moreover, following the central limit theorem, it holds [28] that the estimator is a normal distribution with the following mean value and standard deviation: e φi(N,v)∼N φi,σ2 φi q!,(16) with σ2 φi=1 |N|! X π∈5(N)mπ i(N,v)−φi(N,v)2,∀i∈N. (17) Consequently, if the number of permutations qis chosen satisfying the following condition, ∀i∈N[28]: q≥Z2 λ/2σ2 φi ε2,(18) the estimation error is is guaranteed to be bounded by [28] P|e φi(N,v)−φi(N,v)| ≤ ε≥1−λ, (19) with εbeing the approximation error, Z∼N(0,1), and where Z2 λ/2is the value such that P(Z≥Z2 λ/2)=λ/2, with 0≤λ≤1. Finally, note that by taking σφi=αε, i.e., proportionally to the desired error, condition (18) is reduced to q≥αZ2 λ/2.(20) 42248 VOLUME 6, 2018 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning IV. SHAPLEY-VALUE-BASED PARTITIONING ALGORITHM The main objective of the algorithm presented in this paper is to find which agents should cooperate to improve the overall system performance. Notice that, some preliminar steps are needed before it can be launched. In the first place, there is a pre-partitioning stage in which a set of atomic agents needs to be defined by assigning states, actions and constraints to minimum size entities that could work in a fully decentralized fashion, i.e., without the need for communication with other parts of the system. In this work, as it will be shown in Section V-A, these agents stem from the constraints imposed on the system by the node equations. Once the agents are defined, a communication link between each pair of agents is considered, with the full number of links given by (3). Then, it is needed to classify these links according to their relevance in terms of their impact on the overall system performance. To this end, a measure index related to the Shapley value is associated with each link as follows: Measure Indices Procedure Let (N,E) be a network that describes a set Nof agents connected by links l∈E. Consider also a measured initial state ˆ xN(k) and a forecast of the expected disturbances ˆ WN(k:k+Np−1). Then, a) Calculate a size qthat guarantees, following (18), that the estimation error is under desired limits. b) Compute e φi(N,v),∀i∈N, by using (15). For each coalition C∈NC, the optimal input sequence over Np is obtained by solving (8) for Cand also for the agents out of C. Only the first control input is applied, and the rest of elements are discarded. At the next time step these optimization problems are solved in a receding horizon fashion. This process is performed during Tsim time instants and the cumulated cost of this closed-loop simulation is used to build v(C,xN) by means of (9). c) Redistribute the obtained Shapley value among the links by indices e ξl(N,v), calculated by using (11). Therefore, index e ξl(N,v) measures the impact of link lin the control network. Based on these indices, it is possible to rank the links, which in turns allows to obtain the following subsets: •Set Ec⊆E: it includes the links that are inexpensive enough in control terms to always be fixed. This way, agents connected by links belonging to Eccooperate together and will be merged in a single agent, which corresponds to any of the communication components in NC= {C1,C2,...,Cnc}. •Set Ee⊆E: it comprises the links that are too costly for the system in terms of control performance, and therefore will be permanently disconnected. Basically, the partitioning algorithm in this section is introduced with the aim of determining sets Ecand Ee. Both sets are initially assumed to be empty, and links will be gradually included in those sets if they satisfy certain conditions. This way, links in Ec(s) define the communication components in NC(s) in a given iteration s∈N+. Some concepts that will be needed to perform the partitioning are introduced next: •K: symbolizes the mean span among indices e ξl(N,v) and it is defined by K=e ξlmax (N,v)−e ξlmin (N,v) |E|,(21) where lmax and lmin denote, respectively, the links with maximum and minimum measure indices e ξl(N,v). •Ci(s): denotes the component in NC(s) where agent i belongs to. •Ei(s): denotes the set of remaining links in E\Ec(s) connected to agent i. Notice that the sizes of sets Ci(s) and Ei(s) are inversely related. Both sets will be of interest in the Shapley-value- based partitioning algorithm, which is presented at the beginning of the next page. Notice that the inclusion of a new link l∗ cin Ec(s) depends on the size of the components at sthat this link if e ξ(s) l∗ c(N,v)+0 < LcAND Ci∗(s)6= Cj∗(s) H⇒                  Ec(s+1) =Ec(s)∪l∗ c, e ξ(s+1) l(N,v)=           e ξ(s) l(N,v),l/∈ {Ei∗(s+1) ∪Ej∗(s+1)}, e ξ(s) l(N,v)+ρK |Ei∗(s+1)|,l∈Ei∗(s+1), e ξ(s) l(N,v)+ρK |Ej∗(s+1)|,l∈Ej∗(s+1), else if Ci∗(s)=Cj∗(s)H⇒ (Ec(s+1) =Ec(s)∪l∗ c, e ξ(s+1) l(N,v)=e ξ(s) l(N,v), otherwise H⇒ (Ec(s+1) =Ec(s), e ξ(s+1) l(N,v)=e ξ(s) l(N,v). (23) VOLUME 6, 2018 42249 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning Partitioning Algorithm 1 Lete ξl(N,v) be the indices related to each link l∈E. Let Lc, Le∈Rbe given thresholds, verifying Lc≤Le. Finally, let sbe a counter variable. I) Computation of set Ec Let γ, ρ ∈R+\{0},ν≥1 be scalar parameters. Let also Kbe the mean span given by (21). Starting with s=0, and assuming e ξ(0) l(N,v)=e ξl(N,v) and Ec(0) = ∅, do 1) Obtain the link with minimum measure index from the remaining links that are not yet included in set Ec(s), i.e., l∗ c=arg min le ξ(s) l(N,v),l∈E\Ec(s).(22) 2) Validate link l∗ c= {i∗,j∗}as a suitable candidate to be added to Ec(s), and update this set and the links neighbors of l∗ cconsequently, doing, ∀l∈E\Ec(s+1), the procedure defined by (23), with 0being calculated as 0=γK|Ci∗(s)|+|Cj∗(s)|ν.(24) 3) Make s=s+1 and go to Step 1, whilee ξ(s) l∗ c(N,v)<Lc. Otherwise, the procedure ends and set Ecis fully determined, i.e., Ec=Ec(s). II) Computation of set Ee Starting again with s=0, and assuming e ξ(0) l(N,v)= e ξl(N,v), Ee(0) = ∅, do 4) Obtain the link with maximum measure index from the remaining links, i.e., l∗ e=arg max le ξ(s) l(N,v),l∈E\(Ec∪Ee(s)).(25) 5) Validate link l∗ e= {i∗,j∗}as a suitable candidate for set Ee(s), and update this set consequently, doing Ee(s+1) =Ee(s)∪l∗ e,if e ξ(s) l∗ e(N,v)>Le, Ee(s+1) =Ee(s),otherwise.(26) 6) Make s=s+1 and go to Step 4, while e ξ(s) l∗ e(N,v)> Le. Otherwise, the procedure ends and set Eeis fully determined, i.e., Ee=Ee(s). will connect. More specifically, 0penalizes a new link candidate to Ec(s) before deciding whether it should be included in that set, in case that this link would connect two different components in NC(s), and proportionally to their cardinality. Additionally, in case that l∗ cis accepted, the proposed algorithm penalizes its neighboring links that remain in set E\Ec(s+1), by a term that is larger as less neighbors of l∗ cremain in that set, which in turns implies that l∗ cis more congested in Ec(s+1). These mechanisms induce size constraints on the components, which avoid inefficient partitionings that could lead to an almost centralized scheme. This way, the proposed parameters γ,νand ρ could be adjusted to obtain some properties of interest, e.g., to impose a maximum cardinality for any communication component. FIGURE 1. Two iteration steps in the process of obtaining set Ec. Example 1: Take the network in Fig. 1, with six agents connected by 15 links. In a given iteration s (see Fig. 1a), it is obtained Ec(s)={1,2},NC(s)={1,2},{3},{4},{5},{6}, (27) Then, consider that link l∗ c= {i∗,j∗} = {1,3}is proposed to be fixed. The sets related to this link in iteration s are described by C1(s)= {1,2},E1(s)={1,3},{1,4},{1,5},{1,6}, C3(s)= {3},E3(s)={1,3},{2,3},{3,4},{3,5},{3,6}. (28) Assume at this point that e ξ(s) l∗ c(N,v)+0 < Lc. This way, given that C1(s)6= C3(s), the first statement in (23) is fulfilled, hence link {1,3}is included in set Ec(s+1) (see Fig. 1b), obtaining Ec(s+1) ={1,2},{1,3}, NC(s+1) ={1,2,3},{4},{5},{6}, C1(s+1) =C3(s+1) = {1,2,3}, E1(s+1) ={1,4},{1,5},{1,6}, E3(s+1) ={2,3},{3,4},{3,5},{3,6}.(29) Therefore, ∀l∈E\Ec(s+1), all measure indices are updated if l belongs either to E1(s+1) or E3(s+1), by increasing in an inversely proportional way to the cardinality of those sets e ξ(s+1) l(N,v)=e ξ(s) l(N,v)+ρK 3,l∈E1(s+1), e ξ(s+1) l(N,v)=e ξ(s) l(N,v)+ρK 4,l∈E3(s+1).(30) Finally, consider that l∗ c= {i∗,j∗}={2,3}is also proposed to be fixed. In that case, given that C2(s+1) = C3(s+1) = {1,2,3}, the second statement in (25) is satisfied, and the link will be included in set Ec(s+2). Nevertheless, no updates on the measure indices of links l ∈E\Ec(s+2) would be considered. Once set Ecis fully determined, a new single agent corresponding to each component in NCis established, independently of whether the agents inside this component are directly or indirectly connected. Therefore, the system is 42250 VOLUME 6, 2018 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning reduced to |NC|new agents, which may communicate or not, depending on the needs of the control scheme. The possible links among the agents are denoted by EC=NC×NC, which verifies |EC| = |NC|(|NC|−1) 2, according to (3). That is, links lC∈ECare defined as lC= {Ca,Cb},∀Ca,Cb∈NC.(31) Finally, the information provided by Eeis used to determine links lCthat should be permanently disconnected. Given that links in Eeare referred to agents instead of components, it is necessary to obtain a new set, say EeC, referred to components. In this work, it is considered that two components should not have a direct cooperation if all links that interconnect the agents inside both components belong to subset Ee, i.e., If l={i,j} ∈ Ee,∀i∈ˇ Ca,∀j∈ˇ Cb−→ˇ lC={ ˇ Ca,ˇ Cb} ∈ EeC. (32) Summing up, the configuration of the system will be described after performing the partitioning by the following network: NC,EC\EeC,(33) where the links in EC\EeCmay be dynamically enabled or disabled at each time instant by means of a coalitional control approach [22], [24]. Remark 4: The proposed Shapley-value-based algorithm represents a heuristic methodology for the system partitioning that avoids an exhaustive exploration of every coalition involved in the control scheme. Note that this methodology is independent from the model dynamics or the game choice, i.e., nonlinear systems or alternative definitions for the game different to (9) are possible. For example, it might be considered theoretical aspects such as stability or robustness [2], [33], which are out of the scope here since this work only focus on the partitioning methodology. Likewise, for the sake of clarity, the class of linear systems described by (1), which is widely studied in the literature, is assumed here. Remark 5: The way the agents inside a component are actually connected once the partitioning is performed is beyond of the scope of this work. This issue could be dealt with, e.g., by using spanning tree algorithms [34], [35], in order to find the minimum set of links that is necessary to connect all agents belonging to a given component. In any case, note that the partitioning approach reduces the communication costs of the original centralized scheme, given that the agents inside a component after performing the partitioning are only required to communicate to their neighbors. Example 2: Consider again the network presented in Example 1, with six agents and 15 links. Assume that after applying the partitioning algorithm, sets Ecand Eeare given by (see Fig. 2a): Ec={1,2},{1,3},{2,3},{4,5}, Ee={1,6},{3,6},{4,6},{5,6}.(34) FIGURE 2. Establishing the components and their removed links by Ec and Ee. The links in Ecdefine the following components: C1= {1,2,3},C2= {4,5},C3= {6},(35) which are also assumed to be connected by links {C1,C2}, {C1,C3}and {C2,C3}. From these three links, only link {C2,C3}verifies the criterion given in (32), i.e., all links that connect agents in components C2and C3are included in set Ee. Hence, this link should be permanently disconnected. Therefore, the final configuration of the network is shown in Fig. 2b and it is given by (NC,EC\EeC)=C1,C2,C3,{C1,C2},{C1,C3}.(36) SENSITIVITY ANALYSIS OF THE CONTROL PERFORMANCE: A PARTITIONING ALGORITHM FINE TUNING The rationale behind the partitioning procedure is to provide a reasonable trade-off between control and communication costs. Therefore, the proposed Shapley-value-based approach, denoted from now on by SVBA, provides us with a suboptimal solution NCfor the partitioning of an LSS, where the optimal solution corresponds with the centralized case (only one component) when communication costs are not considered. Once NCis established, the closed-loop system performance can be related to the cumulated cost Jcum(NC), which is obtained by computing each component C∈NCby using (9). Then, in order to give an insight of the SVBA fitness, it would be interesting to compare the cumulated cost of partition NCwith the rest of possible partitioning approaches. Nevertheless, note that the number of ways to partition a set of |N|agents into nonempty components is given by the Bell number [36] B|N|= |N| X s=0 1 s! s X j=0 (−1)s−js jj|N| ,(37) which becomes computationally infeasible for LSS so as comparing NCwith this full set. To solve this issue, here it is considered the subset composed of all partitions Nswi C, which differ from NCin the fact that only one agent i∈N switches components. This set will be denoted by 9N,NCand VOLUME 6, 2018 42251 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning its cardinality is given by |9N,NC|=|N||NC|−|N|C|=1 C| |N|C|=1 C| + 1 2!,(38) where |N|C|=1 C|is the number of singletons in NC. Note that a new component could be formed assuming the agent that switches components is not already a singleton in NC. Likewise, redundant switches between any two singletons are also discarded from set 9N,NC. Once set 9N,NCis introduced, some related indices will be obtained and compared with those of NC, which can be interpreted as a sensitivity analysis of the SVBA. In particular, the minimum, maximum, and mean cumulated costs of partitions Nswi C∈9N,NCwill be of interest. Likewise, a parameter that computes the portion of partitions Nswi Cthat are improved by NCwill also be considered and symbolized by ηp, with pbeing a certain uncertainty limit, i.e., to be better than NCit is required to outperform its cost beyond a certain threshold. Notice also that the partition with minimum cumulated cost from 9N,NC, say N(1) C, provides a suboptimal solution that improves NC. Consequently, it is possible to optimize recursively the SVBA in a greedy fashion by using the minimumcost solutions N(r) Cfrom the successive sets 9(r−1) N,NC, whose elements in turns admit that only one agent switches components from partition N(r−1) C, with r∈N+,r>1, i.e., N(r) C=arg min Nswi C Jcum(Nswi C) s.t. Nswi C∈9(r−1) N,NC,(39) until reaching any pre-established stopping criterion, e.g., a maximum number of iterations rmax or a minimum performance improvement between iterations. This optimization represents a fine tuning of the SVBA, denoted here by SVBA-FT. Note that, as considered in the SVBA, some additional constraints should be included by the control designer in the SVBA-FT to balance the size of the components. Likewise, note that sets Ec,Eeand EeCcould be modified as a consequence of the fine tuning procedure. In any case, these changes improve the performance of the optimized solution, symbolized by Nopt C. Remark 6: Given how 9N,NCis built, the impact on communication burden between two consecutive optimization steps is negligible. Nevertheless, when a high number of steps is performed, the aforementioned size constraints and also a stopping criterion are necessary to avoid inefficient centralized partitionings. Example 3: Let the solution of the SVBA described by (35). Following (37), the full set of different solutions for six agents is given by B6=203, whereas the cardinality of 9N,NCis reduced to 17, according to (38). All partitions included in that set are detailed in Table 1, where the switching agent for each case with respect to NCis represented in blue color. Note that the cases of any agent in C1or C2switching to a new singleton C4are taking into account. Consider for instance TABLE 1. Set 9N,NCrelated to NCdescribed by (35). that Nopt C, i.e., the solution after performing the fine tuning, is given by Partition 14 in Table 1as Copt 1= {1,2,3},Copt 2= {4},Copt 3= {5,6}.(40) Then, note that link {5,6}should be removed from set Ee. Consequently, set Eopt eCand the final network configuration for the SVBA-FT would be respectively described by Eopt eC= ∅,(41a) (Nopt C,Eopt C\Eopt eC)=Copt 1,Copt 2,Copt 3,Eopt C,(41b) with Eopt C=Nopt C×Nopt C. V. CASE STUDY The proposed partitioning scheme has been implemented in the Barcelona DWN, which is managed by Aguas de Barcelona, S.A. (AGBAR). The Barcelona DWN distributes the water supplied by the Ter and Llobregat rivers, which are regulated at their head by dams with an overall capacity of 600 hm3, to the whole Barcelona metropolitan area. Besides the rivers, some additional underground wells also contribute to an overall flow of around 7 m3 /s, which becomes potable by using four drinking water treatment plants. Given the limits in the water flow provided by each source, there exist different water prices depending on water treatments and legal extraction canons. A. COALITIONAL CONTROL MODEL Control-oriented schemes for DWNs have been widely analyzed in [37] and [38]. In particular, the control approach of the full Barcelona DWN discussed in [13] and [14] is considered in this paper and depicted in Fig. 3. This model contains a total amount of 63 tanks, 114 actuators – divided into 75 pumps and 39 valves – and 88 sectors of consume that represent the external disturbances. A graph that summarizes the physical connections among the storage tanks and the junction nodes is provided in Fig. 4. In the approach proposed in this paper, as commented before, an initial pre-partitioning into agents is performed 42252 VOLUME 6, 2018 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning FIGURE 3. Entire model of the Barcelona DWN [13], [14]. FIGURE 4. Graph representing the full Barcelona DWN, where the tanks are denoted by x, the junction nodes by N, and with the arrows representing the directions of the flows. due to the node equations that appear in the system (see Fig. 3), e.g., u(25)−u(27)−u(28)−u(29)−u(105)−d(15) =0, u(27)−u(26)−d(36) =0,(42) physically connect flows u(25), u(26), u(27), u(28), u(29) and u(105). Hence, the values of these flows must be simultaneously determined. For this reason, they are assigned to the same agent. As a consequence, the only coupling among the subsystems is due to the inputs effect in the dynamical model. Therefore, in the case study, Aij =0 in (1), and equivalently, ACj=0 in (4). Considering this approach, 43 agents have been obtained, where the criterion of considering outflows as disturbances has been assumed, i.e., agents control their inflows. The explicit definition of each agent is included in Appendix, where the identification of Agent 1 is detailed as an example. Remark 7: Following this approach, the constraints imposed by the node equations are assigned to a given agent and are always satisfied. This fact represents an advantage with respect to the partitioning performed in [13], where the agents do not satisfy in general the node equations and the resulting components need to communicate partially following a hierarchical structure and generating virtual demands among them, i.e., they cannot work in a truly decentralized fashion. From an overall centralized viewpoint, the following equations are satisfied: xN(k+1) =ANxN(k)+BNuN(k)+BpNdN(k), (43a) 0=ENuN(k)+EdNdN(k),(43b) VOLUME 6, 2018 42253 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning By considering this approach, the following 43 Agents have been obtained: •Agent 1: –States: x(22), x(27), x(57). –Inputs: u(22), u(25), u(26), u(27), u(28), u(29), u(80), u(89), u(105). –Disturbances: d(15), d(23), d(28), d(36), u(23), u(30), u(78). •Agent 2: –States: x(7), x(8), x(9), x(10), x(32), x(35), x(38), x(42), x(43), x(44), x(45), x(46), x(48), x(49), x(50), x(53), x(55), x(56), x(60). –Inputs: u(7), u(8), u(9), u(10), u(33), u(36), u(40), u(41), u(44), u(45), u(46), u(47), u(48), u(49), u(50), u(51), u(52), u(53), u(54), u(55), u(56), u(57), u(58), u(59), u(61), u(62), u(63), u(64), u(66), u(67), u(70), u(71), u(72), u(74), u(75), u(76), u(77), u(78), u(79), u(81), u(82), u(83), u(84), u(85), u(86), u(87), u(90), u(91), u(92), u(93), u(95), u(96), u(97), u(106), u(107), u(110), u(111), u(113), u(114). –Disturbances: d(7), d(8), d(9), d(10), d(32), d(40), d(42), d(43), d(45), d(47), d(50), d(52), d(53), d(54), d(55), d(57), d(58), d(59), d(60), d(62), d(63), d(64), d(65), d(69), d(70), d(71), d(72), d(73), d(74), d(75), d(76), d(77), d(79), d(80), d(81), d(82), d(83), d(84), u(3), u(4), u(5), u(6), u(13), u(21), u(38), u(42), u(43), u(60), u(67), u(68), u(69), u(72), u(74), u(94), u(95), u(98), u(101), u(106), u(107), u(108), u(109), u(111), u(112). •Agent 3: –States: x(59). –Inputs: u(102), u(103), u(104). –Disturbances: u(88), u(89), u(97). •Agent 4: –States: x(1). –Inputs: u(1). –Disturbances: d(1). •Agent 5: –States: x(2). –Inputs: u(2). –Disturbances: d(2), u(1). •Agent 6: –States: x(3). –Inputs: u(3). –Disturbances: d(3). •Agent 7: –States: x(4). –Inputs: u(4). –Disturbances: d(4). •Agent 8: –States: x(5). –Inputs: u(5). –Disturbances: d(5). •Agent 9: –States: x(6). –Inputs: u(6). –Disturbances: d(6), u(2). •Agent 10: –States: x(11). –Inputs: u(11). –Disturbances: d(11). •Agent 11: –States: x(12). –Inputs: u(12). –Disturbances: d(12), u(11). •Agent 12: –States: x(13). –Inputs: u(13). –Disturbances: d(13), u(12). •Agent 13: –States: x(14). –Inputs: u(14). –Disturbances: d(14). •Agent 14: –States: x(15). –Inputs: u(15). –Disturbances: d(16), u(14). •Agent 15: –States: x(16). –Inputs: u(16). –Disturbances: d(17). •Agent 16: –States: x(17). –Inputs: u(17). –Disturbances: d(18). •Agent 17: –States: x(18). –Inputs: u(18). –Disturbances: d(19), u(15). •Agent 18: –States: x(19). –Inputs: u(19). –Disturbances: d(20). •Agent 19: –States: x(20). –Inputs: u(20). –Disturbances: d(21), u(16), u(17). •Agent 20: –States: x(21). –Inputs: u(21). –Disturbances: d(22), u(18), u(19), u(20). 42260 VOLUME 6, 2018 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning •Agent 21: –States: x(23). –Inputs: u(23). –Disturbances: d(24), u(24). •Agent 22: –States: x(24). –Inputs: u(24). –Disturbances: d(25), d(38). •Agent 23: –States: x(25). –Inputs: u(30). –Disturbances: d(26). •Agent 24: –States: x(26). –Inputs: u(31). –Disturbances: d(27), d(35). •Agent 25: –States: x(30). –Inputs: u(32). –Disturbances: d(34). •Agent 26: –States: x(28). –Inputs: u(34). –Disturbances: d(29), u(31). •Agent 27: –States: x(29). –Inputs: u(35). –Disturbances: d(30), d(37). •Agent 28: –States: x(36). –Inputs: u(37). –Disturbances: d(41). •Agent 29: –States: x(34). –Inputs: u(38). –Disturbances: d(39). •Agent 30: –States: x(40). –Inputs: u(39). –Disturbances: d(51). •Agent 31: –States: x(39). –Inputs: u(42). –Disturbances: d(48), d(49). •Agent 32: –States: x(41). –Inputs: u(43). –Disturbances: d(56), u(39). •Agent 33: –States: x(47). –Inputs: u(60). –Disturbances: d(61). •Agent 34: –States: x(51). –Inputs: u(65). –Disturbances: d(66). •Agent 35: –States: x(52). –Inputs: u(68). –Disturbances: d(67), u(65). •Agent 36: –States: x(54). –Inputs: u(69). –Disturbances: d(68). •Agent 37: –States: x(33). –Inputs: u(73), u(108). –Disturbances: d(33), u(32), u(33). •Agent 38: –States: x(58). –Inputs: u(88). –Disturbances: d(78), u(73), u(80), u(82), u(87). •Agent 39: –States: x(61). –Inputs: u(94), u(98), u(99). –Disturbances: d(85), u(93), u(100). •Agent 40: –States: x(62). –Inputs: u(100). –Disturbances: d(87), d(88). •Agent 41: –States: x(63). –Inputs: u(101). –Disturbances: d(86). •Agent 42: –States: x(31). –Inputs: u(109). –Disturbances: d(31), u(34), u(35). •Agent 43: –States: x(37). –Inputs: u(112). –Disturbances: d(44), d(46), u(37), u(114). ACKNOWLEDGEMENT The authors would like to thank the Editor and the anonymous reviewers for their valuable suggestions and comments. REFERENCES [1] E. F. Camacho and C. B. Alba, Model Predictive Control (Advances Textbooks in Control and Signal Processing), 2nd ed. London, U.K.: Springer, 2003. [2] J. M. Maestre and R. R. Negenborn, Eds., Distributed Model Predictive Control Made Easy (Intelligent Systems, Control and Automation: Science and Engineering), vol. 69. Dordrecht, The Netherlands: Springer, 2014. [3] R. R. Negenborn, P.-J. van Overloop, T. Keviczky, and B. De Schutter, ‘‘Distributed model predictive control of irrigation canals,’’ Netw. Heterogeneous Media, vol. 4, no. 2, pp. 359–380, Jun. 2009. VOLUME 6, 2018 42261 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning [4] D. D. Siljak, Decentralized Control of Complex Systems. Boston, MA, USA: Academic, 1991. [5] A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz, ‘‘Recent advances in graph partitioning,’’ in Algorithm Engineering: Selected Results and Surveys (Lecture Notes in Computer Science, vol. 9220), L. Kliemann and P. Sanders, Eds. Cham, Switzerland: Springer, 2016, ch. 25, pp. 117–158. [6] H. Meyerhenke, P. Sanders, and C. Schulz, ‘‘Parallel graph partitioning for complex networks,’’ IEEE Trans. Parallel Distrib. Syst., vol. 28, no. 9, pp. 2625–2638, Sep. 2017. [7] Y. Guo, S. Hong, H. Chafi, A. Iosup, and D. Epema, ‘‘Modeling, analysis, and experimental comparison of streaming graph-partitioning policies,’’ J. Parallel Distrib. Comput., vol. 108, pp. 106–121, Oct. 2017. [8] F. Rahimian, A. H. Payberah, S. Girdzijauskas, M. Jelasity, and S. Haridi, ‘‘A distributed algorithm for large-scale graph partitioning,’’ ACM Trans. Auton. Adapt. Syst., vol. 10, no. 2, pp. 12:1–12:24, Jun. 2015. [9] R. Schneider, ‘‘A solution for the partitioning problem in partition-based moving-horizon estimation,’’ IEEE Trans. Autom. Control, vol. 62, no. 6, pp. 3076–3082, Jun. 2017. [10] A. Di Nardo, M. Di Natale, C. Giudicianni, D. Musmarra, G. F. Santonastaso, and A. Simone, ‘‘Water distribution system clustering and partitioning based on social network algorithms,’’ Procedia Eng., vol. 119, pp. 196–205, Sep. 2015. [11] C. Pizzuti, ‘‘A multiobjective genetic algorithm to find communities in complex networks,’’ IEEE Trans. Evol. Comput., vol. 16, no. 3, pp. 418–430, Jun. 2012. [12] K. Tsumura and H. Yamamoto, ‘‘Optimal multiple controlling nodes problem for multi-agent systems via Alt-PageRank,’’ IFAC Proc. Volumes, vol. 46, pp. 433–438, Jan. 2013. [13] C. Ocampo-Martinez, S. Bovo, and V. Puig, ‘‘Partitioning approach oriented to the decentralised predictive control of large-scale systems,’’ J. Process Control, vol. 21, no. 5, pp. 775–786, Jun. 2011. [14] F. Tedesco, C. Ocampo-Martinez, A. Casavola, and V. Puig, ‘‘Centralized and distributed command governor approaches for water supply systems management,’’ IEEE Trans. Syst., Man, Cybern. Syst., vol. 48, no. 4, pp. 586–595, Apr. 2018. [15] A. Rahman and Z. Y. Wu, ‘‘Multistep simulation-optimization modeling approach for partitioning water distribution system into district meter areas,’’ J. Water Resour. Planning Manage., vol. 144, no. 5, pp. 04018018-1–04018018-14, May 2018. [16] J. Li, C.-C. Liu, and K. P. Schneider, ‘‘Controlled partitioning of a power network considering real and reactive power balance,’’ IEEE Trans. Smart Grid, vol. 1, no. 3, pp. 261–269, Dec. 2010. [17] A. Golshani, W. Sun, and K. Sun, ‘‘Advanced power system partitioning method for fast and reliable restoration: Toward a self-healing power grid,’’ IET Gener., Transmiss. Distrib., vol. 12, no. 1, pp. 42–52, Jan. 2018. [18] J. Anderson, Y.-C. Chang, and A. Papachristodoulou, ‘‘Model decomposition and reduction tools for large-scale networks in systems biology,’’ Automatica, vol. 47, no. 6, pp. 1165–1174, Jun. 2011. [19] A. B. Kahng, J. Lienig, I. L. Markov, and J. Hu, VLSI Physical Design: From Graph Partitioning to Timing Closure. Dordrecht, The Netherlands: Springer, 2011. [20] Z. Zhou, S. Lin, and Y. Xi, ‘‘A dynamic network partition method for heterogenous urban traffic networks,’’ in Proc. 15th Int. IEEE Conf. Intell. Transp. Syst., Anchorage, AK, USA, Sep. 2012, pp. 820–825. [21] F. J. Muros, J. M. Maestre, E. Algaba, C. Ocampo-Martinez, and E. F. Camacho, ‘‘An application of the Shapley value to perform system partitioning,’’ in Proc. 33rd Amer. Control Conf. (ACC), Chicago, IL, USA, Jul. 2015, pp. 2143–2148. [22] F. J. Muros, J. M. Maestre, E. Algaba, T. Alamo, and E. F. Camacho, ‘‘Networked control design for coalitional schemes using game-theoretic methods,’’ Automatica, vol. 78, pp. 320–332, Apr. 2017. [23] F. J. Muros, J. M. Maestre, C. Ocampo-Martinez, E. Algaba, and E. F. Camacho, ‘‘Partitioning of large-scale systems using game-theoretic coalitional methods,’’ in Proc. 16th Eur. Control Conf. (ECC), Limassol, Cyprus, Jun. 2018, pp. 2517–2522. [24] F. Fele, J. M. Maestre, and E. F. Camacho, ‘‘Coalitional control: Cooperative game theory and control,’’ IEEE Control Syst. Mag., vol. 37, no. 1, pp. 53–69, Feb. 2017. [25] D. Bauso and G. Notarstefano, ‘‘Distributed n-player approachability and consensus in coalitional games,’’ IEEE Trans. Autom. Control, vol. 60, no. 11, pp. 3107–3112, Nov. 2015. [26] R. Olfati-Saber and R. M. Murray, ‘‘Consensus problems in networks of agents with switching topology and time-delays,’’ IEEE Trans. Autom. Control, vol. 49, no. 9, pp. 1520–1533, Sep. 2004. [27] L. S. Shapley, ‘‘A value for n-person games,’’ in Contributions to the Theory of Games (Annals of Mathematics Studies), vol. 28, H. W. Kuhn and A. W. Tucker, Eds. Princeton, NJ, USA: Princeton Univ. Press, 1953, pp. 307–317. [28] J. Castro, D. Gómez, and J. Tejada, ‘‘Polynomial calculation of the Shapley value based on sampling,’’ Comput. Oper. Res., vol. 36, no. 5, pp. 1726–1730, May 2009. [29] H. Ishii and R. Tempo, ‘‘Distributed randomized algorithms for the PageRank computation,’’ IEEE Trans. Autom. Control, vol. 55, no. 9, pp. 1987–2002, Sep. 2010. [30] R. A. DeVore and V. N. Temlyakov, ‘‘Some remarks on greedy algorithms,’’ Adv. Comput. Math., vol. 5, no. 1, pp. 173–187, Dec. 1996. [31] J. Qin, Y. Chow, J. Yang, and R. Rajagopal, ‘‘Distributed online modified greedy algorithm for networked storage operation under uncertainty,’’ IEEE Trans. Smart Grid, vol. 7, no. 2, pp. 1106–1118, Mar. 2016. [32] J. M. Maestre and H. Ishii, ‘‘A PageRank based coalitional control scheme,’’ Int. J. Control, Automat. Syst., vol. 15, no. 5, pp. 1983–1990, 2017. [33] R. R. Negenborn and J. M. Maestre, ‘‘Distributed model predictive control: An overview and roadmap of future research opportunities,’’ IEEE Control Syst., vol. 34, no. 4, pp. 87–97, Aug. 2014. [34] R. L. Graham and P. Hell, ‘‘On the history of the minimum spanning tree problem,’’ Ann. History Comput., vol. 7, no. 1, pp. 43–57, 1985. [35] J. Li, X.-Y. Ma, C.-C. Liu, and K. P. Schneider, ‘‘Distribution system restoration with microgrids using spanning tree search,’’ IEEE Trans. Power Syst., vol. 29, no. 6, pp. 3021–3029, Nov. 2014. [36] H. W. Becker and J. Riordan, ‘‘The arithmetic of bell and stirling numbers,’’ Amer. J. Math., vol. 70, no. 2, pp. 385–394, Apr. 1948. [37] M. A. Brdys and B. Ulanicki, Operational Control of Water Systems: Structures Algorithms and Applications. London, U.K.: Prentice-Hall International, 1994. [38] A. K. Sampathirao, P. Sopasakis, A. Bemporad, and P. P. Patrinos, ‘‘GPU- accelerated stochastic predictive control of drinking water networks,’’ IEEE Trans. Control Syst. Technol., vol. 26, no. 2, pp. 551–562, Mar. 2018. [39] M. Girvan and M. E. J. Newman, ‘‘Community structure in social and biological networks,’’ Proc. Nat. Acad. Sci. USA, vol. 99, no. 12, pp. 7821–7826, Jun. 2002. [40] U. Brandes, ‘‘On variants of shortest-path betweenness centrality and their generic computation,’’ Soc. Netw., vol. 30, no. 2, pp. 136–145, May 2008. FRANCISCO JAVIER MUROS received the M.S. degree in telecommunications engineering from the University of Seville in 2004, the master’s degree in design, construction and maintenance of high voltage electrical transmission infrastructure from Comillas Pontifical University, Madrid, in 2014, and the Ph.D. degree (summa cum laude) in automation, robotics and telematics from the University of Seville in 2017. Between 2015 and 2016, he was a Coordinator of his master’s degree. He performed a Ph.D. stay in the Department of Data Science and Knowledge Engineering, Maastricht University, The Netherlands, in 2016. Since 2005, he has acquired a wide experience in several works related to the electricity sector. He is currently with the Department of Systems and Automation Engineering, University of Seville. He participated in the European Union Project DYMASOS and in several MINECO-Spain projects. He has authored or co-authored over 20 publications, including journal papers, book chapters, and conference papers. His research interests focus on cooperative and noncooperative game theory and coalitional and distributed control. 42262 VOLUME 6, 2018 F. J. Muros et al.: A Game Theoretical Randomized Method for LSS Partitioning JOSÉ MARÍA MAESTRE (M’14–SM’18) received the joint B.Eng. and M.Eng. degree in telecommunication engineering and the Ph.D. degree in automation and robotics from the University of Seville in 2005 and 2010, respectively, the master’s degree in smart homes and intelligent buildings from the Universidad Politécnica de Madrid, in 2006, the master’s degree in telecommunications economics from the Universidad Nacional de Educación a Distancia, in 2010, and the master’s degree in economics and development from the University of Seville, in 2016. He received the Extraordinary Prize from the University of Seville, for his Ph.D. degree. He was a Guest Researcher with the Faculty of Engineering LTH, Lund University, a Post-Doctoral Researcher with TU Delft, an Assistant Professor with the University of Cadiz, and a Visiting Professor with the Tokyo Institute of Technology. He is one of the founders of the technological firms Idener and Eskesso. He is currently an Associate Professor with the University of Seville. His main research interests are the control of distributed systems and the integration of service robots in the smart home. He has authored or co-authored over 100 conference and journal papers regarding these topics. He is an Editor of the books, Service Robotics Within the Digital Home: Applications and Future Prospects (Springer, 2011), Distributed Model Predictive Control Made Easy (Springer, 2014), and Domótica Para Ingenieros (Paraninfo, 2015). CARLOS OCAMPO-MARTINEZ (M’11–SM’13) received the B.Eng. degree in electronics and the M.Sc. degree in industrial automation from the National University of Colombia, Campus Manizales, in 2001 and 2003, respectively, and the Ph.D. degree in control engineering from the Technical University of Catalonia–BarcelonaTech, Barcelona, Spain, in 2007. Between 2014 and 2018, he was the Deputy Director of the Institut de Robòtica i Informàtica Industrial. Since 2011, he has been with the Automatic Control Department (ESAII), Universitat Politècnica de Catalunya, where he is currently an Associate Professor in automatic control and model predictive control. His main research interests include constrained model predictive control, large-scale systems management (partitioning and noncentralized control), and industrial applications (mainly related to the key scopes of water and energy). ENCARNACIÓN ALGABA received the Ph.D. degree in mathematical sciences from the University of Seville. She is currently an Associate Professor with the Department of Applied Mathematics II, Advanced Engineering School, University of Seville, where she is also a member with the Mathematics Research Institute. Her main research line is about cooperative games on combinatorial structures with relevant contributions in the area. She has been one of the Spanish representatives in the Spain, Italy, Netherlands Game Theory (SING) Committee since 2012. She was a member of the Scientific Committee in SING 10, Cracow, Poland, in 2014; the European Meeting on Game Theory SING 11-GTM 2015, St. Petersburg, Russia, in 2015; SING 12, Odense, Denmark, in 2016; SING 13, Paris, France, in 2017; and SING 14, Bayreuth, Germany, in 2018. She acted as an evaluator of projects at national and European levels. She belongs to the National Expert Evaluators Board since 2014. She organized diverse courses, streams in international conferences, and workshops on game theory. She is an invited speaker and a guest researcher in various universities. She has given invited summer courses and numerous talks in international conferences. EDUARDO F. CAMACHO (M’84–SM’00–F’11) received the Ph.D. degree in electrical engineering from the University of Seville, Seville, Spain. He is currently a Full Professor with the Department of System and Automation Engineering, University of Seville. He has authored Model Predictive Control in the Process Industry (1995), Advanced Control of Solar Plants (1997), Model Predictive Control (1999), (Springer, 2004, second edition), Control e Instrumentación de Procesos Químicos (Ed. Síntesis), Control of Dead-Time Processes (Springer, 2007), and Control of Solar Systems (Springer, 2011). He is a member of the IEEE/CSS Board of Governors. He served for various IFAC technical committees. He was the Chair of the IFAC Publication Committee from 2002 to 2005. He was the President of the European Control Association from 2005 to 2007. He was the Chair of the IEEE/CSS International Affairs Committee from 2003 to 2006. He was the Chair of the IFAC Policy Committee. He acted as an evaluator of projects at national and European levels and was appointed as the Manager of the Advanced Production Technology Program of the Spanish National Research and Development Program from 1996 to 2000. He was one of the Spanish representatives on the Program Committee of the Growth Research Program. He was an expert for the Program Committee of the NMP Research Priority of the European Union. He carried out reviews and editorial work for various technical journals and many conferences. He is currently one of the editors of the IFAC Control Engineering Practice, the Editor-at-Large of the European Journal of Control, and a Subject Editor of Optimal Control: Applications and Methods. Dr. Camacho is an IFAC Fellow. He was the Publication Chair of the IFAC World Congress in 2002, the General Chair of the joint 44th IEEE CDC-ECC in 2005, and the Co-General Chair of the joint 50th IEEE CDC-ECC in 2011. VOLUME 6, 2018 42263