Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Cooperative Resource Allocation in Open Systems of Systems

Published: 09 June 2015 Publication History

Abstract

Resource allocation is a common problem in many technical systems. In multi-agent systems, the decentralized or regionalized solution of this problem usually requires the agents to cooperate due to their limited resources and knowledge. At the same time, if these systems are of large scale, scalability issues can be addressed by a self-organizing hierarchical system structure that enables problem decomposition and compartmentalization. In open systems, various uncertainties—introduced by the environment as well as the agents’ possibly self-interested or even malicious behavior—have to be taken into account to be able to allocate the resources according to the actual demand.
In this article, we present a trust- and cooperation-based algorithm that solves a dynamic resource allocation problem in open systems of systems. To measure and deal with uncertainties imposed by the environment and the agents at runtime, the algorithm uses the social concept of trust. In a hierarchical setting, we additionally show how agents create constraint models by learning the capabilities of subordinate agents if these are not able or willing to disclose this information. Throughout the article, the creation of power plant schedules in decentralized autonomous power management systems serves as a running example.

References

[1]
Gerrit Anders, Christian Hinrichs, Florian Siefert, Pascal Behrmann, Wolfgang Reif, and Michael Sonnenschein. 2012. On the influence of inter-agent variation on multi-agent algorithms solving a dynamic task allocation problem under uncertainty. In Proceedings of the 2012 6th IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO’12). IEEE Computer Society, Washington, D.C., 29--38.
[2]
Gerrit Anders, Alexander Schiendorfer, Jan-Philipp Steghöfer, and Wolfgang Reif. 2014a. Robust scheduling in a self-organizing hierarchy of autonomous virtual power plants. In Proceedings of the 2014 27th International Conference on Architecture of Computing Systems (ARCS'14). 1--8.
[3]
Gerrit Anders, Florian Siefert, Michael Mair, and Wolfgang Reif. 2014b. Proactive guidance for dynamic and cooperative resource allocation under uncertainties. In Proceedings of the 2014 IEEE 8th International Conference on Self-Adaptive and Self-Organizing Systems (SASO'14). 21--30.
[4]
Gerrit Anders, Florian Siefert, Jan-Philipp Steghöfer, and Wolfgang Reif. 2014c. Trust-based scenarios—Predicting future agent behavior in open self-organizing systems. In Self-Organizing Systems, Lecture Notes in Computer Science, Vol. 8221, Wilfried Elmenreich, Falko Dressler, and Vittorio Loreto (Eds.). Springer Berlin Heidelberg, 90--102.
[5]
Gerrit Anders, Jan-Philipp Steghöfer, Florian Siefert, and Wolfgang Reif. 2013. A trust- and cooperation-based solution of a dynamic resource allocation problem. In Proceedings of the 2013 IEEE 7th International Conference on Self-Adaptive and Self-Organizing Systems (SASO'13). IEEE Computer Society, Washington, D.C., 1--10.
[6]
Alexander Artikis, Marek Sergot, and Jeremy Pitt. 2009. Specifying norm-governed computational societies. ACM Transactions on Computational Logic (TOCL) 10, 1 (2009), 1.
[7]
Sulin Ba and Paul Pavlou. 2002. Evidence of the effect of trust building technology in electronic markets: Price premiums and buyer behavior. MIS Quarterly 26, 3 (2002), 243--268.
[8]
Sulin Ba, Andrew B. Whinston, and Hang Zhang. 1999. Building trust in the electronic market through an economic incentive mechanism. In Proceedings of the 20th International Conference on Information Systems. Association for Information Systems, 208--213.
[9]
Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. 2001. A unified approach to approximating resource allocation and scheduling. Journal of the ACM (JACM) 48, 5 (2001), 1069--1090.
[10]
Atli Benonysson, Benny Bøhm, and Hans F. Ravn. 1995. Operational optimization in a district heating system. Energy Conversion and Management 36, 5 (1995), 297--314.
[11]
Marita Blank, Sebastian Gerwinn, Olav Krause, and Sebastian Lehnhoff. 2011. Support vector machines for an efficient representation of voltage band constraints. In Proceedings of the 2nd IEEE PES International Conference and Exhibition on Innovative Smart Grid Technologies (ISGT Europe). IEEE, 1--8.
[12]
Jörg Bremer, Barbara Rapp, and Michael Sonnenschein. 2011. Encoding distributed search spaces for virtual power plants. In 2011 IEEE Symposium on Computational Intelligence Applications In Smart Grid (CIASG). 1--8.
[13]
Georgios Chalkiadakis, Valentin Robu, Ramachandra Kota, Alex Rogers, and Nicholas R. Jennings. 2011. Cooperatives of distributed energy resources for efficient virtual power plants. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’11), Vol. 2. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 787--794.
[14]
Chih-Chung Chang and Chih-Jen Lin. 2011. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology 2, 3 (2011), 27:1--27:27. Software available at http://www.csie.ntu.edu.tw/∼cjlin/libsvm/.
[15]
Yann Chevaleyre, Paul E. Dunne, Ulle Endriss, Jérôme Lang, Michel Lemaître, Nicolas Maudet, Julian Padget, Steve Phelps, Juan A. Rodríguez-aguilar, and Paulo Sousa. 2006. Issues in multiagent resource allocation. Informatica 30, 1 (2006), 3--31.
[16]
Rajdeep K. Dash, Sarvapali D. Ramchurn, and Nicholas R. Jennings. 2004. Trust-based mechanism design. In Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 2. IEEE Computer Society, 748--755.
[17]
Christian Derksen, Tobias Linnenberg, Rainer Unland, and Alexander Fay. 2013. Unified energy agents as a base for the systematic development of future energy grids. In Multiagent System Technologies, Lecture Notes in Computer Science, Vol. 8076, Matthias Klusch, Matthias Thimm, and Marcin Paprzycki (Eds.). Springer, Berlin, 236--249.
[18]
Florian Dötsch, Jörg Denzinger, Holger Kasinger, and Bernhard Bauer. 2010. Decentralized real-time control of water distribution networks using self-organizing multi-agent systems. In Proceedings of the 2010 4th IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO). 223--232.
[19]
Rui He, Jianwei Niu, and Guangwei Zhang. 2005. CBTM: A trust model with uncertainty quantification and reasoning for pervasive computing. In Parallel and Distributed Processing and Applications, Yi Pan, Daoxu Chen, Minyi Guo, Jiannong Cao, and Jack Dongarra (Eds.). Lecture Notes in Computer Science, Vol. 3758. Springer, Berlin, 541--552.
[20]
Jin S. Heo, Kwang Y. Lee, and Raul Garduno-Ramirez. 2006. Multiobjective control of power plants using particle swarm optimization techniques. IEEE Transactions on Energy Conversion 21, 2 (2006), 552--561.
[21]
Christian Hinrichs, Jörg Bremer, and Michael Sonnenschein. 2013a. Distributed hybrid constraint handling in large scale virtual power plants. In Proceedings of the 2013 4th IEEE/PES Innovative Smart Grid Technologies Europe (ISGT EUROPE). 1--5.
[22]
Christian Hinrichs, Michael Sonnenschein, and Sebastian Lehnhoff. 2013b. Evaluation of a self-organizing heuristic for interdependent distributed search spaces. In Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART’13), Volume 1—Agents. SciTePress, 25--34.
[23]
Trung Dong Huynh, Nicholas R. Jennings, and Nigel R. Shadbolt. 2006. An integrated trust and reputation model for open multi-agent systems. Journal of Autonomous Agents and Multi-Agent Systems 13, 2 (2006), 119--154.
[24]
Gareth James, Daniela Witten, Trevor Hastie, and Robert Tibshirani. 2014. An Introduction to Statistical Learning: with Applications in R. Springer, New York.
[25]
Catholijn Jonker and Jan Treur. 1999. Formal analysis of models for the dynamics of trust based on experiences. In Multi-Agent System Engineering, Francisco Garijo and Magnus Boman (Eds.), Lecture Notes in Computer Science, Vol. 1647. Springer, Berlin, 221--231.
[26]
Piotr Juszczak, David M. J. Tax, and Robert P. W. Duin. 2002. Feature scaling in support vector data description. In Proceedings of the ASCI 2002 8th Annual Conference of the Advanced School for Computing and Imaging. Citeseer, 95--102.
[27]
Sarah Keung and Nathan Griffiths. 2008. Towards improved partner selection using recommendations and trust. In Trust in Agent Societies, Rino Falcone, Suzanne Barber, Jordi Sabater-Mir, and Munindar Singh (Eds.). Lecture Notes in Computer Science, Vol. 5396. Springer, Berlin, 43--64.
[28]
Rolf Kiefhaber, Gerrit Anders, Florian Siefert, Theo Ungerer, and Wolfgang Reif. 2012. Confidence as a means to assess the accuracy of trust values. In Proceedings of the IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications. IEEE Computer Society, 690--697.
[29]
Paul Klemperer. 2002. What really matters in auction design. Journal of Economic Perspectives 16, 1 (2002), 169--189.
[30]
Koen Kok, Cor Warmer, and René Kamphuis. 2005. PowerMatcher: Multiagent control in the electricity infrastructure. In Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS’05). ACM, New York, NY, 75--82.
[31]
Michael Koller. 1988. Risk as a determinant of trust. Basic and Applied Social Psychology 9, 4 (1988), 265--276.
[32]
Jiaming Li, Geoffrey Poulton, and Geoffrey James. 2010. Coordination of distributed energy resource agents. Applied Artificial Intelligence 24, 5 (2010), 351--380.
[33]
Benjamin Mack and Björn Waske. 2011. Optimizing support vector data description by automatically generating outliers. In Proceedings of the EARSeL 7th SIG-Imaging Spectroscopy Workshop.
[34]
Stephen Paul Marsh. 1994. Formalising Trust as a Computational Concept. Ph.D. dissertation. University of Stirling.
[35]
Stephen D. J. McArthur, Euan M. Davidson, Victoria M. Catterson, Aris L. Dimeas, Nikos D. Hatziargyriou, Ferdinanda Ponci, and Toshihisa Funabashi. 2007. Multi-agent systems for power engineering applications—Part I: Concepts, approaches, and technical challenges. IEEE Transactions on Power Systems 22, 4 (2007), 1743--1752.
[36]
D. Harrison McKnight, Larry L. Cummings, and Norman L. Chervany. 1998. Initial trust formation in new organizational relationships. The Academy of Management Review 23, 3 (1998), 473--490.
[37]
Thamar Mora, Abu B. Sesay, Jörg Denzinger, Hossein Golshan, Gene Poissant, and Cameron Konecnik. 2008. Cooperative search for optimizing pipeline operations. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems: Industrial Track (AAMAS’08). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 115--122. http://dl.acm.org/citation.cfm?id=1402795.1402817.
[38]
Lik Mui, Mojdeh Mohtashemi, and Ari Halberstadt. 2002. A computational model of trust and reputation. In Proceedings of the 35th Hawaii International Conference on System Sciences. 188--196.
[39]
Ming-Qing Pan, Su-Xiang Qian, Liang-Yu Lei, and Xiao-Jun Zhou. 2005. Support vector data description with model selection for condition monitoring. In Proceedings of the 2005 International Conference on Machine Learning and Cybernetics, Vol. 7. 4315--4318.
[40]
Jeremy Pitt, Julia Schaumeier, and Alexander Artikis. 2011. The axiomatisation of socio-economic principles for self-organising systems. In Proceedings of the 2011 5th IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO’11), 138--147.
[41]
Sarvapali D. Ramchurn, Trung Dong Huynh Huynh, and Nicholas R. Jennings. 2004a. Trust in multi-agent systems. The Knowledge Engineering Review 19, 01 (2004), 1--25.
[42]
Sarvapali D. Ramchurn, Nicholas R. Jennings, Carles Sierra, and Lluis Godo. 2004b. Devising a trust model for multi-agent interactions using confidence and reputation. Applied Artificial Intelligence 18, 9--10 (2004), 833--852.
[43]
Sarvapali D. Ramchurn, Perukrishnen Vytelingum, Alex Rogers, and Nicholas R. Jennings. 2012. Putting the “Smarts” into the smart grid: A grand challenge for artificial intelligence. Communications of the ACM 55, 4 (2012), 86--97.
[44]
Andrew P. Sage and Christopher D. Cuppan. 2001. On the systems engineering and management of systems of systems and federations of systems. Information, Knowledge, Systems Management 2, 4 (2001), 325--345.
[45]
Alexander Schiendorfer, Jan-Philipp Steghöfer, and Wolfgang Reif. 2014. Synthesis and abstraction of constraint models for hierarchical resource allocation problems. In Proceedings of the 6th International Conference on Agents and Artificial Intelligence (ICAART'14), Volume 2. SciTePress, 15--27.
[46]
Jan-Philipp Steghöfer, Gerrit Anders, Florian Siefert, and Wolfgang Reif. 2013a. A system of systems approach to the evolutionary transformation of power management systems. In Proceedings of INFORMATIK 2013—Workshop on “Smart Grids”, Lecture Notes in Informatics, Vol. P-220. Bonner Köllen Verlag.
[47]
Jan-Philipp Steghöfer, Pascal Behrmann, Gerrit Anders, Florian Siefert, and Wolfgang Reif. 2013b. Hi-SPADA: Self-organising hierarchies for large-scale multi-agent systems. In Proceedings of the 9th International Conference on Autonomic and Autonomous Systems (ICAS’13). IARIA.
[48]
Jan-Philipp Steghöfer, Rolf Kiefhaber, Karin Leichtenstern, Yvonne Bernard, Lukas Klejnowski, Wolfgang Reif, Theo Ungerer, Elisabeth André, Jörg Hähner, and Christian Müller-Schloer. 2010. Trustworthy organic computing systems: Challenges and perspectives. In Proceedings of the 7th International Conference on Autonomic and Trusted Computing (ATC’10), Bing Xie, Jürgen Branke, S. Sadjadi, Daqing Zhang, and Xingshe Zhou (Eds.). Lecture Notes in Computer Science, Vol. 6407. Springer, Berlin, 62--76.
[49]
David M. J. Tax and Robert P. W. Duin. 1999. Data domain description using support vectors. In Proceedings of the European Symposium on Artificial Neural Networks. 251--256.
[50]
David M. J. Tax and Robert P. W. Duin. 2004. Support vector data description. Machine Learning 54, 1 (2004), 45--66.
[51]
David M. J. Tax and Klaus-Robert Müller. 2004. A consistency-based model selection for one-class classification. In Proceedings of the 17th International Conference on Pattern Recognition (ICPR’04). Vol. 3, 363--366.
[52]
Sven Tomforde, Joerg Haehner, Hella Seebach, Wolfgang Reif, Bernhard Sick, Arno Wacker, and Ingo Scholtes. 2014. Engineering and mastering interwoven systems. In Proceedings of the 2nd International Workshop on “Self-optimisation in Organic and Autonomic Computing Systems” (SAOS’14) in conjunction with ARCS 2014, Vol. 2.
[53]
Edward Tsang. 1993. Foundations of Constraint Satisfaction. Vol. 289. Academic Press, London.
[54]
Vladimir N. Vapnik. 1995. The Nature of Statistical Learning Theory. Springer-Verlag, New York.
[55]
Asimina Vasalou and Jeremy Pitt. 2005. Reinventing forgiveness: A formal investigation of moral facilitation. In Trust Management, Peter Herrmann, Valérie Issarny, and Simon Shiu (Eds.). Lecture Notes in Computer Science, Vol. 3477. Springer, Berlin, 39--90.
[56]
Perukrishnen Vytelingum, Sarvapali D. Ramchurn, Thomas D. Voice, Alex Rogers, and Nicholas R. Jennings. 2010. Trading agents for the smart electricity grid. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, Vol. 1. International Foundation for Autonomous Agents and Multiagent Systems, 897--904.
[57]
Chi-Kai Wang, Yung Ting, Yi-Hung Liu, and G. Hariyanto. 2009. A novel approach to generate artificial outliers for support vector data description. In Proceedings of the IEEE International Symposium on Industrial Electronics (ISIE’09). 2202--2207.
[58]
Yonghong Wang and Munindar P. Singh. 2007. Formal trust model for multiagent systems. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07). Morgan Kaufmann, San Francisco, CA 1551--1556.
[59]
Horst F. Wedde. 2012. DEZENT—A cyber-physical approach for providing affordable regenerative electric energy in the near future. In Proceedings of the 2012 38th EUROMICRO Conference on Software Engineering and Advanced Applications (SEAA’12). 241--249.
[60]
David H. Wolpert. 1996. The lack of a priori distinctions between learning algorithms. Neural Computing 8, 7 (Oct. 1996), 1341--1390.
[61]
Han Yu, Zhiqi Shen, C. Leung, Chunyan Miao, and V. R. Lesser. 2013. A survey of multi-agent trust management systems. IEEE Access 1 (2013), 35--50.
[62]
Ascensión Zafra-Cabeza, Miguel A. Ridao, Ignacio Alvarado, and Eduardo F. Camacho. 2008. Applying risk management to combined heat and power plants. IEEE Transactions on Power Systems 23, 3 (2008), 938--945.

