Strategy Synthesis in Adversarial Patrolling Games

Understand

Patrolling is one of the central problems in operational security.

• Formally, a patrolling problem is specified by a set $U$ of nodes (admissible defender's positions), a set $T \subseteq U$ of vulnerable targets, an admissible defender's moves over $U$, and a function which to every target assigns the time needed to complete an intrusion at it.
• The goal is to design an optimal strategy for a defender who is moving from node to node and aims at detecting possible intrusions at the targets.
• The goal of the attacker is to maximize the probability of a successful attack.