In this project, we consider simultaneously generating coalitions of agents and assigning the coalitions to independent tasks. This optimization problem has many real-world applications, including forming goal-oriented teams of agents.

Simultaneous coalition generation and task assignmentA fundamental problem in artificial intelligence is how to organize and coordinate agents to improve their performance and skills.  

We have developed several state-of-the-art-algorithms to solve the problem. To evaluate the algorithms’ performance, we extend established methods for synthetic problem set generation, and benchmark the algorithm using randomized data sets of varying distribution and complexity. We also apply the algorithm to solve real problems in a major commercial strategy game, and show that the algorithm can be utilized in game-playing to coordinate groups of agents in real-time.

The algorithm solves real problems in a major commercial strategy game

Researchers

Publications

2021

Fredrik Präntare, Herman Appelgren, Fredrik Heintz (2021) Anytime Heuristic and Monte Carlo Methods for Large-Scale Simultaneous Coalition Structure Generation and Assignment THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, p. 11317-11324 Continue to DOI
Fredrik Präntare, Fredrik Heintz (2021) Hybrid Dynamic Programming for Simultaneous Coalition Structure Generation and Assignment PRIMA 2020: Principles and Practice of Multi-Agent Systems: 23rd International Conference, Nagoya, Japan, November 18–20, 2020, Proceedings, p. 19-33 Continue to DOI

2020

Fredrik Präntare, Mattias Tiger, David Bergström, Herman Appelgren, Fredrik Heintz (2020) Towards Utilitarian Combinatorial Assignment with Deep Neural Networks and Heuristic Algorithms
Veronika Domova, Erik Gärtner, Fredrik Präntare, Martin Pallin, Johan Källström, Nikita Korzhitskii (2020) Improving Usability of Search and Rescue Decision Support Systems: WARA-PS Case Study In proceedings of the 2020 25th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), p. 1251-1254 Continue to DOI
Fredrik Präntare, Fredrik Heintz (2020) An anytime algorithm for optimal simultaneous coalition structure generation and assignment Autonomous Agents and Multi-Agent Systems, Vol. 34, Article 29 Continue to DOI

2018

Fredrik Präntare, Fredrik Heintz (2018) An Anytime Algorithm for Simultaneous Coalition Structure Generation and Assignment PRIMA 2018: Principles and Practice of Multi-Agent Systems: 21st International Conference, Tokyo, Japan, October 29-November 2, 2018, Proceedings, p. 158-174 Continue to DOI

2017

Fredrik Präntare, Ingemar Ragnemalm, Fredrik Heintz (2017) An Algorithm for Simultaneous Coalition Structure Generation and Task Assignment PRIMA 2017: Principles and Practice of Multi-Agent Systems 20th International Conference, Nice, France, October 30 – November 3, 2017, Proceedings, p. 514-522 Continue to DOI

More WASP research