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

Investor logo

Warning

This publication doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

KUČERA Antonín LAMSER Tomáš

Year of publication 2016
Type Article in Proceedings
Conference Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems
MU Faculty or unit

Faculty of Informatics

Citation
Web ACM Digital Library
Field Informatics
Keywords patrolling games; strategy synthesis
Description 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 utilize non-linear programming to synthesize (sub)optimal patroller's strategies, which has a negative impact on their scalability. Further, the solution space is usually restricted to positional strategies or to strategies dependent on a bounded history of patroller's moves. In this paper we introduce regular strategies that utilize deterministic finite-state automata to collect some information about the whole history of patroller's moves, 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 solving large non-linear programs. Intuitively, we start with some regular strategy, and then improve this strategy by performing a finite number of rounds, where each round produces another regular strategy obtained by combining the ``old'' one with a solution of a certain linear program. Our experiments demonstrate that, compared to the existing methods, our approach is applicable to patrolling problems of considerably larger size, and can quickly produces strategies of very good quality.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info