Searching for multiple objects in multiple locations
Lin, Kyle Y.
MetadataShow full item record
Many practical search problems concern the search for multiple hidden objects or agents, such as earthquake survivors. In such problems, knowing only the list of possible locations, the Searcher needs to find all the hidden objects by visiting these locations one by one. To study this problem, we formulate new game-theoretic models of discrete search between a Hider and a Searcher. The Hider hides k balls in n boxes, and the Searcher opens the boxes one by one with the aim of finding all the balls. Every time the Searcher opens a box she must pay its search cost, and she either finds one of the balls it contains or learns that it is empty. If the Hider is an adversary, an appropriate payoff function may be the expected total search cost paid to find all the balls, while if the Hider is Nature, a more appropriate payoff function may be the difference between the total amount paid and the amount the Searcher would have to pay if she knew the locations of the balls a priori (the regret). We give a full solution to the regret version of this game, and a partial solution to the search cost version. We also consider variations on these games for which the Hider can hide at most one ball in each box. The search cost version of this game has already been solved in previous work, and we give a partial solution in the regret version.
RightsThis 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.
Showing items related by title, author, creator and subject.
Santos, Almir Garnier (Monterey, California. Naval Postgraduate School, 1993-09);The need to search effectively for objects presents itself in many civilian and military applications. This thesis develops and tests six heuristics and an optimal branch and bound procedure to solve the heretofore ...
Lidbetter, Thomas; Lin, Kyle Y. (Elsevier, 2020-03);A set of n boxes, located on the vertices of a hypergraph G, contain known but different rewards. A Searcher opens all the boxes in some hyperedge of G with the objective of collecting the maximum possible total reward. ...
Atkinson, Michael P.; Lange, Rutger-Jan (2016);We analyze a variant of the whereabouts search problem, in which a searcher looks for a target hiding in one of n possible locations. Unlike in the classic version, our searcher does not pursue the target by actively moving ...