In this thesis we present an algorithm that is designed to improve the collaborative capabilities of agents that operate in real-time multi-agent systems. Furthermore, we study the coalition formation and task assignment problems in the context of real-time strategy games. More specifically, we design and present a novel anytime algorithm for multi-agent cooperation that efficiently solves the simultaneous coalition formation and assignment problem, in which disjoint coalitions are formed and assigned to independent tasks simultaneously. This problem, that we denote the problem of collaboration formation, is a combinatorial optimization problem that has many real-world applications, including assigning disjoint groups of workers to regions or tasks, and forming cross-functional teams aimed at solving specific problems.

The algorithm's performance is evaluated using randomized artificial problems sets of varying complexity and distribution, and also using Europa Universalis 4 – a commercial strategy game in which agents need to cooperate in order to effectively achieve their goals. The agents in such games are expected to decide on actions in real-time, and it is a difficult task to coordinate them. Our algorithm, however, solves the coordination problem in a structured manner.

The results from the artificial problem sets demonstrates that our algorithm efficiently solves the problem of collaboration formation, and does so by automatically discarding suboptimal parts of the search space. For instance, in the easiest artificial problem sets with 12 agents and 8 tasks, our algorithm managed to find optimal solutions after only evaluating approximately 0.000003% of the possible solutions. In the hardest of the problem sets with 12 agents and 8 tasks, our algorithm managed to find a 80% efficient solution after only evaluating approximately 0.000006% of the possible solutions.

I denna uppsats presenteras en ny algoritm som är designad för att förbättra samarbetsförmågan hos agenter som verkar i realtidssystem. Vi studerar även koalitionsbildnings- och uppgiftstilldelningsproblemen inom realtidsstrategispel, och löser dessa problem optimalt genom att utveckla en effektiv anytime-algoritm som löser det kombinerade koalitionsbildnings- och uppgiftstilldelningsproblemet, inom vilket disjunkta koalitioner formas och tilldelas uppgifter. Detta problem, som vi kallar samarbetsproblemet, är en typ av optimeringsproblem som har många viktiga motsvarigheter i verkligheten, exempelvis för skapandet av arbetsgrupper som skall lösa specifika problem, eller för att ta fram optimala tvärfunktionella team med tilldelade uppgifter.

Den presenterade algoritmens prestanda utvärderas dels genom att använda simulerade problem av olika svårighetsgrad, men också genom att använda verkliga problembeskrivningar från det kommersiella strategispelet Europa Universalis 4, vilket är ett spel som agenter måste samarbeta i för att effektivt uppnå deras mål. Att koordinera agenter i sådana spel är svårt, men vår algoritm åstadkommer detta genom att systematiskt söka efter de optimala agentgrupperingarna för ett antal givna uppgifter.

Resultaten från de simulerade problemen visar att vår algoritm effektivt löser samarbetsproblemet genom att systematiskt sålla bort suboptimala delar av sökrymden. I dessa tester lyckas vår algoritm generera högkvalitativa anytime-lösningar. Till exempel, i de enklaste problemen med 12 agenter och 8 uppgifter lyckas vår algoritm hitta den optimala lösningen efter det att den endast utvärderat 0.000003% av de möjliga lösningarna. I de svåraste problemen med 12 agenter och 8 uppgifter lyckas vår algoritm hitta en lösning som är 80% från den optimala lösningen efter det att den endast utvärderat 0.000006% av de möjliga samarbetsstrukturerna.