Knowledge Based Strategies in Grid-Based Pursuit-Evasion Games of Imperfect Information

Sammanfattning: 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.