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):

Report Date:

1993-03-01

Pagination or Media Count:

64.0

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 searchers 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

Subject Categories:

  • Target Direction, Range and Position Finding

Distribution Statement:

APPROVED FOR PUBLIC RELEASE