liu.seSearch for publications in DiVA
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
An Algorithm for Simultaneous Coalition Structure Generation and Task Assignment
Linköpings universitet, Institutionen för datavetenskap, Artificiell intelligens och integrerade datorsystem. Linköpings universitet, Tekniska fakulteten. (KPLAB - Knowledge Processing Lab)
Linköpings universitet, Institutionen för systemteknik, Informationskodning. Linköpings universitet, Tekniska fakulteten.
Linköpings universitet, Institutionen för datavetenskap, Artificiell intelligens och integrerade datorsystem. Linköpings universitet, Tekniska fakulteten. (KPLAB - Knowledge Processing Lab)
2017 (engelsk)Inngår i: PRIMA 2017: Principles and Practice of Multi-Agent Systems 20th International Conference, Nice, France, October 30 – November 3, 2017, Proceedings / [ed] Bo An, Ana Bazzan, João Leite, Serena Villata and Leendert van der Torre, Cham: Springer, 2017, Vol. 10621, s. 514-522Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Groups of agents in multi-agent systems may have to cooperate to solve tasks efficiently, and coordinating such groups is an important problem in the field of artificial intelligence. In this paper, we consider the problem of forming disjoint coalitions and assigning them to independent tasks simultaneously, and present an anytime algorithm that efficiently solves the simultaneous coalition structure generation and task assignment problem. This NP-complete combinatorial optimization problem has many real-world applications, including forming cross-functional teams aimed at solving tasks. To evaluate the algorithm's performance, we extend established methods for synthetic problem set generation, and benchmark the algorithm using randomized data sets of varying distribution and complexity. Our results show that the presented algorithm efficiently finds optimal solutions, and generates high quality solutions when interrupted prior to finishing an exhaustive search. Additionally, we apply the algorithm to solve the problem of assigning agents to regions in a commercial computer-based strategy game, and empirically show that our algorithm can significantly improve the coordination and computational efficiency of agents in a real-time multi-agent system.

sted, utgiver, år, opplag, sider
Cham: Springer, 2017. Vol. 10621, s. 514-522
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 10621
Emneord [en]
coalition formation, task allocation, multi-agent system, artificial intelligence, optimal assignment
HSV kategori
Identifikatorer
URN: urn:nbn:se:liu:diva-141867DOI: 10.1007/978-3-319-69131-2_34ISBN: 9783319691305 (tryckt)ISBN: 9783319691312 (digital)OAI: oai:DiVA.org:liu-141867DiVA, id: diva2:1148303
Konferanse
PRIMA International Conference on Principles and Practice of Multi-Agent Systems, Nice, France, 30 October - 3 November, 2017
Tilgjengelig fra: 2017-10-10 Laget: 2017-10-10 Sist oppdatert: 2018-10-31bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Präntare, FredrikRagnemalm, IngemarHeintz, Fredrik

Søk i DiVA

Av forfatter/redaktør
Präntare, FredrikRagnemalm, IngemarHeintz, Fredrik
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 160 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf