A patrol problem in a building by search theory

Art gallery problem has been extensively studied by computational geometry, where major issue was to find the minimum number of guards and their locations to watch inside an art gallery or a facility. In this paper, we are concerned with the dynamic and game-theoretic aspects of a security problem, where a thief tries to invade the gallery while watchmen try to prevent it. We consider the following problems: an invasion scheduling problem and an invasion route problem on thief´s side, a selection problem of patrol routes and a distribution problem of watching effort for the guards. We solve the first and the second problems by a dynamic programming formulation, and the third and the fourth problems by game theory and search theory. By the proposed methodology, we can evaluate the vulnerability of patrol routes and thus recommend better strategies for the security of a building or a facility.