Publications
Detailed Information
A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search
Cited 18 time in
Web of Science
Cited 23 time in Scopus
- Authors
- Issue Date
- 2009-03-01
- Publisher
- ELSEVIER SCIENCE BV
- Citation
- EUROPEAN JOURNAL OF OPERATIONAL RESEARCH; Vol.193 2; 351-364
- Keywords
- Search theory ; Heuristics ; Network flows ; Markov processes
- Abstract
- We propose a new heuristic for the single-searcher path-constrained discrete-time Markovian-target search. The algorithm minimizes an approximate, instead of exact, nondetection probability computed from the conditional probability that reflects the search history over the time windows of a fixed length, l. Having a pseudo-polynomial complexity, it can solve, in reasonable time, the instances an order of magnitude larger than those solved in the previous studies. By an asymptotic analysis relying on the fast-mixing Markov chain, we show that the relative error of the approximation exponentially diminishes as l increases and the experimental results confirm the analysis. The experiment also reveals a correlation very close to 1 between the approximate and exact nondetection probability of a search path. This means that the heuristic produces near-optimal search paths. (C) 2007 Elsevier B.V. All rights reserved.
- ISSN
- 0377-2217
- Language
- English
- Files in This Item:
- There are no files associated with this item.
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.