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

Imagine for a moment we are living in the distant future where autonomous robots are patrollingthe streets as police officers. Two such robots are chasing a robber through the city streets. Fearingthe thief might listen in to any potential transmission, both robots remain radio silent and are thuslimited to a strictly visual pursuit. Since the robots cannot see the robber the entire time, they haveto deduce the potential location of the robber. What would the best strategy be for these robots toachieve their objective? This bachelor's thesis investigated the above example by creating strategies through reinforcementlearning. The thesis also investigated the performance of the players when they have differentabilities of deduction. This was tested by creating a suitable game and corresponding reinforcementlearning algorithm and running the simulations for different degrees of knowledge. The study provedthat reinforcement learning is a viable method for strategy construction, reaching nearly guaranteedvictory for cases when the agent knows everything about the environment and a slightly lower winratio when there is uncertainty introduced. The implementation yielded only a small gain in win ratiowhen the agents could deduce even more about each other. / Föreställ dig för ett ögonblick att vi lever i en avlägsen framtid där autonoma robotar patrullerar pågatorna som poliser. Två sådana robotar jagar en rånare genom stadens gator. Eftersom de är räddaför att tjuven kan lyssna på alla möjliga sändningar, förblir båda robotarna radiotysta och är därförbegränsade till en strikt visuell strävan. Eftersom robotarna inte kan se rånaren hela tiden, måste dehärleda den potentiella platsen för rånaren. Vilken skulle den bästa strategin vara för dessa robotarför att uppnå sitt mål? Denna kandidatuppsats undersökte ovanstående exempel genomskapa strategier genomförstärkningsinlärning. Avhandlingen undersökte också spelarnas prestationer när de har olikaavdragsförmåga. Detta testades genom att skapa ett lämpligt spel och motsvarandeförstärkningsinlärningsalgoritm och köra simuleringarna för olika kunskapsgrader. Studien visade attförstärkningsinlärning är en användbar metod för strategikonstruktion, och når nästan garanteradseger i fall då agenten vet allt om miljön och en något lägre vinstkvot när det finns osäkerhet.Implementeringen gav bara en liten vinst i vinstförhållandet när agenterna kunde härleda ännu merom varandra. / Kandidatexjobb i elektroteknik 2023, KTH, Stockholm

Strategies in games have since long been of interestto humans, mainly to beat our friends in games such as Chessor Monopoly, but also to model real world scenarios. Thesestrategies are often difficult to find, even more so if the playerslack important information about the current state of the game.Pursuit-Evasion games are a type of games that can be usedto model police chasing criminals, autonomous car collisionavoidance systems and many other scenarios. It is therefore ofinterest to find effective strategies in these scenarios.This bachelor thesis project examined Pursuit-Evasion gamesof imperfect information on grids where a number of pursuerswork together to capture a number of evaders whose locationsare unknown. A set of knowledge-based strategies, one of theminspired by the Knowledge Based Subset Construction, wereexplored and analyzed. The strategies were compared againsteach other and against both an optimal strategy where thepursuers always were aware of the evaders whereabouts anda reference strategy where the pursuers moved randomly.The constructed strategies proved to be efficient in comparisonto the reference and in cases even close to the optimal strategyin efficiency. / Strategier i spel har sedan länge varit avintresse för oss människor, framförallt för att vinna mot vårakompisar i spel som Schack eller Monopol, men också för attmodellera verkliga scenarion. Dessa strategier är ofta svåra attlista ut, och ännu svårare då spelarna saknar viktig informationom spelets nuvarande läge. Pursuit-Evasion är en klass av spelsom kan användas för att modellera polisjakter eller kollisionsundvikandesystem i autonoma bilar för att nämna några. Detligger därför i vårt intresse att finna effektiva strategier i dessascenarion.Detta kandidatsexamensarbete studerade Pursuit-Evasion spelav imperfekt information på rutnät där ett antal så kallade pursuerssamarbetade för att fånga ett antal så kallade evaders varspostioner var okända. En kunskaps-representation utformadesoch en mängd kunskaps-baserade strategier, en inspirerad avmetoden Knowledge Based Subset Construction, utforskades ochtestades. De olika strategierna jämfördes mot varandra och motbåde en optimal strategi då pursuers hade all kunskap om varalla evaders befann sig och en referensstrategi då pursuers rördesig slumpmässigt.De utformade strategierna visade sig vara effektiva i jämförelsemed referensen och i vissa fall till och med nära den optimalastrategin i effektivitet. / Kandidatexjobb i elektroteknik 2021, KTH, Stockholm

No description available.