One group of games studied within game theory are grid-based pursuit evasion games of imperfect information. A pursuit evasion game is in essence a game where there exists a set of pursuers which have as their objective to capture a set of evaders. This thesis aims to develop a formalisation of this type of games as well as describing and integrating vital game theoretical concepts such as order of knowledge into this game. With the developed formalism at hand, the concept of knowledge-based strategies is then introduced, which is essential when searching for the way to play the game most efficiently. The formalisation of the game is then followed by a simulation, measuring the performance of some older and some newly developed knowledge-based strategies. The thesis concludes that the formalisation is applicable on a more general class of pursuit evasion games and enables a wider study of the game. The simulation results indicate that knowledge-based strategies of higher order do not always perform better compared to simpler strategies of lower order of knowledge. Furthermore, strategies which allow for communication between agents are found to be superior to communication-less strategies. / En typ av spel som studeras inom spelteori är rutnätsbaserade jakt-flykt-spel med ofullständig information. Ett jakt-flykt-spel går ut på att det existerar en samling jagande aktörer som försöker fånga en samling flyende aktörer. Denna uppsats söker utveckla en formalism för denna typ av spel såväl som att beskriva och integrera ett antal nyckelkoncept inom spelteori såsom kunskapsordning. Med hjälp av den utvecklade formalismen, framställs så kallade kunskapsbaserade strategier, vilka är av fundamental vikt i sökandet efter sätt att spela spelet på det effektivaste sättet. Kapitlet om formalismen följs sedan av simuleringar där några äldre och några nyare kunskapsbaserade strategier prövas. Slutsatsen dras att den nya formalismen kan vara applicerbar på en bredare samling jakt-flykt-spel än den initialt påtänkta. Vidare underlättar formalismen en generalisering till andra sätt att beskriva spel. Simulationsresultaten indikerar att kunskapsbaserade strategier av högre ordning inte alltid presterar bättre än enklare strategier av lägre ordning. Till yttermera visso visar sig kommunikationslösa strategier vara underlägsna strategier som tillåter kommunikation. / Kandidatexjobb i elektroteknik 2022, KTH, Stockholm
Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-323736 |
Date | January 2022 |
Creators | Granqvist, Jacob, Haker, Jonas |
Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
Source Sets | DiVA Archive at Upsalla University |
Language | English |
Detected Language | Swedish |
Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
Format | application/pdf |
Rights | info:eu-repo/semantics/openAccess |
Relation | TRITA-EECS-EX ; 2022:179 |
Page generated in 6.1666 seconds