Minimizing Expected Intrusion Detection Time in Adversarial Patrolling

In adversarial patrolling games, a mobile Defender strives to discover intrusions at vulnerable targets initiated by an Attacker. The Attacker's utility is traditionally defined as the probability of completing an attack, possibly weighted by target costs. However, in many real-world scenarios,...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-02
Main Authors: Klaška, David, Kučera, Antonín, Musil, Vít, Řehák, Vojtěch
Format: Article
Language:English
Subjects:
Algorithms
Optimization
Patrols
Strategy
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In adversarial patrolling games, a mobile Defender strives to discover intrusions at vulnerable targets initiated by an Attacker. The Attacker's utility is traditionally defined as the probability of completing an attack, possibly weighted by target costs. However, in many real-world scenarios, the actual damage caused by the Attacker depends on the \emph{time} elapsed since the attack's initiation to its detection. We introduce a formal model for such scenarios, and we show that the Defender always has an \emph{optimal} strategy achieving maximal protection. We also prove that \emph{finite-memory} Defender's strategies are sufficient for achieving protection arbitrarily close to the optimum. Then, we design an efficient \emph{strategy synthesis} algorithm based on differentiable programming and gradient descent.
ISSN:2331-8422