Portal de Periódicos da CAPES

Optimal Search for a Moving Target

1995; Cambridge University Press; Volume: 9; Issue: 2 Linguagem: Inglês

10.1017/s0269964800003764

1469-8951

I. M. MacPhee, Benjamin Paul Jordan,

Optimization and Search Problems

Consider the problem of searching for a leprechaun that moves randomly between two sites. The movement is modelled with a two-state Markov chain. One of the sites is searched at each time t = 1,2,…, until the leprechaun is found. Associated with each search of site i is an overlook probability α i and a cost C i Our aim is to determine the policy that will find the leprechaun with the minimal average cost. Let p denote the probability that the leprechaun is at site 1. Ross conjectured that 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) when α 1 = α 2 and C 1 = C 2 , (ii) for general C i when the overlook probabilities α, are small, and (iii) for general α i and C i 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 α i , and C i .