×

Optimal discrete search with technological choice. (English) Zbl 1371.90063

Math. Methods Oper. Res. 81, No. 3, 317-336 (2015); correction ibid. 94, No. 1, 169-170 (2021).
Summary: Consider a search problem in which a stationary object is in one of \(L \epsilon \mathcal {N}\) locations. Each location can be searched using one of \(T \epsilon \mathcal {N}\) technologies, and each location-technology pair has a known associated cost and overlook probability. These quantities may depend on the number of times that the technology is applied to the location. This paper finds a search policy that maximizes the probability of finding the object given a constraint on the available budget. It also finds the policy that maximizes the probability of correctly stating at the end of a search where the object is. Additionally it exhibits another policy that minimizes the expected cost required to find the object and the optimal policy for stopping.

MSC:

90B40 Search theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agmon N, Kraus S, Kaminka G, Sadov V (2009) Adversarial uncertainty in multi-robot patrol. In: IJCAI’09 proceedings of the 21st international joint conference on artificial intelligence. pp 1811-1817
[2] Alpern S, Fokkink R, Gasieniec L, Lindelauf R, Subrahmanian V (eds) (2013) Search theory: a game theoretic perspective. Springer, Heidelberg · Zbl 1263.91001
[3] Babichenko, Y; Peres, Y; Peretz, R; Sousi, P; Winkler, P, Hunter, Cauchy rabbit and optimal Kakeya sets, Trans Am Math Soc, 366, 5567-5586, (2014) · Zbl 1305.91042
[4] Bellman R (1957) Dynamic programming. Princeton University Press, Princeton · Zbl 0077.13605
[5] Benkoski, S; Monticino, M; Weisinger, J, A survey of the search theory literature, Nav Res Log, 38, 469-494, (1991) · Zbl 0731.90043
[6] Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge · Zbl 1058.90049
[7] Brown, S, Optimal search for a moving target in discrete time and space, Oper Res, 28, 1275-1289, (1980) · Zbl 0447.90046
[8] DeGroot M (1970) Optimal statistical decisions. McGraw-Hill, New York · Zbl 0225.62006
[9] DeGroot M (1986) Probability and statistics, 2nd edn. Addison-Wesley, Reading · Zbl 0619.62001
[10] DeGroot M (2004) Optimal statistical decisions. Wiley, Hoboken (reprinted) · Zbl 1136.62011
[11] Dumitriu, I; Tetali, P; Winkler, P, On playing golf with two balls, SIAM J Discrete Math, 16, 604-615, (2003) · Zbl 1032.60065
[12] Gal S (1980) Search games. Academic Press, New York · Zbl 0439.90102
[13] Gal S, Alpern S (2003) The theory of search and rendezvous. Kluwer Acadmic Publishers, Boston · Zbl 1034.91017
[14] Gittins, J, Bandit processes and dynamic allocation indices (with discussion), J R Stat Soc Ser B, 41, 148-177, (1979) · Zbl 0411.62055
[15] Gittins J, Glazebrook K, Weber R (2011) Multi-armed bandit allocation indices. Wiley, Chichester · Zbl 1401.90257
[16] Kadane, J, Discrete search and the Neyman-Pearson lemma, J Math Anal Appl, 22, 156-171, (1968) · Zbl 0155.25402
[17] Kadane, J, Optimal whereabouts search, Oper Res, 19, 894-904, (1971) · Zbl 0226.90018
[18] Koopman, B, The theory of search, part I, kinematic bases, Oper Res, 4, 324-346, (1956) · Zbl 1414.90177
[19] Koopman, B, The theory of search, part II, target detection, Oper Res, 4, 503-531, (1956) · Zbl 1415.94334
[20] Koopman, B, The theory of search, part III, the optimum distribution of search effort, Oper Res, 5, 613-626, (1957) · Zbl 1414.90176
[21] Kress, M; Lin, K; Szechtman, R, Optimal discrete search with imperfect specificity, Math Methods Oper Res, 68, 539-549, (2008) · Zbl 1155.90009
[22] Kriheli B, Levner E (2013) Search and detection of failed components in repairable complex systems under imperfect inspections. In: Batyrshin I, Mendoza M (eds) Advances in computational intelligence, vol 7630. Lecture notes in computer science, pp 399-410
[23] Lehmann E (1959) Testing statistical hypotheses. Wiley, New York · Zbl 0089.14102
[24] Mela, D, Information theory and search theory as special cases of decision theory, Oper Res, 9, 907-909, (1961) · Zbl 0097.34403
[25] Nakai, T, Dynamical and game-theoretial approaches to an optimal patrol problem, J Inf Optim Sci, 16, 491-500, (1995) · Zbl 0861.90079
[26] Qingxin Z, Oommen J (1997) On the optimal search problem: the case when the target distribution is unknown. In: Proceedings of the XVII international conference of the Chilean Computer Science Society. pp 268-277
[27] Song, NO; Teneketzis, D, Discrete search with multiple sensors, Math Methods Oper Res, 60, 1-13, (2004) · Zbl 1081.90031
[28] Stone L (1975) Theory of optimal search. Academic Press, New York · Zbl 0343.90030
[29] Stone L, Streit R, Corwin T, Bell K (2014) Bayesian mutiple target tracking. Artech House, Boston · Zbl 1281.78001
[30] Tognetti, K, An optimal strategy for whereabouts search, Oper Res, 16, 209-211, (1968)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.