Cited By

View all
  • (2023)A Genetic Programming-based Framework for Semi-automated Multi-agent Systems EngineeringACM Transactions on Autonomous and Adaptive Systems10.1145/358473118:2(1-30)Online publication date: 28-May-2023
  • (2021)Forming Multi-agents Collaborative Communities in Overlapping Communities2021 4th International Conference on Robotics, Control and Automation Engineering (RCAE)10.1109/RCAE53607.2021.9638948(114-120)Online publication date: 4-Nov-2021
  • (2019)Requirements Based Design of Environmental System of Systems: Development and Application of a Nexus Design FrameworkSustainability10.3390/su1112346411:12(3464)Online publication date: 24-Jun-2019
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Autonomous and Adaptive Systems
ACM Transactions on Autonomous and Adaptive Systems  Volume 10, Issue 2
June 2015
175 pages
ISSN:1556-4665
EISSN:1556-4703
DOI:10.1145/2790463
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2015
Accepted: 01 October 2014
Revised: 01 July 2014
Received: 01 March 2014
Published in TAAS Volume 10, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Resource allocation problem
  2. constraint satisfaction optimization
  3. electronic markets
  4. open multiagent systems
  5. smart grids
  6. systems of systems
  7. trust
  8. uncertainty

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

  • research unit OC-Trust (FOR 1085) of the German Research Foundation

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)12
  • Downloads (Last 6 weeks)1
