Optimal search and ambush for a hider who can escape the search region

Abstract

Search games for a mobile or immobile hider traditionally have the hider permanently confined to a compact ‘search region’ making eventual capture inevitable. Hence the payoff can be taken as time until capture. However in many real life search problems it is possible for the hider to escape an area in which he was known to be located (e.g. Bin Laden from Tora Bora) or for a prey animal to escape a predator's hunting territory. We model and solve such continuous time problems with escape where we take the probability of capture to be the searcher's payoff. We assume the searcher, while cruise searching, can cover the search region at unit rate of area, for a given time horizon T known to the hider. The hider can stay still or choose any time to flee the region. To counter this, the searcher can also adopt an ambush mode which will capture a fleeing hider. The searcher wins the game if he either finds the hider while cruise searching or ambushes him while he is attempting to flee; the hider wins if he flees successfully (while the searcher is cruising) or has not been found by time T. The optimal searcher strategy involves decreasing the ambush probability over time, to a limit of zero. This surprising behaviour is opposite to that found recently by Alpern et al. (2011, 2013) in a predator-prey game with similar dynamics but without the possibility of the hider escaping. Our work also complements that of Zoroa et al. (2015) on searching for multiple prey and Gal and Casas (2014) for a combined model of search and pursuit.