Optimal Search for a Moving Target in Discrete Time and Space

We consider optimal search for a moving target in discrete space. A limited amount of search effort is available at each of a fixed number of time intervals and we assume an exponential detection function. We show that a search plan maximizes the overall probability of detection if and only if for each time interval i the search conducted at time i maximizes the probability of detecting a stationary target with the probability that the stationary target occupies cell c equal to the probability that the moving target occupies cell c at time i and is not detected by the search at any time interval other than i. This characterization gives an iterative algorithm to compute optimal search plans. These plans are compared with incrementally optimal plans.