Mining Coal or Finding Terrorists: The Expanding Search Paradigm

Steve Alpern () and Thomas Lidbetter ()
Additional contact information
Steve Alpern: ORMS Group, Warwick Business School, University of Warwick, Coventry CV4 7AL, United Kingdom
Thomas Lidbetter: Department of Mathematics, London School of Economics, London WC2A 2AE, United Kingdom

Operations Research, 2013, vol. 61, issue 2, 265-279

Abstract: We show how to optimize the search for a hidden object, terrorist, or simply Hider, located at a point H according to a known or unknown distribution (nu) on a rooted network Q . We modify the traditional “pathwise search” approach to a more general notion of “expanding search.” When the Hider is restricted to the nodes of Q , an expanding search S consists of an ordering \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$(a_{1},a_{2},\ldots)$\end{document} of the arcs of a spanning subtree such that the root node is in a 1 and every arc a i is adjacent to a previous arc a j , j i . If a k contains H , the search time T is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\lambda (a_{1}) +\cdots +\lambda (a_{k})$\end{document} , where (lambda) is length measure on Q . For more general distributions (nu) , an expanding search S is described by the nested family of connected sets S ( t ) that specify the area of Q that has been covered by time t . S (0) is the root, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\lambda (S(t) ) =t$, and $T=\min \{ t: H \in S(t)\}$\end{document} . For a known Hider distribution (nu) on a tree Q , the expected time minimizing strategy \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\bar{S}$\end{document} begins with the rooted subtree Q ' maximizing the “density” (nu) ( Q ')/ (lambda) ( Q '). (For arbitrary networks, we use this criterion on all spanning subtrees.) The search \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\bar{S}$\end{document} can be interpreted as the optimal method of mining known coal seams, when the time to move miners or machines is negligible compared to digging time. When the Hider distribution is unknown, we consider the zero-sum search game where the Hider picks H , the Searcher S , and the payoff is T . For trees Q , the value is V = ( (lambda) ( Q ) + D )/2, where D is a mean distance from root to leaf nodes. If Q is 2-arc connected, V = (lambda) ( Q )/2. Applications and interpretations of the expanding search paradigm are given, particularly to multiple agent search.

Keywords: teams; games/group decisions; search/surveillance; tree algorithms; networks/graphs (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (27)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1134 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:61:y:2013:i:2:p:265-279

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().