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
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-308453 |
| Date | January 2021 |
| Creators | Gabi Goobar, Tobias, Söderberg, Samuel |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2021:193 |
Page generated in 0.0025 seconds