The Optimal Search for a Moving Target When the Search Path Is Constrained

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 searcher path, i.e., a sequence of search cells, that maximizes the probability of detecting the target in a fixed number of time periods. We formulate the problem as a partially observable Markov decision process and present a finite time horizon POMDP solution technique which is simpler than the standard linear programming methods.