A Search-Based Approach to Solve Pursuit-Evasion Games with Limited Visibility in Polygonal Environments

A pursuit-evasion game is a non-cooperative game in which a pursuer tries to detect or capture an adversarial evader. We study a pursuit-evasion game which takes place in a known polygonal environment. The goal of the pursuer is to capture the evader by moving onto its location. The players can observe each others' locations only if they can "see" each other-i.e., if the line segment connecting their locations lies entirely inside the polygonal environment. The complexity of representing the information available to the players at a given time makes solving pursuit-evasion games with visibility limitations dicult. We represent the state of the game using an ecient visibility-based decomposition of the environment paired with a more classical grid-based decomposition. The optimal players' strategies are computed using a min-max search algorithm improved with specic speedup techniques that preserve optimality. We show that our decomposition is complete for a rash evader, which hides from the pursuer and does not move from its hiding location when the pursuer is not visible. Simulations in realistic indoor environments and comparison with a Monte Carlo tree search algorithm validate our approach.