liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Präntare, Fredrik
Publications (2 of 2) Show all publications
Präntare, F. & Heintz, F. (2018). An Anytime Algorithm for Simultaneous Coalition Structure Generation and Assignment. In: Tim Miller, Nir Oren, Yuko Sakurai, Itsuki Noda, Bastin Tony Roy Savarimuthu and Tran Cao Son (Ed.), PRIMA 2018: Principles and Practice of Multi-Agent Systems: 21st International Conference, Tokyo, Japan, October 29-November 2, 2018, Proceedings. Paper presented at PRIMA 2018: Principles and Practice of Multi-Agent Systems: 21st International Conference, Tokyo, Japan, October 29-November 2, 2018 (pp. 158-174). Cham, 11224
Open this publication in new window or tab >>An Anytime Algorithm for Simultaneous Coalition Structure Generation and Assignment
2018 (English)In: PRIMA 2018: Principles and Practice of Multi-Agent Systems: 21st International Conference, Tokyo, Japan, October 29-November 2, 2018, Proceedings / [ed] Tim Miller, Nir Oren, Yuko Sakurai, Itsuki Noda, Bastin Tony Roy Savarimuthu and Tran Cao Son, Cham, 2018, Vol. 11224, p. 158-174Conference paper, Published paper (Refereed)
Abstract [en]

A fundamental problem in artificial intelligence is how to organize and coordinate agents to improve their performance and skills. In this paper, we consider simultaneously generating coalitions of agents and assigning the coalitions to independent tasks, and present an anytime algorithm for the simultaneous coalition structure generation and assignment problem. This optimization problem has many real-world applications, including forming goal-oriented teams of agents. To evaluate the algorithm’s performance, we extend established methods for synthetic problem set generation, and benchmark the algorithm against CPLEX using randomized data sets of varying distribution and complexity. We also apply the algorithm to solve the problem of assigning agents to regions in a major commercial strategy game, and show that the algorithm can be utilized in game-playing to coordinate smaller sets of agents in real-time.

Place, publisher, year, edition, pages
Cham: , 2018
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 11224Lecture notes in artificial intelligence ; 11224
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-152438 (URN)10.1007/978-3-030-03098-8_10 (DOI)9783030030971 (ISBN)9783030030988 (ISBN)
Conference
PRIMA 2018: Principles and Practice of Multi-Agent Systems: 21st International Conference, Tokyo, Japan, October 29-November 2, 2018
Available from: 2018-10-31 Created: 2018-10-31 Last updated: 2018-11-20
Präntare, F., Ragnemalm, I. & Heintz, F. (2017). An Algorithm for Simultaneous Coalition Structure Generation and Task Assignment. In: Bo An, Ana Bazzan, João Leite, Serena Villata and Leendert van der Torre (Ed.), PRIMA 2017: Principles and Practice of Multi-Agent Systems 20th International Conference, Nice, France, October 30 – November 3, 2017, Proceedings: . Paper presented at PRIMA International Conference on Principles and Practice of Multi-Agent Systems, Nice, France, 30 October - 3 November, 2017 (pp. 514-522). Cham: Springer, 10621
Open this publication in new window or tab >>An Algorithm for Simultaneous Coalition Structure Generation and Task Assignment
2017 (English)In: 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, p. 514-522Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
Cham: Springer, 2017
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 10621
Keywords
coalition formation, task allocation, multi-agent system, artificial intelligence, optimal assignment
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-141867 (URN)10.1007/978-3-319-69131-2_34 (DOI)9783319691305 (ISBN)9783319691312 (ISBN)
Conference
PRIMA International Conference on Principles and Practice of Multi-Agent Systems, Nice, France, 30 October - 3 November, 2017
Available from: 2017-10-10 Created: 2017-10-10 Last updated: 2018-10-31Bibliographically approved
Organisations

Search in DiVA

Show all publications