We study the problem of searching for a hidden target in an environment that is modeled by an edge-weighted graph. A sequence of edges is chosen starting from a given root vertex such that each edge is adjacent to a previously chosen edge. This search paradigm, known as expanding search was recently introduced by Apern and Lidbetter [2013] for modeling problems such as searching for coal or minesweeping in which the cost of re-exploration is negligible. It can also be used to model a team of searchers successively splitting up in the search for a hidden adversary or explosive device, for example. We define the search ratio of an expanding search as the maximum over all vertices of the ratio of the time taken to reach the vertex and the shortest-path cost to it from the root. This can be interpreted as a measure of the multiplicative regret incurred in searching, and similar objectives have previously been studied in the context of conventional (pathwise) search. In this paper we address algorithmic and computational issues of minimizing the search ratio over all expanding searches, for a variety of search environments, including general graphs, trees and star-like graphs. Our main results focus on the problem of finding the randomized expanding search with minimum expected search ratio, which is equivalent to solving a zero-sum game between a Searcher and a Hider. We solve these problems for certain classes of graphs, and obtain constant-factor approximations for others.
A specific search environment that has attracted considerable attention in the search literature is the star-like environment. More specifically, in the unbounded variant, the search domain consists of a set of infinite lines which have a common intersection point (the root of the Searcher); this problem is also known as ray searching . Ray searching is a natural generalization of the well-known linear search problem introduced independently by @cite_40 and @cite_13 (informally called the cow-path problem''). Optimal strategies for linear search under the (deterministic) competitive ratio were first given by @cite_26 . @cite_29 gave optimal strategies for the generalized problem of ray searching, a result that was rediscovered later by computer scientists (see @cite_39 ). Other related work includes the study of randomization by @cite_6 and @cite_21 ; multi-Searcher strategies by @cite_36 ; searching with turn cost by @cite_14 ; the variant in which some probabilistic information on target placement is known by @cite_35 and @cite_8 ; and the related problem of designing hybrid algorithms by @cite_18 .
@cite_35 @cite_18 @cite_26 @cite_14 @cite_8 @cite_36 @cite_29 @cite_21 @cite_6 @cite_39 @cite_40 @cite_13
1995434882 2051092461 32433637 2085216434
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 for an explicit proof of optimality. 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 cowpath 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 + 2mm (m - 1)m-1)OPT + m((m (m - 1))m-1 - 1)d. We also discuss tradeoffs between the corresponding coefficients and we consider randomized strategies on the line. In this paper we investigate parallel searches on m concurrent rays for a point target t located at some unknown distance along one of the rays. A group of p agents or robots moving at unit speed searches for t. The search succeeds when an agent reaches the point t. Given a strategy S the competitive ratio is the ratio of the time needed by the agents to find t using S and the time needed if the location of t had been known in advance. We provide a strategy with competitive ratio of 1 + 2(m p - 1)(m (m - p))m p and prove that this is optimal. This problem has applications in multiple heuristic searches in AI as well as robot motion planning. The case p = 1 is known in the literature as the cow path problem. In this paper we consider the group search problem, or evacu- ation problem, in which k mobile entities ( ( M E )s) located on the line perform search for a specific destination. The ( M E )s are initially placed at the same origin on the line L and the target is located at an unknown distance d, either to the left or to the right from the origin. All ( M E )s must simultaneously occupy the destination, and the goal is to minimize the time necessary for this to happen. The problem with k = 1 is known as the cow-path problem, and the time required for this problem is known to be 9d − o(d) in the worst case (when the cow moves at unit speed); it is also known that this is the case for k ≥ 1 unit-speed ( M E )s. In this paper we present a clear argument for this claim by showing a rather counter-intuitive result. Namely, independent of the number of ( M E )s, group search cannot be performed faster than in time 9d − o(d). We also examine the case of k = 2 ( M E )s with different speeds, showing a surprising result that the bound of 9d can be achieved when one ( M E ) has unit speed, and the other ( M E ) moves with speed at least 1 3. We consider the problem of searching on m current rays for a target of unknown location. If no upper bound on the distance to the target is known in advance, then the optimal competitive ratio is 1+2mm (m−1)m−1. We show that even if an upper bound of D on the distance to the target is known in advance, then the competitive ratio of any search strategy is at least 1+2mm (m−1)m−1−O(1 log2D). This is again optimal – but in a stricter sense. In particular, this result implies the same lower bound for a robot searching for a target on infinite rays and finding it at a distance of D. To show that our lower bound is, indeed, optimal we construct a search strategy that achieves this ratio. Our strategy does not need to know an upper bound on the distance to the target in advance; it achieves a competitive ratio of 1+2mm (m−1)m−1−O(1 log2D) if the target is found at distance D. Finally, we also present a linear time algorithm to compute the strategy that allows the robot to search the farthest for a given competitive ratio C.