Publications

Detailed Information

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

DC Field Value Language
dc.contributor.authorHong, Sung-Pil-
dc.contributor.authorCho, Sung-Jin-
dc.contributor.authorPark, Myoung-Ju-
dc.date.accessioned2012-03-05T02:30:09Z-
dc.date.available2012-03-05T02:30:09Z-
dc.date.issued2009-03-01-
dc.identifier.citationEUROPEAN JOURNAL OF OPERATIONAL RESEARCH; Vol.193 2; 351-364-
dc.identifier.issn0377-2217-
dc.identifier.urihttps://hdl.handle.net/10371/75330-
dc.description.abstractWe 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.isoen-
dc.publisherELSEVIER SCIENCE BV-
dc.subjectSearch theory-
dc.subjectHeuristics-
dc.subjectNetwork flows-
dc.subjectMarkov processes-
dc.titleA pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search-
dc.typeArticle-
dc.contributor.AlternativeAuthor홍성필-
dc.contributor.AlternativeAuthor조성진-
dc.contributor.AlternativeAuthor박명주-
dc.identifier.doi10.1016/j.ejor.2007.10.048-
dc.citation.journaltitleEUROPEAN JOURNAL OF OPERATIONAL RESEARCH-
dc.description.citedreferenceSingh S, 2003, IEEE T AUTOMAT CONTR, V48, P493, DOI 10.1109/TAC.2003.809165-
dc.description.citedreferenceDambreville F, 2002, NAV RES LOG, V49, P117, DOI 10.1002/nav.10009-
dc.description.citedreferenceFROST JR, 2001, CGD1501 US COAST GUA-
dc.description.citedreferenceHohzaki R, 1997, EUR J OPER RES, V100, P236-
dc.description.citedreferenceDell RF, 1996, NAV RES LOG, V43, P463-
dc.description.citedreferenceTHOMAS LC, 1995, NAV RES LOG, V42, P27-
dc.description.citedreferenceSINCLAIR A, 1993, ALGORITHMS RANDOM GE, P42-
dc.description.citedreferenceBENKOSKI SJ, 1991, NAV RES LOG, V38, P469-
dc.description.citedreferenceEAGLE JN, 1990, OPER RES, V38, P110-
dc.description.citedreferenceTRUMMEL KE, 1986, OPER RES, V34, P324-
dc.description.citedreferenceEAGLE JN, 1984, OPER RES, V32, P1107-
dc.description.citedreferenceBROWN SS, 1980, OPER RES, V28, P1275-
dc.description.citedreferenceSTEWART TJ, 1979, COMPUT OPER RES, V6, P129-
dc.description.citedreferencePOLLOCK SM, 1970, OPER RES, V18, P883-
dc.description.citedreferenceKOOPMAN BO, 1946, 56 OEG COL U DIV WAR-
dc.description.tc2-
dc.identifier.wosid000260749100003-
Appears in Collections:
Files in This Item:
There are no files associated with this item.

Altmetrics

Item View & Download Count

  • mendeley

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

Share