Decentralized Coalition Formation with Agent-based Combinatorial Heuristics


A steadily growing pervasion of the energy distribution grid with communication technology is widely seen as an enabler for new computational coordination techniques for renewable, distributed generation as well as for bundling with controllable consumers. Smart markets will foster a decentralized grid management. One important task as prerequisite to decentralized management is the ability to group together in order to jointly gain enough suitable flexibility and capacity to assume responsibility for a specific control task in the grid. In self-organized smart grid scenarios, grouping or coalition formation has to be achieved in a decentralized and situation aware way based on individual capabilities. We present a fully decentralized coalition formation approach based on an established agent-based heuristics for predictive scheduling with the additional advantage of keeping all information about local decision base and local operational constraints private. Two closely interlocked optimization processes orchestrate an overall procedure that adapts a coalition structure to best suit a given set of energy products. The approach is evaluated in several simulation scenarios with different type of established models for integrating distributed energy resources and is also extended to the induced use case of surplus distribution using basically the same algorithm.
  • Referencias
  • Cómo citar
  • Del mismo autor
  • Métricas
Abarrategui, O., Marti, J., and Gonzalez, A., 2009. Constructing the Active European Power Grid. In Proceedings of WCPEE09. Cairo.

Awerbuch, S. and Preston, A. M., editors, 1997. The Virtual Utility: Accounting, Technology & Competitive Aspects of the Emerging Industry, volume 26 of Topics in Regulatory Economics and Policy. Kluwer Academic Publishers. ISBN 0-7923-9902-1.

Bachrach, Y., Markakis, E., Procaccia, A. D., Rosenschein, J. S., and Saberi, A., 2008. Approximating power indices. In Padgham, L., Parkes, D. C., Müller, J. P., and Parsons, S., editors, 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), Estoril, Portugal, May 12-16, 2008, Volume 2, pp. 943–950. IFAAMAS. ISBN 978-0-9817381-1-6.

Bazzan, A. and de O. Ramos, G., 2015. Forming Coalitions of Electric Vehicles ina?Constrained Scenarios. In Bajo, J., Hallenborg, K., Pawlewski, P., Botti, V., Sánchez-Pi, N., Duque Meléndez, N. D., Lopes, F., and Julian, V., editors, Highlights of Practical Applications of Agents, Multi-Agent Systems, and Sustainability - The PAAMS Collection, volume 524 of Communications in Computer and Information Science, pp. 237–248. Springer International Publishing. ISBN 978-3-319-19032-7. doi:10.1007/978-3-319-19033-4_20.

Beer, S. and Appelrath, H.-J., 2013. A formal model for agent-based Coalition Formation in Electricity Markets. In Innovative Smart Grid Technologies Europe (IEEE ISGT EUROPE), pp. 1-5. doi:10.1109/ISGTEurope. 2013.6695442.

Bistaffa, F., Farinelli, A., Vinyals, M., and Rogers, A., 2012. Decentralised Stable Coalition Formation Among Energy Consumers in the Smart Grid (Demonstration). In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 3, AAMAS’12, pp. 1461–1462. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC. ISBN 0-9817381-3-3, 978-0-9817381-3-0.

Bremer, J. and Lehnhoff, S., 2016. Decentralized Coalition Formation in Agent-Based Smart Grid Applications. In Highlights of Practical Applications of Scalable Multi-Agent Systems. The PAAMS Collection, volume 616 of Communications in Computer and Information Science, pp. 343–355. Springer. ISBN 978-3-319-39386-5.

Bremer, J., Rapp, B., and Sonnenschein, M., 2010. Support Vector based Encoding of Distributed Energy Resources’ Feasible Load Spaces. In IEEE PES Conference on Innovative Smart Grid Technologies Europe. Chalmers Lindholmen, Gothenburg, Sweden.

