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

A searcher and target move among a finite set of cells C = 1, 2, …,N in discrete time. At the beginning of each time period, one cell is searched. If the target is in the selected cell j, it is detected with probability q_j. If the target is not in the cell searched, it cannot be detected during the current time period. After each search, a target in cell j moves to cell k with probability p_jk. The target transition matrix, P = [p_jk] is known to the searcher. The searcher's path is constrained in that if the searcher is currently in cell j, the next search cell must be selected from a set of neighboring cells C_j. The object of the search is to minimize the probability of not detecting the target in T searches.