Reflects downloads up to 21 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2023)A Genetic Programming-based Framework for Semi-automated Multi-agent Systems EngineeringACM Transactions on Autonomous and Adaptive Systems10.1145/358473118:2(1-30)Online publication date: 28-May-2023
  • (2021)Forming Multi-agents Collaborative Communities in Overlapping Communities2021 4th International Conference on Robotics, Control and Automation Engineering (RCAE)10.1109/RCAE53607.2021.9638948(114-120)Online publication date: 4-Nov-2021
  • (2019)Requirements Based Design of Environmental System of Systems: Development and Application of a Nexus Design FrameworkSustainability10.3390/su1112346411:12(3464)Online publication date: 24-Jun-2019
  • (2019)Using Social Dependence to Enable Neighbourly Behaviour in Open Multi-Agent SystemsACM Transactions on Intelligent Systems and Technology10.1145/331940210:3(1-31)Online publication date: 22-Apr-2019
  • (2019)On learning in collective self-adaptive systemsProceedings of the 14th International Symposium on Software Engineering for Adaptive and Self-Managing Systems10.1109/SEAMS.2019.00012(13-24)Online publication date: 25-May-2019
  • (2018)Multipotent Systems: Combining Planning, Self-Organization, and Reconfiguration in Modular Robot EnsemblesSensors10.3390/s1901001719:1(17)Online publication date: 20-Dec-2018
  • (2017)Facilitating Planning by Using Self-Organization2017 IEEE 2nd International Workshops on Foundations and Applications of Self* Systems (FAS*W)10.1109/FAS-W.2017.178(371-374)Online publication date: Sep-2017
  • (2017)ApplicationsOrganic Computing – Technical Systems for Survival in the Real World10.1007/978-3-319-68477-2_8(429-547)Online publication date: 28-Dec-2017
  • (2016)Trust as Important Factor for Building Robust Self-x SystemsTrustworthy Open Self-Organising Systems10.1007/978-3-319-29201-4_6(153-183)Online publication date: 21-Jun-2016
  • (2016)Specification and Design of Trust-Based Open Self-Organising SystemsTrustworthy Open Self-Organising Systems10.1007/978-3-319-29201-4_2(17-54)Online publication date: 21-Jun-2016
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media