Accession Number : ADA265276


Title :   A New Branch-and-Bound Procedure for Computing Optimal Search Paths


Descriptive Note : Master's thesis,


Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA


Personal Author(s) : Martins, Gustavo H


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a265276.pdf


Report Date : Mar 1993


Pagination or Media Count : 64


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


Descriptors :   *PATHS , *MOVING TARGETS , *SEARCHING , DETECTION , THESES , TIME , NUMBERS , POLYNOMIALS , TARGETS , CELLS , PROBABILITY


Subject Categories : Target Direction, Range and Position Finding


Distribution Statement : APPROVED FOR PUBLIC RELEASE