Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems

In patrolling problems, the task is to compute an optimal strategy for a patroller who moves among vulnerable targets and aims at detecting possible intrusions. Previous approaches to this problem were mostly based on non-linear programming, and the solution space was restricted to positional strategies or to strategies dependent on a bounded history of patroller's moves. In this paper, we extend the solution space to regular strategies, and show that regular strategies are strictly more powerful than strategies dependent on a bounded history. Further, we design a strategy improvement technique for regular strategies which completely avoids the use of non-linear programming. Intuitively, we start with some regular strategy, and then repeatedly improve this strategy by incorporating a solution of a certain linear program. Our experiments demonstrate that the proposed approach can quickly produce strategies of very good quality even for quite large patrolling problems.