Search

We consider a classic rendezvous game in which two players try to meet each other on a set of n locations. In each round, every player visits one of the locations, and the game finishes when the players meet at the same location. The goal is to devise strategies for both players that minimize the expected waiting time till the rendezvous. In the asymmetric case, when the strategies of the players may differ, it is known that the optimum expected waiting time of (n + 1) / 2 is achieved by the wait-for-mommy pair of strategies, in which one of the players stays at one location for n rounds, while the other player searches through all the n locations in a random order. However, if we insist that the players are symmetric—they are expected to follow the same strategy—then the best known strategy, proposed by Anderson and Weber [Anderson EJ, Weber RR (1990) The rendezvous problem on discrete locations. J. Appl. Probab. 27(4):839–851], achieves an asymptotic expected waiting time of 0.829 n. We show that the symmetry requirement indeed implies that the expected waiting time needs to be asymptotically larger than in the asymmetric case. Precisely, we prove that for every n ⩾ 2 , if the players need to employ the same strategy, then the expected waiting time is at least (n + 1) / 2 + ε n , where ε = 2 − 36 . We propose in addition a different proof for one our key lemmas, which relies on a result by Ahlswede and Katona [Ahlswede R, Katona GOH (1978) Graphs with maximal number of adjacent pairs of edges. Acta Mathematica Academiae Scientiarum Hungaricae 32(1–2):97–120]: the argument is slightly shorter and provides a constant larger than 2 − 36 , namely, 1 / 3600 . However, it requires that n be at least 16. Both approaches seem conceptually interesting to us. Funding: This work is a part of project TOTAL (Mi. Pilipczuk) that has received funding from the European Research Council under the European Union's Horizon 2020 research and innovation program [Grant 677651]. It is also partially funded by French ANR projects [Grant ANR-16-CE40-0023] (DESCARTES) and [Grant ANR-17-CE40-0015] (DISTANCIA). [ABSTRACT FROM AUTHOR]

Consider a two-person zero-sum search game between a hider and a searcher. The hider hides among n discrete locations, and the searcher successively visits individual locations until finding the hider. Known to both players, a search at location i takes ti time units and detects the hider—if hidden there—independently with probability α i for i = 1 , ... , n. The hider aims to maximize the expected time until detection, whereas the searcher aims to minimize it. We prove the existence of an optimal strategy for each player. In particular, any optimal mixed hiding strategy hides in each location with a nonzero probability, and there exists an optimal mixed search strategy that can be constructed with up to n simple search sequences. Funding: This work was supported by the Engineering and Physical Sciences Research Council [Grant EP/L015692/1] STOR-i Centre for Doctoral Training. [ABSTRACT FROM AUTHOR]

The Flaming Datum (FD) problem refers to the search for a hostile Evader that is fleeing after momentarily revealing its position. If Evader’s direction is fixed but unknown, while its maximal speed is known, Koopman argued in 1980 that the best trajectory for Searcher is a spiral starting from the revealed position. The objective of our study is to verify the hypothesis of a spiral search path, by formulating the FD problem in the framework of a finite two-player zero-sum partially observed stochastic search game, where the opponent plays repeatedly a fixed but unknown pure strategy. Using a realistic sensor model, current information about the position of Evader is represented by an occupancy map, updated in the Bayesian framework. The utility is computed as the entropy reduction of the occupancy map. The game was implemented in software and solved using the maxmin method. By running repeatedly the described search game, we have found that the search pattern, although random (due to the uncertainties in sensing and mixed strategies), is indeed a spiral on every play of the game, thus confirming the hypothesis.

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. [ABSTRACT FROM AUTHOR]

Suppose that some objects are hidden in a finite set S of hiding places that must be examined one by one. The cost of searching subsets of S is given by a submodular function, and the probability that all objects are contained in a subset is given by a supermodular function. We seek an ordering of S that finds all the objects with minimal expected cost. This problem is NP-hard, and we give an efficient combinatorial 2-approximation algorithm, generalizing analogous results in scheduling theory. We also give a new scheduling application where a set of jobs must be ordered subject to precedence constraints to minimize the weighted sum of some concave function of the completion times of subsets of jobs. We go on to give better approximations for submodular functions with low total curvature, and we give a full solution when the problem is what we call series-parallel decomposable. Next, we consider a zero-sum game between a cost-maximizing hider and a cost-minimizing searcher. We prove that the equilibrium mixed strategies for the hider are in the base polyhedron of the cost function, suitably scaled, and we solve the game in the series-parallel decomposable case, giving approximately optimal strategies in other cases. [ABSTRACT FROM AUTHOR]

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 Alpern 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. [ABSTRACT FROM AUTHOR]

We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic "expanding search" paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs ai such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper's main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown. [ABSTRACT FROM AUTHOR]

We consider a 'manhunting' game in which one player, the Hider, chooses one of several cells to hide and a second player, the Seeker, distributes his resources among the several cells. The cells differ in their characteristics: it may be easier to hide in some cells, or there may be a lower probability of betrayal in others, etc. The Hider's survival probability depends on the characteristics of the cell chosen, as well as on the amount of resources which the Seeker expends in that cell. The Hider may need to carry out some activity while in his cell. If so, the activity creates a signal which can help the Seeker to locate the Hider. The Seeker must of course try to distinguish between the noise due to the activity and random "white" noise. We obtain a complete analytic solution for the case without signals. Simulation is used to develop good strategies for the case with signals. [ABSTRACT FROM AUTHOR]

This paper addresses the high-level search planning that is necessary to find hidden objects in difficult undersea environments where sensor performance varies geographically and the susceptibility to false alarms is high. We develop a game-theoretic approach for maximizing the information that is collected as a multiagent collaborative search is conducted over a region of interest. To accomplish this, we apply 1) a search channel formalism to the discrete search modeling paradigm to develop information measures as a function of searcher regional visitation; and 2) a receiver operator characteristic analysis to map sensor detection characteristics to search events. We formulate an area search game where player action directs where and how information is collected under a fixed cost constraint on search effort. We discuss the properties of the information measure developed for a repeated look over the area search channel and examine the impact of setting ROC operating points to their game equilibrium values. We describe a new algorithmic capability for solving the search allocation problem where searchers can collaborate in their efforts to resolve false alarm outcomes. Results are presented to show the dominance of this approach over alternative strategies allotted to the game and to demonstrate the capability of exploiting the known nonhomogeneity in the search environment. [ABSTRACT FROM AUTHOR]

We consider a search and rescue game introduced recently by the first author. An immobile target or targets (for example, injured hikers) are hidden on a graph. The terrain is assumed to be dangerous, so that when any given vertex of the graph is searched, there is a certain probability that the search will come to an end, otherwise with the complementary success probability the search can continue. A Searcher searches the graph with the aim of finding all the targets with maximum probability. Here, we focus on the game in the case that the graph is a cycle. In the case that there is only one target, we solve the game for equal success probabilities, and for a class of games with unequal success probabilities. For multiple targets and equal success probabilities, we give a solution for an adaptive Searcher and a solution in a special case for a non-adaptive Searcher. We also consider a continuous version of the model, giving a full solution for an adaptive Searcher and approximately optimal solutions in the non-adaptive case. [ABSTRACT FROM AUTHOR]

Combining the search and pursuit aspects of predator-prey interactions into a single game, where the payoff to the Searcher (predator) is the probability of finding and capturing the Hider (prey) within a fixed number of searches was proposed by Gal and Casas ( J. R. Soc. Interface 11 , 20140062 (doi:10.1098/rsif.2014.0062)). Subsequent models allowed the predator to continue its search (in another 'round') if the prey was found but escaped the chase. However, it is unrealistic to allow this pattern of prey relocation to go on forever, so here we introduce a limit of the total number of searches, in all 'rounds', that the predator can carry out. We show how habitat structural complexity affects the mean time until capture: the quality of the location with the lowest capture probability matters more than the number of hiding locations. Moreover, we observed that the parameter space defined by the capture probabilities in each location and the budget of the predator can be divided into distinct domains, defining whether the prey ought to play with pure or mixed hiding strategies.

ABSTRACT In the rendezvous problem, two parties with different labelings of the vertices of a complete graph are trying to meet at some vertex at the same time. It is well-known that if the parties have predetermined roles, then the strategy where one of them waits at one vertex, while the other visits all n vertices in random order is optimal, taking at most n steps and averaging about [ABSTRACT FROM AUTHOR]

In this paper, we study a multistage search game. The general situation is described as a predator-prey problem as follows: in a certain region there is a predator and a group of prey. The prey have h different places to go to eat, and every day the group goes to one of these places, but all the days, the herd is forced to go to a certain place, W, say to drink. Simultaneously, the predator has to select a strategy to meet the herd of prey and catch one of them, it can use its ambush strategy, which consists of going to place W, and wait there for the herd, or select a search strategy and go to one of the h different places where the herd goes to eat and search for a prey there. When predator and prey meet each other in one place, predator can catch a prey with a probability depending on the place and on the movement of the predators. Since animals require a minimum consumption of energy over time to survive, we suppose that the predator has to catch a minimum number of prey, K, over a number of days, M. We model this problem as a two-person zero-sum multistage game, which we solve in some situations by giving optimal strategies for prey and for predator and the value of the game. [ABSTRACT FROM AUTHOR]

Abstract: 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 , 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. [Copyright &y& Elsevier]

Howard [Howard, J. V. 2006. Unsolved symmetric rendezvous search problems: Some old and some new. Presentation, Sixth International Workshop in Search Games and Rendezvous, July 26, London School of Economics, London] has described a simply but nontrivial symmetric rendezvous search game in which two players are initially placed in two distinct locations. The game is played in discrete steps, at each of which each player can either stay where she is or move to the other location. When the players are in the same location for the first time they do not see one another, but when they are in the same location for a second time, then they meet. We wish to find a strategy such that, if both players follow it independently, then the expected number of steps at which this second meeting occurs is minimized. Howard conjectured that the optimal strategy is 3-Markovian, such that in each successive block of three steps the players should, with equal probability, do SSS, SMS, MSM, MMM, where "M" means move and "S" means stay. We prove that this strategy is optimal. [ABSTRACT FROM AUTHOR]

In the symmetric rendezvous search game played on n locations two players are initially placed at two distinct locations. The game is played in discrete steps, at each of which each player can either stay where he is or move to a different location. The players share no common labelling of the locations. We wish to find a strategy such that, if both players follow it independently, then the expected number of steps until they are in the same location is minimized. Informal versions of the rendezvous problem have received considerable attention in the popular press. The problem was proposed by Alpern in 1976 [Alpern, S. 1976. Hide and seek games. Seminar at the Institut für Höhere Studien, Vienna], and it has proved notoriously difficult to analyse. In this paper we prove a 20-year-old conjecture that the following strategy is optimal for the game on three locations: in each block of two steps, stay where you are, or search the other two locations in random order, doing these with probabilities 1=3 and 2=3, respectively. This is now the first nontrivial symmetric rendezvous game of any type to be fully solved. [ABSTRACT FROM AUTHOR]

Abstract: 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 , 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 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 . We also discuss tradeoffs between the corresponding coefficients and we consider randomized strategies on the line. [Copyright &y& Elsevier]

Directed path-width was defined by Reed, Thomas and Seymour around 1995. The author and P. Hajnal defined a cops-and-robber game on digraphs in 2000. We prove that the two notions are closely related and for any digraph D, the corresponding graph parameters differ by at most one. The result is achieved using the mixed-search technique developed by Bienstock and Seymour. A search is called monotone, in which the robber's territory never increases. We show that there is a mixed-search of D with k cops if and only if there is a monotone mixed-search with k cops. For our cops-and-robber game we get a slightly weaker result: the monotonicity can be guaranteed by using at most one extra cop. [ABSTRACT FROM AUTHOR]

We introduce a new zero-sum matrix game for modeling search in structured domains. In this game, one player tries to find a "bug" while the other tries to hide it. Both players exploit the structure of the "search" domain. Intuitively, this search game is a mathematical generalization of the well known binary search. The generalization is from searching over totally ordered sets to searching over more complex search domains such as trees, partial orders and general set systems. As there must be one row for every search strategy, and there are exponentially many ways to search even in very simple search domains, the game's matrix has exponential size ("space"). In this work we present two ways to reduce the space required to compute the Nash value (in pure strategies) of this game: • First we show that a Nash equilibrium in pure strategies can be computed by using a backward induction on the matrices of each "part" or sub structure of the search domain. This can significantly reduce the space required to represent the game. • Next, we show when general search domains can be represented as DAGs (Directed Acycliqe Graphs). As a result, the Nash equilibrium can be directly computed using the DAG. Consequently the space needed to compute the desired search strategy is reduced to O(n2) where n is the size of the search domain. [ABSTRACT FROM AUTHOR]

Search games with capacities are bipersonal zero-sum games where a player has to hide a number of objects or an amount of material in a fixed number of containers and his opponent attempts to locate them. In this article, we deal with games on a discrete structureless set and on a discrete set with linear order. In both cases, the capacities under consideration are continuous. Some of the games studied generalize previously studied games. [ABSTRACT FROM AUTHOR]

