The optimal search for a Markovian target when the search path is constrained: the infinite-horizon case

TitleThe optimal search for a Markovian target when the search path is constrained: the infinite-horizon case
Publication TypeJournal Article
Year of Publication2003
AuthorsSingh, S., and V. Krishnamurthy
JournalAutomatic Control, IEEE Transactions on
Pagination493 - 497
Date Publishedmar.
Keywordsdecision 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

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.


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia