Séminaire SPACE Tours

Search games on a lattice. Some open problems.
Noemi Zoroa (Universidad de Murcia)
Friday 13 February 2015 14:00 -  Tours -  Salle 1180 (Bât E2)

Résumé :
Work on search theory began in the US Navy’s Antisubmarine Warfare Operations Research group in 1942 in response to the German submarine threat in the Atlantic. After several decades of development, search problems are still largely of the same form as in 1492, a single target is lost, and the problem is to find it efficiently with fixed resources. Traditionally it is assumed that the target is simply stationary and hidden according to a known distribution, or its motion is determined stochastically by known rules. But if the target is an independent player of equal status to the searcher, and he does not want to be found, the problem can be modelled as a two person zero sum game between the searcher and the hider. These problems have been called Search Games. The search space can be a graph, a bounded domain, a mixture of the above, or an unbounded set. In some situations the search space can be represented as the Cartesian product of two finite sets. We will present games of these kind, some of them completely solved and other for which only partial solutions have been obtained.

Liens :