All Title Author
Keywords Abstract

Non-Detection Probability of a Diffusing Target by a Stationary Searcher in a Large Region

DOI: 10.4236/am.2016.73023, PP. 250-266

Keywords: Detection of a Random Target, Asymptotic Solutions, Decay of the Non-Detection Probability

Full-Text   Cite this paper   Add to My Lib


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.


[1]  Koopman, B.O. (1999) Search and Screening: General Principles with Historical Applications. The Military Operations Research Society, Inc., Alexandria, Virgina.
[2]  Beckhusen, R. (2013) Search Theory and Big Data: Applying the Math That Sank the U-Boats to Today’s Intel Problems.
[3]  Benkoski, S.J., Monticino, M.G. and Weisinger, J.R. (1991) A Survey of the Search Theory Literature. Naval Research Logistics, 38, 469-494.<469::AID-NAV3220380404>3.0.CO;2-E
[4]  Chudnovsky, D.V. and Chudnovsky, G.V. (1989) Search Theory: Some Recent Developments. Marcel Dekker, Inc., New York.
[5]  Chung, T.H., Hollinger, G.A. and Isler, V. (2011) Search and Pursuit-Evasion in Mobile Robotics: A Survey. Auton Robot, 31, 299-316.
[6]  Dobbie, J.M. (1968) A Survey of Search Theory. Operations Research, 16, 525-537.
[7]  Stone, L.D. (1989) Theory of Optimal Search. 2nd Edition, Academic Press, San Diego.
[8]  Stone, L.D. (1989) What’s Happened in Search Theory Since the 1975 Lanchester Prize? Operations Research, 37, 501-506.
[9]  Washburn, A.R. (2002) Search and Detection. Topics in Operations Research Series. 4th Edition, Institute for Operations Research and the Management Sciences, Linthicum, MD.
[10]  Mangel, M. (1981) Search for a Randomly Moving Object. SIAM Journal on Applied Mathematics, 40, 327-338.
[11]  Mangel, M. (1981) Optimal Search for and Mining of Under Water Mineral Resources. SIAM Journal on Applied Mathematics, 43, 99-106.
[12]  Washburn, A.R. (1995) Dynamic Programming and the Backpacker’s Linear Search Problem. Journal of Computational and Applied Mathematics, 60, 357-365.
[13]  Eagle, J.N. (1984) The Optimal Search for a Moving Target When the Search Path Is Constrained. Operations Research, 22, 1107-1115.
[14]  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.
[15]  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.<27::AID-NAV3220420105>3.0.CO;2-H
[16]  Washburn, A.R. (1998) Branch and Bound Methods for a Search Problem. Naval Research Logistics, 45, 243-257.<243::AID-NAV1>3.0.CO;2-7
[17]  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.<463::AID-NAV1>3.0.CO;2-5
[18]  MacPhee, I.M. and Jordan, B.P. (1995) Optimal Search for a Moving Target. Probability in the Engineering and Informational Sciences, 9, 159-182.
[19]  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).
[20]  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.
[21]  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.
[22]  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.
[23]  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.
[24]  Eagle, J.N. and Washburn, A.R. (1991) Cumulative Search-Evasion Games, Naval Research Logistics, 38, 495-510.<495::AID-NAV3220380405>3.0.CO;2-6
[25]  Thomas, L.C. and Washburn, A.R. (1991) Dynamic Search Games. Operations Research, 39, 415-422.
[26]  Gal, S. (1980) Search Games. Academic Press, New York.
[27]  Alpern, S. and Gal, S. (2003) The Theory of Search Games and Rendezvous. Kluwer Academic Publishers, Boston.
[28]  Alpern, S., Fokkink, R., Gasieniec, L., Lindelauf, R. and Subrahmanian, V.S. (2013) Search Theory: A Game Theoretic Perspective. Springer, New York.
[29]  Eagle, J.N. (1987) Estimating the Probability of a Diffusing Target Encountering a Stationary Sensor. Naval Research Logistics, 34, 43-51.<43::AID-NAV3220340105>3.0.CO;2-6


comments powered by Disqus