Search

The article of record as published may be found at https://doi.org/10.1016/j.tcs.2020.03.011 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. Some of the boxes, however, are booby trapped. If the Searcher opens a booby trapped box, the search ends and she loses all her collected rewards. We assume the number k of booby traps is known, and we model the problem as a zero-sum game between the maximizing Searcher and a minimizing Hider, where the Hider chooses k boxes to booby trap and the Searcher opens all the boxes in some hyperedge. The payoff is the total reward collected by the Searcher. This model could reflect a military operation in which a drone gathers intelligence from guarded locations, and a booby trapped box being opened corresponds to the drone being destroyed or incapacitated. It could also model a machine scheduling problem, in which rewards are obtained from successfully processing jobs but the machine may crash. We solve the game when G is a 1-uniform hypergraph (the hyperedges are all singletons), so the Searcher can open just 1 box. When G is the complete hypergraph (containing all possible hyperedges), we solve the game in a few cases: (1) same reward in each box, (2) k=1, and (3) n=4 and k = 2. The solutions to these few cases indicate that a general simple, closed form solution to the game appears unlikely. This material is based upon work supported by the National Science Foundation under Grant No. IIS-1909446. This material is based upon work supported by the National Science Foundation under Grant No. IIS-1909446.

We study the classic problem in which a Searcher must locate a hidden point, also called the Hider in a network, starting from a root point. The network may be either bounded or unbounded, thus generalizing well-known settings such as linear and star search. We distinguish between pathwise search, in which the Searcher follows a continuous unit-speed path until the Hider is reached, and expanding search, in which, at any point in time, the Searcher may restart from any previously reached point. The former has been the usual paradigm for studying search games, whereas the latter is a more recent paradigm that can model real-life settings such as hunting for a fugitive, demining a field, or search-and-rescue operations. We seek both deterministic and randomized search strategies that minimize the competitive ratio, namely the worst-case ratio of the Hider’s discovery time, divided by the length of the shortest path to it from the root. Concerning expanding search, we show that a simple search strategy that applies a “waterfilling” principle has optimal deterministic competitive ratio; in contrast, we show that the optimal randomized competitive ratio is attained by fairly complex strategies even in a very simple network of three arcs. Motivated by this observation, we present and analyze an expanding search strategy that is a 5 4 -approximation of the randomized competitive ratio. Our approach is also applicable to pathwise search, for which we give a strategy that is a 5-approximation of the randomized competitive ratio, and which improves upon strategies derived from previous work.

The article of record as published may be found at http://dx.doi.org/10.1016/j.cor.2006.09.020 We develop and analyze a “manhunting” game involving a mobile hider, who wishes to maximize his time to capture, and a mobile searcher, who wishes to minimize this same time. The game takes place within a variegated environment that offers better and worse locations to evade capture. The hider is able to move from one hide site to another at will. In choosing a hide site, he must consider the risk of discovery, the risk that he will be betrayed, and the risk that he will be captured while moving from one site to another. The searcher can select any cell to search within the fugitive’s feasible hiding set. We examine the strategic behavior of both players and provide examples. Published by Elsevier Ltd.

We consider the problem of searching for an object on a line at an unknown distance OPT from the original position of the searcher, in the presence of a cost of d for each time the searcher changes direction. This is a generalization of the well-studied linear-search problem. We describe a strategy that is guaranteed to find the object at a cost of at most 9*OPT + 2d, which has the optimal competitive ratio 9 with respect to OPT plus the minimum corresponding additive term. Our argument for upper and lower bound uses an infinite linear program, which we solve by experimental solution of an infinite series of approximating finite linear programs, estimating the limits, and solving the resulting recurrences. We feel that this technique is interesting in its own right and should help solve other searching problems. In particular, we consider the star search or cow-path problem with turn cost, where the hidden object is placed on one of m rays emanating from the original position of the searcher. For this problem we give a tight bound of (1+(2(m^m)/((m-1)^(m-1))) OPT + m ((m/(m-1))^(m-1) - 1) d. We also discuss tradeoff between the corresponding coefficients, and briefly consider randomized strategies on the line., 15 pages, 2 figures, 1 table; to appear in Theoretical Computer Science. Did some minor editorial changes, fixed some typos, etc

We consider the problem of searching for an unknown horizontal or vertical line in a plane. A search path in the plane starts at the origin and detects the unknown line, if the path hits the line for the first time. The performance of the search path is measured by competitive analysis. That is, we compute the ratio of the length of the path until the line is detected over the shortest path from the origin to the given line. The competitive ratio of a given search path is the worst-case ratio of the path among all horizontal and vertical lines in the plane. In this paper, we design a search path that attains a competitive ratio of 12.53853842…, and slightly improves the current best-known search path. Furthermore, we prove that the search path is optimal among all paths that proceed in a cyclic manner. There is a strong conjecture that this path is the general optimal search path for searching axis-parallel lines.

We define a general game which forms a basis for modelling situations of static search and concealment over regions with spatial structure. The game involves two players, the searching player and the concealing player, and is played over a metric space. Each player simultaneously chooses to deploy at a point in the space; the searching player receiving a payoff of 1 if his opponent lies within a predetermined radius r of his position, the concealing player receiving a payoff of 1 otherwise. The concepts of dominance and equivalence of strategies are examined in the context of this game, before focusing on the more specific case of the game played over a graph. Methods are presented to simplify the analysis of such games, both by means of the iterated elimination of dominated strategies and through consideration of automorphisms of the graph. Lower and upper bounds on the value of the game are presented and optimal mixed strategies are calculated for games played over a particular family of graphs.