A new branch-and-bound procedure for computing optimal search paths
Loading...
Authors
Martins, Gustavo H. A.
Subjects
Optimal search paths
Search
Branch-and-Bound
Optimal search
Moving target
Search
Branch-and-Bound
Optimal search
Moving target
Advisors
Eagle, James N.
Rasmussen, Craig W.
Date of Issue
1993-03
Date
March 1993
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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
Type
Thesis
Description
Series/Report No
Department
Department of Operations Research
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
55 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Copyright is reserved by the copyright owner