Search

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.

Many interactions between searching agents and their elusive targets are composed of a succession of steps, whether in the context of immune systems, predation or counterterrorism. In the simplest case, a two-step process starts with a search-and-hide phase, also called a hide-and-seek phase, followed by a round of pursuit-escape. Our aim is to link these two processes, usually analysed separately and with different models, in a single game theory context. We define a matrix game in which a searcher looks at a fixed number of discrete locations only once each searching for a hider, which can escape with varying probabilities according to its location. The value of the game is the overall probability of capture after k looks. The optimal search and hide strategies are described. If a searcher looks only once into any of the locations, an optimal hider chooses it's hiding place so as to make all locations equally attractive. This optimal strategy remains true as long as the number of looks is below an easily calculated threshold; however, above this threshold, the optimal position for the hider is where it has the highest probability of escaping once spotted.

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 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]

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]

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]

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]

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]