The theory of guaranteed searching
Some pursuit-evasion problems and the most remarkable results on this subject, as well as a wide range of applications of the guaranteed search theory in mathematics and other sciences are considered. The survey consists mainly the search problems that were of great interest to the members of the Department of Operation Research at Saint Petersburg University. In general, a search problem is a game between a team of pursuers and an evader. The pursuers are trying to catch the invisible evader in a graph that is the phase constraint for all players. An exact formalization of the problem may vary depending on the dynamics of the agents, capture condition and other restrictions of the game. A search number is the minimum number of pursuers that guarantees the capture of the evader in each particular case. The initial guaranteed search problem also known as the edge search problem and the node search problem which is closely connected with the first one are discussed. Searching with counteraction is considered. The case of topological graphs as the arena of the search game brings a lot of difficulties as one can see from problems with restricted players’ speed or with non-zero radius of capture. Some unresolved problems of guaranteed search are also stated.