Search Games: A Review
This review presents an update on the area of Search Games, highlighting recent developments in the field, as well as presenting some new problems for further research. The search space is either a graph, a bounded domain, a mixture of the above, or an un
- PDF / 260,135 Bytes
- 13 Pages / 439.36 x 666.15 pts Page_size
- 67 Downloads / 236 Views
Search Games: A Review Shmuel Gal
Abstract This review presents an update on the area of Search Games, highlighting recent developments in the field, as well as presenting some new problems for further research. The search space is either a graph, a bounded domain, a mixture of the above, or an unbounded set. The search process is presented as a two-player zero-sum game between the searcher and the hider. The searcher moves along a continuous trajectory and the cost function is the time needed to find the hider. Our review emphasises general results concerning minimax search trajectories and optimal search strategies. We present a review on mathematical modeling of hide and seek situations that we all know from our childhood. These situations are common in military and antiterror activity, as well as many other areas. Isaacs [30] provided a mathematical foundation to study of such situations in the last chapter of his book, introducing the concept of a continuous search game, which was further developed by Gal [24]. That work, and the updated version by Alpern and Gal [4], has stimulated much research, with applications to Computer Science, Economics and Biology. The present chapter reviews different types of search games, putting an emphasis on recent results. As such, it is an update of a previous survey article on search games that appeared in the encyclopedia of Operations Research [26]. The present chapter also contains some new observations on searching a graph using the Traveling Salesman Tour and on searching mixed spaces which did not appear in print before, outlining possible directions of future research. We consider a zero-sum game played between a searcher and a hider in a search space Q which is either a compact set in a Euclidean space or an unbounded connected set, e.g., the real line. The searcher usually starts moving from a specified
S. Gal () Department of Statistics, University of Haifa, 31905 Haifa, Israel e-mail: [email protected]
S. Alpern et al. (eds.), Search Theory: A Game Theoretic Perspective, DOI 10.1007/978-1-4614-6825-7__1, © Springer Science+Business Media New York 2013
3
4
S. Gal
point O called the origin but choosing the starting point arbitrarily is also considered. It is assumed that the searcher is free to choose any continuous trajectory inside Q, subject to a maximal velocity constraint which is normalized to 1. The hider can be either stationary or mobile. It will always be assumed that neither the searcher nor the hider has any knowledge about the movement of the other player until their distance apart is less than or equal to the discovery radius r, and at this moment capture occurs. The discovery radius r is assumed to be small with respect to the dimension of Q. For one dimensional sets, r is assumed zero. A search trajectory will be denoted by S and a hiding point or trajectory (depending whether the hider is immobile or mobile) by H. The cost function (payoff to the maximizing hider) c (S, H) , is the time spent until the hider is found (the search time).
Data Loading...
