A new branch-and-bound procedure for computing optimal search paths
Martins, Gustavo H. A.
Eagle, James N.
Rasmussen, Craig W.
Washburn, Alan R.
MetadataShow full item record
We consider the problem of a searcher trying to detect a target that moves among a finite set of cells, C= 1,...,N, in discrete time, according to a specified Markov process. In each time period the searcher chooses one cell to search. Suppose the searcher is in cell j at time t. If the target is in j, it is detected with probability p sub j. If the target is not in j, no detection will occur in that time period. The set of cells the searcher can choose in time t + 1 is denoted c sub j. If T periods of time are available for search, the searcher's objective is to maximize the probability of detecting the target during the T searches. We propose and implement a branch-and-bound procedure for solving the problem above, using the expected number of detections as the bound. We also propose and implement a combination of two heuristic as an effective way of obtaining approximate solutions in polynomial time
Approved for public release; distribution is unlimited.
Showing items related by title, author, creator and subject.
Atkinson, Michael P.; Lange, Rutger-Jan (2016);We analyze a variant of the whereabouts search problem, in which a searcher looks for a target hiding in one of n possible locations. Unlike in the classic version, our searcher does not pursue the target by actively moving ...
Akin, Ezra W. (Monterey, California: Naval Postgraduate School, 2017-06);Across defense, homeland security, and law enforcement communities, leaders face the tension between making quick but also well informed decisions regarding time-dependent entities of interest. For example, consider a law ...
Chung, Timothy H.; Silvestrini, Rachel T. (2014);This article explores a probabilistic formulation for exhaustive search of a bounded area by a single searcher for a single static target. The searcher maintains an aggregate belief of the target’s presence or absence in ...