Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Simultaneous coalition formation and task assignment in a real-time strategy game
Linköping University, Department of Computer and Information Science, Artificial Intelligence and Integrated Computer Systems.
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2017. , p. 65
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-139210ISRN: LIU-IDA/LITH-EX-A--17/032--SEOAI: oai:DiVA.org:liu-139210DiVA, id: diva2:1119823
External cooperation
Paradox Development Studio
Subject / course
Computer science
Presentation
2017-06-15, Herbert Simon, Linköping, 16:15 (English)
Supervisors
Examiners
Available from: 2017-12-22 Created: 2017-07-05 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

fulltext(4906 kB)457 downloads
File information
File name FULLTEXT01.pdfFile size 4906 kBChecksum SHA-512
42d4de9816adf8947d298df30e94230ef96be942fc35bb185d1e6f0085d1bb968d1099bc5d1e79c2121c4ce63554163b1909aa10d7e9276e3935f8308baa3103
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Präntare, Fredrik
By organisation
Artificial Intelligence and Integrated Computer Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 457 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 2719 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf