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
2027345534 2020391710 1995434882 2183618110 2051092461 2095419417 2085497871 2100098951 2019729116 1990654078 2077296948
We study on-line strategies for solving problems with hybrid algorithms. There is a problemQandw basicalgorithms for solvingQ. For some ??w, we have a computer with ? disjoint memory areas, each of which can be used to run a basic algorithm and store its intermediate results. In the worst case, only one basic algorithm can solveQin finite time, and all of the other basic algorithms run forever without solvingQ. To solveQwith ahybridalgorithm constructed from the basic algorithms, we run a basic algorithm for some time, then switch to another, and continue this process untilQis solved. The goal is to solveQin the least amount of time. Usingcompetitive ratiosto measure the efficiency of a hybrid algorithm, we construct an optimal deterministic hybrid algorithm and an efficient randomized hybrid algorithm. This resolves an open question on searching with multiple robots posed by Baeza-Yates, Culberson, and Rawlins. We also prove that our randomized algorithm is optimal for ?=1, settling a conjecture of Kao, Reif, and Tate. The linear search problem has been discussed previously by one of the present authors. In this paper, the probability distribution of the point sought in the real line is not known to the searcher. Since there is noa priori choice of distribution which recommends itself above all others, we treat the situation as a game and obtain minimax type solutions. Different minimaxima apply depending on the factors which one wishes to minimize (resp. maximize). Certain criteria are developed which help the reader judge whether the results obtained can be considered “good advice” in the solution of real problems analogous to this one. 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. We extend the classic on-line search problem known as the cow-path problem to the case in which goal locations are selected according to one of a set of possible known probability distributions. We present a polynomial-time linear-programming algorithm for this problem. 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. We consider several extensions of the linear search problem, treating them from the point of view of game theory. Previous results established by the author are used to find minimax solutions for these problems. Searching for a goal is a central and extensively studied problem in computer science. In classical searching problems, the cost of a search function is simply the number of queries made to an oracle that knows the position of the goal. In many robotics problems, as well as in problems from other areas, we want to charge a cost proportional to the distance between queries (e.g., the time required to travel between two query points). With this cost function in mind, the abstract problem known as the @math -lane cow-path problem was designed. There are known optimal deterministic algorithms for the cow-path problem, and we give the first randomized algorithms in this paper. We show that our algorithm is optimal for two paths ( @math ), and give evidence that it is indeed optimal for larger values of @math . The randomized algorithms give expected performance that is almost twice as good as is possible with a deterministic algorithm. We consider the problem of on-line searching on m rays. A point robot is assumed to stand at the origin of m concurrent rays one of which contains a goal g that the point robot has to find. Neither the ray containing g nor the distance to g are known to the robot. The only way the robot can detect g is by reaching its location. We use the competitive ratio as a measure of the performance of a search strategy, that is, the worst case ratio of the total distance DR traveled by the robot to find g to the distance D from the origin to g.We present a new proof of a tight lower bound of the competitive ratio for randomized strategies to search on m rays. Our proof allows us to obtain a lower bound on the optimal competitive ratio for a fixed m even if the distance of the goal to the origin is bounded from above.Finally, we show that the optimal competitive ratio converges to 1 +2(eα- 1) α2 m ∼ 1 + 2.1.544 m, for large m where α minimizes the function(ex- 1) x2. In this paper we initiate a new area of study dealing with the best way to search a possibly unbounded region for an object. The model for our search algorithms is that we must pay costs proportional to the distance of the next probe position relative to our current position. This model is meant to give a realistic cost measure for a robot moving in the plane. We also examine the effect of decreasing the amount of a priori information given to search problems. Problems of this type are very simple analogues of non-trivial problems on searching an unbounded region, processing digitized images, and robot navigation. We show that for some simple search problems, knowing the general direction of the goal is much more informative than knowing the distance to the goal. A man in an automobile searches for another man who is located at some point of a certain road. He starts at a given point and knows in advance the probability that the second man is at any given point of the road. Since the man being sought might be in either direction from the starting point, the searcher will, in general, have to turn around many times before finding his target. How does he search so as to minimize the expected distance travelled? When can this minimum expectation actually be achieved? This paper answers the second of these questions.