On optimal search for a moving target

Abstract

The work of this thesis is concerned with the following problem and its derivatives. Consider the problem of searching for a target which moves randomly between n sites. The movement is modelled with an n state Markov chain. One of the sites is searched at each time t = 1, 2,…until the target is found. Associated with each search of site i is an overlook probability a(_i) and a cost C(_i). Our aim is to determine the policy that will find the target with the minimal average cost. Notably in the two site case we examine the conjecture that if we let p denote the probability that the target is at site 1, an optimal policy can be defined in terms of a threshold probability P(^*) such that site 1 is searched if and only if p ≥ P(^*). We show this conjecture to be correct (i) for general C(_1) ≠ C(_2) when the overlook probabilities a(_i) are small and (ii) for general a, and d for a large range of transition laws for the movement. We also derive some properties of the optimal policy for the problem on n sites in the no-overlook case and for the case where each site has the same a, and Q. We also examine related problems such as ones in which we have the ability to divide available search resources between different regions, and a couple of machine replacement problems.