A New Branch-and-Bound Procedure for Computing Optimal Search Paths
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. Optimal search paths, Search, Branch-and-bound, Optimal search, Moving target
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1993
- Accession Number
- ADA265276
Entities
People
- Gustavo H. Martins
Organizations
- Naval Postgraduate School