Tatiana Viktorovna Abramovskaya
post-graduate student
Saint-Petersburg State University
Faculty Mathematics and Mechanics
Nikolay Nikolaevich Petrov
Professor
Saint-Petersburg State University
Faculty Mathematics and Mechanics
We consider some pursuit-evasion problems on graphs, the most significant results on the topic under discussion and a number of their applications in the various fields of mathematics and other sciences are represented.
For the most part, the survey deals with the problems of interest of the scientists of the Department of Operations Research of St. Petersburg University. The fortieth anniversary of the Department was celebrated at 2010.
In general, the search problem is the game between a team of pursuers and an evader. The team of the pursuers tries to capture the invisible evader on a graph that is the phase constraint for all agents. A formalization of the search problem is defined by specifying the dynamic abilities of the agents, the conditions of the capture and other game parameters. For a particular search problem, the required search number is the minimal number of the pursuers that guarantee the capture of the evader.
We discuss the problem on edge-search number of graphs that was posed at the very beginning of the guaranteed search studies, the problem on the node-search number that is in close connection with the first one and the problems with counteraction are examined too. The results that are obtained in differential search problems with the restrictions on the velocities of the players and in the game with a radius of capture show that the great difficulties appear on topological graphs. Authors state some open problems of the guaranteed search theory.