SHERP

A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search

Cited 0 time in webofscience Cited 0 time in scopus
Authors
Hong, Sung-Pil; Cho, Sung-Jin; Park, Myoung-Ju
Issue Date
2007-11-06
Publisher
Elsevier
Citation
European Journal of Operational Research 193 (2009) 351-364
Keywords
Search theory; Heuristics; Markov processes; Network flows
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.
ISSN
0377-2217
Language
English
URI
http://hdl.handle.net/10371/5336
DOI
https://doi.org/10.1016/j.ejor.2007.10.048
https://doi.org/10.1016/j.ejor.2007.10.048
Files in This Item:
There are no files associated with this item.
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Journal Papers (저널논문_산업공학과)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse