A game theoretical approach to finding optimal strategies for pursuit evasion in grid environments

Pursuit evasion problems, in which evading targets must be cleared from an environment, are encountered in surveillance and search and rescue applications. Several works have addressed variants of this problem in order to study strategies for the pursuers. As a common trait, many of these works present results in the general form: given some assumptions on the environment, on the pursuers, and on the evaders, upper and lower bounds are calculated for the time needed for (the probability of, the resources needed for, ...) clearing the environment. The question “what is the optimal strategy for a given pursuer in a given environment to clear a given evader?” is left largely open. In this paper, we propose a game theoretical framework that contributes in finding an answer to the above question in a version of the pursuit evasion problem in which the evader enters and exits a grid environment and the pursuer has to intercept it along its path. We adopt a criterion for optimality related to the probability of capture. We experimentally evaluate the proposed approach in simulated settings and we provide some hints to generalize the framework to other versions of the pursuit evasion problem.