Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-30T14:52:11.811Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal Search for a Moving Target

Published online by Cambridge University Press:  27 July 2009

I. M. MacPhee  and
B. P. Jordan
I. M. MacPhee
Affiliation:
Department of Mathematical Sciences, University of Durham, Durham DH1 3LE, United Kingdom
B. P. Jordan
Affiliation:
Department of Mathematical Sciences, University of Durham, Durham DH1 3LE, United Kingdom
Get access Rights & Permissions [Opens in a new window]

Abstract

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 Ci 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 C1 = C2, (ii) for general Ci when the overlook probabilities α, are small, and (iii) for general αi and Ci 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 Ci.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 9 , Issue 2 , April 1995 , pp. 159 - 182
Copyright
Copyright © Cambridge University Press 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Ahlswede, R. & Wegener, I. (1979). Search problems. Salisbury: John Wiley.Google Scholar
2.Assaf, D. & Sharlin-Bilitzky, A. (1994). Dynamic search for a moving target. Journal of Applied Probability 31: 438–457.CrossRefGoogle Scholar
3.Benkoski, S.J., Monticino, M.G., & Weisinger, J.R. (1991). A survey of the search theory literature. Naval Research Logistics 38: 469–494.Google Scholar
4.Nakai, T. (1973). A model of search for a target among three boxes: Some special cases. Journal of the Operations Research Society of Japan 16: 151–162.Google Scholar
5.Pollock, S.M. (1970). A simple model of search for a moving target. Operations Research 18: 883–903.CrossRefGoogle Scholar
6.Ross, S.M. (1983). Introduction to stochastic dynamic programming. New York: Academic Press.Google Scholar
7.Weber, R.R. (1986). Optimal search for a randomly moving object. Journal of Applied Probability 23: 708–717.CrossRefGoogle Scholar