Sökning: onr:"swepub:oai:DiVA.org:liu-141867" >
An Algorithm for Si...
An Algorithm for Simultaneous Coalition Structure Generation and Task Assignment
-
- Präntare, Fredrik, 1990- (författare)
- Linköpings universitet,Artificiell intelligens och integrerade datorsystem,Tekniska fakulteten,KPLAB - Knowledge Processing Lab
-
- Ragnemalm, Ingemar, 1962- (författare)
- Linköpings universitet,Informationskodning,Tekniska fakulteten
-
- Heintz, Fredrik, 1975- (författare)
- Linköpings universitet,Artificiell intelligens och integrerade datorsystem,Tekniska fakulteten,KPLAB - Knowledge Processing Lab
-
(creator_code:org_t)
- 2017-10-05
- 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. - Cham : Springer. - 9783319691305 - 9783319691312 ; , s. 514-522
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- coalition formation
- task allocation
- multi-agent system
- artificial intelligence
- optimal assignment
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas