We revisit the linear search problem where a robot, initially placed at the origin on an infinite line, tries to locate a stationary target placed at an unknown position on the line. Unlike previous studies, in which the robot travels along the line at a constant speed, we consider settings where the robot's speed can depend on the direction of travel along the line, or on the profile of the terrain, e.g. when the line is inclined, and the robot can accelerate. Our objective is to design search algorithms that achieve good competitive ratios for the time spent by the robot to complete its search versus the time spent by an omniscient robot that knows the location of the target. We consider several new robot mobility models in which the speed of the robot depends on the terrain.These include 1) different constant speeds for different directions, 2) speed with constant acceleration and or variability depending on whether a certain segment has already been searched, 3) speed dependent on the incline of the terrain. We provide both upper and lower bounds on the competitive ratios of search algorithms for these models, and in many cases, we derive optimal algorithms for the search time.
The search problem has been extensively studied, e.g. see the survey by Benkoski @cite_2 ; deterministic algorithms for optimal linear search @cite_4 ; incorporating a when a robot changes direction during the search @cite_13 ; when bounds on the distance to the target are known in advance @cite_11 ; and for moving targets or more general linear cost functions @cite_15 . Other approaches include optimal randomized algorithms for the related @cite_0 , and stochastic and game theoretic investigations @cite_6 @cite_17 .
@cite_4 @cite_17 @cite_6 @cite_0 @cite_2 @cite_15 @cite_13 @cite_11
1995434882 2085497871 2005693620 2774807875
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. 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. The linear search problem concerns a search on the real line for a point selected at random according to a given probability distribution. The search begins at zero and is made by a continuous motion with constant speed, first in one direction and then the other. The problem is to determine when it is possible to devise a “best” search plan. In former papers the best plan has been selected according to the criterion of minimum expected path length. In this paper we consider a more general, nonlinear criterion for a “best” plan and show that the substantive requirements of the earlier results are not affected by these changes. Consider a setting where robots must visit sites represented as nodes in a graph, but each robot may fail when traversing an edge. The goal is to find a set of paths for a team of robots which maximizes the expected number of nodes collectively visited, while guaranteeing that the paths satisfy a notion of “independence” formalized by a matroid (e.g. limits on team size, number of visits to regions), and that the probabilities that each robot survives to its destination are above a given threshold. We call this problem the Matroid Team Surviving Orienteers (MTSO) problem, which has broad applications such as environmental monitoring in risky regions and search and rescue in dangerous conditions. We present the MTSO formally and detail numerous examples of matroids in a path planning context. We then propose an approximate greedy algorithm for selecting a feasible set of paths and prove that the value of the output is within a factor p s p s + λ of the optimum, where p s is the per-robot survival probability threshold and 1 λ ≤ 1 is the approximation factor of an oracle routine for the well known orienteering problem. We demonstrate the efficiency of our approach by applying it to a scenario where a team of robots must gather information while avoiding pirates in the Coral Triangle.