@article {Singh2003The-optimal-sea,
title = {The optimal search for a Markovian target when the search path is constrained: the infinite-horizon case},
journal = {Automatic Control, IEEE Transactions on},
volume = {48},
number = {3},
year = {2003},
month = {mar.},
pages = {493 - 497},
abstract = {A target moves among a finite number of cells according to a discrete-time homogeneous Markov chain. The searcher is subject to constraints on the search path, i.e., the cells available for search in the current epoch is a function of the cell searched in the previous epoch. The aim is to identify a search policy that maximizes the infinite-horizon total expected reward earned. We show the following structural results under the assumption that the target transition matrix is ergodic: 1) the optimal search policy is stationary; and 2) there exists epsi;-optimal stationary policies which may be constructed by the standard value iteration algorithm in finite time. These results are obtained by showing that the dynamic programming operator associated with the search problem is an m-stage contraction mapping on a suitably defined space. An upper bound of m and the coefficient of contraction alpha; is given in terms of the transition matrix and other variables pertaining to the search problem. These bounds on m and alpha; may be used to derive bounds on suboptimal search polices constructed.},
keywords = {decision theory, dynamic programming, infinite horizon, iteration algorithm, iterative methods, Markov chain, Markov processes, Markovian target, partially observed Markov decision process, probability, search problem, search problems, stochastic shortest path, target tracking, transition matrix, upper bound},
issn = {0018-9286},
doi = {10.1109/TAC.2003.809165},
url = {http://dx.doi.org/10.1109/TAC.2003.809165},
author = {Singh, S. and Krishnamurthy, V.}
}