Bremer, J. and Sonnenschein, M., 2013a. Constraint-handling for Optimization with Support Vector Surrogate Models - A Novel Decoder Approach. In Filipe, J. and Fred, A., editors, ICAART 2013 - Proceedings of the 5th International Conference on Agents and Artificial Intelligence, volume 2, pp. 91–105. SciTePress, Barcelona, Spain. ISBN 978-989-8565-38-9.

Bremer, J. and Sonnenschein, M., 2013b. Estimating Shapley Values for Fair Profit Distribution in Power Planning Smart Grid Coalitions. In Klusch, M., Thimm, M., and Paprzycki, M., editors, Multiagent System Technologies, volume 8076 of Lecture Notes in Computer Science, pp. 208–221. Springer Berlin Heidelberg. ISBN 978-3-642-40775-8. doi:10.1007/978-3-642-40776-5_19.

Bremer, J. and Sonnenschein, M., 2013c. Sampling the Search Space of Energy Resources for Self-organized, Agent-based Planning of Active Power Provision. In Page, B., Fleischer, A. G., Göbel, J., and Wohlgemuth, V., editors, 27th International Conference on Environmental Informatics for Environmental Protection, EnviroInfo 2013, pp. 214–222. Shaker.

Champsaur, P., 1975. How to share the cost of a public good? International Journal of Game Theory, 4:113–129. ISSN 0020-7276. doi:10.1007/BF01780629.

Deng, X. and Papadimitriou, C. H., 1994. On the complexity of cooperative solution concepts. Math. Oper. Res., 19(2):257–266. ISSN 0364-765X. doi:10.1287/moor.19.2.257.

European Parliament & Council, 2009. Directive 2009/28/EC of 23 April 2009 on the promotion of the use of energy from renewable sources and amending and subsequently repealing Directives 2001/77/EC and 2003/30/EC.

Fatima, S. S., Wooldridge, M., and Jennings, N. R., 2008. A linear approximation method for the Shapley value. Artif. Intell., 172(14):1673–1699.

Friedman, E. and Moulin, H., 1999. Three Methods to Share Joint Costs or Surplus. Journal of Economic Theory, 87(2):275–312.

Gensollen, N., Becker, M., Gauthier, V., and Marot, M., 2015. Coalition formation algorithm of prosumers in a smart grid environment. In 2015 IEEE International Conference on Communications, ICC 2015, London, United Kingdom, June 8-12, 2015, pp. 5896–5902. IEEE. doi:10.1109/ICC.2015.7249262.

Hinrichs, C., 2014. Selbstorganisierte Einsatzplanung dezentraler Akteure im Smart Grid. Ph.D. thesis, Carl von Ossietzky Universität Oldenburg. doi:10.13140/2.1.1792.0008.

Hinrichs, C., Bremer, J., and Sonnenschein, M., 2013a. Distributed Hybrid Constraint Handling in Large Scale Virtual Power Plants. In IEEE PES Conference on Innovative Smart Grid Technologies Europe (ISGT Europe 2013). IEEE Power & Energy Society. doi:10.1109/ISGTEurope.2013.6695312.

Hinrichs, C., Lehnhoff, S., and Sonnenschein, M., 2014. A Decentralized Heuristic for Multiple-Choice Combinatorial Optimization Problems. In Operations Research Proceedings 2012, pp. 297–302. Springer. ISBN 978-3-319-00795-3. ISSN 0721-5924. doi:10.1007/978-3-319-00795-3_43.

Hinrichs, C., Sonnenschein, M., and Lehnhoff, S., 2013b. Evaluation of a Self-Organizing Heuristic for Interdependent Distributed Search Spaces. In Filipe, J. and Fred, A. L. N., editors, International Conference on Agents and Artificial Intelligence (ICAART 2013), volume Volume 1 - Agents, pp. 25–34. SciTePress. ISBN 978-989-8565-38-9. doi:10.5220/0004227000250034.

Hsu, M.-C. and Soo, V.-W., 2009. Fairness in Cooperating Multi-agent Systems - Using Profit Sharing as an Example. In Lukose, D. and Shi, Z., editors, Multi-Agent Systems for Society, pp. 153–162. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-642-03337-7. doi:10.1007/978-3-642-03339-1\_13.

