On the complexity of searching for an evader with a faster pursuer

In this paper we examine pursuit-evasion games in which the pursuer has higher speed than the evader. This scenario is motivated by visibility-based pursuit-evasion problems, particularly by the question of what happens when the pursuer loses visual track of the moving evader. In these cases the pursuer has two options for recovering visual contact with the evader: to perform search over the possible locations where the evader might be moving, or to clear the environment, in other words to progressively search it without allowing the evader to move into locations that have already been cleared. It has been shown that in sufficiently complex environments a single pursuer having the same speed as the evader cannot clear the environment. In this work we prove that computing the minimum speed which enables a faster pursuer to clear a graph environment is NP-hard. In light of this result we provide an experimental comparison of randomized and deterministic search strategies on planar graphs, which has practical significance in search and rescue settings.