Publications
Detailed Information
A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hong, Sung-Pil | - |
dc.contributor.author | Cho, Sung-Jin | - |
dc.contributor.author | Park, Myoung-Ju | - |
dc.date.accessioned | 2012-03-05T02:30:09Z | - |
dc.date.available | 2012-03-05T02:30:09Z | - |
dc.date.issued | 2009-03-01 | - |
dc.identifier.citation | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH; Vol.193 2; 351-364 | - |
dc.identifier.issn | 0377-2217 | - |
dc.identifier.uri | https://hdl.handle.net/10371/75330 | - |
dc.description.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. | - |
dc.language.iso | en | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.subject | Search theory | - |
dc.subject | Heuristics | - |
dc.subject | Network flows | - |
dc.subject | Markov processes | - |
dc.title | A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search | - |
dc.type | Article | - |
dc.contributor.AlternativeAuthor | 홍성필 | - |
dc.contributor.AlternativeAuthor | 조성진 | - |
dc.contributor.AlternativeAuthor | 박명주 | - |
dc.identifier.doi | 10.1016/j.ejor.2007.10.048 | - |
dc.citation.journaltitle | EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | - |
dc.description.citedreference | Singh S, 2003, IEEE T AUTOMAT CONTR, V48, P493, DOI 10.1109/TAC.2003.809165 | - |
dc.description.citedreference | Dambreville F, 2002, NAV RES LOG, V49, P117, DOI 10.1002/nav.10009 | - |
dc.description.citedreference | FROST JR, 2001, CGD1501 US COAST GUA | - |
dc.description.citedreference | Hohzaki R, 1997, EUR J OPER RES, V100, P236 | - |
dc.description.citedreference | Dell RF, 1996, NAV RES LOG, V43, P463 | - |
dc.description.citedreference | THOMAS LC, 1995, NAV RES LOG, V42, P27 | - |
dc.description.citedreference | SINCLAIR A, 1993, ALGORITHMS RANDOM GE, P42 | - |
dc.description.citedreference | BENKOSKI SJ, 1991, NAV RES LOG, V38, P469 | - |
dc.description.citedreference | EAGLE JN, 1990, OPER RES, V38, P110 | - |
dc.description.citedreference | TRUMMEL KE, 1986, OPER RES, V34, P324 | - |
dc.description.citedreference | EAGLE JN, 1984, OPER RES, V32, P1107 | - |
dc.description.citedreference | BROWN SS, 1980, OPER RES, V28, P1275 | - |
dc.description.citedreference | STEWART TJ, 1979, COMPUT OPER RES, V6, P129 | - |
dc.description.citedreference | POLLOCK SM, 1970, OPER RES, V18, P883 | - |
dc.description.citedreference | KOOPMAN BO, 1946, 56 OEG COL U DIV WAR | - |
dc.description.tc | 2 | - |
dc.identifier.wosid | 000260749100003 | - |
- Appears in Collections:
- 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.