Kahan, J. and Rapoport, A., 1984. Theories of coalition formation. Basic Studies in Human Behavior. L. Erlbaum Associates. ISBN 9780898592986.

Kamphuis, R., Warmer, C., Hommelberg, M., and Kok, K., 2007. Massive Coordination of Dispersed Generation using Powermatcher based Software Agents. In 19th International Conference on Electricity Distribution. Karaboga, D. and Basturk, B., 2007. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization, 39(3):459–471. doi:10.1007/s10898-007-9149-x.

Leech, D., 2003. Computing Power Indices for Large Voting Games. Management Science, 49(6):831–837. Liben-Nowell, D., Sharp, A., Wexler, T., and Woods, K., 2012. Computing Shapley Value in Supermodular

Coalitional Games. In Gudmundsson, J., Mestre, J., and Viglas, T., editors, COCOON, volume 7434 of Lecture Notes in Computer Science, pp. 568–579. Springer. ISBN 978-3-642-32240-2.

Lima, J., Pereira, M., and Pereira, J., 1995. An Integrated Framework For Cost Allocation In A Multi-Owned Transmission-System. IEEE Transactions On Power Systems, 10(2):971–977.

Lust, T. and Teghem, J., 2010. The multiobjective multidimensional knapsack problem: a survey and a new approach. CoRR, abs/1007.4063.

Ma, R., Chiu, D., Lui, J., Misra, V., and Rubenstein, D., 2007. Internet economics: the use of Shapley value for ISP settlement. In Proceedings of the 2007 ACM CoNEXT conference, CoNEXT ’07, pp. 6:1–6:12. ACM, New York, NY, USA. ISBN 978-1-59593-770-4. doi:10.1145/1364654.1364662.

Mann, I. and Shapley, L., 1960. Values of Large Games, IV: Evaluating the Electoral College by Montecarlo Techniques. Technical report, Santa Monica, CA: RAND Corporation.

Mas-Colell, A., 1980. Remarks on the game-theoretic analysis of a simple distribution of surplus problem.International Journal of Game Theory, 9:125–140. ISSN 0020-7276. doi:10.1007/BF01781368.

Mas-Colell, A., Whinston, M. D., and Green, J. R., 1995. Microeconomic Theory. Oxford University Press.ISBN 0195073401.

Matsui, Y. and Matsui, T., 2001. NP-completeness for calculating power indices of weighted majority games.Theor. Comput. Sci., 263(1-2):306–310. ISSN 0304-3975.

Neugebauer, J., Kramer, O., and Sonnenschein, M., 2015. Classification Cascades of Overlapping Feature Ensembles for Energy Time Series Data. In Proceedings of the 3rd International Workshop on Data Analytics for Renewable Energy Integration (DARE’15). Springer.

Nieße, A., Beer, S., Bremer, J., Hinrichs, C., Lünsdorf, O., and Sonnenschein, M., 2014. Conjoint dynamic aggrgation and scheduling for dynamic virtual power plants. In Ganzha, M., Maciaszek, L. A., and Paprzycki, M., editors, Federated Conference on Computer Science and Information Systems - FedCSIS 2014, Warsaw, Poland.

Nieße, A., Lehnhoff, S., Tröschel, M., Uslar, M., Wissing, C., Appelrath, H. J., and Sonnenschein, M., 2012. Market-based self-organized provision of active power and ancillary services: An agent-based approach for Smart Distribution Grids. In Complexity in Engineering (COMPENG), 2012, pp. 1-5. doi:10.1109/ CompEng.2012.6242953.

Nieße, A. and Sonnenschein, M., 2015. A Fully Distributed Continuous Planning Approach for Decentralized Energy Units. In Cunningham, D. W., Hofstedt, P., Meer, K., and Schmitt, I., editors, Informatik 2015. GI-Edition - Lecture Notes in Informatics (LNI), volume 246, pp. 151–165. Bonner Köllen Verlag. ISBN ISBN 978-3-88579-640-4.

