I projektet studerar vi hur man sätter samman grupper av agenter och tilldelar dem uppgifter som de ska lösa så att alla uppgifter utförs så bra och effektivt som möjligt. Våra algoritmer har exempelvis testats på strategispel.

Koalitioner formas och uppgifter allokerasEtt fundamentalt problem inom artificiell intelligens är hur man organiserar och koordinerar olika agenter för att förbättra deras prestation och förmåga. Detta är ett optimeringsproblem med många tillämpningar, exempelvis för att skapa arbetslag som utför specifika uppgifter.

Vi har tagit fram flera nya algoritmer som löser problemet. För att utvärdera algoritmerna har vi utökat etablerade metoder för att generera tester för den här typen av system, vi har även jämfört algoritmerna på syntetisk data som varierar både i hur den ser ut och hur komplex den är. Vi har bland annat använt algoritmerna i ett kommersiellt strategispel och har kunnat visa att algoritmer kan användas i spel för att koordinera grupper av agenter i realtid.

Algoritmerna har använts i ett kommersiellt dataspel

Forskare

Publikationer

2026

Fredrik Präntare, Leif Eriksson, George Osipov, Fredrik Heintz, Peter Jonsson (2026) Concise representations and complexity results for welfare-maximizing combinatorial assignment Autonomous Agents and Multi-Agent Systems, Vol. 40, Artikel 30 (Artikel i tidskrift) https://dx.doi.org/10.1007/s10458-026-09753-9

2024

Fredrik Präntare (2024) Dividing the Indivisible: Algorithms, Empirical Advances, and Complexity Results for Value-Maximizing Combinatorial Assignment Problems (Doktorsavhandling, monografi) https://dx.doi.org/10.3384/9789180756013

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, s. 11317-11324 (Konferensbidrag) https://dx.doi.org/10.1609/aaai.v35i13.17349
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, s. 19-33 (Konferensbidrag) https://dx.doi.org/10.1007/978-3-030-69322-0_2

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 Trustworthy AI - Integrating Learning, Optimization and Reasoning: First International Workshop, TAILOR 2020, Virtual Event, September 4–5, 2020, Revised Selected Papers, s. 104-111 (Konferensbidrag) https://dx.doi.org/10.1007/978-3-030-73959-1_10
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), s. 1251-1254 (Konferensbidrag) https://dx.doi.org/10.1109/ETFA46521.2020.9211980
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, Artikel 29 (Artikel i tidskrift) https://dx.doi.org/10.1007/s10458-020-09450-1

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, s. 158-174 (Konferensbidrag) https://dx.doi.org/10.1007/978-3-030-03098-8_10

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, s. 514-522 (Konferensbidrag) https://dx.doi.org/10.1007/978-3-319-69131-2_34

WASP forskning