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.
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 ...
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 ...
Dell, Robert F.; Eagle, James N.; Martins, Gustavo Henrique Alves; Santos, Almir Garnier (1996);The search theory open literature has paid little, if any, attention to the multiple-searcher, moving-target search problem. We develop an optimal branch-and-bound procedure and six heuristics for solving constrained-path ...