Owen, G., 1972. Multilinear extension of games. Management Science, 18(5-Part-2):64–79.

Poli, R., Kennedy, J., and Blackwell, T., 2007. Particle swarm optimization. Swarm Intelligence, 1(1):33–57. ISSN 1935-3812. doi:10.1007/s11721-007-0002-0.

Rahwan, T., Michalak, T. P., Wooldridge, M., and Jennings, N. R., 2015. Coalition structure generation: A survey. Artificial Intelligence, 229:139–174. ISSN 0004-3702. doi: Rahwan, T., Ramchurn, S. D., Jennings, N. R., and Giovannucci, A., 2014. An Anytime Algorithm for Optimal Coalition Structure Generation. CoRR, abs/1401.3466.

Ramchurn, S. D., Vytelingum, P., Rogers, A., and Jennings, N. R., 2011. Agent-based Homeostatic Control for Green Energy in the Smart Grid. ACM Trans. Intell. Syst. Technol., 2(4):35:1–35:28. ISSN 2157-6904. doi:10.1145/1989734.1989739.

Ramchurn, S. D., Vytelingum, P., Rogers, A., and Jennings, N. R., 2012. Putting the ’Smarts’ into the Smart Grid: A Grand Challenge for Artificial Intelligence. Commun. ACM, 55(4):86–97. ISSN 0001-0782. doi:10.1145/2133806.2133825.

Rapoport, A., 1970. N-person game theory. Concepts and applications. Ann Arbor science library. Univ. of Michigan Pr. ISBN 9780486414553.

Saad, W., Han, Z., Poor, H. V., and Basar, T., 2012. Game Theoretic Methods for the Smart Grid. CoRR, abs/1202.0452.

Sen, A. K., 1966. Labour Allocation in a Cooperative Enterprise. The Review of Economic Studies, 33(4):pp. 361–371. ISSN 00346527.

Shapley, L. S., 1953. A value for n-person games. Contributions to the theory of games, 2:307–317. Sonnenschein, M., Appelrath, H.-J., Canders, W.-R., Henke, M., Uslar, M., Beer, S., Bremer, J., Lünsdorf, O., Nieße, A., Psola, J.-H. et al., 2015a. Decentralized Provision of Active Power. In Smart Nord - Final Report. Hartmann GmbH, Hannover.

Sonnenschein, M., Hinrichs, C., Nieße, A., and Vogel, U., 2015b. Supporting Renewable Power Supply Through Distributed Coordination of Energy Resources. In Hilty, L. M. and Aebischer, B., editors, ICT Innovations for Sustainability, volume 310 of Advances in Intelligent Systems and Computing, pp. 387–404. Springer International Publishing. ISBN 978-3-319-09227-0. doi:10.1007/978-3-319-09228-7_23.

Valiant, L. G., 1979. The Complexity of Computing the Permanent. Theor. Comput. Sci., 8:189-201.

Vinyals, M., Bistaffa, A., Farinelli, A., and Rogers, A., 2012. Stable Coalition formation among energy consumers in the Smart Grid. Proceedings of the 3th International Workshop on Agent Technologies for Energy Systems (ATES 2012), pp. 73–80.

Watts, D. and Strogatz, S., 1998. Collective dynamics of ’small-world’ networks. Nature, 393(6684):440-442. Zlotkin, G. and Rosenschein, J. S., 1994. Coalition, Cryptography, and Stability: Mechanisms for Coalition Formation in Task Oriented Domains. In Proceedings of the Eleventh National Conference on Artificial Intelligence, pp. 32–437. AAAI Press.
Bremer, J., & Lehnhoff, S. (2017). Decentralized Coalition Formation with Agent-based Combinatorial Heuristics. ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal, 6(3), 29–44.


Download data is not yet available.