Effects of Varied Terrain on Knowledge-Based Strategies in Grid-Based Pursuit-Evasion Games
2024 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE credits
Student thesisAlternative title
Effekter av Olika Terräng på Kunskapsbaserade Strategier i Rutnätsbaserade Jakt-flyktspel (Swedish)
Abstract [en]
This study explores pursuit-evasion games, where two teams of agents, the pursuers and the evaders, play against each other. The pursuers’ goal is to capture the evaders, while the evaders’ goal is not to get captured. The game concludes when the pursuers have captured all evaders, while the evaders aim to stall the game for as long as possible by avoiding capture. Finding winning strategies for the pursuer can have real-world applications such as, for instance, when police pursue a robber. The type of pursuit-evasion game we will study is a game of imperfect information, meaning each agent is not always aware of the exact game state but only has partial information in the form of limited vision. Identifying good pursuer strategies can be essential to effectively capturing evaders in this scenario. We are interested in how adding complexity to the terrain of a grid-based pursuit-evasion game with imperfect information affects the performance of knowledge-based pursuer strategies. Therefore, this study produced multiple matrix-based terrains of varying complexity and multiple knowledge-based strategies, which we used to run many simulations. The different knowledge-based strategies we studied were either knowledge level 0 strategies that only act upon what they see or knowledge level 1 strategies that also utilize memory of previous moves and observations of their surroundings to move more efficiently. The study concluded that increasing environmental complexity seems to cause the time for all of our first and zero-order strategies to catch the evaders to grow non-linearly. In contrast, the time for the perfect information strategy seems to keep growing linearly. We also observed that the growth was significantly slower for strategies better suited to the specific environment. This indicates that as environmental complexity increases, it becomes more important to have a good strategy, and we hypothesize that a higher-order strategy or a better-suited strategy could perform better than first-order strategies as it should be able to remove some of this uncertainty by better deduction.
Abstract [sv]
Den här studien utforskar jakt-flyktspel, där två lag, jägarna och undvikarna, spelar mot varandra. Jägarnas mål är att fånga de undvikande, medan de undvikandes mål inte är att bli tillfångatagna. Spelet avslutas när jägarna har fångat alla undvikande, medan de undvikande strävar efter att undvika att bli fångade så länge som möjligt. Att hitta vinnande strategier för förföljaren kan tillämpningar som till exempel när polisen förföljer en rånare. Den typ av jakt-flykt spel vi kommer att studera är ett spel med ofullständig information, vilket innebär att varje agent inte alltid är medveten om det exakta speltillståndet utan bara har partiell information i form av ett begränsat synfält. Att identifiera bra jägarstrategier kan vara väsentligt för att effektivt fånga de undvikande i detta scenario. Vi är intresserade av hur komplexitet till terrängen i ett rutnätsbaserat jakt-undvikande spel med ofullständig information påverkar effektiviteten av kunskapsbaserade förföljarstrategier. Därför producerade denna studie flera matrisbaserade terränger av varierande komplexitet och flera kunskapsbaserade strategier, som vi använder för att köra många simuleringar. De olika kunskapsbaserade strategierna vi studerade var antingen kunskaps-nivå 0-strategier som bara agerar på vad de ser eller kunskapsnivå 1-strategier som också använder minne av tidigare händelser och observationer av sin omgivning för att förflytta sig mer effektivt. Studien drog slutsatsen att ökande komplexitet hos terrängen verkar få tiden för alla våra första och nollordningsstrategier att fånga de undivkande att växa icke-linjärt, medan tiden för den perfekta informationsstrategin verkar fortsätta växa linjärt. Vi observerade också att tillväxten var betydligt långsammare för strategier som var bättre lämpade för den specifika terrängen. Detta indikerar att när terrängen blir mer komplex, blir det viktigare att ha en bra strategi, och vi antar att en strategi av högre ordning eller en bättre lämpad strategi skulle kunna prestera bättre än första ordningens strategier eftersom den borde kunna ta bort en del av denna osäkerhet genom bättre analysförmåga.
Place, publisher, year, edition, pages
2024. , p. 45
Series
TRITA-EECS-EX ; 2024:329
Keywords [en]
Knowledge-based strategies, Game theory, Pursuit-evasion, Imperfect Information, Terrain, Order of Knowledge.
Keywords [sv]
Kunskapsbaserade strategier, Spelteori, Jakt-flyktspel, Imperfekt information, Terräng, Order av kunskap.
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-351036OAI: oai:DiVA.org:kth-351036DiVA, id: diva2:1885901
Supervisors
Examiners
2024-08-212024-07-262024-08-21Bibliographically approved