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
Investigating the Epistemic Unfolding of Multi-Player Games of Imperfect Information
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Utredning av den epistemiska utvecklingen av flerspelarspel med ofullständig information (Swedish)
Abstract [en]

Solving multi-agent planning problems entails finding strategies that ensure that the agents achieve their cooperative objective. In practice, since the agents do not necessarily have perfect knowledge, these planning problems may involve imperfect information. For example, a robot agent may have a damaged or imperfect sensor, or one agent may be in another room and therefore cannot see what the other agents can. A useful model for these problems are cooperative multi-player games of imperfect information. In this paper, we investigate a novel construction known as epistemic unfolding. Epistemic unfolding translates multi-player games of imperfect information to single-player games of perfect information, for which strategy synthesis is much easier. Essentially, the idea of epistemic unfolding is to track the knowledge of the players throughout the duration of the game. Although epistemic unfolding is previously defined, to our knowledge it had neither been implemented nor properly visualized. In order to provide a foundation for future research, we implemented epistemic unfolding as a tool, visualized a set of epistemically unfolded games, and, finally, developed an intuitive understanding of epistemically unfolded games.

Abstract [sv]

Att lösa planeringsproblem med flera agenter medför att hitta strategier som garanterar att agenterna uppnår deras gemensamma mål. Eftersom agenterna inte nödvändigtvis har perfekt kunskap om spelets utveckling kommer dessa planeringsproblem innefatta ofullständig information. Till exempel kan en robotagent ha en skadad eller imperfekt sensor, eller kan någon agent befinna sig i ett annat rum och därmed inte se vad de andra kan. En lämplig modell för dessa problem är kooperativa flerspelarspel med ofullständig information. I denna text utreder vi en hittills outredd konstruktion känd som epistemisk utveckling. Idén bakom epistemisk utveckling är väsentligen att följa spelarnas kunskap under ett spel. Fast epistemisk utveckling redan är en definierad metod, har metoden inte till vår kunskap någonsin implementerats eller ordentligt visualiserats. För att förse en grund till vidare forskning implenterade vi epistemisk utveckling som ett verktyg, visualiserade vi de epistemiska utvecklingarna av en samling spel, och slutligen utarbetade vi en intuitiv förståelse för epistemiskt utvecklade spel.

Place, publisher, year, edition, pages
2019.
Series
TRITA-EECS-EX ; 2019:329
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-255163OAI: oai:DiVA.org:kth-255163DiVA, id: diva2:1338771
Subject / course
Computer and Systems Sciences
Supervisors
Examiners
Available from: 2019-07-29 Created: 2019-07-24 Last updated: 2019-07-29Bibliographically approved

Open Access in DiVA

fulltext(1110 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 1110 kBChecksum SHA-512
52b377ccf46b9a491d6187185dc852690b52d469da3476afc0ac29bd211712ba5de4e6c381e54345d0a0fd522b64c54d69656672c2f2852a4c1d9f833b78d116
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 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: 30 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