A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search |
| |
Authors: | Sung-Pil Hong Sung-Jin Cho Myoung-Ju Park |
| |
Affiliation: | Department of Industrial Engineering, Seoul National University, Seoul, Republic of Korea |
| |
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. |
| |
Keywords: | Search theory Heuristics Markov processes Network flows |
本文献已被 ScienceDirect 等数据库收录! |
|