Robust search policies against an intelligent evader
Abstract
In a classical search model, an object is hidden in one of many cells. Knowing the probability that the object is in each cell, a searcher
wishes to find it. Each search in a cell incurs a cost and will discover the object with some probability, with both the cost and
discovery probability dependent on the cell. This paper revisits this search problem with an intelligent evader who decides where to
hide in order to evade the search. We make two contributions to the literature. First, we show how to compute a randomized policy
for the searcher to minimize the expected cost until discovering the evader. Second, if the search has to stop at some point, with the
deadline unannounced in advance, we show how the searcher can sequentially allocate each search to simultaneously maximize the
probability of discovering the evader by an arbitrary deadline. In the case where the search cost is identical for all cells, our analysis
shows that the latter policy is more robust.
Description
The previous version has a signature misplaced on Figure 1, which is corrected in this version.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.NPS Report Number
NPS-OR-15-009Related items
Showing items related by title, author, creator and subject.
-
A game theory analysis of proposed strategies of an aerial search for a mobile surface target.
Smith, Charles James (Monterey, California. U.S. Naval Postgraduate School, 1966-10);This thesis investigates the problem of aerial search for a mobile surface target. The initial position of the target is known, and a certain amount of time elapses before the search begins. The target has a variety of ... -
Localization of Surface or Near-Surface Drifting Mines for Unmanned Systems in the Persian Gulf
Yau, Meng Wee Joses (Monterey, California. Naval Postgraduate School, 2012-06);This thesis investigates the combined use of ocean models, such as idealized surface current flows, and search models, including expanding area and discrete myopic search methods, to improve the probability of detecting a ... -
Myopic search plans
de Paula Neto, Antonio Francisco (Naval Postgraduate School, 1978);Different strategies can be used to search for a moving object. If the searcher's action at each time unit maximizes his chances of immediate detection, his strategy is said to be myopic. If, however, the searcher seeks ...