liu.seSök publikationer i DiVA
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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 (Engelska)Ingå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-522Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Cham: Springer, 2017. Vol. 10621, s. 514-522
Serie
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 10621
Nyckelord [en]
coalition formation, task allocation, multi-agent system, artificial intelligence, optimal assignment
Nationell ämneskategori
Datavetenskap (datalogi)
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
Konferens
PRIMA International Conference on Principles and Practice of Multi-Agent Systems, Nice, France, 30 October - 3 November, 2017
Tillgänglig från: 2017-10-10 Skapad: 2017-10-10 Senast uppdaterad: 2018-10-31Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Präntare, FredrikRagnemalm, IngemarHeintz, Fredrik

Sök vidare i DiVA

Av författaren/redaktören
Präntare, FredrikRagnemalm, IngemarHeintz, Fredrik
Av organisationen
Artificiell intelligens och integrerade datorsystemTekniska fakultetenInformationskodning
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 271 träffar
RefereraExporteraLänk till posten
Permanent länk

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