This paper presents research combining an agent-based modeling and simulation paradigm with game theory for an in silico historical analysis of the Bay of Biscay submarine war during WWII. The U-boat threat was of great concern to the Allies, prompting initial operational research efforts to devise counterstrategies. Focusing search efforts in the Bay of Biscay enabled an effective Allied response. Using the historical record as a means to create a reasonably accurate model of the U-boat campaign, we allow the resulting agents within the model to adapt their strategies to counter-opposition strategies. Model output data are examined with respect to the historical record and game theory. The results hold promise for extending the agent-based modeling paradigm into more complex military-based domains. [ABSTRACT FROM PUBLISHER]

In a continuous accumulation game on a continuous region, a Hider distributes material over a continuous region at each instant of discrete time, and a Seeker examines the region. If the Seeker locates any of the material hidden, the Seeker confiscates it. The goal of the Hider is to accumulate a certain amount of material before a given time, and the goal of the Seeker is to prevent this. In previous works, we have studied accumulation games involving discrete objects and continuous material over discrete locations. The issues raised when the region is continuous are substantially different. In this paper, we study accumulation of continuous material over two types of continuous regions: the interval and the circle. [ABSTRACT FROM AUTHOR]

Thanks to the advent of new technologies and higher real-time computational capabilities, the use of unmanned vehicles in the marine domain has received a significant boost in the last decade. Ocean and seabed sampling, missions in dangerous areas, and civilian security are only a few of the large number of applications which currently benefit from unmanned vehicles. One of the most actively studied topic is their full autonomy; i.e., the design of marine vehicles capable of pursuing a task while reacting to the changes of the environment without the intervention of humans, not even remotely. Environmental dynamicity may consist of variations of currents, the presence of unknown obstacles, and attacks from adversaries (e.g., pirates). To achieve autonomy in such highly dynamic uncertain conditions, many types of autonomous path planning problems need to be solved. There has thus been a commensurate number of approaches and methods to optimize this kind of path planning. This work focuses on game-theoretic approaches and provides a wide overview of the current state of the art, along with future directions. [ABSTRACT FROM AUTHOR]

In this paper, we study a discrete search game on an array of N ordered cells, with two players having opposite goals: player I (searcher) and player II (hider). Player II has to hide q objects at consecutive cells and player I can search p consecutive cells. The payoff to player I is the number of objects found by him. In some situations, the players need to adopt sophisticated strategies if they are to act optimally. [ABSTRACT FROM AUTHOR]

In an accumulation game, a hider places objects at locations, and a seeker examines these locations. If the seeker discovers an object, the seeker confiscates it. The goal of the hider is to accumulate a certain number of objects before a given time, and the goal of the seeker is to prevent this. In this paper, we first classify various possible variations on the accumulation game. Next, we discuss the so-called noisy accumulation game in which the hider can observe each action of the seeker. We present the solution of this game for all but some marginal cases and illustrate it with computational examples. [ABSTRACT FROM AUTHOR]

Suppose we are searching for a target point t in a certain restricted search space. To pinpoint the location of t , we issue query points q 1 , ... , q n in the search space. As a response, we obtain an ordering of the query points by distance to t. This restricts possible locations of t. In this paper, we consider the case where the search space is the unit interval [ 0 , 1 ]. We define the accuracy of a query strategy as the reciprocal of the size of the subinterval to which we can pinpoint t in the worst case. We describe a strategy with accuracy Θ (n 2) , which is at most a factor two from optimal if all query points have to be generated at once. With query points generated one by one depending on the response received on previous query points, we achieve accuracy Ω (2.29 n) , and prove that no strategy can achieve Ω (3.66 n). These strategies can be extended to higher dimensional cases, where the search space is the unit cube or unit ball. [ABSTRACT FROM AUTHOR]

When the spatial density of both prey and predators is very low, the problem they face may be modelled as a two-person game (called a 'search game') between one member of each type. Following recent models of search and pursuit, we assume the prey has a fixed number of heterogeneous 'hiding' places (for example, ice holes for a seal to breathe) and that the predator (maybe polar bear) has the time or energy to search a fixed number of these. If he searches the actual hiding location and also successfully pursues the prey there, he wins the game. If he fails to find the prey, he loses. In this paper, we modify the outcome in the case that he finds but does not catch the prey. The prey is now vulnerable to capture while relocating with risk depending on the intervening terrain. This generalizes the original games to a stochastic game framework, a first for search and pursuit games. We outline a general solution and also compute particular solutions. This modified model now has implications for the question of when to stay or leave the lair and by what routes. In particular, we find the counterintuitive result that in some cases adding risk of predation during prey relocation may result in more relocation. We also model the process by which the players can learn about the properties of the different hiding locations and find that having to learn the capture probabilities is favourable to the prey.