A Method for Finding Strategies in Pursuit-Evasion Games

Abstract: Many real-world situations can be described as games over finite graphs, con- sisting of a set of agents performing joint actions affecting the state of the game. One class of games over finite graphs are the so called pursuit-evasion games, where a set of pursuers try to capture an evader on a finite map. In some pursuit-evasion games where the position of the evader is unknown finding an optimal strategy to ensure victory for the pursuers can be difficult. One way to simplify this process is by using the multiplayer knowledge-based subset construction (MKBSC) to transform the game graph to an expanded graph where the pursuers’ knowledge is included in the construction. In this report we investigate the usefulness of MKBSC for finding knowledge-based strate- gies for pursuit-evasion games by analyzing the generated graph by hand and extracting useful information from it. It was found that in general it is difficult to find the best knowledge-based strategies for pursuit-evasion games by hand with a non-symbolic representation of the game. This is mainly due to the fact that the sizes of the expanded graphs tended to be very large. It is pos- sible that MKBSC can be useful for finding knowledge-based strategies for pursuit-evasion games with the use of symbolic representations of the game or by algorithmically finding the strategies based on the generated graphs.