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.
It must be emphasized that star search has applications that are not necessarily confined to the concept of locating a target (which explains its significance and popularity). Indeed star search offers an abstraction that applies naturally in settings in which we seek an intelligent allocation of resources to tasks. More precisely, it captures decision-making aspects when the objective is to successfully complete at least one task, without knowing in advance the completion time of each task. Some concrete applications include: drilling for oil in a number of different locations in @cite_1 ; the design of efficient interruptible algorithms, i.e., algorithms that return acceptable solutions even if interrupted during their execution in @cite_37 and @cite_19 ; and database query optimization (in particular, pipelined filter ordering in @cite_10 ). We discuss the latter work in more detail in .
@cite_19 @cite_37 @cite_1 @cite_10
2949341268 1986214908 1567718955
This paper addresses two classes of different, yet interrelated optimization problems. The first class of problems involves a robot that must locate a hidden target in an environment that consists of a set of concurrent rays. The second class pertains to the design of interruptible algorithms by means of a schedule of contract algorithms. We study several variants of these families of problems, such as searching and scheduling with probabilistic considerations, redundancy and fault-tolerance issues, randomized strategies, and trade-offs between performance and preemptions. For many of these problems we present the first known results that apply to multi-ray and multi-problem domains. Our objective is to demonstrate that several well-motivated settings can be addressed using the same underlying approach. Anytime algorithms offer a tradeoff between computation time and the quality of the result returned. They can be divided into two classes: contract algorithms, for which the total run time must be specified in advance, and interruptible algorithms, which can be queried at any time for a solution. An interruptible algorithm can be constructed from a contract algorithm by repeatedly activating the contract algorithm with increasing run times. The acceleration ratio of a run-time schedule is a worst-case measure of how inefficient the constructed interruptible algorithm is compared to the contract algorithm. The smallest acceleration ratio achievable on a single processor is known. Using multiple processors, smaller acceleration ratios are possible. In this paper, we provide a schedule for m processors and prove that it is optimal for all m. Our results provide general guidelines for the use of parallel processors in the design of real-time systems. Given n potential oil locations, where each has oil at a certain depth, we seek good trade-offs between the number of oil sources found and the total amount of drilling performed. The cost of exploring a location is proportional to the depth to which it is drilled. The algorithm has no clue about the depths of the oil sources at the different locations or even if there are any. Abstraction of the oil searching problem applies naturally to several life contexts. Consider a researcher who wants to decide which research problems to invest time into. A natural dilemma whether to invest all the time into a few problems, or share time across many problems. When you have spent a lot of time on one problem with no success, should you continue or move to another problem?