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 qj. 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 pjk. The target transition matrix, P=[pjk] 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 Cj. The object of the search is to minimize the probability of not detecting the target in T searches.