We revisit one of the classical search problems in which a diffusing target encounters a stationary searcher. Under the condition that the searcher’s detection region is much smaller than the search region in which the target roams diffusively, we carry out an asymptotic analysis to derive the decay rate of the non-detection probability. We consider two different geometries of the search region: a disk and a square, respectively. We construct a unified asymptotic expression valid for both of these two cases. The unified asymptotic expression shows that the decay rate of the non-detection probability, to the leading order, is proportional to the diffusion constant, is inversely proportional to the search region, and is inversely proportional to the logarithm of the ratio of the search region to the searcher’s detection region. Furthermore, the second term in the unified asymptotic expansion indicates that the decay rate of the non-detection probability for a square region is slightly smaller than that for a disk region of the same area. We also demonstrate that the asymptotic results are in good agreement with numerical solutions.
KeywordsDetection of a Random TargetAsymptotic SolutionsDecay of the Non-Detection Probability
Koopman, B.O. (1999) Search and Screening: General Principles with Historical Applications. The Military Operations Research Society, Inc., Alexandria, Virgina.
Beckhusen, R. (2013) Search Theory and Big Data: Applying the Math That Sank the U-Boats to Today’s Intel Problems. http://www.defensenews.com/article/20130705/C4ISR02/307050013/Search-theory-big-data-Applying-math-sank-U-boats-today-s-intel-problems
Benkoski, S.J., Monticino, M.G. and Weisinger, J.R. (1991) A Survey of the Search Theory Literature. Naval Research Logistics, 38, 469-494. http://dx.doi.org/10.1002/1520-6750(199108)38:4 3.0.CO;2-E
Chudnovsky, D.V. and Chudnovsky, G.V. (1989) Search Theory: Some Recent Developments. Marcel Dekker, Inc., New York.
Chung, T.H., Hollinger, G.A. and Isler, V. (2011) Search and Pursuit-Evasion in Mobile Robotics: A Survey. Auton Robot, 31, 299-316. http://dx.doi.org/10.1007/s10514-011-9241-4
Dobbie, J.M. (1968) A Survey of Search Theory. Operations Research, 16, 525-537. http://dx.doi.org/10.1287/opre.16.3.525
Stone, L.D. (1989) Theory of Optimal Search. 2nd Edition, Academic Press, San Diego.
Stone, L.D. (1989) What’s Happened in Search Theory Since the 1975 Lanchester Prize? Operations Research, 37, 501-506. http://dx.doi.org/10.1287/opre.37.3.501
Washburn, A.R. (2002) Search and Detection. Topics in Operations Research Series. 4th Edition, Institute for Operations Research and the Management Sciences, Linthicum, MD.
Mangel, M. (1981) Search for a Randomly Moving Object. SIAM Journal on Applied Mathematics, 40, 327-338. http://dx.doi.org/10.1137/0140028
Mangel, M. (1981) Optimal Search for and Mining of Under Water Mineral Resources. SIAM Journal on Applied Mathematics, 43, 99-106. http://dx.doi.org/10.1137/0143008
Washburn, A.R. (1995) Dynamic Programming and the Backpacker’s Linear Search Problem. Journal of Computational and Applied Mathematics, 60, 357-365. http://dx.doi.org/10.1016/0377-0427(94)00038-3
Eagle, J.N. (1984) The Optimal Search for a Moving Target When the Search Path Is Constrained. Operations Research, 22, 1107-1115. http://dx.doi.org/10.1287/opre.32.5.1107
Eagle, J.N. and Yee, J.R. (1990) An Optimal Branch-and-Bound Procedure for the Constrained Path, Moving Target Search Problem. Operations Research, 38, 110-114. http://dx.doi.org/10.1287/opre.38.1.110
Thomas, L.C. and Eagle, J.N. (1995) Criteria and Approximate Methods for Path-Constrained Moving-Target Search Problems. Naval Research Logistics, 42, 27-38. http://dx.doi.org/10.1002/1520-6750(199502)42:1 3.0.CO;2-H
Washburn, A.R. (1998) Branch and Bound Methods for a Search Problem. Naval Research Logistics, 45, 243-257. http://dx.doi.org/10.1002/(SICI)1520-6750(199804)45:3 3.0.CO;2-7
Dell, R.F., Eagle, J.N., Martins, G.H.A. and Santos, A.G. (1996) Using Multiple-Searchers in Constrained-Path, Moving-Target Search Problems. Naval Research Logistics, 43, 463-480. http://dx.doi.org/10.1002/(SICI)1520-6750(199606)43:4 3.0.CO;2-5
MacPhee, I.M. and Jordan, B.P. (1995) Optimal Search for a Moving Target. Probability in the Engineering and Informational Sciences, 9, 159-182. http://dx.doi.org/10.1017/S0269964800003764
Majumdar, S.N. and Bray, A.J. (2003) Survival Probability of a Ballistic Tracer Particle in the Presence of Diffusing traps. Physical Review E, 68, Article ID: 045101(R). http://dx.doi.org/10.1103/PhysRevE.68.045101
Fernando, P.W. and Sritharan, S.S. (2014) Non-Detection Probability of Diffusing Targets in the Presence of a Moving Searcher. Communications on Stochastic Analysis, 8, 191-203.
Wang, H. and Zhou, H. (2015) Computational Studies on Detecting a Diffusing Target in a Square Region by a Stationary or Moving Searcher. American Journal of Operations Research, 5, 47-68. http://dx.doi.org/10.4236/ajor.2015.52005
Wang, H. and Zhou, H. (2015) Searching for a Target Traveling between a Hiding Area and an Operating Area over Multiple Routes. American Journal of Operations Research, 5, 258-273. http://dx.doi.org/10.4236/ajor.2015.54020
Wang, H. and Zhou, H. (2016) Performance of Stochastically Intermittent Sensors in Detecting a Target Traveling between Two Areas. American Journal of Operations Research, in Press.
Eagle, J.N. and Washburn, A.R. (1991) Cumulative Search-Evasion Games, Naval Research Logistics, 38, 495-510. http://dx.doi.org/10.1002/1520-6750(199108)38:4 3.0.CO;2-6
Gal, S. (1980) Search Games. Academic Press, New York.
Alpern, S. and Gal, S. (2003) The Theory of Search Games and Rendezvous. Kluwer Academic Publishers, Boston.
Alpern, S., Fokkink, R., Gasieniec, L., Lindelauf, R. and Subrahmanian, V.S. (2013) Search Theory: A Game Theoretic Perspective. Springer, New York. http://dx.doi.org/10.1007/978-1-4614-6825-7
Eagle, J.N. (1987) Estimating the Probability of a Diffusing Target Encountering a Stationary Sensor. Naval Research Logistics, 34, 43-51. http://dx.doi.org/10.1002/1520-6750(198702)34:1 3.0.CO;2-6