Accession Number : ADA188962

Title :   An Optimal Branch-and-Bound Procedure for the Constrained Path, Moving Target Search Problem.

Descriptive Note : Technical rept.,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Eagle, James N ; Yee, James R

PDF Url : ADA188962

Report Date : Dec 1987

Pagination or Media Count : 10

Abstract : A search is conducted for a target moving in discrete time among a finite number of cells according to a known Markov process. The searcher must choose one cell in which to search in each time period. The set of cells available for search depends upon the cell chosen in the last time period. The problem is to find a search path, i.e., a sequence of search cells that maximizes the probability of detecting the target in a fixed number of time periods. Closely following earlier work by Theodor Stewart, a branch-and-bound procedure is developed which finds optimal search paths. This procedure is tested and appears to be more efficient than existing dynamic programming solution methods. Keywords: Moving targets; Target detection; Searching.

Descriptors :   *MARKOV PROCESSES, *MOVING TARGETS, *SEARCHING, *TARGET DETECTION, CELLS, DYNAMIC PROGRAMMING, OPTIMIZATION, PATHS, SEQUENCES, SOLUTIONS(GENERAL), TIME, TIME INTERVALS

Subject Categories : Target Direction, Range and Position Finding
      Statistics and Probability

Distribution Statement : APPROVED FOR PUBLIC RELEASE