Name
Title | ||
|---|---|---|
A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search |
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.ejor.2007.10.048 | European Journal of Operational Research |
Keywords | Field | DocType |
Search theory,Heuristics,Markov processes,Network flows | Pseudo-polynomial time,Heuristic,Incremental heuristic search,Markov process,Conditional probability,Markov chain,Algorithm,Beam search,Mathematics,Approximation error | Journal |
Volume | Issue | ISSN |
193 | 2 | 0377-2217 |
Citations | PageRank | References |
4 | 0.44 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sung-Pil Hong | 1 | 137 | 13.07 |
| Sung-Jin Cho | 2 | 157 | 28.33 |
| Myoung-Ju Park | 3 | 29 | 7.50 |